Amazon Interview Question Software Engineer / Developers
0of 0 votestotal 3 questions
1)pre fix to post fix
Country: India
Interview Type: Written Test
split the prefix into tokens and process those tokens one by one
use a stack
read a operator, push the token to the stack
read a non-operator, if the top element is operator, push the token to the stack otherwise, pop an element, which is the left operand, and another element, which is the operator, to construct an postfix expression, repeat it until the stack becomes empty or the top element is operator and then push the expression to the stack
pop the postfix expression and return it
public String prefixToPostfix(String prefix)
{
Stack<String> s = new Stack<String>();
String[] tokens = prefix.split(" ");
for(String token: tokens) {
if(isOperator(token)) {
s.push(token);
} else {
String operand = token;
while(!s.empty() && !isOperator(s.peek())) {
operand = s.pop() + " " + operand + " " + s.pop();
}
s.push(operand);
}
}
return s.pop();
}
private boolean isOperator(String s)
{
return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
}
Question: If we are only given prefix, how are we to guess any structure to the tree. There can be multiple trees that give the same prefix.
Unless I am mistaken, we can only reconstruct a tree if we are given atleast two out of the tree recursive traversal techiques.
Algorithm
- pratikrd November 04, 20121. Read the characters
a. Opening brackets : push in the stack and go to step 1
b. operator: push in the stack and go to step 1
c. number: print
d. closing brackets: pop from stack
i. if it is a closing bracket - ignore
ii. if it is an operator - print
e. new line - exit