Amazon Interview Question for Systems Design Engineers
- 0of 0 votes
there is n node graph, each node having only one root. All nodes are labeled in a random order from int 0 to n-1
the graph is represented in a array format such that the value in the array at index equal to child node label is root node label.
For root assume the value is -1.
3 4 1 2 0 5
the array is- Sanjay Kumar March 19, 2012 in India
value : 1, 3, 3, -1, 3, 1
Index : 0, 1, 2, 3, 4, 5
Find the hight of graph. I have given an answer in O(n^2)
follow up question, if you dont have any restiction on space reduced the time complexity.
| Report Duplicate | Flag | PURGE
Amazon Systems Design Engineer Data Structures
Interview Type: Phone Interview
Open Chat in New Window