Web Rarely

Here are a bunch of programming problems that I gathered from the internet, and my solutions to them. I'm posting them so smart people can give me better ideas and new problems to solve, and to prove to myself that I can do them. I'm sure some of my solutions are non-optimal or even wrong. They were all written without the aid of a development environment, so I'm not even sure that they all work. Feel free to correct me.

The code is a combination of C, C#, and pseudocode. It's intended to demonstrate an idea, so not all code snippets will compile as-is, and most lack error checking.

Arrays of Integers

I believe this can be done with a single pass over the array. We'll simply keep track of the best subarray seen so far, which is initialized to an empty subarray (a valid subarray of any input), which has a sum of 0. The pseudocode looks like this:

int bestStart = bestLength = bestSum = 0
for(int i=0,start=0,sum=0; i < array.Length; i++)
{
    sum += array[i];
    if(sum < 0) start = i+1, sum = 0;
    else if(sum > bestSum) bestStart = start, bestLength = i-start+1, bestSum = sum;
}
// the subarray with the greatest sum is stored in (bestStart, bestLength)

That might be incorrect but my reasoning is that at whatever point we're at in the array we have greatest sum of the items before it. (This is initially true.) When we encounter a new element, it may increase or decrease the sum (or leave it unchanged). If it increases the sum beyond the best seen so far, we remember the new best. Either way, if the new sum is negative, it's not worth including in whatever comes next, so we forget it. Otherwise, it is worth including because it increases the sum (or leaves it the same). So when we begin the next iteration we again have the best sum of the items before the current element. Also, the method doesn't handle overflow. My solution makes a single pass over the array and needs no additional space, but it destroys the array. If there are no duplicates, the array will necessarily be a permutation of the sequence 1, 2, 3, ... N. For each element m in the array, the algorithm sets the element to zero and "jumps" to the m'th element. If it jumps to an element that already has a zero, then there is a duplication.

for(int count=0, i=0; count < N; count++)
{
    if(array[i] == 0) return true; // there is a duplicate
    int m = array[i];
    array[i] = 0;
    i = m-1;
}
return false; // no duplicate

Is there a solution that runs in O(N) time, uses only constant space, and doesn't alter the original array? If so, I think it would have to use the fact that an array without duplicates is a permutation of 1..N to its advantage. A probabilistic approach would be to checksum the array and the desired permutation using a checksum that doesn't care about the data order. But I don't like algorithms that only work most of the time. This is a strange problem. I can only assume this means to use pointers rather than array indexing.

void Reverse<T>(T* array, int count)
{
    for(T* start=array, end=array+count-1; start < end; end--,start++)
    {
        Swap(start, end);
    }
}

void Swap<T>(T* a, T* b)
{
    T temp = *a;
    *a = *b;
    *b = temp;
}

Since the array is sorted, duplicates will only occur in groups, so it's trivial to see if an element is a duplicate.

int[] GetUnique(int[] list)
{
    if(list == null) throw new ArgumentNullException();
    List<int> unique = new List<int>();
    foreach(int i in list)
    {
        if(unique.Count == 0 || i != unique[unique.Count-1]) unique.Add(i);
    }
    return unique.ToArray();
}

It sounds like they want a counting sort.

void Sort(int[] array)
{
    int[] scratch = new int[K];
    foreach(int i in array) scratch[i-1]++;

    for(int i=1,j=0; i <= K; i++)
    {
        int count = scratch[i-1];
        while(count-- != 0) array[j++] = i;
    }
}

This requires just a slight change to the stardard permutation algorithm.

void Permute(int *array)
{
    for(int i=0; i < N; i++)
    {
        int swapIndex;
        do swapIndex = rand_n()-1; while(swapIndex >= i);
        Swap(&array[i], &array[swapIndex]); // Swap() is defined above
    }
}

Note that it's not strictly correct to take the number returned from rand_n() and use modulo to clip it to the desired range. In general, rand() % M does not produce a truly random distribution, even if rand() does. It only works if M is a divisor of the number of possible values returned from rand(). So, if rand() has a range of 2^31 values, rand() % M is properly distributed only if M divides 2^31, because otherwise the first (2^31 % M) values would be slightly more likely to be chosen than the rest. It's possible to use a counting sort in the cases where the range of the numbers is small, but in this case the range is only two, which allows even more optimization. We can work from both ends of the array, moving ones to the end and leaving the zeros at the beginning.

