UKSJayarathna
BAN USER- 0of 0 votes
AnswersDuring my 2nd interview
- UKSJayarathna in United States
1. Use 2 stacks to create a queue structure
2. If you have a tree how to verify it a BST
A. User the inorder traversal
3. Write a code to implement above question 2.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Java
OK, I'm totally confused. This is too simple, and I'm not sure why everybody writing some complex codes to solve this. We need to just combine the 2 Arrays and if the question is not asking to have the first array sorted after the merge, things are much easier. You can just swap whenever you find the " " in the Array 1.
public static void merge2Arrays(String[] a1, String[] a2){
for(int i=0,j=0;i<a1.length;i++ ){
if(a1[i]==" "){
a1[i] = a2[j];
j++;
}
}
}
I'm not sure why everybody wanna make it so complex :)
The question was simple and my answer was straight forward and the Amazon interviewer agreed with me when I mentioned the inorder traversal solution. I guess there may be different solutions, but don't make it over complicated, you have only may be 10 mintues to discuss the algo and then code it correctly.
It is simple, you can do an in-order traversal of the tree and every time you read the root, put that to an array, then you can go through the array by comparing elements which should be in ascending order.
public void checkBST(Node tree){
if(tree!=null){
checkBST(tree.left);
arrayList.put(tree.data);
checkBST(tree.right);
}
}
I guess you cannot provide a result without reversing the list for the given original example, where you need to start summation from the last Nodes and backward. So the steps would be
- UKSJayarathna January 03, 20121. Reverse both lists
2. Start summing nodes from each list by going through the links