Amazon Interview Question
SDE-2sTeam: Bangalore
Country: India
Interview Type: In-Person
i'd improve findHeight by
1.add
if(height[tree[i]] !=-1)
height[i]+=height[tree[i]];
2.remove
if (height[i] != -1)
return height[i];
This solution works but it's absolutely NOT a O(n). For each tree node, you traverse the tree upwards to the root and calculate the depth at the starting node. This happens for every single node, making runtime complexity O(n * log n)
This should work as a simple solution, does anyone have a more effecient one? (call it with -1 for the parent value to start it)
private static int calcDepth(int parent, int[] tree) {
int maxDepth = 0;
for (int i = 0; i < tree.length; i++) {
if (tree[i] == parent) {
int depth = 1 + calcDepth(i, tree);
if (depth > maxDepth) maxDepth = depth;
}
}
return maxDepth;
}
int getdepth(int input_array[],int depth[],int k,int size)
{
if(depth[k]!=-1)
return depth[k];
if(input_array[k]==-1)
{
depth[k] = 1;
return 1;
}
if(depth[k]==-1)
{
depth[k] = 1+getDepth(input_array,depth,input_array[k],size);
return depth[k];
}
}
int calcDepth(int input_array[],int size)
{
int depth[size] = {-1};
int max=0;
for(int i=0;i<size;i++)
{
if(max<getdepth(input_array,depth,i,size))
max = getdepth((input_array,depth,i,size);
}
return max;
}
the above code should visit each edge of the tree only once O (n) while the worst case complexity for donnell code is around O(n^2)
We can do this problem in O(n) time using O(n) space.
1) As each element of the given array(except the root) will be in the range [0,n), so we can create an array of Linked Lists.
2) Now traverse the given array. Insert the index of the element to the respective parent. Also mark out the root in this process. So now the array becomes:
[null,null,4,1->2->3,null]
3) Now create a Queue. Insert the root index into it. And also insert a special symbol say $, to mark the end of the current level. Each time you pop out a element from the queue, push all its children into the queue.
A bit of pseudocode to help.
q.add(rootIndex);
q.add($);
while(!q.isEmpty())
{
current = q.pop();
if(current == $ ) // marks the end of current level
{
height ++;
if(!q.isEmpty())
q.add($);
}
else
{
for each element child in the linked list of the popped element
q.add(popped element child);
}
}
Because each node is pushed and popped in the queue at most once, the complexity is O(n).
I think following should work
#include<iostream>
using namespace std;
int arr[]={2,6,3,6,3,6,-1};
int main(){
int size=7;
int cov[size];
for(int i=0;i<size;i++){
cov[i]=0;
cout<<arr[i]<<" ";
}
int l=0;
for(int i=0;i<size;i++){
if(arr[i]==-1)continue;
else {
cov[arr[i]]=max(cov[arr[i]],cov[i]+1);
l=max(l,cov[arr[i]]);
}
}
cout<<"\nlength = "<<l+1;
}
why u find the max value from l and cov[] .....in my opinion we will count the value which is greater then 0 will b desired result::
if the input is as input[]={5,5,5,5,,5,-1}
then the content of cov[]={0,0,0,0,5,0} so from your side answer should b 5 but the height will b 1 can u explain more..(am i wrong or..?)
@G25
for every node, cov would store depth of the of that node, the test case which you are referring is below
5
/ / \ \ \
0 1 2 3 4
for which cov array at the end is (after executing this same code)
cov = {0,0,0,0,0,1}
so answer in end is 2 (the height, 1 more than maximum value in array)
kindly check it on your machine, and let me know if still you find some bug in it.
#include<stdio.h>
#include<limits.h>
int main()
{
int tree[50], n, i,cur, h=INT_MIN, t;
printf("No of nodes: ");
scanf("%d",&n);
printf("Elements: ");
for(i=0; i<n; i++)
scanf("%d",&tree[i]);
for(i=0; i<n; i++)
{
cur=i;
t=0;
while(tree[cur]!=-1)
{
cur=tree[cur];
t++;
}
if(t>h)
h=t;
}
printf("\nheight = %d",h);
}
static void GetHeight(int [] a)
{
int height=0;
if ( a != null && a.Length > 0)
{
int[] level = new int[a.Length];
for (int i = 0; i < a.Length; i++)
{
int parentNode = a[i];
if (parentNode == -1)
{
level[i] = 1;
}
else
{
if (level[parentNode] == 0)
{
level[parentNode] = 1;
}
level[i] = 1 + level[parentNode];
}
height = Math.Max(height, level[i]);
}
}
Console.WriteLine("Height of tree is : {0}", height);
}
Nagendra, above code looks incorrect as you are assuming level[parentnode] which are not yet traversed as 0.
1. Create an array of n elements, lets call it level[ ]
2. Find the root element index with value -1from node [ ], search(O(n))
3. Set the value of that index in level [ ] to 0
4. Traverse through the node [ ], for each index(lets say index 0), find its parent index value(parent index is 3, index 3's value in level[ ] is 0 and set the value in level[ ] to parent index value (here 0 ) + 1 = 1 This is also O(n)
e.g node[ ] = { 3, 3, 3, 3, -1, 2, 1, 0}
level[ ] = {1, 1, 1, 0, 2, 2, 2}
max value in level [ ] will be the height of the tree. find max is also o(n)
{{
class Program
{
static int[] parent = { 3, 4, 3, -1, 2 };
static int[] nodes = { 0, 1, 2, 3, 4 };
static int[] heigths = { 0, 0, 0, 0, 0 };
static int root = -1;
static int max = -1;
static int FindHeigth(int i)
{
var h = heigths[parent[i]];
if (h == 0)
{
return 1 + FindHeigth(parent[i]);
}
else
{
return h + 1;
}
}
static void Main(string[] args)
{
for (var i = 0; i < nodes.Length; i++) {
if (parent[i] == -1) {
heigths[i] = 1;
root = nodes[i];
}
}
for (var i = 0; i < nodes.Length; i++)
{
if (i != root)
{
heigths[i] = FindHeigth(i);
if(max < heigths[i]){
max = heigths[i];
}
}
}
System.Console.WriteLine("Depth " + max);
System.Console.Read();
}
}
}}
Iterative way, use Time O(n) and Space O(n), with C++
#include<iostream>
#include<string.h>
using namespace std;
int GetHeight(int A[], int n){
if(n <= 1) return 0;
int height[n];
memset(height, 0, sizeof(height));
int v, h, maxH = 0;
for(int i = 0; i < n; ++i){
v = A[i]; h = 0;
while(v >= 0){
if(height[v] > 0){ h+= (height[v] + 1); break; }
else ++h;
v = A[v];
}
height[i] = h;
maxH = max(h, maxH);
}
return maxH;
}
int main(){
int A[] = {3, 3, 3, -1, 2};
cout << GetHeight(A, sizeof(A)/sizeof(int)) << endl;
return 0;
}
I have found a nice O(N) time and O(1) space algorithm for this problem (I know its been 4 years but bear with me). A few observations led me to this algorithm:
1. If we idealize and imagine we have O(N) space we can cache the heights of each node we've considered before and for later nodes we can simply go up the tree until we hit a parent in the cache when we instantly know the height and can add all nodes we saw on that path to the cache with their corresponding heights. This is what many people have done in their O(N) time O(N) space solutions. Its clear that this runs in O(N) time as each node in the tree is considered at most twice (except the root).
2. A natural extension to obtain a constant space algorithm would then be to try to use the existing array as a cache. This is exactly what I have achieved. I realized that if we cache the heights directly in the array, we will have no way to tell on successive iterations when to "bail out" and compute the heights from the cached value, as they'd be indistinguishable from other nodes in the array. For example, if we have an array:
[2,0,-1], computing and caching the height of node 0 and its predecessors yields an array that looks like [2,1,-1], but when we consider node 1, it will naively think the value at arr[1] is the predecessor and we will get nonsense output.
Thus, in order for nodes to distinguish between cached values and predecessor values, I cache N+height_of_node. Then, caching works as described in part 1, if I perform comparisons of the predecessor value with N to determine if it is a cached height or not.
Here is the algorithm in C++ (feel free to comment or ask questions):
//This function runs in linear time because each node that is "observed" is set to N+k for some k.
int findTreeHeightFromArray(vector<int> arr) {
int max_height = 0;
int N = arr.size();
for (int i = 0; i < arr.size(); i++) {
if (arr[i] >= N) {
//its been marked by a lower node so continue:
continue;
}
int node = i;
int height = 0;
while (arr[node] != -1 && arr[node] < N) {
node = arr[node];
height++;
}
//now go up the tree from i until node and set their values
int top_height = 0;
if (arr[node] >= N) {
top_height = arr[node]-N;
}
node = i;
int tmp_height = N + top_height + height;
while (arr[node] != -1 && arr[node] < N) {
int temp = arr[node];
arr[node] = tmp_height;
tmp_height--;
node = temp;
}
}
for (int i = 0; i < arr.size(); i++) {
if (N - arr[i] > max_height) {
max_height = arr[i] -N;
}
}
return max_height;
}
Brute force. Space O(1) Time i guess is O(n* m) being m the total depth
#include <iostream>
using namespace std;
// No idea why we cant calculate the size ourself :(, and we need to pass as parameter
int getMaximumDepth(int array[], int arraySize){
cout<<"getMaximumDepth start \n";
if(array == NULL){
return 0;
}
// int arraySize = sizeof(array)/sizeof(*array);
cout<<"arraySize" << arraySize << "\n";
int currentDept;
int maxDept = 1;
for(int i = 0; i < arraySize; i++) {
cout<<"i" << i << "\n";
cout<<"array[" << i << "] = " << array[i] << "\n";
currentDept = 1;
int parent = array[i];
while(parent != -1){
currentDept ++;
parent = array[parent];
}
cout<<"currentDept" << currentDept << "\n";
if(maxDept < currentDept){
maxDept = currentDept;
}
}
return maxDept;
}
int main()
{
int array [] = {3,3,3,-1,2,0,1,2,3,4};
int arraySize = sizeof(array)/sizeof(*array);
cout<<"arraySize" << arraySize << "\n";
cout<<"maxDept:" << getMaximumDepth(array, arraySize) << "\n";
return 0;
}
Not correct, check with {3,3,3,-1,2,1,0}. According to your solution the answer should be 4 but the correct answer is 2.
You are right, my mistake!
Here`s a working version:
int parent[]={3,3,3,-1,2,1,0};
int node[]={0,1,2,3,4,5,6};
int n=SIZE(parent);
int *height=new int[n];
int i;
for(i=0;i<n;i++)
{
if(parent[i]==-1)
{
height[i]=0;
break;
}
}
for(i=0;i<n;i++)
{
if(height[i]!=0)
height[i]=height[parent[i]]+1;
}
// disp(height,n);
printf("\nHeight of the Tree:\t%d\n",height[n-1]);
Here's a dynamic programming solution which does this in O(n).
- goknicks July 23, 2013