DS
BAN USER@Karthik is nailed it -- LCA problem. Greatly simplified LCA problem because we have a parent link. As such all that is necessary is:
- get depth of A (logN) by walking up
- get depth of B (logN) by walking up
- take deeper one and level with another one
- walk in parallel until they meet
@saurabh answer will work just fine. This is just for fun :) Painter's like algorithm.
If we know MAX tree size, we can allocate an array of that size and starting from the back of the input array, fill in first elements of our working array with the index of a current tree. Number of elements to fill is the height of a current tree. Repeat the process for each tree in the input array in reverse order. The output would be unique numbers in the working array. Basically projection of all trees to a single array. For example:
Working array (result):
0011125557
Input:
7
5 7
5 7
5 7
2 5 7
12 45 7
12 45 7
12345 7
012345 7
01234567
Some thoughts.
For N node and possibility of multiple zeros, the worst case scenario appears to be N^2, i.e. we blindly look for a zero and when found we sink it to the bottom of the current subtree (square because for a degenerate tree, i.e. a tree is a list, it's N^2).
Alternatively we may look for the first non-zero child and swap with it and repeat. This may improve N^2 but I am not positive by how much.
Sinking N zeros is sinking of 1 zero N times, thus since sinking 1 is at worst N (if we have to traverse the whole tree and find no zero) then sinking N is N^2.
I can see 2 options:
- a graph with each cell representing a node. This gives very easy way to setup walls (no connectivity between nodes), traps (some property of edges), etc. as well as base for solving the maze. As as side effect it doesn't restrict number of connections between cells, i.e. it could be hexagon based maze.
- a matrix with 4 bits representing ability to move in each direction. Same graph algorithms applied if the matrix is treated as connectivity matrix. The downside is that non-flat mazes (2D) could be harder to comprehend and cells must be uniform in shape, i.e. more bits that 4 maybe confusing and connection between cells of different shape could be hard to describe.
Not sure why so much very hard to read code is dumped here...
Let's consider 'con'. The distance between 'c' and 'o' is 'o'-'c'=12. This means currently we are 12/5=2 rows up and 12%5=2 cols left. So go down 2 and right 2. Similarly 'n'-'o'=1, so we are 0 rows down/up and 1 col to the left. Thus just go 1 to the right. We must be careful to stay in bounds, i.e. if the word is 'conq' then diff is 3 but we are at distance of 2 from the border (we always know where we are) then we have to wrap, i.e. add a row and go left instead of right. I guess the devil is in details :)
In general and random set, that would work just fine. Here we have ordered set so we have good understanding if we need to go up or down or left or right.
BTW, in order to avoid 'z' problem, if preference is always given to go up or down then... there is no 'z' problem because we always go up from 'z'.
How about this: walk the tree N times looking up for target nodes keeping a hash table with visited counter for each node in the order of when a node was first found. Once all nodes are found, traverse the hash table from the back and find the first node that has the counter of N.
- DS January 20, 2014DP solution provided on StackOverflow.com. Put 1726632 in search there (CC doesn't allow links in the answers). In essence this is an algorithm:
At each scan do this:
If the cell has 0 assign count=0
If the cell has 1 and is an edge cell (bottom or right edge only), assign count=1
For all other cells, check the count of the cell on its right, right-below, and below. Take the min of them and add 1 and assign that to the count. Keep a global max_count variable to keep track of the max count so far.
In theory it will work if you are assuming it's all run in the same process space. However 1000 rps is 1ms per request. Thread synchronization will not keep up with such speeds (acquiring and releasing locks is expensive and usually takes longer than 1 ms). Since if you have to spawn multiple processes, the model you presented breaks.
- DS January 13, 2014That's a good observation -- prefix tree edges will give you all possible combinations of digits. What are your estimates on running time?
Building a tree (or trie) in performant way (linear or close to it) is difficult though so I wonder what would interviewer expectations would be in such case.
Brute force approach is something in these lines (basically start from individual numbers and then increase the size by 1 and repeat for the subarray) with X to be our target. However I'd be much more interested in dynamic programming solution, which appears could exist for this problem:
return foo(A, 0)
bool foo(A, startIndex) {
for size in (1...Length-startIndex) {
n = getNumberOfSize(startIndex, size)
if (n + foo(A, startIndex + size) == X {
return true;
}
}
return false;
}
Why the down vote?
- DS January 20, 2014