Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
i think height should be j+1 instead of j as j implies max of no. of ancestors of a node.......u r not including that node......
I would concur with crazygeek. However, that just depends on the definition of height and is very easily fixed.
There's no need to have a return at the end of a void function.
Yes, it's recursing through the height of the tree. No, that doesn't make it O(N^2). It's O(N). Each call to "level" does O(1) work before possibly calling "level" again, but another call to "level" can only happen if "level" has never been called with the given argument before. So a maximum of O(N) calls to "level" can be opened, each of which costs O(1) time and O(1) space to evaluate, for a total cost of O(N) time and O(N) space.
A small change wud make it better:
for(i=0;i<size;i++)
level(i);
change it to
for(i=0;i<size;i++){
if(b[i]==-1)
level(i);
}
The worst case is quadratic. An illustration would help , if my tree is linear like
0->1->2->3->4->5
the array would be
Parent = - 1 0 1 2 3 4
index = 0 1 2 3 4 5
The level api will have to ripple back to zeroth index always , when this has happens i times for ith call , n time for n th call.
Quadratic !
PA (ParentArray) be the given Array.
TempArray = new int[PA.length];
Initialize TempArray elements to -1;
for( int i=0; i<PA.length;i++){
populateTempArray(PA,i);
}
function populateTempArray(PA,i){
if(PA[i] == -1){
tempArray[i] =0;
}
if(TempArray[i]!=-1){
return;
}
if(TempArray[PA[i]]==-1){
populateTempArray(PA,PA[i]);
}
TempArray[i] = TempArray[PA[i]]+1;
}
Now loop Throgh TempArray to find the Max no, which corresponds to height.
here is O(n) solution
1.for each entry in the array,
-> look up in hashmap for the value(parent)
if there is an entry add the child(index) to it and add child to hashmap
else
create one entry for the value(parent) and add child(index) to it and add both to
hashmap
At the end you end up with n-ary tree. Now calculate depth of it O(n).
This requires you to actually build nodes that have storage for child pointers, which uses more space than a more optimized solution. This also requires a hashtable, which significantly increases the constant factor over an array-only solution. It also means you get O(N) expected, not deterministic time.
You can solve this in O(n) deterministic time, and with a much lower constant factor too, by just using a couple arrays.
I had the same solution in mind as Barney, the top-voted answer. I would have used iteration instead of recursion to make it more efficient.
Use DP.
Say we want to calculate the height of a node p. So, its height is equal to the height of its parent plus 1.
So, while calculating the height of a node, store it somewhere so that we do not need to calculate the height again once we fall in the same path.
Lets take an example of a BST: 1,2,3,4;
For calculating the height of 3, we need height of 2. However its already stored[using DP]
Hope its clear.
#include <stdio.h>
#include <limits.h>
int findheight(int *par,int size)
{
int i,j,height[size],count,maxheight;
for(i=0;i<size;i++)
height[i]=0;
for(i=0;i<size;i++)
{
count=0;j=i;
while(par[j]!=-1 && !height[j])
{
++count;
j=par[j];
}
height[i]=count+(j!=i?height[j]:0);
}
maxheight=INT_MIN;
for(i=0;i<size;i++)
if(maxheight<height[i])
maxheight=height[i];
return maxheight;
}
int main()
{
int par[]={-1,0,1,6,6,0,0,2,7},size;
size=sizeof(par)/sizeof(par[0]);
printf("%d ",findheight(par,size));
return 0;
}
ideone.com/vCLF4
That's true, this is O(n^2), for instance, in the case of a degenerate tree that becomes a linked list. However, there's a fairly simple fix. When searching until you find a parent whose depth is known, keep track of all previously unseen nodes in the path, and then backtrack through them and assign their depths. For instance, if you see 5 -> 8 -> 13 -> 45 -> 3 and that's where it stops because the depth of 3 is known to be, let's say for example, 2, you should store the sequence 5 -> 8 -> 13 -> 45 -> 3 somewhere and then backtrack, saying 45 is depth 3, 13 is depth 4, 8 is depth 5, 5 is depth 6. That way you can see that each node is traversed exactly once and the algo is O(N).
I have a similar approach, and while traversing from current "node" up to the root, I store all intermediate nodes on a stack so that I can set their heights after I reached the root. I also would stop traversing once I encounter a "node" with a known height.
static int height(int[] parent) {
int len = parent.length;
int[] height = new int[len];
int maxHeight = 0;
for(int i=len-1; i>=0; i--) {
int n = i;
Stack<Integer> stack = new Stack<Integer>();
while(parent[n] != -1) {
if(height[n] > 0) // optimization when height is already known
break;
stack.push(n);
n = parent[n];
}
int depth = height[n] + 1;
while(!stack.isEmpty()) {
n = stack.pop();
height[n] = depth++;
maxHeight = Math.max(maxHeight, height[n]);
}
}
return maxHeight + 1;
}
public int findDepth(int[] input) {
List<Integer>[] children = new ArrayList[input.length];
for (int i = 0; i < input.length; i++) {
int parent = input[i];
if (parent == -1)
continue;
if (children[parent] == null) {
children[parent] = new ArrayList<>();
}
children[parent].add(i);
}
return findDepth(0, children);
}
private int findDepth(int root, List<Integer>[] children) {
List<Integer> list = children[root];
if (list == null)
return 0;
int depth = 0;
for (Integer child : list) {
depth = max(depth, findDepth(child, children));
}
return depth + 1;
}
Yoda coding not good. Yoda do pseudo code write.
struct node {
int val;
struct node *next;
}node;
//A simple hash-map from int to node *. Supports chaining
HASHMAP<int, node*> theMap;
FILL_MAP(int A)
{
for(int i=0;i<A.length(); i++)
theMap[A(i)].PUSH_BACK( i);
}
int recurse_map(int node_val){
if( NOT_EXIST( theMap[node_val] ) ) return 0;
node * p= GET_FIRST_ELEMENT(theMap[node_val]);
int cur_ht=0; int max_ht=0;
while(p)
{
cur_ht=recurse_map(p->val);
if(max_ht<cur_ht) max_ht=cur_ht;
p=p->next;
}
return max_ht+1;
}
int FIND_HEIGHT_N_ARY( int A[]) {
FILL_MAP(A);
return recurse_map(-1);
}
IF Understand you not Yoda ask. Yoda code Proper then.
package puzzles.twostacks;
public class TreeArrayHeight {
int getAndSetHeight(int[] array, int index) {
if (array[index] == -1) {
return 1;
}
if (array[index] >= 0) {
array[index] = -(getAndSetHeight(array, array[index]) + 1);
}
return -array[index];
}
public void getMaxHeight(int[] array) {
for (int i = 0; i < array.length; i++) {
getAndSetHeight(array, i);
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < array.length; i++) {
min = Math.min(min, array[i]);
}
System.out.println(-min-1);
}
public static void main(String[] args) {
new TreeArrayHeight().getMaxHeight(new int[]{-1,0,1,2,3,4});
}
}
1. O(n^2)
for(int i=0; i<n;i++)
{
p=Parent[i];
while(p!=-1)
{
Height[p]=max(Height[p], Height[i]+1);
i=p;
p=Parent[i];
}
}
return Height[root];
2. O(n) time, and O(n) space
1- build a n-ary tree based the parent array
2- traverse n-nary tree to compute height
void BuildTree()
{
Tree[n];
for(i=0;i<n;i++)
{
if(Parent[i]!=-1)
{
Tree[Parent[i]]->nextChild = &Tree[i]; //add i to its parent's child list
}
}
int Height(node)
{
if(!node->Child) //leaves
return 0;
int h=0;
while(!node->Child)
{
h=max(h,Height(node->Child));
node->Child = node->nextChild;
}
return h+1;
}
void create_hash(int parent[],int n)
{
int i;
for(i=0;i<n;i++)
{
if(parent[i]!=-1)
hash[parent[i]]++;
}
}
void Find_unique(int unique[],int child[],int n)
{
for(int i=0;i<n;i++)
{
if(hash[child[i]] == 0) //abset from parent array
{unique[pos] = child[i];
pos++;}
}
}
int Find_height(int unique[],int child[],int parent[],int n)
{
int x = 0,i;
int ht = 0;
int maxht = 0;
for(i=0;i<pos;i++)
{
ht = 0;
x = unique[i];
while(parent[x]!=-1)
{
x = parent[x];
ht++;
}
//check when stops
if(ht > maxht)
maxht = ht;
}//end of for
return maxht;
}
Just using a recursion with memoization so that we do not check the paths again. This will be O(n) time and space. Here is the Java code bellow:
public int maxDistance(int[] arr) {
int[] dp = new int[arr.length];
int result = 0;
for (int i = 0; i < arr.length; i++)
result = Math.max(result, maxDistance(arr, dp, i));
return result;
}
private int maxDistRec(int[] arr, int[] dp, int i) {
int result = 0;
if (dp[i] != 0 || arr[i] == -1)
result = dp[i];
else {
result = maxDistRec(arr, dp, arr[i]) + 1;
dp[i] = result;
}
return result;
}
import java.util.*;
class Test{
static int[] A = {-1,0,1,6,6,0,0,2,7,5,9,10,11,12};
public static void main(String[] str){
Test test = new Test();
System.out.println(test.height(0));
}
public int height(int e){
int depth = 0;
int eFound=find(e);
if(eFound == -1){
return 0;
}
else{
ArrayList aList = new ArrayList();
for( int k=eFound; k <14; k++)
{
if( e == A[k] ){
depth=height(k)+1;
//System.out.println(depth+" "+e);
aList.add(depth);
}
}
int max=((Integer)aList.get(0)).intValue();
for ( int h = 1; h<aList.size();h++){
int temp = ((Integer)aList.get(h)).intValue();
if(max < temp)
max=temp;
}
return max;
}
}
public static int find(int e){
int flag = -1;
for(int i=0; i <14; i++ ){
if( A[i] == e ){
flag=i;
break;
}
}
return flag;
}
}
in java:
public int findHeight(int [] parents){
int len = parents.length;
HashMap<Integer, Boolean> seen = new HashMap<Integer,Boolean>;
int height = 0;
for(int i=0;i<len;i++){
seen.put(parents[i],false);
}
for(int i=0;i<len;i++){
int p = parents[i];
boolean seenParent = seen.get(p);
if(!seenParent){
height++;
seen.put(p,true);
}
}
return height;
}
public static void FindTreeHeight(int[] inputArray)
{
int arrLen = inputArray.Length;
int[] tempArr = new int[arrLen];
for(int i=0;i<arrLen;i++)
{
int level =0;
int j=i;
while (inputArray[j] != -1)
{
j = inputArray[j];
level++;
}
tempArr[i]=level;
}
foreach(int ele in tempArr)
{
Console.WriteLine(ele);
}
}
if no additional memory is allowed, this is my solution with a while loop instead of recursion.
static int maxDepth(int[] parents) {
int maxDepth = 0, curDepth = 0, curNode;
for (int i=0;i<parents.length;i++) {
curNode = i;
curDepth = 1;
while (parents[curNode] != curNode) {
curDepth += 1;
curNode = parents[curNode];
}
maxDepth = Math.max(curDepth,maxDepth);
}
return maxDepth;
}
- Shobhit July 08, 2012