Amazon Interview Report
- 2of 2 votes
AnswersQuestion on Tree Data Structure: How can we fill all inorder successor pointer of all tree nodes ?
Tree node contains 3 pointers *left, *right and *Successor .Struct node{ int data; struct node *left; struct node *right; struct node *successor; };
A / \ B C / \ / \ D E F G
INORDER Traversal: **DBEAFCG**
**Note:** A inorder successors are F,C and G.
**Function prototype:** void FillSuccessorNodes( struct node *root);
Tree's root node given to us and we need to fill successor pointer for all nodes.case 1) some of the Successor pointers may be **NULL** . This case you have to fill that pointer with immediate Inorder Successor.
Example: if A->Successor == NULL, then fill A->Successor = F
case 2) some of the Successor pointers may already points to correct successors. This case You no need to modify successor pointers.
Example: 1) A->successor = F is valid
2) A->successor = C is valid
3) A-successor = G is valid . All these three cases you no need to modify successor pointer since these already pointing to correct successor nodes.case 3) Some of the successor pointers are **not NULL** but these pointers pointing to INVALID successors i.e it could be inorder successor or some garbage value. This case you have to fill these nodes with immediate successor nodes.
Example:
1) A->successor = B is invalid since B is not successor node , so we have to correct it to A->successor = F.
2) A->successor = 0x23237463478 is invalid since it is pointing to garbage value. So we we have to correct it to A->successor = F.**1) Interviewer asked me time efficient solution in O(n) time complexity. Extra space allowed. 2) she gave some hint i.e we can use HASHing.**
- siva.sai.2020 December 01, 2010**If you know the solution for this problem, please let me know .**
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer - 0of 0 votes
AnswersHow can we generate all possibilities on braces ?
- siva.sai.2020 December 01, 2010
N value has given to us and we have to generate all possibilities.
**Examples:**
1) if N == 1, then only one possibility () .
2) if N==2, then possibilities are (()), ()()
3) if N==3, then possibilities are ((())), (())(),()()(), ()(()) ...
Note: left and right braces should match. I mean )( is INVALID for the N==1
How can we solve this problem by using recurrence approach ?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer