Linearity of Expectation

100 people arrive at a party. Each of them puts his hat away in a common area. When they leave, they randomly pick a hat from the common area. What is the expected number of people leaving with the hats they arrived with?

Solution:

This is a classic. The answer is 1, essentially because of linearity of expectations:

E[total#matching hats] = Sum {i} E[ith guy leaving with matching hat]

Each E[ith guy leaving with matching hat] is equal, with value == 1/100.

A priori, there's no reason to assume E[ith guy leaving with matching hat] would be identical... but turns out they are. The proof is relatively straightforward and the application of this result is quite surprising in less obvious cases.

Burning the chopsticks

You have two identical pieces of chopsticks... they burn at different rates and not at steady rates. BUT! They only burn for one hour.

You have to use them to show 45 minutes exactly. How would you do it?

Crossing the bridge

You have four people at a bridge... one HAS to carry a flashlight as they cross, but only two can cross at a time. And nobody can go alone.

It only takes the first person 1 minute to cross. The second person takes 2 minutes. The third person takes 5 minutes. And the last one takes 10 minutes.

If the person who takes 1 minute goes with the person who takes 10, it automatically takes 10 minutes.

How many minutes will it take them all to cross at the quickest?

Check whether a singly linked list contains a loop

Given a singly linked list, determine whether it contains a loop or not.

ANS. (a) Start reversing the list. If you reach the head, gotcha! there is a loop!
But this changes the list. So, reverse the list again.
(b) Maintain two pointers, initially pointing to the head. Advance one of them one node at a time. And the other one, two nodes at a time. If the latter overtakes the former at any time, there is a loop!

p1 = p2 = head;

do {
p1 = p1->next;
p2 = p2->next->next;
} while (p1 != p2);

Jars of Pills

You have 5 jars of pills. Each pill weighs 10 gram, except for contaminated pills contained in one jar, where each pill weighs 9 gm. Given a scale, how could you tell which jar had the contaminated pills in just one measurement?

ANS. 1. Mark the jars with numbers 1, 2, 3, 4, and 5.
2. Take 1 pill from jar 1, take 2 pills from jar 2, take 3 pills from jar 3, take 4 pills from jar 4 and take 5 pills from jar 5.
3. Put all of them on the scale at once and take the measurement.
4. Now, subtract the measurement from 150 ( 1*10 + 2*10 + 3*10 + 4*10 + 5*10)
5. The result will give you the jar number which has contaminated pill.

Apples, Oranges and Mixes

There are 3 baskets. one of them have apples, one has oranges only and the other has mixture of apples and oranges. The labels on their baskets always lie. (i.e. if the label says oranges, you are sure that it doesn't have oranges only,it could be a mixture) The task is to pick one basket and pick only one fruit from it and then correctly label all the three baskets.

HINT. There are only two combinations of distributions in which ALL the baskets have wrong labels. By picking a fruit from the one labeled MIXTURE, it is possible to tell what the other two baskets have.

Cake Cutting Technique

Given a rectangular (cuboidal for the puritans) cake with a rectangular piece removed (any size or orientation), how would you cut the remainder of the cake into two equal halves with one straight cut of a knife?

ANS. Join the centers of the original and the removed rectangle. It works for cuboids too! BTW, I have been getting many questions asking why a horizontal slice across the middle will not do. Please note the "any size or orientation" in the question! Don't get boxed in by the way you cut your birthday cake :) Think out of the box.

Reverse a linked list

Reverse a singly linked list recursively.
The function prototype is node * reverse (node *) ;

node * reverse (node * n)
{
node * m ;

if (! (n && n -> next))
return n ;

m = reverse (n -> next) ;
n -> next -> next = n ;
n -> next = NULL ;
return m ;
}


Alternatively, we can use 3 points to reverse the list:

void reverselist(void)
{
if(head==0)
return;
if(head->next==0)
return;
if(head->next==tail)
{
head->next = 0;
tail->next = head;
}
else
{
node* pre = head;
node* cur = head->next;
node* curnext = cur->next;
head->next = 0;
cur->next = head;
for(; curnext!=0; )
{
cur->next = pre;
pre = cur;
cur = curnext;
curnext = curnext->next;
}
curnext->next = cur;
}
}

Find the permutations of a string using recursion

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <iostream>
using namespace std;

void swap(char* src, char* dst)
{
char ch = *dst;
*dst = *src;
*src = ch;
}
/* permute [set[begin], set[end]) */
int permute(char* set, int begin, int end)
{
int range = end - begin;
if (range == 1) {
printf("set: %s\n", set);

} else {
for(int i=0; i<range; i++) {
swap(&set[begin], &set[begin+i]);
permute(set, begin+1, end);
swap(&set[begin], &set[begin+i]); /* set back */
}
}
return 0;
}
int main()
{
char str[] = "abcd";
permute(str, 0, strlen(str));
return 0;
}

Two Normal Distributions

Given X,Y, both normal random distributions (N(0,1)). Their correlation is rho. If I tell you X is negative, what can you tell me about Y?

Solution:

Draw All Balls

There are 100 distinguishable balls in an urn. Each time you draw one ball and put it back. How many times do you expect you need to draw in order to have drawn each ball at least once?

Solution:

So on your first draw, you obviously draw a ball you've never drawn before. On your next draw, there's a 99/100 chance you draw a different one. After you've drawn 2 distinct balls, there's a 98/100 chance you draw a different one from those 2. And so on. The expected number of draws is just the reciprocal of the probability of that event happening.

So we simply have: 1 + 100/99 + 100/98 + ... +100/3+100/2+100.

I wasn't asked to evaluate this sum during the actual interview, and quite frankly I wouldn't know how to do this exactly. I probably would have taken the integral of 1/x over 1 to 100, which is ln 100 ~= 4.61 so about 461 draws.

The actual answer is 518.74 so that approximation would be way off--not surprising. I'm gonna be anal here and look at the graph--okay, so half of the 1st bar of the sum I'm approximating by the integral isn't included. That got an area of 50! Add 50 to 461 and we have 511. That's much better.

I suppose at this point, if you have gone this route, an interviewer could start talking about numerical methods, especially if he happened did his thesis on something related.

ps. check out the harmonic series page from mathworld. the closed form formula for the sum is... certainly not fair game for an interview.

Random Reduction

This one I like a lot.

N_1 = 10^100.
N_2 = random number picked from 1 to N_1.
...
N_k = random number picked from 1 to N_(k-1).

For what k do you expect to see N_k = 1?

Solution:

The following is my solution, passing to using continuous probabilities. It's a little long-winded, so maybe there's a better solution, especially during an interview. Let me know!

Basically, we're applying some random number X of uniform distribution k-1 number of times:

N_k = X_1 * X_2 * ... X_(k-1) * N_1

Dealing with products is tough, so the natural thing to do would be to take the log of both sides:

log (N_k) = log (X_1) + ... + log (X_(k-1)) + log (N_1)

which leads to:

- log (N_1) = Sum{i from 1 to k-1} log (X_i)

The X_i's are independent, so the question now becomes:

Find k such that:

(k-1) E[log(X)] <= -log(N_1)

Where the minus signs are seriously annoying.

So what's E[log(X)], X being a uniform distribution from [0,1]? That's an integration exercise, taking the integral of X*logX from 0 to 1, dX...

which yields a value of -1. Surprising, no?

which means you would expect N_1 by a factor of e every time you multiply it by a uniform random variable. So 100/(1/e) = 100e ~= 271.8.

Add 1 to that and you have k = 272.8, or 273 to take the next greatest integer.

There has gotta be a more elegant solution to this!

Sorting

A favorite category of quant interview questions is sorting and complexity. Obviously, if you're doing quant, most of the time you'll be coding, and a good understanding of computer science (algorithms in particular) is crucial.

Here's one that's more computer science oriented than most, but fair game nonetheless:

You're given 1 billion integers to sort. You have 1Gb in memory. How would you achieve the task? Complexity?

Would you do it differently if the integers are guaranteed to be unique? Complexity?


Solution:

Basically, some kind of merge sort. Assume memory M and integers N. Step 1: sort N/M length-M lists. Step 2: merge the N/M lists.

Yeah, for non-CS people, it's time to review the various ways to sort. For step 2, review heaps. The answer is straightforward if you remember what a heap is. The complexity is some combination of N log M and N log (N/M).

If the integers are guaranteed to be unique... this is kinda neat. So you have 1Gb in memory, which is more than enough bits to use each bit as a flag to indicate the existence of a, say 32-bit integer. So simply go through your list of N integers and populate the corresponding bit in memory for each of those integers.

This will yield a O(N) solution. Essentially a simple bucket sort.

Remove Node in Linked List

This is apparently a question from Microsoft.

Given a singly linked list. You're given a pointer to a node in the list. Give me an algorithm that efficiently removes that node from the list.

Solution:

Some might consider this solution a cheat, but really it's quite elegant. Obviously, you can traverse the entire list up to that node, but equally obvious is that it's not the solution they'll be looking for. You should do this: copy the data from the next node into this node. Now erase the next node and update where the given node is pointing to.

Unless copying data is the bottleneck, this should be the best solution in most cases. Perhaps there are times when the address of the node is critical, but not in an interview question, and certainly not in this interview question.

Scarabs on a Dodecagon

From a problem set, but doesn't mean it's not a good problem.

Consider a regular and convex dodecagon (a polygon with 12 sides). Two scarabs initially located on two opposite vertices (summit) move at each time step along an dege. They ove independently from each other clockwise or counter-clockwise with probability 1/2. What is the proportion of time that the two scarabs spend together (on the same summit, after a large number of steps)?

Solution:

An "official" solution would be: draw your transition graph, write down your transition matrix, calculate your stationary distribution.

A much faster solution would be to simply observe that the distance between the two scarabs would always be even, and since the two scarabs move independently of each other, the expected proportion of time they spend together would simply be 1/6.