0s and 1s oh my!

Problem:  You are given an array with only 1s and 0s.  Sort the array.

void sortArray(int arr[]) {...}

Solution:  Your first thought is probably to use quicksort.  The is a super simple solution and it's worth mentioning:

void sortArray(int arr[]) {

  qSort(arr);

}

Well, that was pretty easy and we have a working solution.  We could go ahead and implement quicksort if we had to, but that just shows that we know how to sort and array.  So, let's look at the run-time of this.  Quicksort is O(n log n), so this is an O(n log n) fuction.  Well, can we do better?

At first thought, this is as good as could be as sorting is optimally an O(n log n) function.  But, we do have another piece of information that we haven't used -- which is that the only elements are a 0 or a 1.  Let's make an example array to help us see how to do this.  Figure 1 shows just such an example.

Figure 1

Try looking at figure 1 and see what information it provides.  We see that there are 0s and 1s and a certain number of each.  Try to image what we could do with the certain number of each.  

This starts to hint at a possible algorithm.  We can go through and count the number of 0s and 1s.  Then, we can back through the array and write the number of 0s and 1s in place.  This should work, and would be O(n) as we only go through the array twice.

Now, let's code up this algorithm:

void sortArray(int arr[]) {

    int curElem, numZeroes = 0;

    /* Count the number of zeroes */

    for (curElem = 0; curElem < arr.length; curElem++) {

        if (arr[curElem] == 0) numZeroes++;

    }

    /* Now, write all the 0s at the beginning and 1s at the end */

    for (curElem = 0; curElem < arr.length; curElem++) {

        if (numZeroes > 0) {

            arr[curElem] = 0;

            numZeroes--;

        }  else {

            arr[curElem] = 1;

        }

    }

}

Let's test this with the sample array in figure 1.  numZeroes will count six 0s.  Then, the second for loop will put 6 zeroes at the front until numZeroes equals 0, upon which it will write eight remaining 1s, perfectly sorting the array in linear time.

It's worth testing the boundary cases, like a null array, in which case this would return null, or if there are nonzero characters, which simply become 1s in this case, which seems ok, but we would have to understand in a greater context if there are other ways to handle this.

Pretty neat.  Now, for next time, think of what it would be if we had 1, 2 or 3 in the array.

/* Please let me know if you find alternate solutions or bugs.  Thanks, Noah */

Print all Fibonacci numbers

Problem:  Print all the Fibonacci numbers from 1 to n using the fibNum() from two problems ago function.

void printFib(int n) {...}

Solution:  This is a relatively simple problem that appears straight forward.  It would be asked early on to simply screen out people.  It is straight forward as:

  int i;

  /* Check for the error case of negative number or 0 */
  if (num <= 0) return ERROR;

    for (=0; i < n; i++) 
        printf("%d\n", fibNum(i));
} 


Well, that's it.  Not too much to it.  Let's analyze the algorithmic run time.  Since we know fibNum is O(n), then we could have to call fibNum n times, this is O(n^2).  Not great, and we know that we're doing this slowly.

Next problem is to do this in linear time.

/* Please let me know if you find any bugs to this.  Thx, Noah */

Lotteries- choose your own numbers or buy a quickpick?

Problem:  Is it better to choose your own lucky numbers or buy a quick pick ticket?  Does it matter?  (Thank you to Wayne L. for this question)


Solution:  The first and obvious answer is that it doesn't matter!  Assuming that the drawing is fair (and it's always good to list assumptions) - then pick whatever numbers you want


This seems like a reasonable answer.  But, now let's challenge the assumptions and see exactly what we're optimizing for before declaring victory.


Ok, so first, we assume that the lottery is fair. That is to say that a truly random set of numbers is drawn.  We assume that some numbers are not more common than others due to the weighting of the paint on a ping pong ball, or simply a not entirely accurate random number generator, whatever process happens to be used.


Let's say that this is true, that we are not going after the random number generator.  So, this assumption seems to hold.


Are there any other assumptions?

Well, let's try a simple example.  Assume that we have a simple lottery of the numbers 1-10.  What would you choose?


7?


Well, what would most people choose?  


You're probably aware that humans are very bad at picking random numbers.  When asked to pick random numbers between 1-10, there is not an even distribution, but many people choose 2 and 7.