void SortBinary(int[] array)
{
    for(int i=0, end=array.Length-1; i < end; )
    {
        if(array[i]) Swap(&array[i], &array[end--]); // Swap() is defined above
        else i++;
    }
}

Well, the straightforward solution is to walk both arrays, sticking all of the integers into a hash table, and returning true if any of the integers in the second array have already been added from the first array. If each array contains no duplicates, you can walk the two arrays in parallel, allowing you to potentially detect an intersection sooner. If the arrays are sorted, you can dispense with the hash table and walk them in parallel with two pointers, advancing whichever pointer is pointing to a lower value until either the end of an array is reached or the pointers are pointing to the same value. There may also be a cleverer solution that I haven't thought of.

String Manipulation and Output Routines

Here's my solution, which is both simple and fast. It handles formatted numbers as well, like "(555) 555-1234".

const string Letters = "ABCDEFGHIJKLMNOPRSTUVWXY";

void PrintPermutations(string number)
{
    PrintPermutations(number, new char[number.Length], 0);
}

void PrintPermutations(string number, char[] prefix, int prefixLength)
{
    if(prefixLength == number.Length)
    {
        Console.WriteLine(prefix);
        return;
    }

    char c = number[prefixLength];
    if(c >= '2' && c <= '9')
    {
        for(int i=(c-'2')*3, end=i+3; i < end; i++)
        {
            prefix[prefixLength] = Letters[i];
            PrintPermutations(number, prefix, prefixLength+1);
        }
    }
    else
    {
        prefix[prefixLength] = c;
        PrintPermutations(number, prefix, prefixLength+1);
    }
}

Here's a simple recursive solution that I think will work:

void putlong(ulong n)
{
    if(n == 0) putchar('0');
    else _putlong(n);
}

void _putlong(ulong n)
{
    if(n != 0)
    {
        _putlong(n / 10);
        putchar('0' + n%10);
    }
}

I'll assume the existence of an issep(char c) function that determines if a character is a word separator. My solution is nothing genius... it just scans the array while keeping track of the start of the current word, and reverses the word when its end is found.

for(int i=0; i<array.Length; i++) // for each word
{
    // scan to find the beginning of the word
    while(i < array.Length && issep(array[i])) i++;
    int wordStart = i;

    // scan to find the end of the word
    while(i < array.Length && !issep(array[i])) i++;

    // reverse the word (in C#, we can use the standard library rather than this function)
    Reverse(array, wordStart, i - wordStart);
}

void Reverse<T>(T[] array, int start, int length)
{
    for(int i=0, j=start+length-1, count=length/2; i < count; j--,i++) Swap(&array[i], &array[j]);
}

If A and B have lengths m and n respectively, and you have 8-bit characters, an easy solution which runs in O(m+n) time is to create an array of 256 booleans, and loop over A, setting the boolean for each extant character to true, and then scan over B and delete the characters for which the boolean is true. If the alphabet is larger than 8 bits, a hash table can be used.

void stripChars(char *charsToRemove, char *string)
{
    if(!charsToRemove || !string) throw an exception;

    bool shouldRemove[256];
    memset(shouldRemove, 0, 256);

    while(*charsToRemove) shouldRemove[*charsToRemove++] = true;
        
    int offset = 0;
    while(true)
    {
        char c = string[offset];
        if(shouldRemove[c]) offset++;
        else
        {
            *string++ = c;
            if(!c) break;
        }
    }
}

This sounds messy. I don't know if there is an elegant way to do it. But here's my solution, which assumes the array is indexed as y,x.

void PrintSpiral(int[,] array, int width, int height)
{
    for(int i=0, count=(min(width, height)+1)/2; i < count; i++)
    {
        PrintOutline(&array[i,i], width-i*2, height-i*2, width);
    }
}

void PrintOutline(int *array, int width, int height, int pitch)
{
    // print across the top
    for(int i=0; i < width; i++) print(array[i]);
    
    // print down the right
    for(int i=1,tr=pitch-1; i < height; i++) print(array[tr + i*pitch]);

    if(height > 1)
    {
        // print along the bottom
        for(int i=1,br=height*pitch-1; i < width; i++) print(array[br - i]));
    }

    if(width > 1)
    {
        // print along the left side
        for(int i=1,bl=(height-1)*pitch; i < height-1; i++) print(array[bl - i*pitch]);
    }
}

