Ashupriya
BAN USER- 1of 1 vote
AnswersHow to stop recursion stack as soon as we find a result.
- Ashupriya in United States
e.g. in a Tree recurion where the Order of the algo is O(n) and suppose we find the result just after 4 calls, can we empty the recursion stack and stop the ececution right away...| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm Data Structures General Questions and Comments Ideas Java
- 9 Answers I know its not ethical to [1...
I know its not ethical to
- Ashupriya July 26, 2012
[1] take help from the internet
[2] refer your own code (written earlier)
in a telephonic interview
But due to the very nature of the telephonic interviews, is it also granted from the interviewer's side to take help?
Should n't the telephonic rounds be replaced with video confrencings?
I know its a debatable topic, but would like to hear other's opinion...| Flag | PURGE
construction of BST would take nLogn time, given that both has same no of elements
so On is difficult to achieve, though there are certain checks that we can impose to quit early
[1] if the length of the two arrays are different then they can not be identical
[2] Construction of BST mostly depends on the order of the elements they come (unsorted)
keep track of the height of each tree (since we are not building height balanced tree) if the height of tree with same no of elements inserted then its unlikely that they will be same later
by the way did you happen to aswer it in On time? or the interviewer was emphasizing to be in On
And here is the Java version : It uses java's reflection mechanism
public void traverseAndCallFunction(AvlNode root, String functionName)
{
if(root == null) return;
else
{
traverseAndCallFunction(root.left, functionName);
traverseAndCallFunction(root.right, functionName);
if(root.left == null && root.right== null)
{
try{
this.getClass().getMethod(functionName).invoke(this, (Object[]) null);
}catch(Exception e)
{
e.printStackTrace();
}
}
}
}
public void dummyFunction()
{
System.out.println("Dummy Function called using reflection technique of Java");
}
The solution to this problem is Treap, a BST as well as a heap,
TreapNode {
left, right, parent
value
priority
}
In the node keep an extra field named Priority (OR insertion Order) increment it everytime a new node comes...
So keep creating the BST based on the value and .... rotate it (kind of heapify) whenever a high priority item is inserted on a lower levels in BST untill it becomes a root
Please see Treap for better understanding:
Order of insertion and deletion would be O(logN) as we need to rotate (heapify)
not correct,
here we need to see if the right and left sub trees are quasi Isomorphic or Not...
public boolean isQuasiIsomorphic(AvlNode root1, AvlNode root2)
{
if(root1 == null & root2 == null)
return true;
if((root1 == null & root2 != null) || (root1 != null & root2 == null))
return false;
return (
(isQuasiIsomorphic(root1.left, root2.left) && isQuasiIsomorphic(root1.right, root2.right))
||
(isQuasiIsomorphic(root1.left, root2.right) && isQuasiIsomorphic(root1.right, root2.left))
);
}
Can be done in only 4 races ....
Race [1]
Make 5 hourses run from one direction and another 5 from another direction, and also mark the middle point of the race...
Notice first 3 intersections of the hourses and select the hourses who crossed their first half mark as the 3 fastest...
Race [2] repeat this with another 10 hourses
Now we have 6 best hourses and 5 untested
Race [3] Make 4 hourses run from each direction and choose the 3 same as above
Now we have left with 6 hourses
Race [4] Make 3 hourses from each side run and choose the best 3....
Done in 4 races
Only 6 races can fetch the result
Can be done in only 4 races ....
Race [1]
Make 9 hourses run from one direction and another 9 from another direction, and also mark the middle point of the race...
Notice first 3 intersections of the hourses and select the hourses who crossed their first half mark as the 3 fastest...
Race [2, 3,4] repeat this with another 18 hourses
Now we have 12 best hourses and 9 untested
Race [5] Make 9 hourses run from each direction and choose the 3 same as above
Now we have left with 6 hourses
Race [4] Make 3 hourses from each side run and choose the best 3....
Done in 4 races
Can be done in only 4 races ....
Race [1]
Make 5 hourses run from one direction and another 5 from another direction, and also mark the middle point of the race...
Notice first 3 intersections of the hourses and select the hourses who crossed their first half mark as the 3 fastest...
Race [2] repeat this with another 10 hourses
Now we have 6 best hourses and 5 untested
Race [3] Make 4 hourses run from each direction and choose the 3 same as above
Now we have left with 6 hourses
Race [4] Make 3 hourses from each side run and choose the best 3....
Done in 4 races
Can be done in only 4 races ....
Race [1]
Make 5 hourses run from one direction and another 5 from another direction, and also mark the middle point of the race...
Notice first 3 intersections of the hourses and select the hourses who crossed their first half mark as the 3 fastest...
Race [2] repeat this with another 10 hourses
Now we have 6 best hourses and 5 untested
Race [3] Make 4 hourses run from each direction and choose the 3 same as above
Now we have left with 6 hourses
Race [4] Make 3 hourses from each side run and choose the best 3....
Done in 4 races
Here is the code based on the Trie, the code is in java and I am not right now posting the Trie class, you can use any standard Trie implementation available on the net
public void stringProblem (String str)
{
Trie tr = new Trie();
if(str!= null)
{
boolean result = false;
int len = str.length();
for(int i = 0; i< len-2;i++)
{
String subStr = str.substring(i, i+3);
tr.insertWord(subStr);
}
for(int i = len-1;i>1;i--)
{
String subStr = str.substring(i-2, i+1);
StringBuffer sB = new StringBuffer(subStr).reverse();
if(tr.searchWord(sB.toString()))
{
result = true;
break;
}
}
if(result)
System.out.println("Match Found");
else
System.out.println("Match Not Found");
}
}
/* TestCases
s.stringProblem("abcdefhhiufedss");
s.stringProblem("abcdefhhiufdss");
s.stringProblem("aaa");
s.stringProblem("aa");
s.stringProblem("");
s.stringProblem("ssssssssssssssss");
*/
We can do it inplace using heapssort method
- Ashupriya July 01, 2012