Google Interview Question
Software Engineer / DevelopersCountry: India
Here's an easy solution that lazily enumerates the amount in each cup in level order:
def cascade(total, limit):
row = [float(total)]
while 1:
new_row = (len(row) + 1) * [0.0]
for i, amount in enumerate(row):
excess = max(0, amount - limit)
yield amount - excess
if excess:
overflow = 0.5 * excess
new_row[i] += overflow
new_row[i+1] += overflow
row = new_row
With this algorithm, finding the amount in the n first cups takes O(n) time and O(sqrt(n)) space. It also generalizes easily in various directions. One generalization is to arbitrary cascades represented as directed acyclic graphs. Another generalization is allowing arbitrary limits per cup rather than a fixed limit.
This is effectively a breadth-first traversal. The related question that googlybhai linked to contains a linear-time and log-space solution which is essentially the same algorithm using instead a depth-first traversal. However, that assumes that the cascade structure is presented to us explicitly as a tree and that we can cache values on the nodes. Without that assumption, creating the tree would require O(n) space, which is obviously worse than the O(sqrt(n)) space used in my algorithm.
@psykotic : in the provided link by googlybhai... whose code will give correct output with O(N) time.
public List<double> PourWater(int water)
{
List<double> result = new List<double>(){0};
while (water > 0)
{
PourWater(result, 1, 0, 0);
water--;
}
return result;
}
public void PourWater(List<double> cups, double water, int h, int i)
{
int index = h * (h + 1) /2 + i ;
if (cups[index] + water > 1)
{
if (cups.Count <= index + h + 1)
{
cups.AddRange(new double[h + 2]);
}
cups[index] += water - 1;
PourWater(cups, 0.5, h + 1, i);
PourWater(cups, 0.5, h + 1, i + 1);
}
else
{
cups[index] += water;
}
}
what is the index here? their index in their row or is it index starting from the topmost cup?
- Anonymous February 24, 2012PLease post google questions with more clarity, they deserve it