I don't think it's possible to do unless you can examine the entire alphabet in advance. My solution examines each character in the alphabet and passes it to toupper(). If toupper() returns the same character, then it was either uppercase already, or was not a letter. But if toupper() returns a different character, we know the original character was lowercase and the new one is its uppercase version, and we can use that information to map from upper to lower. If the alphabet is larger, say 16-bit, we could still do this with reasonable space efficiency by using a hash table rather than a full lookup table, and only storing the upper to lower case mapping.

void strLower(string s)
{
    static char lookup[256];
    static bool computedTable;

    if(!computedTable)
    {
        for(int i=0; i<256; i++)
        {
            char c = (char)i, upper = toupper(c);
            if(c != upper) lookup[upper] = c; // map upper to lower
            if(lookup[c] == 0) lookup[c] = c; // don't overwrite an existing entry
        }
        computedTable = true;
    }

    for(int i=0; i<s.Length; i++) s[i] = lookup[s[i]];
}

Bit Twiddling

These are usually fun problems. My solution is a single C expression: !(n & (n-1)) && n. An unsigned number is a power of two if exactly one bit is set. Say we have the binary number 0100. If we subtract one, the subtraction will carry from the least significant bit, past all the zero bits (setting them to 1), until it hits the first one bit, which will be set to zero. In our example, this results in 0011. One bits beyond the first will be unaffected. ANDing the result of the subtraction with the original number will effectively mask off the least-significant one bit. If the result is zero, then either the number was zero to begin with, or there was only one bit set. There might be a really clever solution, but if so I didn't find it. I have 3 solutions. The first one is the naive solution, which loops over the bits. A number like 0x80000000 (which has one bit set) needs 32 iterations.

int count = 0;
while(n != 0)
{
    if(n & 1) count++;
    n >>= 1;
}

The second uses my "power of 2" solution above to reduce the number of iterations to the number of one bits, so 0x80000000 (which has one bit set) needs only one iteration, however 0xffffffff still needs 32 iterations.

int count = 0;
while(n != 0)
{
    n &= n-1; // zero out the least significant one bit
    count++;
}

The third is to build a 256-byte lookup table mapping bytes to number of the bits set in the bytes. This trades memory for speed and time consistency.

    count = table[n & 0xFF] + table[(n>>8) & 0xFF] + table[(n>>16) & 0xFF] + table[n>>24];

This is easy to do, but there may be a clever trick that I don't know about. This implementation is at least smart enough to stop iterating when there aren't any one bits left. For instance, the number 5 (binary 00000101) is reversed in 3 iterations rather than 32.

uint ReverseBits(uint n)
{
    uint reversed = 0;
    int bits;
    for(bits=0; n != 0; bits++,n>>=1) reversed = (reversed<<1) | (n & 1);
    return reversed << (32-bits);
}

Linked lists and trees

My best solution uses a few pointers and loops over the list once.

ListNode * Reverse(ListNode *node)
{
    for(ListNode *prev = NULL; node; )
    {
        ListNode *next = node->Next;
        node->Next = prev;
        prev = node, node = next;
    }
    return node;
}

It can also be formulated recursively, but the iterative version is clearer and shorter. Can you improve this?

ListNode * Reverse(ListNode *node)
{
    ListNode *last = NULL;
    if(node) _Reverse(node, &last);
    return last;
}

ListNode * _Reverse(ListNode *node, ListNode **last)
{
    if(!node->Next) *last = node;
    else
    {
        ListNode *rest = _Reverse(node->Next);
        rest->Next = node;
        node->Next = NULL;
    }
    return node;
}

Assuming there's no separate List data structure with Head and Tail pointers to update...

void deleteNode(ListNode *node)
{
    if(!node) throw an exception;
    if(node->Prev) node->Prev->Next = node->Next;
    if(node->Next) node->Next->Prev = node->Prev;
    node->Prev = node->Next = NULL; // this is optional, but a good idea
}

And if there is...