So, let's say you chose 7, is this good or bad?


Now, two things can happen.  One, you can lose, in which case it didn't really matter. Or, you can win -- which seems good.


But, as 7 is very common, someone else, or many people likely chose 7.  So, you'll end up splitting the winning with them.


Here's seems to another optimization, that you want to choose a number that no one else does, so if you win, your expected winnings are higher.


And, this assumption, strongly gives an answer to the original question.  Since humans are bad at choosing random strings, you're more likely to have others choosing the same set of numbers if you choose, than if you get a quick pick.  And, since the likelihood of winning doesn't change, but the expected amount does, quickpicks are the way to go if you're optimizing for expected value!


/* Please let me know if you find bugs or alternative solutions.  Thx, Noah */

Next Fibonacci number (non-recursive)

Problem:  Write a non-recursive function to prints the xth Fibonacci number which can do it in linear time


int finNum(int num) {...}


Solution:  The last two problems go into the Fibonacci sequence, so let's start by thinking about how this could be implemented non recursively.


We would need to iterate and always keep track of the two previous numbers, and then finish up with the new Fibonacci number.  And, if we pay attention to error cases, this should be straight forward.


The iteration step needs to be done in the correct order and can be a little tricky, so you may want to write out an example, say 4, and then try it.


So, let's go ahead and implement this:


int fibNum(int num) {

  int i, fib, fib0, fib1;

  /* Check for the error case of negative number or 0 */
  if (num <= 0) return ERROR;


  /* Now, enter the two base cases */
  if (num == 1) return 0;
  else if (num == 2) return 1;


  /* Now, write an iterative loop to figure out the fib num */
  /* Intialize fib0 as 0, fib1 as 1, and fib as their sum (1) */
  for (i = 2, fib0=0, fib1=1, fib=1; i < num; i++) {
    fib0 = fib1 + fib;
    fib1 = fib;
    fib = fib0 + fib1;
  }
  
  return fib;
}


Well, that's it.  What's the run time?  Since we go through the lop up to num-2 times, it is num.  We should check boundary cases of num = 2, and an error.  


Also, let's test with the number 5 -- and it works.


So, we have now implemented a non-recursive solution.  Let's talk about the trade-offs.  First, it's longer than the simple fib implementation.  But, it is efficient (linear) and does not have the recursive overhead.


The boundary cases can be tricky, and it doesn't read as nicely as the simple recursive Fibonacci solutions.


This is a problem that seems really easy, but it's important to always check the boundary cases and do an example, as trying to figure out all the fib0, fib1 and fib otherswise and where to initialize the variables, is very tricky otherwise, but fairly simple with an example.


/* Please let me know if you find any bugs or other solutions. */

Fibonacci (today) + Fibonacci (yesterday)

Problem:  Write a recursive function to prints the xth Fibonacci number which can do it in linear time


int finNum(int num) {...}


Solution:  


Yesterday, we printed the the nth Fibonacci number with a very simple algorithm, but wow, was it slow.  The running time was O(2^n).  Wow.  That's really, really bad, even for relatively low values of n (like 60).


Well, we have to keep it recursive, but need to do in linear time.  


Let's start by taking a look at yesterday's code:




int fibNum(int num) {


  /* Check for the error case of negative number or 0 */
  if (num <= 0) return ERROR;


  /* Now, enter the two base cases */
  if (num == 1) return 0;
  else if (num == 2) return 1;

  /* and now, recursive call to figure out the number */
  else return (fibNum(num-1) + fibNum(num-2));
}


This code makes spawns to new calls, which each spawns two more threads as it recurs on itself.  This leads to the really horrible run time for the code.  Clearly, we have to do better


Also, this is very, very repetitive, as we continually call fibNum on the same number.  For example, in yesterday's example, we would call fibNum on fibNum of 1 or 2 as much as O(2^n).  Other numbers are called significantly too.  This seems unnecessary


Think about how you could change the number of times that fibNum is called for each number.  


One solution might appear to build a data structure, that you would populate the first time you get a fibNum, then could check if you had already called fibNum on that number, and recur if you did not.  This would certainly work.  You could do this by storing an array, which would allow easy lookup by index, and then only recur if it was undefined.


Good solution, but we can do even better, without additional memory.


