Interview Question
Software Engineer / DevelopersCountry: India
| | | | | 1 | | | | |
| | | | 2 | |3 | | | |
| | | 4| | 5| | | | |
| | | | | 6| | 7| | |
| | 8| | 9| | | | | |
| | | | 10| | 11| | | |
| | | | 12| | 13| | | |
| | | | | | 14| |15| |
| | | | | 1 | | | | |
| | | | 2| |3 | | | |
| | | 4| | 5 | | | | |
| | | | | 6 | | 7| | |
| |8 | |9 | | | | | |
| | | |10| |11| | | |
| | | |12| |13| | | |
| | | | | |14| |15| |
In the above diagram, 1,5,6 comes in a single line and all the linked list(2->9->10->12 and
3->11->13->14) mentioned above comes in a single line. Imagining this tree, we have to devise to code put all the nodes that comes in a single line in a linked list.
if what you say is what it is required then below is what i'll do:
1. Assign coordinate (0,0) to the root node.
2. If the coordinate of a node is (x,y) then its left child should have a coordinate (x-1,y+1) and right child should have (x+1,y+1)
3. Recurse through the tree assigning coordinate to each node and also maintaining a hash table with x values as key and a linked list of nodes with that values of x as value. When you reach the leaf node the hash table values are the required link list. Instead of hash tabke an array of linked list can be used where array index will define the value of x.
Seems an irrelevant question...
- Messiah December 19, 2012