void deleteNode(List *list, ListNode *node)
{
    if(!list || !node) throw an exception;
    if(node->Prev) node->Prev->Next = node->Next;
    if(node->Next) node->Next->Prev = node->Prev;
    if(list->Head == node) list->Head = node->Next;
    if(list->Tail == node) list->Tail = node->Prev;
    node->Prev = node->Next = NULL; // this is optional, but a good idea
}

My solution:

int findDepth(TreeNode *node)
{
    if(!node) return 0;
    return max(findDepth(node->Left), findDepth(node->Right)) + 1;
}

A basic binary search problem. In C#, you can actually just use the built-in BinarySearch() method of List<T>.

void Insert<T>(List<T> list, T newItem)
{
    int index = BinarySearch(list, newItem);
    list.Insert(index < 0 ? ~index : index, newItem);
}

int BinarySearch<T>(List<T> list, T item)
{
    int min = 0, max = list.Count-1;
    while(min <= max)
    {
        int middle = min + (max-min)/2, cmp = Compare(item, list[middle]);
        if(cmp > 0) min = middle + 1;
        else if(cmp < 0) max = middle - 1;
        else return middle;
    }
    return ~min;
}

The code computes the middle as min + (max-min)/2 rather than the simpler (min+max)/2 because the latter will fail if min+max overflows.

Other Programming Questions

In almost every language and circumstance, the best way is n*7. Trickery like (n<<3)-n is dubious because it obscures the meaning of the code, not only for humans, but for the compiler, too. The shifting trick is not guaranteed to be faster on modern CPUs, and the compiler may have better optimizations available than shifting, which it will only be able to use if you don't obscure the code. In interpreted languages, this trickery is even more dubious, since the overhead of interpreting the more complex shift expression is probably much higher than the time to do the multiplication.

A few short 80386 sequences that multiply EAX by seven:

; ebx = eax*7
lea ebx, [eax*8]
sub ebx, eax

; eax *= 7
mov ebx, eax
lea eax, [eax*8]
sub eax, ebx

; another eax *= 7
mov ebx, eax
shl eax, 3
sub eax, ebx

; and another
lea ebx, [eax+eax*4]
shl eax, 1
add eax, ebx

etc...

This uses a little trick which I happen to know but didn't discover independently. The naive approach, comparing each item to the largest and smallest seen so far takes (N-1)*2 comparisons. It's possible to reduce this to (N-1)*3/2 by walking the array in pairs, doing three comparisons per two items. The basic idea is to compare the two items in each pair. Then we can avoid testing the lesser against the maximum so far and the greater against the minimum so far. I think this is also the lower bound, at least for this optimization, because walking the array in larger groups doesn't seem like it'd improve the result.

void MinMax<T>(T[] array, out T min, out T max)
{
    if(array == null || array.Length == 0) throw new ArgumentException();

    min = max = array[0];
    int i;
    for(i=1; i<array.Length-1; i+=2)
    {
        int cmp = Compare(array[i], array[i+1]), minOffset, maxOffset;
        if(cmp < 0) minOffset=0, maxOffset=1;
        else if(cmp > 0) minOffset=1, maxOffset=0;
        else minOffset = maxOffset = 0;

        if(Compare(array[i+minOffset], min) < 0) min = array[i+minOffset];
        if(Compare(array[i+maxOffset], max) > 0) max = array[i+maxOffset];
    }

    if(i < array.Length)
    {
        if(Compare(array[i], min) < 0) min = array[i];
        if(Compare(array[i], max) > 0) max = array[i];
    }
}

I believe an overflow occurs if the sum is less than either of the operands:

if(a + b < a) // overflow occurred. if(a + b < b) also works.

Logic and Math Problems

The "obvious" answer is 23 (0:00, 1:05, 2:10, 3:15, ...) but it's wrong. If you actually try to complete the sequence, you'll notice that after 11:55PM, the next overlap would be at 12:00AM, only five minutes later. That can't be right. The hands simply don't overlap at 1:05, 2:10, etc. At 1:00, the hour hand is on the 5 minute mark. By the time the minute hand catches up to the hour hand, the hour hand has moved ahead slightly. This is very much like Zeno's paradox of the tortoise and Achilles, and can be solved in the same way.

