Amazon Interview Report
- 0of 0 votes
AnswersWritten-Qn-1) Write complete working code (only the function) to check whether the given char sequence is valid.
- Arang May 26, 2010
bool isValid(char *str)
Example:
I/P: ()()().... O/P: Valid.
I/P: ())()(.... O/P: Invalid.
* We can assume that the input will have only squence of '(' and ')' chars.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Coding Data Structures - 0of 0 votes
AnswersRound-3-Qn-1) It was repeated one. they asked the same round-1-Qn-1 question.
- Arang May 26, 2010
At starting of round-3, I noticed that interviewer has answer sheet of all my previous rounds and so i thought she is looking for some other alternatives than what i gave in round-1.
So i took 5 minutes to think of better solution but gave the same solution as i could not find any other better solution.
I made a big mistake by answering this question without saying "it was already asked in round-1". Because she assumed "i am cheating them.."... like that.
Thoguh i answered all the questions and performed well in previous rounds, it was the major reason for my elimination :(| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersWritten-Qn-2) Write complete working code (only the function) to traverse a binary tree in ZigZag order
void printTree(Node *root)
Example:1 / \ 2 3 / \ / \ 4 5 6 7
O/P: 1 3 2 4 5 6 7
- Arang May 26, 2010| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Coding Data Structures - 0of 0 votes
AnswersWritten-Qn-3) Given a binary tree and a number N, check is there any path exists in the tree such sum of the nodes in the path equals to N.
bool isPathExists(Node *root, int N)
Note: We can assume that node contains only positive integers
Example:1 / \ 2 3 / \ / \ 4 5 6 7
if N = 8, return TRUE
- Arang May 26, 2010
if N = 9, return FALSE| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Coding Data Structures - 0of 0 votes
AnswersRound-1-Qn-1) Find vertical sum of given binary tree.
Example:1 / \ 2 3 / \ / \ 4 5 6 7
The tree has 5 vertical lines
Vertical-1: nodes-4 => vertical sum is 4 Vertical-2: nodes-2 => vertical sum is 2 Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12 Vertical-4: nodes-3 => vertical sum is 3 Vertical-5: nodes-7 => vertical sum is 7
We need to output: 4 2 12 3 7
- Arang May 26, 2010| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Coding Data Structures - 0of 0 votes
AnswersRound-1-Qn-2) Given a binary tree, we need to create a matrix.
Example:
- Arang May 26, 2010A / \ B C / \ / \ D E F G |A|B|C|D|E|F|G| ------------------ A| B|1 (B is child of A) C|1 (C is child of A) D|1 1 (D is child of A & B) E|1 1 (E is child of A & B) F|1 1 (F is child of A & C) G|1 1 (G is child of A & C)
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Coding Data Structures - 0of 0 votes
AnswersRound-2-Qn-1) Given a linked list L, we need to make a clone L'.
Note: a) Each node in the given list has an additional link called random that can point to any node (can also be null)
b) we need to make a clone of the list without using any additional space (need to allocate memory only for new nodes 1', 2', 3',...)
c) complexity should be O(n)
- Arang May 26, 2010-->------ | | L = 1-->2-->3-->4-->NULL | | ^ | |___|___| | | |___| | |<----------- 1->next = 2 1->random = 3 2->next = 3 2->random = 3 3->next = 4 3->random = NULL 4->next = NULL 4->random = 1 In L', the nodes should be 1'->next = 2' 1'->random = 3' 2'->next = 3' 2'->random = 3' 3'->next = 4' 3'->random = NULL 4'->next = NULL 4'->random = 1'
| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersRound-2-Qn-2) Implement a data structure such that it provides push(), pop() and GetMax() operations and running time of all operations should be constant O(1).
- Arang May 26, 2010
Note: GetMax need not remove the max from the data structure.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Coding Data Structures - 1of 1 vote
AnswersRound-3-Qn-2)
- Arang May 26, 2010
- You are given two 4 digits prime numbers N1 and N2,
- You can change only one digit of N1 at a time.
- Resultant of changing a digit of N1 should also be a prime number.
How many number of digit changes (minimum) are required to convert N1 to N2?
Example:
Assume (8785, 8787, 8887, 9887, 9897) are prime numbers.
Lets say N1=8785 and N2 = 9897 then
change-1: 8785 => 8787
change-2: 8787 => 8887
change-3: 8887 => 9887
change-4: 9887 => 9897
So 4 digit changes are require to convert N1 to N2.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm Coding Data Structures