Write OR and AND from NAND.

Problem:  You are told that you only have one logical operator, !&& which is NAND.  Write or()and and().


bool or(bool a, bool b) {...}


bool and(bool a, bool b) {...}

Solution:
Let's start by making sure that we understand NAND well.  NAND takes the AND function and then negates it, returning the opposite of the standard AND function.  It's worth drawing a table (called a truth table) which shows the output of NAND


The truth table below shows NAND and its values.  (As you can see, it's the opposite of an AND truth table)
Table 1:  NAND truth table

INPUT		OUTPUT
A	B	A NAND B
0	0	1
0	1	1
1	0	1
1	1	0

Let's start now by comparing this with the OR function.  Or is true when either or both of the values are true.  This gives us the truth table of:
Table 2:  OR truth table

INPUT		OUTPUT
A	B	A OR B
0	0	0
0	1	1
1	0	1
1	1	1

Now, let's think about how we could write the or() function using only the !&& operator.  Well let's think about some ideas here.  If we simply NAND the input together, we will get the outputs of table 1.  This is close and works for the middle two case, but we need to flip the two edges to get the correct output.  We could try NAND-ing the values together again, but this doesn't get us anywhere. 


This is a good time to take a step back and start over.  Clearly, our 'just get going approach' isn't going anywhere.


Now, let's look at what happens if we NAND a value with itself.  Well, if the value is 1, 1 NAND 1 is 0.  And, if the value is 0, 0 NAND 0 is 1.  So, we can essentially, flip or negate a value.


Now, look at the truth tables again.  See if this can be useful.


In fact, it can be useful, as if we flight each input, and then NAND the output, we will only return false if both inputs are originally 0, which is what we want to create a proper or.


Now, coded up, this is:


Instead, let's go back to our original case and maybe we don't want to NAND the numbers together immediately.  Let's look at the truth table 2 again, and we can see that so long as there is at least one 1, we want to output 1.  In the truth table in Table 1, we only get a 0 when we have two 1s.  


This is a critical insight, and we can apply it if we consider what happens when we NAND a value with 1 (or true).  


bool or(bool a, bool b) {
    return ((a !&& a) !&& (b !&& b));
}


Now, we can probably already see how to make the AND gate if we were paying attention.  We saw that we can flip (or negate a value) by NANDING with itself, as we did with both a and b to make or(). Hence, NAND is simply Not-And, so we can apply the not or negate operator again by NANDING the outpub with itself.  


As code, this is:

bool or(bool a, bool b) {
    return ((a! && b) !&& (a !&& b));
}



It's worth doing the truth table for both or and and to convince yourself, and your interviewer, that these are correct in all four cases of a and b.


This is a good example of where it's useful to try examples and gain insights (e.g., NANDing a and b, NAND-ing a value with itself to see that it flips) and also be willing to go back a step if you're not making progress.  Also, drawing pictures and truth tables is very helpful.


It's worth nothing that this isn't as contrived a problem as it seems.  In digital logic, NAND gates (and NOR gates) are known as universal gates because you can make all other logical operations (OR, AND, NOT, XOR, NAND, AND) from any one of these.  So, often, these operations are quite useful.  If you would like further practice, try doing the same problem but with !|| as your only operator instead.


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

What goes with if?

Problem:  Write what goes inside of the if statement to produce, "Hello World.\n"

void printHelloWorld () {
   
    if(...) {
        printf("Hello ");
    } else {
        printf("World.\n");
    }
}


Solution:  Let's start by trying some of the obvious conditions that could go inside the if statement.  The most obvious are true and false.


Clearly, neither of these works.  If we use true, the output is only "Hello".  And, if we do false, the output is only "World.\n".  


So this is tricky, which it would almost have to be to be an interview question.  


One thing that we know about an if statement is that 0 evaluates to false, and everything else to true.  Can we use this fact?  Well, we could put in something that could be contingent, but ultimately, the if statement would evaluate to true of false, so this doesn't help us to have both the clause after if and the clause after else print.


But, that's not to say that it won't help us.  We can have something print in the if statement.  For example, we can have a function in the if statement, which would both print and return a boolean value.  If we do this, we can then print part of the if/else statement.  


And, since the evaluation part comes first, we would want to print the first part of the "Hello World\n." statement and then trigger the second half (We can't do it backwards by printing World\n. last).  


And, we'll need a function that always returns false, but that is easy too.


Now, we can code up just such a function as:


bool printHelloAndReturnFalse () {


    printf("Hello ");
    return (false);
}


Now, let's test our function and make sure if works.   When we call PrintHelloWorld(), the function will call what we wrote above and print, "Hello ".  The false will trigger the else clause and print, "World.\n".  This is exactly what we want.


Now, this is a good solution, but try not to stop here.  Other than a programming exercise, can you think of a time when you may have to do something like this?  (Even if you're not asked this, it's good to think about it.)


Well, we may need an evaluator function for certain packages.  And, we may want the evaluator function to do more than just evaluate (e.g., print to a log, etc.).  In this case, we would want to make sure that an evaluator did more than just return a boolean value, and it's a case of where we would write such a function.


This is a good example of a problem where it's important to try (and quickly realize that they don't work) obvious answers, then think about the challenges to the question and how it can be overcome.  Write a solution (pretty easy) -- and then stretch your answer to show your interviewer that you're always looking for an even better solution.


/*Please let me know if there are bugs or if you find a better solution.  Thank you.  Noah */

3 integers that sum to zero

Problem:  Given an unsorted array of integers, return true if there is a 3-element subset, of distinct elements, that sums to zero


bool threeSumToZero(int a[]){
...
}


Soution:  Well, there seems to be an obvious answer here.  We can iterate through the array and for each element, we iterate and then iterate again to check all three element combinations.  And, so long as we're careful and make sure that we use distinct elements, we can get this right.  


The code for this is:



bool threeSumToZero(int a[]){


    int i, j, k;


    for(i=0; i < a.length, i++) {
        for (j=0; j < a.length; j++) {
            for (k=0; k < a.length; k++) {
                //check for distinct elements
                if (i !=j && i != k && j!= k) {
                    if ((a[i] + a[j] + a[k]) == 0 ) 
                        return (true);
                }
            }
        }
    }
    return (false); 
}


Well, this works beautifully and is a very simple solution.  There are a few optimizations possible (like starting j at 1 and k at 2) and combining the two if statements, but basically this is pretty sound.  


What is the algorithmic run time for this?  


Well, since for each element, we check each element and then check each element for that, we  have an O(n) with another O(n) for each n and then another O(n) for each of those.  This results in a run time of O(n^3).


We could stop here, but O(n^3) is pretty slow.  So, let's think about a potential optimization. You may see an optimization, but if you don't, let's try an example:

Pic 1 shows an array that will sum to zero.  How do we know this.  Well, we can see that -3 + 2 + 1 = 0.


Now, how did we inuit this?  


What you probably did, was check the sums, and then see if there was a value which was opposite that (e.g., negative if the sum was positive, and positive if it was negative).  You didn't have to actually check the sum of each element, only the membership of the opposite of the sum.


This hints at the solution to make it faster.  Since we don't have to check all sums of triplets; we can just check the sum of every pair, and then see if there is an opposite.  And, since look up can be a constant time operation after we build a data structure with O(n) time, we can:


1.  Build a constant time lookup, like a hashtable, an O(n) operation
2.  Determine the sum of all pairs,  an O(n^2) operation, and
3.  Check if we have the opposite of the sum in a hash table, an O(1) operation


This will give us an O(n^2) algorithm, but at the tradeoff of needing a data structure.


The code for this is:

bool threeSumToZero(int a[]){


    int i, j;
    //assume we have hashtable functions:
    hash *h;
    
    h = buildHashTable(a);


    for(i=0; i < a.length, i++) {
        for (j=0; j < a.length; j++) {
            //check for distinct elements
            if (i !=j) {
                if (lookup(h, -(a[i] + a[j]))) 
                    return (true);
            }
        }
    }
    //you could free the hashtable here if needed
    return (false); 
}



Beautiful.  This is an example of an obvious solution being nice, but inefficient.  It's good to always get to a working solution fast.  Then, by doing an example and intuiting what we were doing, it's possible to build a much more efficient algorithm.  And, the coding isn't too difficult; it's mostly the algorithm here.


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

Let's Make a Deal

Problem:  (Thank you to Mr. Schwartz in 9th grade for this).  In the classic TV game show, "Let's Make a Deal," you win a prize if you can choose which of three doors the big prize is behind.  After choosing the door, the host opens one of the other doors which has a booby prize (like a bag of sand).  You are then asked whether you want to switch to the one remaining closed door, or stick with your original choice.  Should you switch?


Solution:  
Let's start with a drawing of the situation.  Pic 1 shows the basics where there are three closed doors, two with booby prizes and one with the big prize behind it.  We are asked to choose any door first.  Let's say we choose door 2.  

Then, the host opens another door, let's say door 1, revealing a booby prize (e.g., a bag of sand). We are then asked if we want to switch -- from door 2 to door 3.  We know that one of the remaining closed doors has the big prize, and one another booby prize  This situation is shown in pic 2.

Well, should we switch?


The obvious answer is that it just doesn't matter.  We know that there is a prize behind one of two doors, and we have a 50% shot.  So, switch or don't switch; we should be indifferent and we will have a 50% chance of winning regardless of strategy.


This is a fairly straight-forward answer and is tempting.  However, before we accept it, let's think about the situation a little more and if we're using all available information.


Certainly, if we were presented with two doors and told to choose 1, we could make an overwhelming case for the strategy not mattering -- similar to the strategy not mattering if you call heads or tails on a fair coin toss.


However, we were given lots more information here with a longer set up, one choice, some information revealed, and then asked to make another choice.


Unless your an information/logic expert, a good strategy is to try some examples to see what happens when we choose different doors (with big prize, without) and what happens when we switch/don't switch to see if it helps us figure out the optimal strategy:


Strategy 1:  Never switch
  A- Choose big prize door out of three (chance 1/3)
       - Don't switch when given choice
       - Win
       - Chance:  1/3


  B-Choose booby prize door (chance 2/3)
       - Don't switch when given choice
       - Lose
       - Chance 2/3


Strategy 2:  Always switch
  A-Choose big prize door out of three (chance 1/3)
       - Switch when given choice
       - Lose
       - Chance 1/3


  B-Choose booby prize door out of three (chance 2/3)
       - Switch when given choice
       - Win
       - Chance 2/3


See if these examples help you figure out what to do.


To win:
    - If we never switch, we have a 1/3 chance of winning; we need to choose the correct door initially
    - If we always switch, we have a 2/3 chance of winning; we need to choose the incorrect door initially


Hence, we should always switch to improve our odds of winning.


This answer is correct, but there's something that can be unsatisfying about it, because intuitively, staring at two doors -- which is our situation, it still feels like we should be able to choose either and have a 50% chance.  


So, why isn't this the case?


Well, we were given significant information by the door that was opened.  Since the door had to be either: 1) the other booby prize (if we chose the first), or 2) could be either other door, we are given information because it cannot simply be a random door that was opened.  This information can be used to improve our odds by switching.


