# Web Rarely

Obstacles are what you see when you take your eyes off your goal.

## programming problems

2008-08-12

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

Given an array of integers, find the subarray with the largest sum.
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.
Given an array of size N containing integers between 1 and N inclusive, determine if the array contains duplicates. The array can be destroyed.
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.
Reverse an array without indexing into it.
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;
}
```
Extract the unique elements from a sorted array of integers.
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();
}
```
Sort an array of size N containing integers between 1 and K inclusive, using a scratch array of length K.
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;
}
}
```
Given an array of integers of size N and a function rand_n() that returns a random number from 1 to N, generate a random permutation of the array.
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.
Given an array containing zeros and ones, sort the array.
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++;
}
}
```
Given two arrays of integers, determine whether the intersection of the sets of integers is non-empty.
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

Given a string representing a telephone number, print all of the permutations formed from the letters associated with those telephone digits. (Remember 0 and 1 have no letters; 2 has A,B,C; 3 has D,E,F; 4 has G,H,I; 5 has J,K,L; 6 has M,N,O; 7 has P,R,S; 8 has T,U,V; and 9 has W,X,Y.)
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);
}
}
```
Given only putchar(char c), write a routine putlong(ulong n) that prints out an unsigned long in decimal.
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);
}
}
```
Given an array of characters which form a sentence of words, give an algorithm to reverse the order of the words (not characters) in it.
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]);
}
```
Given two strings A and B, delete from B the characters which occur in A.
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;
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;
}
}
}
```
Write a routine that prints out a 2D array in spiral order.
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]);
}
}
```
Convert a string to lower case given only toupper(char c). The only assumption that can be made about the character set is that the characters are 8-bit.
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;
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.
Write code to determine whether an unsigned number is a power of 2.
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.
Give a method to count the number of bits set in a 32-bit unsigned number.
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];
```
Reverse the order of the bits of an unsigned integer.
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);
}
```

Reverse a linked list, and return the reversed list.
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;
}
```
Delete an element from a doubly-linked list.
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->Tail == node) list->Tail = node->Prev;
node->Prev = node->Next = NULL; // this is optional, but a good idea
}
```
Write a function to find the depth of a binary tree.
My solution:
```int findDepth(TreeNode *node)
{
if(!node) return 0;
return max(findDepth(node->Left), findDepth(node->Right)) + 1;
}
```
Insert an item into a sorted list.
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

Give a fast way to multiply a number by 7.
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

etc...
```
Given an array of items of length N and a compare function, find the largest and smallest items using as few item comparisons as possible.
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;
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];
}
}
```
Determine if the sum of two unsigned integers overflows.
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

How many times a day do a clock's hands overlap?
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.
You have eight balls of the same size. Seven weigh the same, and one weighs slightly more. Given a balance, how can you determine which ball weighs more using only two measurements?
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.
There are five pirates of different rank. The highest-ranked pirate gets to propose how 100 gold coins get divided among them. But if less than half of the pirates agree with the allocation, the highest-ranked pirate will be killed and they'll start over. How should he divide the gold to maximize his share but live to enjoy it?
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.
In a country in which people only want boys, every family continues to have children until they have a boy. if they have a girl, they have another child. if they have a boy, they stop. what is the proportion of boys to girls in the country?
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.
If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default probability)?
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.
If you look at a clock and the time is 3:15, what is the angle between the hour and the minute hands?
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.
You have five bottles of pills. In four of the bottles, the pills weigh one gram each, but in one bottle, they weigh only 0.9 grams each. Given a scale, how can you determine which bottle contains the lighter pills with just one measurement?
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.

boys/girls ratio 2008-09-04 02:57PM
I got a different answer :)
an anonymous K.
re: boys/girls ratio 2008-09-04 04:12PM
What is it? How did you get it? :-)
If you have to ask... 2008-09-04 04:22PM
I guess that the problem with your solution is that half of the families would have only one child - a boy, 1/4 would have 1 girl, 1/8 would have two girls (that makes 2/8 N girls) etc, so it's the sum of (i-1)/2^1.

But even easier is to think that if all the families will start at the same time, half will have boys and half will have girls, so the ratio is 1:1. One half will stop, the half of the other half will have boys, half will have girls as a second child, so the ratio will remain 1 to 1, etc

Well, I know a lot about having children ;-)
an anonymous K.
re: boys/girls ratio 2008-09-04 05:01PM
Hey, you weren't supposed to tell me! (Actually, I wasn't supposed to ask.) But that's okay, I managed to rethink it before I saw your answer. ;-) The problem with my solution is that I counted some girls more than once. In 1/2 + 2/4 + 3/8 + ..., the 2/4 included 1/4 that I'd already counted, the 3/8 included 2 * 1/8 that I'd already counted, etc. When I drew it on paper, my double-counting mistake became obvious.

I had originally assumed there'd be an imbalance, and then sought to keep working until I found it. Not making assumptions, especially about questions that are probably designed to trick me, is a lesson I never seem to fully learn...

Thanks.