To provide a hint, take a look at the return statement.  The Fibonacci function requires the two previous values, but we do not keep track of them, so we have to recur each time to get them.  Think about a recursive function which kept track of the two previous values each time.


In fact, if we could do this, we would not have to go ahead and spawn two threads each time.  To do this recursively, we would need a function which kept track of the two previous values, and then would update on each recursive call, so that it would 'shift' and move the previous value back two, and our current value back one.  


The base case here would be reaching the second value, or num.  And we can imagine num getting smaller until we reach the base case, while we build up the value for num.


This is a slightly more complicated function, but much more efficient.  It is a recursive solution that keeps track of the two previous values each time, and we seed a helper funciton with the first two values, 0 and 1.


Now, using this recursive insight, we can go ahead and code the problem, making sure that check bases cases.



int fibNum(int num) {


  /* Check for the error case of negative number or 0 */
  if (num <= 0) return ERROR;


  /* Now, enter the two base cases */
  if (num == 1) return 0;
  else if (num == 2) return 1;

  /* and now, recursive call to figure out the number */
  else return (fibHelper(num, 0, 1);
}





int fibHelper(int num, int one_prev, int two_prev) {


  if(n == 1) return two_prev;
  return fibHelper(n - 1, two_prev, one_prev  + two_prev);
}




Now, let's try an example, say 5.  Yup.  It works!


So, what is the run time of this function?  We will make the same number of calls to fibHelper as num, so it is O(n), a WHOLE lot faster that the previous, simple implementation.  


We can also drop one of the base cases now, for simplicity, as we don't need to treat num=2 as a special case anymore, which give us (fibHelper remains the same):



int fibNum(int num) {


  /* Check for the error case of negative number or 0 */
  if (num <= 0) return ERROR;


  /* Now, enter the two base cases */
  if (num == 1) return 0;


  /* and now, recursive call to figure out the number */
  else return (fibHelper(num, 0, 1);
}





This is a good example of where by simply going a little further, we are able to take a disastrously inefficient function, and make it better, and why you shouldn't stop at just a 'good' solution.


/* Please let me know if you find any bugs here.  */

The Fibonacci Sequence

Problem:  Write a recursive function to prints the xth Fibonacci number.


int finNum(int num) {...}


Solution:  


This is a canonical recursive problem, but can be encountered.  Let's start this problem with a review of the Fibonacci sequence.  This is a sequence of numbers where each number is the sum of the previous two numbers, and the first two numbers in the sequence are 0 and 1.  


A mathematician expresses this as:






Now, let's do an example of the first say, 7, Fibonacci numbers to make sure that we get the pattern:


0
1
1
2
3
5
8


And we could go more.  


Well, with this, it seems set up for recursion.  We have our two base cases, which is if the num is 1 or 2.  And, otherwise, we have the sum of the two previous numbers.


With this, we can code it up, and we need to check for base cases:


int fibNum(int num) {


  /* Check for the error case of negative number or 0 */
  if (num <= 0) return ERROR;


  /* Now, enter the two base cases */
  if (num == 1) return 0;
  else if (num == 2) return 1;

  /* and now, recursive call to figure out the number */
  else return (fibNum(num-1) + fibNum(num-2));
}


And, that's it.  Let's do an example, say 7 above, and walk through it to make sure that it works.


It does!


So, this solution works recursively.  What is it's runtime?


Well, it calls fibNum two times more as num grows.  This means that the function is O(2^n).  This is horrible for even small sizes of n.  Wow.  Just awful!


Think about how to make this better, while still recurring.  That's tomorrow's problem. 


/* Please let me know if you find any bugs here.  */

Biggest and There (part II)

Problem:  Create a data structure and functions that can insert into the structure and then output the largest element and whether an element is a member

bool insert (int elem, struct node * dataStruct) {...}


int largest (struct node * dataStruct) {...}


bool isMember(int elem, struct node * dataStruct) {...}


Solution:  At its core, this is a fairly straight-forward problem.  We need to do three common operations in data structure:  insert, determine membership and determine the largest value.  


First, we need to figure out what data structure to use.  Let's go through a few common ones and talk about the trade-offs, efficiency and maintenance required for each data structure.


One common data structure we could use is an array.  This has the advantage of being fairly simple.  We could just add elements to the end of the array.  This would be an O(1) step.  Then, we could lookup any element by iterating through the array O(n) and could determine the max value in O(1) time.  Also, there is virtually no data structure overhead in this case.


Well, this is a possible solution.  If we will do lots of inserts and very few lookups and largest calls -- and we just want something simple; maybe this could work.


But, there are a few possible optimizations.  First, we could keep the list ordered.  This has the advantage of making lookup an O(log n) operation, which is much faster, and making the largest function an O(1) time operation as we simply return the last element.  The downside here is that insert takes much longer.  We may frequently have to shift values in the array down to make room, so insert could be as long as an O(n) function, which seems pretty long to build up the data structure.


So, let's look another structure.  How about a binary tree?  Well, a tree has insertion in O(log n), but would occasionally have to be rebalanced, usually an O(n) operation.  Lookup is O(log n), as is finding the max element (follow the right branch to the bottom).  Also, there is the overhead of the pointers to maintain the tree structure.  So, this could be a good solution if we were doing a good amount of lookups, insertions and finding the max value repeatedly.


Let's think about the ideal characteristics of this data structure.  It would have constant time insert and constant time lookup and constant time max value.


Well, a hashtable could do the first two.  We can create a hashtable that would allow us to insert and lookup in constant time, but getting the max value would normally be O(n).


But, does it have to be?  What if simply modified the data structure to be a hashtable as well as a value representing the max value. During the insertion step, we could do a comparison to always track the max value. This would then make returning the max value an O(1) step (in theory -- we could to this addition to any data structure, but a hashtable is still fastest for lookup and insertion).  There is some hashtable overhead, but this seems manageable given the efficiency of this structure.


So, the ideal data structure is a modified hashtable which tracks its max value during the insertion step.  This makes all of the functions we need to implement constant time functions.


Now to implement.  Let's start with insert:



bool insert (int elem, struct node * dataStruct) {
   
    /* Check to see if it's the biggest or the first*/
    if (dataStruct->max < elem || dataStruct->Max == UNINITIALIZED) 
        dataStruct->max = elem;


    /* Insert into the hashtable */
    return( hashInsert(dataStruct->hashtable, elem));
}



int largest (struct node * dataStruct) {
    /* check to make sure there is a value */
    if (dataStruct->max != UNINITIALIZED) 
        return dataStruct->max;
    else
        return ERROR;
}


bool isMember(int elem, struct node * dataStruct) {
    return (hashMember(dataStruct->hashtable, elem));
}


This is a pretty clean implementation, and assuming that you have hashtable functions, quite easy to implement.  Now, let's push the solution, as interviewers like.  What are some downsides of this?


Well, first, you need the hashtable functions!  Also, we didn't implement a delete function, and we should at least consider how to implement one.  It's a fairly straight forward hashtable delete, except when we're deleting the max element, which then requires a linear search to determine the max element.  So, if there were lots of deleting of the max element, this may not be a good choice.


/* Please let me know if there are bugs or alternate solutions */

Biggest and there

Problem:  Create a data structure and functions that can insert into the structure and then output the largest element and whether an element is a member

void insert (int elem, struct node * dataStruct) {...}


int largest (struct node * dataStruct) {...}


int isMember(int elem, struct node * dataStruct) {...}


Solution:  At its core, this is a fairly straight-forward problem.  We need to do three common operations in data structure:  insert, determine membership and determine the largest value.  


First, we need to figure out what data structure to use.  Let's go through a few common ones and talk about the trade-offs, efficiency and maintenance required for each data structure.


One common data structure we could use is an array.  This has the advantage of being fairly simple.  We could just add elements to the end of the array.  This would be an O(1) step.  Then, we could lookup any element by iterating through the array O(n) and could determine the max value in O(1) time.  Also, there is virtually no data structure overhead in this case.


Well, this is a possible solution.  If we will do lots of inserts and very few lookups and largest calls -- and we just want something simple; maybe this could work.


But, there are a few possible optimizations.  First, we could keep the list ordered.  This has the advantage of making lookup an O(log n) operation, which is much faster, and making the largest function an O(1) time operation as we simply return the last element.  The downside here is that insert takes much longer.  We may frequently have to shift values in the array down to make room, so insert could be as long as an O(n) function, which seems pretty long to build up the data structure.


So, let's look another structure.  How about a binary tree?  Well, a tree has insertion in O(log n), but would occasionally have to be rebalanced, usually an O(n) operation.  Lookup is O(log n), as is finding the max element (follow the right branch to the bottom).  Also, there is the overhead of the pointers to maintain the tree structure.  So, this could be a good solution if we were doing a good amount of lookups, insertions and finding the max value repeatedly.


Let's think about the ideal characteristics of this data structure.  It would have constant time insert and constant time lookup and constant time max value.


Well, a hashtable could do the first two.  We can create a hashtable that would allow us to insert and lookup in constant time, but getting the max value would normally be O(n).


But, does it have to be?  What if simply modified the data structure to be a hashtable as well as a value representing the max value. During the insertion step, we could do a comparison to always track the max value. This would then make returning the max value an O(1) step (in theory -- we could to this addition to any data structure, but a hashtable is still fastest for lookup and insertion).  There is some hashtable overhead, but this seems manageable given the efficiency of this structure.


So, the ideal data structure is a modified hashtable which tracks its max value during the insertion step.  This makes all of the functions we need to implement constant time functions.


Tomorrow's problem is to implement these.


/* Please let me know if you find any bugs or alternative solutions. Thank you, Noah */

Brainteaser: Turn a 6-sided dice into 5-sided dice

Problem:  Use a fair, six-sided die to play a game requiring a five-sided die.


Solution:  So, we're given one die as shown in the picture below.  

There is nothing terribly special about this die; it's the standard type that is used in casino board games, etc, and we can assume that it's a fair die for this problem (not shaved, weighted to bias a number, etc.).

Unfortunately, when we roll it, it give us numbers from 1-6, not 1-5 as the problem requires.  What algorithm can we use that can allow us to generate random numbers?

Let's start by thinking about fairly obvious algorithms to transfer the range of numbers.

Some algorithms jump out immediately as fairly obvious.  One thing we could do is half the numbers and round up.  So, 1 and 2 could be 1.  3 and 4 could be 2.  5 and 6 could be 3.  This would give us numbers from 1-3 in a fair way.  Similarly, we can generate numbers from 1-2 by mapping numbers to range.

Unfortunately, there is no obvious way that we can map numbers and get to 5.  

One other possibility is to roll multiple times.  For example, if we did two rolls, we would get a range between 2 and  12, though not an even range.  We could look at ways to divide the outputs of the dies (either the sum, or the sequence) and then slice it into fifths.  Perhaps we could even roll more than once until we found a distribution that could be sliced into fifths.  This could work, but the math very quickly gets tough and we end up with lots and lots of rolls.

Let's look again at the numbers that we can generate a range in so far:

2, 3 and 6.

Let's look at the 2, what does this mean:

Well, first, we generate this by assigning 1-3 to 1, and 4-6 to 2.

Seem familiar?  This is essentially a bit generator where we can generate a random bit each time where the range 1-3 produces the bit 0, and 4-6 the bit 1.

Now, how can we use a bit generator to generate a random number between 1-5?

Well, if you have a background in cryptography, this is easy.  If not, it's actually quite hard to see how this is helpful (though you can generate any range you want from this algorithm by making a big number and taking it % 5).  There is an easier way though.

So, let's go back to the die.  What else can we do when we roll it?  We looked at assigning ranges and adding, but what else can you do?  Do you need to use ever result of the die, or can you fairly ignore some?

How about ignoring a number?  Why not the number 6?

And there is the answer.  Roll the die like normal, and if you get a six, just re-roll.  There's your range, 1-5.

This is a good example of a class of brainteaser problems that appear to be complicated math, and in fact can be solved like that, but are actually quite simple.  When you get to seemingly really hard math, it's worth going back to your assumptions.  Your interviewer will generally comment that you're on the right path or not as well, so you can read the cluse.

/* Please let me know if you find alternative solutions or bugs.  Thanks, Noah */

Super Simple Reverse Sorting

Problem:  Implement Reverse Super Simple Sort -- a sorting algorithm which works by repeatedly finding the largest remaining element and swapping that with its order in the array.


void reverseSuperSimpleSort(int a[]) {
...
}


Solution:  Let's make sure that we understand this algorithm before we start implementing it.


So, assume we have a sample array with the numbers:


10 8 -5 20 9


To sort this array, we would start in the first position and find the biggest number, 20 in this case.  We would then swap 20 with the first number 10, to get:


20 8 -5 10 9


We then move up our iterator and find the largest of the remaining four numbers.  This is 10.  Then, we swap 10 and 8 and get


20 10 -5 8 9


We continue in this way until we get:


20 10 9 8 -5


This is a very simple sorting algorithm, but let's implement it.  We'll write a helper function first which can do the first part of this function -- find the index of the largest element in an array of a known size:


int indexOfLargest (int a[], int arraySize) {
    int indexLargest, maxSoFar, i;


    /*Check the error case */
    if (arraySize <= 0) return ERROR;


    /* initialize maxSoFar and its index to the first element */
    maxSoFar = a[0];
    indexLargest = 0;


    for (i = 1; i < arraySize; i++) {
        if (a[i] > maxSoFar) {
            maxSoFar = a[i];
            indexLargest = i;
        }
    }
    return indexLargest;
}
        





/*Now, we can write the function which does the sorting */
void reverseSuperSimpleSort(int a[]) {
    int i, swapIndex, temp;
    
    for (i = 0; i < a.size -1; i++) {
        swapIndex = indexOflargest(a + i * sizeof(int), a.size - i);
        temp = a[i];
        a[i] = a[i + swapIndex];
        a[i + swapIndex] = temp;
    }
}


That's it!


Let's check this on our original array.  Go through the numbers, and yup, it works.


So, this is a correct solution.  What is the run time? 


Well, the first function, indexOfLargest(), iterates through the entire array that it is given. So this function goes: n + (n-1) + (n-1)...


This is an O(n^2) function.  It's not a super fast sorting algorithm, but it's pretty simple and intuitive.  


/* Please let me know if you find any bugs or alternative solutions.  Thanks, Noah */

Pi. Yum.

Problem:  Write a function that calculates π.

double calculatePi(void) {
...
}

Solution:  The core of the problem is straight forward -- output a numerical value for π . And yes, you can't simply return a constant like many languages allow (that would be too easy, though it's worth mentioning this to the interviewer). Also, as π is irrational, we can only approximate it with a numerical value. 


Instead, the interviewer will explain a way to do this using a Gregory-Leibniz series.  This is a mathematical sum that calculates pi at infinity.  The proof behind this is quite complicated (and truthfully, I don't understand it, but it works).  This series is shown below which sums up to pi.

Also, this is a very slow converging function.  At k=150, we only have two decimal points of precision, but well, we can go much further than this!


So, coding this up should be fairly straight-forward.  If we choose a big k (say 20,000), we can get a nice value for π.


Let's also put the constraint on that we can't use a power.  This is also not too bad, as the (-1)^k only determines parity, so we can use an if statement letting us know that if k is even, we should pe positive, else negative.


Putting this all together, we can code it up:



double calculatePi(void) {


    int i;
    double pi = 0;


    for (i = 0; i < 20,000; i++){
        /* determine parity */
        if (i%2 == 0)  /* even and positive */
            pi += 4 / (2*i + 1);
        else
            pi -= 4 / (2*i +1);
    }
    return pi;
}


It's worth doing a few examples here (0, 1, 2) which yield (4/1) - (4/3) + (4/5) . . . 


Pretty neat.  Try this, and you'll notice that you can very nice value for pi.


Also, the run-time of this function is O(20,000), which is constant, and actually quite fast as the multiply by 2 is a very fast function.


There are some optimizations possible, but this is good.  


This was written on pi day (3/14).  So, happy pi day!


/* Please let me know if you find errors or alternate solutions.  Thank you.  Noah */

Brainteaser: The two paths

Problem:  A traveler comes to a fork in the road.  One path leads to the land of L, where people always lie, the other path to the land of T, where people always tell the truth.  At the fork is a man, but the traveler does not know if the man is from L or T.  We can ask him only one question.


What question should the traveler ask to ensure he gets to T?

Solution:  Let's draw a picture, as this often helps find the solution.


Pic 1 shows the problem, where we have encountered a man from L or T and we are trying to find the correct path to T.

If the man is from L, he will always lie.  If he is from T, he will always tell the truth.  We have to determine a question, which will allow us to know which way to go, irrespective of whether he is from L or T.


It's better not to just start randomly guessing (unless you immediately see the solution), so let's try to think structurally about what we are trying to get out of the question:


1.  The question must allow us to choose the correct path
2.  The answer must be definitive
3.  The answer must not depend on whether the person is from L or T.   It must be definitive irrespective of the person's home.


Most obvious questions fail this test, e.g.,:
- Which path takes me to T? -- fails because we do no know from the answer where to go
- Which path takes me to L? --If we could get this answer, we could do the opposite, but again, fails
--Are you from L or T?-- They both say T in this answer, and we don't know where to go?


Let's think about a two question combination that could work.  This is in fact trivial.
ny question that uniquely determines where the person is from, e.g.,:
What is 2+2? to determine if the person is from L or T, then
Which path goes to T?


Unfortunately, we don't have two questions (and we can't put both in one question).  One thought here is to try to ask a question that reveals both the person and answers something about the path, like:  What path is the best path?  But again, this doesn't work either.


At this point, let's look at the two question combination?  Is there anything that we don't need in there?  Well, one thing is that we actually figured out too much -- we don't actually need to know what city the man is from.  


So, with this insight, we simply need to know the right path, and we have essentially a true and a false.  We can use these to cancel each other out.


For example, we can ask the man, "What path would the other person say goes to T?"  Hence, each will give the path to F."  Then, we can take the opposite.


There is nothing terribly tricky about this problem.  The important thing is to be structured, not just start guessing and to try to glean insights of what is needed and not needed.  Some people find truth tables helpful in this problem, but I never have.


Also, there are other questions, but they typically involve negating either with someone from 'your town' or 'the other town', e.g., "What path leads to your town (negating with yourself)?"


/* Please let me know if you find bugs or alternate solutions.  Thx, Noah */

Why are manhole covers round?

Problem:  Why are manhole covers round?

Solution:  This is canonical with Microsoft, so it has to be asked.  Also, I was asked this at a Microsoft interview, so it's real!


There are lots of reasons that probably pop into your head, but let's not start by just randomly pushing out answers.  The place to start here is by examining, what is a manhole cover and what does it do?


Well, a manhole cover is a cover for an opening that provides a person access to an underground area (like a sewer or storm drain).  It is used so that people, objects, water and such do not fall in -- and so it can be removed when someone needs access.


So, a manhole cover would need to meet the requirements of:
1.  It is able to cover a manhole to prevent people/objects/water from entering
2.  It can be removed to provide access
3.  It is durable and strong as it may be outside and used aggressively (e.g., trucks may drive over it)
4.  It can be manufactured and made easily
5.  It should use the minimal amount of material needed to keep cost down
6.  It should take up the least space possible as it likely intrusive aesthetically and functionally (e.g., different surface than a road)


Well, let's now design the product that meets this. Clearly, to meet the first requirement, it must be  the same shape or bigger than the manhole.  And, since we want to keep meet requirements 4, 5, and 6, it makes no sense to make it any shape other than the cover itself.  So, manhole covers are round because they cover manholes which are round -- and this shape allows the cover to meet the requirements in the optimal manner.


There is a follow-up question here too -- why are most manholes round (thus creating their round covers).  Again, to answer this question, you would look at the requirements of a manhole:
1.  Allow a man to enter
2.  Cheap/easy to manufacture and maintain
3.  Of minimal required size as manhole creates constraints/weaknesses within their structure and are aesthetically ugly
4.  Durable/strong


Many shapes could meet some of the requirements, but round is often optimal as a round pipe is cheap/easy to manufacture and maximizes volume for a given amount of material.  Also, humans, with their arms in front as is often required to go down a latter -- fit well in a circular pipe.


So, manhole covers are round because it is the optimal shape to cover an optimally designed manhole.


The trick to this question is to realize that it is not a trick question, but a product design question at its core.  A wrong answer to this is starting to spout out true, but unorganized answers, (e.g., the manhole pipe is round,  it's a good shape, etc.).  Questions like this are designed primarily to see if a candidate is organized, hard to fluster and able to think in a structured manner.  


As an aside, not all manhole covers are round -- as sometimes the manhole cover is not round, usually due to constraints on the manhole.  Also, the round shape of a manhole contrasts it with the triangular shape of electrical covers, allowing people to know that a triangle means electricity, even if color or words have faded.


/* Please let me know if you find any bugs or alternative solutions.  Thank you, Noah */