If you're interested there are lots of simulations run showing the benefits of switching vs. not switching. 


This is a good example of the first, intuitive answer of 50% not being correct, which is usually the case in brainteasers.  When stumped, try doing examples, and when possible, the exhaustive answer set, as that can help bring insights into the correct solution.


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

Data structures and DAWGS

Problem:  (Thank you to Stanford’s CS 106X class).  Discuss a data structure, under 64k bytes, which can in near constant time determine whether a string is a valid word in the English language, or is invalid.

Solution:

Let’s start by asking a few more assumptions about this problem.  First, do we have to build the data structure?  No – we just need to figure out what sort of data structure would be able to do this.

Well, let’s start out with one of the parts of the questions – ‘near constant time.’  Well, there are very few common data structures which can achieve this.  Some data structures that fail immediately are binary search trees (log n), sorted arrays (log n), linked lists (n or log n).

One common data structure that is nearly constant time is a hash table.  And, at first this seems like a great data structure.  We could hash based upon the string, end up in a hash bucket, and so long as we keep the hash buckets relatively small, we could get a near constant time data structure.  Well, this is true.  This would work as being nearly constant time.   Pic 1 shows such a hash table.

Now, let’s see if this would work on the space constraint.  Let’s make an assumption that there are 50k words in English (especially with variations like sing, sang, sung, singing, singer, sings, etc.).  This seems about right.  Maybe it’s higher, but let’s see if we can create a hash table with a dataset of this size in the space that we have.

