How do you calculate the height of a tree?
Answer first, then Google.
software interview question
-
Peijen
- Minion to the Exalted Pooh-Bah
- Posts: 2790
- Joined: Fri Jul 18, 2003 2:28 pm
- Location: Irvine, CA
Re: software interview question
From where?Dwindlehop wrote:How do you calculate the height of a tree?
Answer first, then Google.
-
quantus
- Tenth Dan Procrastinator
- Posts: 4891
- Joined: Fri Jul 18, 2003 3:09 am
- Location: San Jose, CA
heh, then I track node depth for each node and update max_depth on inserts when required.
That's an ok solution if you need to know the depth all the time. Really, you need to give a profile of the types of operations that will be performed on the tree so that the right kind of tree/data structure is used to optimize perf. If this is just gonna be used on small scale problems, then it doesn't really matter what you do as long as it works. If you're gonna have a billion entries, then you need to put real thought into this. The Google interview was interesting because they gave a fairly concrete real world'ish problem describing the amount of entries, how much memory you have, etc...
That's an ok solution if you need to know the depth all the time. Really, you need to give a profile of the types of operations that will be performed on the tree so that the right kind of tree/data structure is used to optimize perf. If this is just gonna be used on small scale problems, then it doesn't really matter what you do as long as it works. If you're gonna have a billion entries, then you need to put real thought into this. The Google interview was interesting because they gave a fairly concrete real world'ish problem describing the amount of entries, how much memory you have, etc...
I thought the same thing as Peijen.
I need a protractor, straw, tape, fishing line, a weight, a calculator, and a ruler or measuring tape. With a calculus textbook to refresh my memory and a lot of time, I could do it without the calculator, using series to compute the trig functions.
If I had a saw, then I can skip everything except the ruler. That raises the question of whether you want the height of a tree at the time you ask or at the time I answer? With a flamethrower or explosives, I can hard-code the answer as zero with some side effects.
Alternatively a monkey and string would work, if the monkey could be convinced to climb straight up. A rocket or other projectile could be substituted for the monkey if the branches are spare enough and close enough to the top.
A laser rangefinder plus calculator would work.
You could have a team of cheerleaders of known heights form a pyramid. Unfortunately, that algorithm doesn't scale very well.
Do the roots count, or only the portion above ground?
Coincidentally, almost this exact thing came up at work recently. I had a quad-tree and needed to know the number of things stored in or below a node. So, I just put in the recursive solution to traverse each node and keep a count. Turns out that's pretty expensive, at least relative to the other parts of that code path. So, maintaining the count in each node on inserts and removes is likely to be the better solution (I haven't timed the change yet) in that one case.
So, with that recent experience, I'd say for a general tree, I'd probably consider maintaining the height in each node on updates and removes. It Like Joe says, though, it would depend on the relative frequency and cost of the operations and on how much memory you wanted to throw at the problem.
But, IIRC, a red-black tree guarantees that the maximum and minimum depth are bounded as something like log2(n)+/-1? Been a while. Maybe the number of black nodes to any leaf is constant? Anyway you could just keep a count of the inserts - removes and get an answer that is within one of the correct number. That's if you are able to use a red-black tree. There are other self-balancing trees that probably make similar guarantees.
Or, drawing from my side-effect-based solution to the plant tree version, you could make a one-tree and know that the height = N.
Ok, now off to google.
I need a protractor, straw, tape, fishing line, a weight, a calculator, and a ruler or measuring tape. With a calculus textbook to refresh my memory and a lot of time, I could do it without the calculator, using series to compute the trig functions.
If I had a saw, then I can skip everything except the ruler. That raises the question of whether you want the height of a tree at the time you ask or at the time I answer? With a flamethrower or explosives, I can hard-code the answer as zero with some side effects.
Alternatively a monkey and string would work, if the monkey could be convinced to climb straight up. A rocket or other projectile could be substituted for the monkey if the branches are spare enough and close enough to the top.
A laser rangefinder plus calculator would work.
You could have a team of cheerleaders of known heights form a pyramid. Unfortunately, that algorithm doesn't scale very well.
Do the roots count, or only the portion above ground?
Coincidentally, almost this exact thing came up at work recently. I had a quad-tree and needed to know the number of things stored in or below a node. So, I just put in the recursive solution to traverse each node and keep a count. Turns out that's pretty expensive, at least relative to the other parts of that code path. So, maintaining the count in each node on inserts and removes is likely to be the better solution (I haven't timed the change yet) in that one case.
So, with that recent experience, I'd say for a general tree, I'd probably consider maintaining the height in each node on updates and removes. It Like Joe says, though, it would depend on the relative frequency and cost of the operations and on how much memory you wanted to throw at the problem.
But, IIRC, a red-black tree guarantees that the maximum and minimum depth are bounded as something like log2(n)+/-1? Been a while. Maybe the number of black nodes to any leaf is constant? Anyway you could just keep a count of the inserts - removes and get an answer that is within one of the correct number. That's if you are able to use a red-black tree. There are other self-balancing trees that probably make similar guarantees.
Or, drawing from my side-effect-based solution to the plant tree version, you could make a one-tree and know that the height = N.
Ok, now off to google.
-
quantus
- Tenth Dan Procrastinator
- Posts: 4891
- Joined: Fri Jul 18, 2003 3:09 am
- Location: San Jose, CA
Ok, how do you do it using the fewest and cheapest tools available? We want a method that will provide an answer that is accurate to within 1%. Roots don't count. Height is defined from ground level to the very top at the time of the measurement. It costs $60/hr/person once the measurement method is started. Your time taken to determine a method to acquire the answer is free. I think this will make solutions such as atomizing the tree and saying 0 cost a lot and be suboptimal even though it is very fast and accurate.George wrote:I thought the same thing as Peijen.
I need a protractor, straw, tape, fishing line, a weight, a calculator, and a ruler or measuring tape. With a calculus textbook to refresh my memory and a lot of time, I could do it without the calculator, using series to compute the trig functions.
If I had a saw, then I can skip everything except the ruler. That raises the question of whether you want the height of a tree at the time you ask or at the time I answer? With a flamethrower or explosives, I can hard-code the answer as zero with some side effects.
Alternatively a monkey and string would work, if the monkey could be convinced to climb straight up. A rocket or other projectile could be substituted for the monkey if the branches are spare enough and close enough to the top.
A laser rangefinder plus calculator would work.
You could have a team of cheerleaders of known heights form a pyramid. Unfortunately, that algorithm doesn't scale very well.
Do the roots count, or only the portion above ground?
Oops, in the course of googling for the programming problem, I came across several solutions for the plant problem. So I'd be cheating. Let's see if anyone else can come up with better or more creative solutions.
Is there a specific page you were think about with your no googling requirement, because I couldn't find anything that looked like it was directly addressing the programming problem.
Is there a specific page you were think about with your no googling requirement, because I couldn't find anything that looked like it was directly addressing the programming problem.