The minute hand is moving at 1 tick per minute, while the hour hand is moving at 1/12 tick per minute. The hour hand has a 5 tick "head start". The number of minutes after the hour when they overlap is the value of 'x' that makes xm * 1t/m = xm * 1t/12m + 5t. We can solve it easily: xt = xt/12 + 5t; 11xt/12 = 5t; 11x/12 = 5; x = 60/11 = 5.4545... minutes. And so, rather than overlapping at 1:05, the hands overlap at about 1:05 and 27 seconds. The overlaps are at 0:00, 1:05:27, 2:10:55, 3:16:22, ... and you end up with 22 overlaps per day. Weigh two groups of three balls. If the two groups are of equal weight, the heavier ball is one of the remaining two. Simply weigh them and find out. If one group of three is heavier, the heavier ball must be in that group. Weigh any two balls from that group. If the two are of equal weight, the heavier ball is the one that remains. This is an ambiguous question, because the criteria that the pirates would use to vote are not given, nor are their dispositions. If they are particularly fair-minded they may only be satisfied with an equal division. But the problem can't be "solved" that way... it's pure speculation. So let's assume the pirates are extremely greedy and ruthless, such that they'd kill for the slightest advantage.

We'll approach this like a game, and number the pirates 1-5, with 5 being the highest rank.

1. If there is only one pirate, he would of course take all the gold. So being the last pirate standing is a winning position.
2. If there are two pirates, the top pirate can take all of the gold by voting yes. So being the top pirate in a two-pirate position is a win.
3. If there are three pirates, the middle-ranked pirate has no reason to agree with the allocation, because he can get all the gold if the top pirate is killed. So the top pirate has to get the lowest-ranked pirate onto his side. The lowest-ranked pirate cannot get any gold if the top-pirate is killed, so he should be willing to accept anything. Presumably, then, the top-ranked pirate could give the lowest-ranked pirate 1 gold piece and keep 99 for himself. (Though if I was the lowest-ranked pirate, I'd vote "no" out of spite!)
4. If there are four pirates, the top-ranked pirate has to get one pirate onto his side. This seems like it could be the lowest-ranked pirate again, with a 99/1 split, but that would not guarantee a win, because then the lowest-ranked pirate would get one coin regardless of the outcome of the vote, and so his vote would come down to personality. To guarantee the lowest-ranked pirate's support, he'd have to be given 2 coins. However, the top pirate can do better than that because he knows that if he dies, pirate 2 gets nothing. So he can secure pirate 2's support with a single coin.
5. If there are five pirates, the top-ranked pirate must get two pirates onto his side. Pirate 4 would like to see the top pirate killed so he can get 99 gold. But if that happened, pirates 1 and 3 would get nothing, so the top pirate can secure their votes with one coin each, keeping 98 coins for himself.

Sadly, this is true in many countries. Assuming a 50% chance to get a boy (in reality it's about 51%), half of the families will stop after one child. Half again will stop after 2 children. Half yet again will stop after 3. So if there are N families, then there are N boys and 1/2N + 1/4N + 1/8N + 1/16N + ... girls, or the sum of N/(2^i), where i ranges from 1 to infinity. This infinite sum converges on N, so there would be one girl for each boy. I guess it's not so sad after all. Well, let's work backwards. Let's say the probability of seeing a car in 10 minutes is p. The probability of seeing a car in 30 minutes is of course equal to one minus the probability of not seing a car in 30 minutes. And the probability of not seeing a car in 30 minutes is equal to the probability of not seing a car in 10 minutes, 1-p, cubed. So we have 1 - (1-p)^3 = 0.95. Then, we can solve for p: (1-p)^3 = 0.05; 1-p = 0.05^(1/3); p = 1 - 0.05^(1/3) ~= 0.6316. So there is about a 63.16% chance of seeing a car in 10 minutes. We can reuse a bit of the information from the clock question, above. At 3:15, the minute hand will be at the 15 minute mark, and the hour hand will be 15/11 minutes ahead of the 15 minute mark. Since there are 60 minutes and 2pi radians in an hour, this is an angle of (15/11) / 60 * 2pi radians = pi/22 radians. This is very tricky. You take 1 pill from the 1st bottle, 2 from the 2nd bottle, 3 from the 3rd, etc., and weigh them all together. If the first bottle contains the lighter pills, the weight will be 0.1 gram less than the expected weight of 1+2+3+4+5 = 15 grams. If the second bottle contains them, it will be 0.2 grams less. Etc.