Let’s also assume that we use ascii and the average word is 5 letters (seems low, but let’s go with it).  So, the average word is 6 bytes long, assuming that it’s null terminated.  Storing all of these words, not include the over head of the hash table, we would have a data structure of 6 * 50k = 300k.  This is much larger than we want, and probably it would be larger as our estimate of words is probably low.  With the overhead of the hash table, we would have an even bigger amount.

So, a hash table can’t work as its data store will be too large.

So, this creates a problem that any data structure would have – we cannot uniquely store each word and meet the space requirements.

Well, where to go from here?

Well, let’s think about what we know about the English language to look for optimizations.  We know that the words are not random character strings, but words with many common parts.  

Again, a good example is:  sing, sang, sung, sings, singer, singing.  Here, we have six distinct words.  In a hash table, we would have six distinct entries and we know that this approach will not work.

However, looking at the words, we can see that they have both common prefix and common suffix.  Four of the words have the common prefix ‘sing’ and four of them end with ‘ng’ and 3 with ‘ing.’

Let’s think about what we could do here.  Well, this screams for a tree approach where individual characters are nodes.  We previously rejected a tree because of the time required, but let’s go with this for now.  We can make ach node only branches when it has a new letter. 

By doing this, we have a tree with s as the root and then the structure as shown in pic 2.  

