viv
BAN USER- 0of 0 votes
AnswersGiven two nodes of a BST and all elements in BST are distinct, write code to determine the shortest distance between the two nodes. (unit distance between two adjacent nodes). Nodes dont have parent pointer.
- viv in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven references to roots of two binary trees, how do you short circuit determine whether the sequences of the leaf elements of both the trees are same ? The structure of two BTs may be different. Short circuit : for ex. If the very first leaf element of each tree is different, the algorithm should stop immediately returning false instead of checking all the leaf elements of both trees.
- viv in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm
we are supposed to use iteration here since it wont take too much stack space since the tree is huge.
1) use BFS with a queue, but while enqueuing nodes enqueue
pseudo code
enqueue(root.left)
enqueue(root.right)
while(queue.size() > 0){
Node node1 = dequeue();
Node node2 = dequeue();
check if node1.data != node2.data return false;
else{
if( (node1.right == null && node2.left !=null) || (node1.right != null && node2.left ==null)
return false;
if(node1.right != null && node2.left!=null){
enqueue(node1.right);
enqueue(node2.left);
}
if(node1.left != null && node2.right!=null){
enqueue(node1.left);
enqueue(node2.right);
}
}
}
Also, each Node should have two int fields - leftId, rightId each store a unique id. we can use this id as the filename of a file in some default directory( the file stores the subtree below that node). if the leftId = -1 or (rightid = -1), we can access the child nodes as usual.
if leftid or rightid is some positive number, we should load that subtree into memory.
This approach would minimize the no. of disk reads. If we were to store each node on disk, that would require a lot of disk accesses which slow downs the execution of the program.
Hi Dinesh,
Good one.
But just a correction or two:
1) '.' matches any single character except end-of-line. So, it has to be escaped when we want to match '.'
2) the strings such as 1234.123.341.243 which has more than 3 digits (1234) should not be included.
so, the final command might look like:
ls -R| grep '[0-9]\{1,3\}\.[0-9]\{1,3\}\.[0-9]\{1,3\}\.[0-9]\{1,3\}' | grep -v '[0-9]\{4,\}'
-v switch: exclude those that match the pattern ( here 4 or more occurrences of digits)
consider the below:
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
If you want to find total number of set bits from 1 to say 14 (1110)
Few Observations:
1) 0th bit (LSB) 1 bit appears once every two bit (see vertically) so number of set bits = n/2 +(1 if n's 0th bit is 1 else 0)
2)1st bit : 2 consecutive 1s appear every four bits (see 1st bit vertically along all numbers)
number of set bits in 1st bit position = (n/4 *2) + 1 (since 1st bit is a set, else 0)
3)2nd bit: 4 consecutive 1s appear every 8 bits ( this one is a bit tricky)
number of set bits in 2nd position = (n/8*4 )+ 1( since 2nd bit is set, else 0) + ((n%8)%(8/2))
the last term is to include the number of 1s that were outside first (n/8) group of bits (14/8 =1 considers only 1 group ie. 4 set bits in 8 bits. we need to include 1s found in last 14-8 = 6 bits)
4)3rd bit: 8 consecutive 1s appear every 16 bits (similar to above)
number of set bits in 3rd position = (n/16*8)+1(since 3rd bit is set, else 0)+ ((n%16)%(16/2))
so we do O(1) calculation for each bit of a number n.
a number contains log2(n) bits. so when we iterate the above for all positions of n and add all the number of set bits at each step, we get the answer in O(logn) steps
hello aaz,
The most efficient algorithm would be finding the longest common substring using the Generalised Suffix Trees by using Ukkonen's algorithm. did the interviewer ask you to write the program for this ? or just give the Idea / algorithm/ pseudocode ? It's a big program to even construct a generalised suffix tree for both strings.
Thank you,
hey ariesgirl069, here is the javacode
class TrimSpacesInString{
public static String trimString(String inputString){
if(inputString == null)
return null;
String inputStringT = inputString.trim();
StringBuffer result = new StringBuffer();
char temp;
int spaceCount = 0;
for(int i = 0; i < inputStringT.length(); i++){
temp = inputStringT.charAt(i);
if( temp != ' '){
if(spaceCount > 0)
result.append(' ');
result.append(temp);
spaceCount = 0;
}
else
spaceCount++;
}
return new String(result);
}
public static void main(String args[]){
System.out.println(trimString(" This is an example "));
return;
}
}
Java------------------------------------------------------------------------------------C++
1) Memory reclaimed by automatic---------------------| 1) Memory needs to be freed manually
memory management via Garbage Collection------ |
2) Java is both compiled and Interpreted. Source----| 2) C++ is compiled
code is compiled to optimized ByteCode. Bytecode|
is then interpreted by JVM
3) Only JVM needs to be implemented for each type|3) C++ needs a special compiler
of CPU to interpret bytecode-------------------------------| targeted at a certain CPU
4) Invented to solve System portability and web------|4) Invented to tackle the disadvantages
portability issues-----------------------------------------------| of Procedural programming
The semantics of synchronized do guarantee that only one thread has access to the protected section at one time, but they also include rules about the synchronizing thread's interaction with main memory. A good way to think about the Java Memory Model (JMM) is to assume that each thread is running on a separate processor, and while all processors access a common main memory space, each processor has its own cache that may not always be synchronized with main memory. In the absence of synchronization, it is allowable (according to the JMM) for two threads to see different values in the same memory location. When synchronizing on a monitor (lock), the JMM requires that this cache be invalidated immediately after the lock is acquired, and flushed (writing any modified memory locations back to main memory) before it is released. It's not hard to see why synchronization can have a significant effect on program performance; flushing the cache frequently can be expensive.
source: wwwdotibmdotcom/developerworks/library/j-threads1/index.html
Solution by Tushar Roy on geeksforgeeks:
Okie i got this approach..
suppose the example
inorder = A B C D E F G H I
postorder = A C E D B H I G F
This can b done recursively following way
you start reading postorder array from backwards. So take F , split inorder array into two subarray.
A B C D E and G H I
take G (before F in postorder) split GHI into null and H I, take I(before G in postorder) split into H I into H and null and so on.
following is the code which worked fine. Check it out.
typedef struct tree
{
int key;
struct tree * left;
struct tree * right;
}Tree;
Tree * createTreeFromPostorderInorder(int postorder[],
int inorder[],int left,int right, int pos)
{
if(left > right)
{
return NULL;
}
Tree *t = (Tree*)malloc(sizeof(Tree));
t->key = postorder[pos];
int index = search(inorder,left, right, t->key);
t->right = createTreeFromPostorderInorder(postorder,inorder,
index +1, right, pos -1);
t->left = createTreeFromPostorderInorder(postorder,inorder ,
left,index-1, pos - 1 - (right - index));
return t;
}
int search(int arr[],int left, int right,int key)
{
for(int i=left; i <= right; i++)
{
if( key == arr[i])
{
return i;
}
}
return -1;
}
int postorder[] = {'A', 'C' , 'E', 'D', 'B', 'H', 'I', 'G', 'F'};
int inorder[] = {'A', 'B','C','D','E','F','G','H','I'};
Tree *newTree = createTreeFromPostorderInorder(postorder,inorder,0,8,8);
Hey P, I dont think BFS works. It seems it works at first, but consider this tree
----------------------------------------23
---------------------------------------/ \
--------------------------------------2 5
------------------------------------/ \ / \
----------------------------------6 11 8 9
--------------------------------/ \ / \
-----------------------------32 21 12 15
---------------------------/ \ / \
------------------------65 72 39 25
BFS leaf sequence :8 9 12 15 65 72 39 25
In order Leaf sequence:65 72 39 25 12 15 8 9
An element from second sequence is what we require to keep comparing both trees. Well I did not think of BFS before. Thanks for mentioning it.
getFirstLeafInorder - returns the next leaf which is not traversed yet in order.
Also the interviewer stressed that the implementation has to be short circuit, you should not traverse any of the trees completely before checking whether the first leaf elements of both trees are same. Other wise, we can just inorder traverse each tree and put the leaf elements in queues and compare the queues.
Guys here is the answer. I have tested too. It works. I have used a combination of iteration and recursion.
1) inside the iteration, get the next leaf element from each tree (using getFirstLeafInorder) and compare, if it is not equal return false here and stop.
2) from the iteration (while loop) , call a function getFirstLeafInorder that uses stack that stacks nodes and also status of nodes (00 - no subtrees visited, 01 - Left subtree would be visited, 11- right subtree would be visited) and inorder traversal to determine the next leaf element and return
3) If all the leaf elements are same, in the iteration both leaf elements would be -999(a flag that says tree is completely in order traversed), return true
public static boolean checkLeafSequenceSame(Node root1, Node root2){
if(root1 == null && root2 == null)
return true;
if((root1 == null && root2 != null) || (root1 != null && root2 == null))
return false;
Stack<NodeStatus> stack1 = new Stack<NodeStatus>();
Stack<NodeStatus> stack2 = new Stack<NodeStatus>();
stack1.push(new NodeStatus(root1, 00));
stack2.push(new NodeStatus(root2,00));
boolean toReturn = false;
while(true){
int number1 = getFirstLeafInorder(stack1, root1);
int number2 = getFirstLeafInorder(stack2, root2);
System.out.println("Numbers compared "+number1+" "+number2);
if(number1 != number2){
toReturn = false;
break;
}
else if(number1 == -999 && number2 == -999){
toReturn = true;
break;
}
else if((number1 == -999 && number2 != -999)||(number1 != -999 && number2 == -999)) {
toReturn = false;
break;
}
}
return toReturn;
}
private static int getFirstLeafInorder(Stack<NodeStatus> stack, Node root){
NodeStatus top = stack.peek();
Node node = top.nodeTraversed;
if(node == null){
stack.pop();
return getFirstLeafInorder(stack,root);
}
//got the leaf element
if(node.left == null && node.right == null){
stack.pop();
return node.data;
}
int number = -99;
int status = top.status;
if(status == 00){
top.status = 01;
stack.push(new NodeStatus(node.left,00));
number = getFirstLeafInorder(stack, root);
}
else if(status == 01){
top.status = 11;
stack.push(new NodeStatus(node.right,00));
number = getFirstLeafInorder(stack, root);
}
else if(status ==11 ){
if(node == root)
return -999;
stack.pop();
number = getFirstLeafInorder(stack, root);
}
return number;
}
Node class and a Wrapper class that stores Node and status
=========
public class Node{
int data;
Node left;
Node right;
Node(int _data, Node _left, Node _right){
data = _data;
left = _left;
right = _right;
}
}
public class NodeStatus{
public Node nodeTraversed;
public int status;
public NodeStatus(Node _nodeTraversed, int _status){
nodeTraversed = _nodeTraversed;
status = _status;
}
}
Let me if you need clarification anywhere.
unfortunately, I was not able to come up with this exact algorithm on the spot in the interview, it was a new problem for me.
this would take a lot of memory due to recursive calls. we need to use iteration.
- viv March 31, 2012