## Thursday, May 31, 2012

### Sort an array of objects

There are just three sizes large, small, medium. what is the optimal complexity? Can you make this in-place?

## Wednesday, May 30, 2012

### Given 2 very large numbers, each of which is so large it can only be represented as an array of integers, write a function to multiply them

```
const unsigned MULTIPLY_BASE = 10;

void multiplyLittleEndian(const vector < unsigned > &a, const vector < unsigned > &b, vector < unsigned >  &r)
{
r.assign(a.size()+b.size(), 0);
unsigned ri=0;
for(unsigned ai=0; ai < a.size(); ++ai)
{
unsigned cri = ri++, carry = 0, am = a[ai], cr;
for(unsigned bi=0; bi < b.size(); ++bi, ++cri)
{
cr = carry + am*b[bi] + r[cri];
r[cri] = cr % MULTIPLY_BASE;
carry = cr / MULTIPLY_BASE;
}
while(carry)
{
cr = carry + r[cri];
r[cri++] = cr % MULTIPLY_BASE;
carry = cr / MULTIPLY_BASE;
}
}
while((!r.empty()) && r.back() == 0) r.pop_back(); // trim result
}

```

## Sunday, May 27, 2012

### add two numbers represented by strings

First need to reverse both strings, then add char by character and reverse final String again.

## Friday, May 25, 2012

Interweave a linked list. Do it in Linear time and constant space. Input: A->B->C->D->E Output: A->E->B->D->C

## Wednesday, May 23, 2012

### Implement a function to compute cubic root what is the time complexity?

pay attention to negative values, but it's a binary search

## Tuesday, May 22, 2012

### Roman strings

Get numeric number out of a roman string, linear time Given: mapping I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000 Input/Output: II = 2, III = 3, IV = 4 VI, VII, VIII IX = 9 XL = 40, XLIX = 49
```
mapping = {
'I' : 1,
'V' : 5,
'X' : 10,
'L' : 50,
'C' : 100,
'D' : 500,
'M' : 1000,
}

def roman(string):
prev = 0
totalsum = 0

for c in string:
if mapping[c] <= prev:
totalsum = totalsum + mapping[c]
else:
totalsum = totalsum - prev
totalsum = totalsum + mapping[c] - prev

prev = mapping[c]

print(totalsum)

roman("XCIX")

```