We could put a bit on each bit indicating whether stopping at the node is a valid word or not.

This tree would be fairly quick to search to see if a word were in it, but the structure isn’t quite good enough for searching.  For example, we would have to search all of the lower nodes to see if a descendant node with the character we’re looking for.

One quick optimization is to create nodes with all 26 characters as pointers and a ‘true’ bit.  We can then easily go down the tree and see if we have a valid word or not.  And, this is almost constant time as we never have to look up more elements the number of characters in the word.  This type of structure is shown in pic 3, and is called a Directed Acyclical Word Graph (DAWG).   

If we think of the size of this structure, it probably reduces the size of the words by a factor of 10 given all of the common prefixes in words (probably  a greater reduction as over time, most prefixes are pretty common, but seems pretty close).  This will get us close to the size we’re looking for, but let’s think about how we can do better.

So far, we have done a good job constructing a data structure that optimizes around prefixes, but if we look at the example of the words like, ‘sing’, we see that we also have lots of common suffixes.  As simple optimizations, we could imagine uniting common prefixes. For example, many words in English end in ‘ing’; we could have all of these words point to a common ‘ing’ ending.

This would be a further optimization, but would obviously require balancing and make the function which inserts words longer. 

This would give us a much optimized and fast data structure.

This is a good example where it’s good to try the first thought of what could work (e.g., a hash table), but then move on and look at optimizations to get to the correct answer.

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

Elevator Algorithm

Problem:   Describe an algorithm that you could use if programming an elevator. 

Solution:  No custom elevator knowledge is assumed here.  Let’s start by drawing a picture to allow us to make sure that we understand the problem.

Pic 1 is a simple picture of an elevator and some floors it can stop on.

Let’s start by talking about the characteristics of the problem, which we will have to optimize:

•        There are a certain number of floors on which the elevator can stop
•        It takes a certain amount of time for the elevator doors to open and close
•        It takes time for the elevator to accelerate, stop and has a max speed
•        People can signal the elevator and indicate whether they are going up or down
•        The elevator has a maximum capacity

Now, lets’ talk about some of the basic elements of an algorithm for an elevator:

