kunalgaind
BAN USERHave you searched on internet???
 kunalgaind December 06, 2009Search on internet dude.........
 kunalgaind December 06, 2009Thiyanesh, question is not about optimizing your solution space.......You don't need to solve these kinds of problem in an interview.......
I think interviewer is just looking for solution posted by xii.....thats divided a single array by assigning fix chunks too each.....and do mention about stack overflow and other problems, but I don't think interviewers is looking for just division of array and implementation details.......
Hi Vishal,
You solution will not work always... You can try it on RACECAR........
Why X has to be even??? I think right answer is 4......
 kunalgaind November 20, 2009Its definitely 36... Since satellite go back 1/4 and then it again cover that 1/4. So effectively satellite will cover 1.5 times full distance around globe to cover one round....So three round = 1.5*3*8 = 36......
 kunalgaind November 20, 2009I am not sure about suffix tree, as I have not read those yet, but I don't think we can solve this question iteratively in less than O(n^3) and I don't think dynamic programming will work too as we cannot use the result that I got in previous iteration because if I have two strings that are palindrome then I cannot say that if I merge both string then those will be palindrome also...
Here is my solution using O(n^3) complexity.
There are n*n different string that can be created using a string of length n......For example there are 1 string of length n that can be formed from given string and there are 2 string of length n1 that can be formed using a string of lenght n1 and there are n string of length 1.
So if you sum it all, there are 1+2+ ........+ n1 + n strings = O(n*n)........
We know how to check for one string in O(n) time, so I think we can just repeat the loop by checking string of length n to 1 and stop whenever we find any palindrome.....
Seriously, I don't think we can solve this question in less than this time, because we have to check for string of each length and in worst case there might not be any palindrome in string and so we might end up with generating palindrome on length 1 i.e . character itself, if you consider that to be a palindrome.....
Please share your thoughts, I would be happy to hear from anyone....who can help me in improve on this solution...........
What do you mean by last row ?? There is no row in binary tree and if we are talking about leaf node, then I think first solution was right......Just push it on the stack when node is a leaf node.........
 kunalgaind November 20, 2009I think we cannot solve this question in less than O(n^3) complexity........as ideally there are n*n different string that can be created using a string of length n......For example there are 1 string of length n that can be formed from given string and there are 2 string of length n1 that can be formed using a string of lenght n1 and there are n string of length 1.
So if you sum it all, there are 1+2+ ........+ n1 + n strings = O(n*n)........
We know how to check for one string in O(n) time, so I think we can just repeat the loop by checking string of length n to 1 and stop whenever we find any palindrome.....
Seriously, I don't think we can solve this question in less than this time, because we have to check for string of each length and in worst case there might not be any palindrome in string and so we might end up with generating palindrome on length 1 i.e . character itself, if you consider that to be a palindrome.....
Please share your thoughts, I would be happy to hear from anyone....who can help me in improve on this solution...........
Yeah, its a standard question from our favorite algorithm book "Cormen" but to solve it in O(n), C row should contains all 0's....and if that condition is there we can solve it in O(n) using following technique.
For example: If A[I][J] = 1, then I cannot be a celebrity as I don't know anybody, so go to A[I+1][J] and cannot skip one row.......but if A[I][J]=0 then J cannot be a celebrity, so move to J+1. If your J reaches N, number of people then nobody is a celebrity because you move from j =1 and reach N and so in each increment, you declared that J cannot be a celebrity except J. So check for J once again.......Otherwise if I reached N, then there is no celebrity.
Check question 22.1.6 in chapter on graph algorithms in Cormen..........
BTW, Here is a code if we keys are stored at every node.
If we know the key then we can traverse the elements going towards the parents.
Suppose that n1 and n2 are two nodes and key1 and key2 are values at these nodes respectively.
Step1: Get the largest of two. Now largest value be on right side of common ancestor and smaller value be on left side of common ancestor and both will be on either right side or left side of parent of common ancestor. So, we can use this property to find the common ancestor.
Step2: Start from smaller key and start moving towards root. If value at parent is less than value at current node then it cannot be common ancestor as smaller value lies on left side of common ancestor. So check next node. And if it is greater than node1, then node1 lies on left side of this ancestor of node1 so this ancestor can be a lowest common ancestor. Go to step 3 to check condition on parent of common ancestor.
Step3: For parent of common ancestor, Check that now both node1 and node2 either should lie on left side or on right side. If even one condition is true then you hit the parent node in step2, otherwise go up one step and repeat from step2. Code for it is as follows:
findCommonAncestor( node1, node2)// Assume node 1 is smaller than node2
{
parent = node1>parent;
while(parent)
{
if(parent>key < node1>key)
continue;
else
{
parentParent = parent>parent;
if((parentParent>key < node1>key && parentParent>key < node2>key)  (parentParent>key > node1>key && parentParent>key > node2>key))
return parent;
else
parent=parentParent;
}
}
}

