soconfusedgrad
BAN USER- 0of 0 votes
AnswersReverse a string. Give complexity.
- soconfusedgrad in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersImplement a stack using two queues (no coding necessary)
- soconfusedgrad in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures - 0of 0 votes
AnswersCheck if a tree is a binary search tree
- soconfusedgrad in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Data Structures
String reverse (String inString) {
Char[] ret= inString.toCharArray();
int length = inString.length;
for (int i = 0; i < length/2; i++){
char temp = ret [length-1-i];
ret [length-1-i] = ret [i];
ret [i] = temp;
}
return ret.toString();
}
Complexity: O(N)
Q1 and Q2
For O(1) push() and O(N) pop():
1. Enqueue into Q1.
2. If pop, check size of Q1, if size > 1, dequeue into Q2 until size == 1
3. Dequeue from Q1, return result
4. Switch back and forth
For O(N) push() and O(1) pop():
1. push() -> Enqueue into Q1
2. push() -> Enqueue into Q2, and Dequeue Q1 into Q2
3. repeat back and forth
4. pop() -> Dequeue from the Q that has element
boolean isBinary (int isLeft, int value, Node node) {
if (!node)
return true;
if (isLeft && (value < node.value)) return false;
if (!isLeft && (value > node.value)) return false;
return (isBinary (1, node.value, node.left) && isBinary (0, node.value, node.right));
}
/* wrapper */
boolean isBinaryTree (Node root) {
if (!root)
return true;
int value = root.value;
return (isBinary (1, value, root.left) && isBinary (0, value, root.right));
}
O(N) complexity - preorder traversal
ahh oops, good thing they didn't actually ask me to identify the name of the traversal haha.
- soconfusedgrad November 01, 2012