•        Elevators should minimize waiting times for people who are signaling the elevator
•        Once an elevator starts going up and someone indicates a higher floor on it, the evator should not go down
•        Same as 2, but for down
•        Elevators should minimize transit times for people in the elevator

Well, already, this is looking much more complicated.  We have multiple characteristics and rules.  Let’s now put this together, and start talking about what we know about elevators:

•       When someone is in the elevator, it is going up or down. 
•       It will go up and stop at every floor where either: 1) someone in the elevator has selected, or 2) someone outside the elevator has pressed the up button
•       It will go down and stop at every floor where: 1) someone in the elevator has selected, or 2) someone outside the elevator has pressed the button
•      It will always stop at the bottom floor when going down if someone has pressed the up button
•      It will always stop at the top floor when going up if someone has pressed the down button

These are the basics.  Now, let’s try an example.  Assume that someone walks into a building and presses the up button on the bottom floor – what happens?

Well, assuming no one is in the elevator, it will come down from the floor it is on.  So, the person will have to wait while the elevator comes down. 

This example highlights another issue.  Where does the elevator wait when it is not in use?

One first thought would be to wait in the middle.  This would seem to optimize between people going up and people going down.  We can probably assume too that there are relatively few trips between floors – though even this may not be true if for example a company has offices on more than one floor.

But, let’s keep it simple.  But, think about someone coming in to go up.  When do people do this?  And, when do people go down primarily?

This would depend a little on the type of building.  In an office building, people will often come in in the morning and leave in the evening.  In an apartment building, it would be the opposite. 

One optimization could be to move the elevator closer to where people are expected at different times of day.  This could reduce wait times dramatically.

We have most of what we need to write out an algorithm.  Let’s do it now:

First, let’s bring in all the rules that are expected:

1    When someone is in the elevator, it is going up or down. 

a.       It will go up and stop at every floor where either: 1) someone in the elevator has selected, or 2) someone outside the elevator has pressed the up button

b.      It will go down and stop at every floor where: 1) someone in the elevator has selected, or 2) someone outside the elevator has pressed the button

2    It will always stop at the bottom floor when going down if someone has pressed the up button

3    It will always stop at the top floor when going up if someone has pressed the down button

And, let’s add, assuming we have an office building:

•      The elevator will wait at the bottom floor when not in use between 7am-10am. 
•      The elevator will wait at the top floor when not in use between 3pm – 7pm.
•      At other times, the elevator will wait in the middle floor

Well, we have a good algorithm here. 

Most important in this problem, is to 1) not ignore the obvious such as the rules of how an elevator works and what it is trying to optimize, and 2) always seek to ‘stretch’ your answer.  In this case, we stretched with an optimization problem.

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

Implement division without using the division or multiplication operation

Problem: Implement division without using the division or multiplication operation.  Round to the nearest whole number

int divide(int numerator, int denominator) {

...

}

Solution:  Let’s start with an example.  In this case,

Numerator= 108

Denominator = 10

We know that the answer to this is 10.8, which rounds up to 11.  But, let’s think about how we got that.  We know that 10 can be multiplied by 10 to get 100.  This is equivalent to adding 10, ten times.

Similarly, we can subtract 10, ten times from 100 to get zero. 

This starts to intuit an algorithm, where we see how many times we can subtract and that is most of the answer. 

But, how do we deal with what is left over?  In this case it is 8.  We’re supposed to round up or down, so we can compare 8 to 10.  We’re not allowed to divide, but we are allowed to add an compare.  So, we can double 8 by adding it to itself.  If the result is greater than 10, we round up.

Putting this into code, we get:

    int answer, curValue, i;

    for (i=0, answer=0, curValue=numerator; i < numerator; i+=denominator) {

        curValue -= denominator;
        answer++;

    }

    // round up if necessary
    if ( curValue + curvalue <= denominator) answer++;

    return answer;

}

This is almost right, but it has at least problem.   Can you see it?  If not, try a negative number example.

What do we do if we get a negative number?  In this case, our algorithm fails as one number will go up or down indefinitely. 

To solve this, we need to use some if statements to make sure that we are always iterating in the right direction.  We also can’t divide by zero and need to check that case too.   We can solve this with three if statements a shown:

