## docomp

BAN USERThis can be done in O(n) time and O(n+e) space for the newly constructed string.

The input string might have palindrome as prefix or not.

palindrome prefix checking is simple and O(n).

If the input string does not have any palindrome as any part of prefix, we reverse the 1 to n-1 index string and append it at the front.

If there is any palindrome of size 2 or more as prefix, then the remaining string is reversed and appended at the front. that e is the part of the non-palindrome prefix. At the most, it can be n-1.

I assume the assistant is dumb and he does not read the coins. Assistant blindly follow my rules.

There are 8 sequences of step I do to make sure that all coins fly up and down.

There are only two possible configuration in the board. Either one coin is odd man out or two coins.

For eg

H H T H

H T or H T

There are several combination of this one odd man out or two odd man out possible. But that is not going to affect our coin.

First I will assume my table has only one odd man out.

1. I ask assistant to flip a coin. If it matches all coins fly up and down. otherwise there are two coins odd man out ( like two H and two tail - odd man out can be any two) bcoz of wrong flip.

2. I try to flip a vertical side of table assuming vertical ( assuming table is plane) could be odd man out. If it matches success or I flipped a Diagonal odd man out to Horizontal or I flipped a horizontal odd man out to Diagonal

3. I try to flip a diagonal side of table assuming diagonal ( assuming table is plane) could be odd man out. If it matches success. Otherwise I flipped a horizontal odd man out to vertical.

4. I apply vertical flip and now if it is success, coins fly up and down otherwise initial configuration is not one odd man out, but two. So it is one odd man out now. So continue all the step again since we know it is one odd man out now.

I think this is the modified Josephus permutation problem with the k being not constant. If k is supposed to be constant it is linear solution problem. We need to use augmented balanced binary search tree with extra field (this field is left sub-tree size and right sub-tree size) in it to get the best next indexed empty slot in the array. This is really very interesting problem. So the complexity analysis goes like this.

First the construction of the augmented binary search tree for all 13 elements in O(nlogn). Then we iterate in loop for each element, we pick the empty slot of particular index from BST which is O(logn). So for n elements it is O(nlogn). I guess this is the solution for it.

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

Open Chat in New Window

Preprocessing Step: Basically the dictionary of words is converted into multiple graphs. Each graph is constructed from words of particular size. The graph nodes have an edge if their edit distance (only replacement) is 1. Once you constructed this graph, then the problem is simple. Shortest path from given node to destination node. You can use BFS. The graph is undirected.

- docomp September 24, 2015