## caffeine_coder

BAN USERCall Rev for the entire string and then call Rev for each word.

- caffeine_coder November 10, 2009The formatting there incorrect. The 4th node links to the 2nd node.

- caffeine_coder November 06, 2009I think the question is about deleting a LL like this,

1->2->3->4

^ |

|_____|

In which case, the code above will end up freeing the 2nd node twice.

You'll have to,

1. Find the loop

2. Find the loop node

3. Break the loop

4. Delete as usual

All that can be done in O(n)

?

- caffeine_coder November 06, 2009To find LCA for nodes A and B:

O((logn)^2):

1. Find in A in left subtree, B in right subtree

2. If both not found, find in A in right subtree, B in left subtree

3. If both found, current node is the common LCA

4. If one found and not the other, make a recursive to call to that branch of the tree and start from 1.

O(nlogn) with O(n) space:

1. Traverse the tree until node A is found, store the path in an array a1.

2. Traverse the tree until node B is found, store the path in an array a2.

3. Compare a1 and a2, the last common element is the LCA.

But there are better, more complicated ways of doing this in constant time using RMQ.

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Lowest%20Common%20Ancestor%20%28LCA%29

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

In a string of length n1 if the length of the longest palindrome is n2 (n2 <= n1), then to convert the entire string to a palindrome it would take (n1 - n2) characters. So, the problem boils down to just finding the longest palindrome in the string (which has been discussed in before on this site.)

- caffeine_coder November 21, 20091. PLATE

n1 = 5

n2 = 1

chars needed = 4

Result: PETLALTEP

2. MADA

n1 = 4

n2 = 3

chars needed = 1

Result: MADAM