int divide(int numerator, int denominator) {

    int answer, curValue, i;

    //check for 0 denominator
    if (denominator == 0) return ERROR_VALUE;

    for (i=0, answer=0, curValue=numerator; (numerator > 0 && i < numerator) || (numerator < 0 && i > numerator);) {

        //if both numerator and denominator are positive or negative:
        if (numberator >= 0 && denominator > 0) {
            curValue -= denominator;
            answer++;
            i+=denominator;
        } else {
            //one is negative
            curValue+=denominator;
            answer--;
            i-= denominator;
        }

    }

    // round up if needed
    if (curValue + curvalue <= denominator) answer++;

    return answer;

}

This is an example of a problem which starts out simple, and gets much more complicated.  It’s good to do some examples now with varying positive and negative numerators and where you round down and up.  There’s actually still a bug in this solution, but I’ll leave it to you to discover it.

/*Please let me know if you know alternate solutions or find bugs other than the one left in there.  Thank you.  Noah */

Number of Drops (Updated/Correct)

This is the updated/correct solution.  Thank you to several community members for pointing this out.


Problem:  You are given two identical cell phones and told to test them to see what is the highest floor of a hundred story building that they can be dropped from before they break.  What is the strategy for the minimum number of drops required and what is that number?


Solution:
Let's start by asking some clarifying questions to ensure that we don't go off down the wrong path.  - First, are all the floors the same height?  Yes
- Do we have to account for that the cell phone may land differently, in a different spot with a different hardness, or in different atmospheric conditions (like wind)?  No.  Assume that the only variable that will influence whether a cell phone breaks or not is the floor it is dropped from
- Can we retest a broken cell phone for any additional information?  No, once a cell phone is broken it can no longer be used usefully


These are good questions to ask.  They show your interviewer that you're thoughtful, do not necessarily assume conditions not stated and do not want to try to solve a problem without fully understanding it.


Now that we have a better view of the problem, let's try to think of a potential solution to this problem.


Well, we could start at the bottom floor and go up one floor and drop the phone. When the phone broke, we would know that we were at the top.  In the worst case, this would take up to 100 floors and 100 drops.  O(n).


It's good to get a working solution, but this is clearly non-ideal.  For starters, we didn't use our second phone.  


A simple optimization that we could imagine when starting this is to skip by 2s:  test on floor 2, 4, 6, 8,...


If the phone breaks, we can then test the phone on one floor lower.  Then, the answer is one lower, else if it survives, the answer is that floor.


This results in a max number of drops of potentially 51 if the top floor is the answer.  Still O(n), but much better.  


At this point, think more about the optimization.  We skipped floors, and then went back and tested some we had skipped once we found a range of a not-broken floor and a broken floor.


Previously, we only skipped one floor, but we could skip more.  Let's try for an example, skipping 3 floors:  We start by testing on floors:  3, 6, 9, 12...


Well, the worst case here is floor 90, which would be 34 drops potentially.  So, it seems that skipping more floors, then going back and testing one-by-one from the last good floor is a good strategy.


It appears that skipping more floors reduces the number of drops, so let's try skipping 50 floors.  Here, the worst case is now 51 floors (floor 99).  So, clearly, skipping too many is not always good.


So, there seems to be an optimal number of floors to skip.  If you work from here using math or simply trying bigger and smaller numbers, you'll get to an answer of about 10 (11 and 9 yield similar answers).


This gives a worst case of 19, which would be if the 99th floor were the fail floor.  


It's tempting to stop here, and frankly, I have egg on my face for previously publishing an answer where I did.


There is a better solution.


Let's try to figure it out by doing some examples where we establish the min/max range by skipping 10 floors each time.  Try 9.  


We would test:
10:  fail
1: pass
2: pass
...
8: pass
9: fail.


This would be a total of 10 tests.


Essentially, if we skip 10 floors each time, the worst case is always the number ending in 9, and the worst case floors take one more test each time:


9:  10 tests
19:  11 tests
29:  12 tests
...
99:  19 tests