kunalgaind
November 20, 2009 I think good way to solve it is to traverse one side till root from one node and put all the pointer in link list in order that we got it and then traverse another list and start comparing it and stop when you found a match. Maximum is that we have to (2logn) moves if lowest common ancestor is a root itself........
If we are not given the keys or tree is not BST, then I don't think we can do it less than logn......Also, in any case worst case it cannot be less than logn............
If we know the key then we can traverse the elements going towards the parents.
Suppose that n1 and n2 are two nodes and key1 and key2 are values at these nodes respectively.
Step1: Get the largest of two. Now largest value be on right side of common ancestor and smaller value be on left side of common ancestor and both will be on either right side or left side of parent of common ancestor. So, we can use this property to find the common ancestor.
Step2: Start from smaller key and start moving towards root. If value at parent is less than value at current node then it cannot be common ancestor as smaller value lies on left side of common ancestor. So check next node. And if it is greater than node1, then node1 lies on left side of this ancestor of node1 so this ancestor can be a lowest common ancestor. Go to step 3 to check condition on parent of common ancestor.
Step3: For parent of common ancestor, Check that now both node1 and node2 either should lie on left side or on right side. If even one condition is true then you hit the parent node in step2, otherwise go up one step and repeat from step2. Code for it is as follows:
findCommonAncestor( node1, node2)// Assume node 1 is smaller than node2
{
parent = node1>parent;
while(parent)
{
if(parent>key < node1>key)
continue;
else
{
parentParent = parent>parent;
if((parentParent>key < node1>key && parentParent>key < node2>key)  (parentParent>key > node1>key && parentParent>key > node2>key))
return parent;
else
parent=parentParent;
}
}
}

kunalgaind
November 20, 2009 I want to point out to people whoever is suggestion hashing and then writing complexity as O(n). Hash table best case complexity is O(1) and in worst case it is O(n). So don't think that Hashing solution is O(n) in best case, it can be O(n^2) in worst case.
Also, what about range of numbers?? Are we sure that array of size N is suffice??? What about collision?? So Hashing is never the best solution and it comes with a tradeoff.
So, I think I will go with the sorting and then binary search. Since we know that its numbers, so we can apply bucket sorting to sort the number in fast manner and then we can search for n numbers in nlogn time and so overall sorting + searching will take O(nlogn) time.........
I think basic idea that interviewers is looking for tradeoff, so its best to discuss both solution with him/her to let him/her know that you Hashing is a solution that looks tantalizing but it does not give the same performance in every case and it depends on numbers whereas sorting does not depends on input........
I don't think, interviewer asked this question to check your understanding on reference......He seems to be concerned with lvalue and rvalue but its make sense to mention about reference after mentioned about lvalue and rvalue........
 kunalgaind November 15, 2009I will use extra space to solve this question, as sorting is a costly affair.
Regarding extra space, we only need to use memory for 256 character, not of O(n) if we know that string is made up of only ASCII characters. We can do more optimization on space, if we can put more restriction on our data type like if string will consist only of lower and upper character than I need space for only 50 characters......
One thing that we have to see if that middle number is 2 and 3 are adjacent to 6 number. So if we take numbers from 1 to 8 then only 1 and 8 satisfy the condition that there are 6 number in the series that are not adjacent to them......Placing other number is just a matter of time.......
 kunalgaind October 23, 2009Open Chat in New Window
I think, we need some special cases too........Like this solution will fail if there is 0 at (1,1) and either 0th row or column has 1 at some other position.........I think this solution will work in other cases..........
 kunalgaind December 06, 2009Very nice solution........