Well, think about one of the assumptions that we had earlier -- always skip the same number of floors to establish a min/max range.  There is no proof that this is the right solution.  In fact, it looks like by doing this, we always have essentially one more test as we go higher.  However, what if we used the fact that we essentially have 'tests' we can do early in a bigger range as we have not used them up to establish the range.  In fact, on each subsequent upping of the potential min/max range, we lose 1 test, to establish the range.


Now, what if we accepted a larger min/max initially and then narrowed it as we went up.  This would get around the problem of always having to get worse as we go higher.  This hints at an optimization to our initial strategy.


As an example, let's try skipping 17 floors and then reducing the range by one each time (one better than our current best result).  Note we should try 17, not 18, so that we are never worst than 18.  This way, the highest range of the min/max will always yield 18, but that is better than our current best result


We could establish min/max ranges of:
1...17
18...33
34..48
....


Well, this works and we can get better than 19.


Now, keep trying smaller min/max ranges to start out with initially.  If you go too small, you can't get to the top.


If you keep trying, or use math, you'll eventually narrow in on skipping 13 floors initially, which gives you a worst case of 14.  This is quite a bit better than our initial case of 19.


/* Thank you to the community for help getting this right.  Apologies for my previous incorrect answer.  Noah */

Largest value in an unordered, unablanced tree

Problem:  Write a function with determines the largest value in unordered, unbalanced binary tree.

int largestValue(struct node * tree) {

...

}  

Solution: 

It’s worth mentioning that if the tree were ordered, this would be trivial – going to the far right.  However, we don’t have it so easy.  So, let’s start by drawing out an example to make sure that we understand the problem.  Pic 1 is a good example of a binary tree which is unbalanced binary tree.

Looking at pic 1, see if you can find a way to intuit the largest element.  Nothing really helps here as the longest element is simply the element which is bigger than all ones.

With the only insight into finding the biggest value that we need to find the element larger than all others, let’s look at how we could do this.

First, it’s tempting to do something that we know how to do.  We could do a breadth first (or depth first) search – put all the elements in an array and then very quickly iterate through the array looking for the largest element.

This solution would work, and it would be O(n), as each element is inspected once, but it’s inelegant as it requires building a new data  structure.  So, let’s only come back to this if we need to.

Let’s look at the tree and look at a sub tree with only two nodes as in pic 2.  Essentially, we would return the largest of the value of the node, its left hand descendant and the right hand descendant.  We can use this build a recursive case (as trees usually do) and return the largest of: 1) the current value, 2) the largest value of the left hand sub-tree, or 3) the largest value of the right hand subtree.

The base case here is when we have a node with no descendants, as a null node has no value.

Using these insights, we can get the code as:

int largestValue(struct node * tree) {

    int rh, lh;
    lh = rh = MAX_NEGATIVE;

    // Check for null in case our node is empty
    if (tree == null) return MAX_NEGATIVE;  // or error value

    //Recursive base case -- no descendant nodes
    if (tree->left == null && tree->right == null)
        return tree->value;

    //else, return the largest of the lh, rh or value
    if (tree->left != null)
        lh = largestValue(tree->left);

    if (tree->right !=null)
        rh = largestValue(tree->right);

  
    //return rh if it's the biggest
    if (rh >= lh && rh >= tree->value)
        return rh;

    //return lh if it's the biggest
    if (lh >= rh && lh >= tree->value)
        return lh;

    //else, the current node's value is the biggest
    return tree->value;
}

Let’s now test this function on our sample tree in pic 1.  Yup, it works.  It's worth going through the exercise, but you can see that it returns 30, as desired.

Algorithmically, this function is O(n) as we examine each node once, with recursive overhead.  O(n) is probably the fastest that we can get as we need to look at each code.  There are certainly optimizations that we could do so we wouldn’t have to use MAX_NEGATIVE, which would be more if statements to make sure that we don’t de-reference a null pointer, but this doesn’t seem hard and we can certainly do the work as we have the structure of the algorithm.

This is a pretty good tree problem and illustrates why it’s always good to draw a picture, think of a simple sub-tree and try to intuit a problem, especially with trees.

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