CareerCup

your answer works except for the logic to find the middle and last node.

I am sorry, but this will not work. How would your Step 1 find the middle and the last when there is a loop in the LL?
Even Step 2 is wrong. You don't really need to care if you are deleting a middle node or any other node. Yes, there will be special handling if the node to be deleted is the last node to restore the loop.

This is the first thing I thought off and I am pretty sure this is the simplest and the most efficient way.
Let's think about it's complexity:

Let length of input string = m
Then 1. is O(m) time and O(m) space

Let the number of words in the dictionary be = n
Let the length of the longest word in the dictionary be l
2. is O(n * l)

Total O(m + n*l) = O(n) Linear time

Let me know if you need more clarification or find any problems with this approach.

I am pretty sure they wanted it with O(1) space.

such stupid questions can only be asked in India !

Take a max heap of size 100. Keep inserting elements into the heap.
Initially, the first 100 elements would all go into the heap. After that, the maximum of those 100 elements would be at the top of the heap. This is the current top 100.
So, if the 101th element is less than the top, it means it is part of the top 100 and the element which is currently at the top must be removed. Add this 101th element to the heap.

If the 101th element is greater than the top, it means it is greater than all of the 100 elements which are currently in the heap. So, don't add it to the heap.

Keep doing this by loading as much of the elements you can in your memory. This can be easily calculated by the total amount of memory - memory to store a heap of size 100.

I think this should convince the interviewer.

english please? What is your approach?

Brilliant !!

Nice one Bugaboo, but have you used the columns also being sorted to your advantage?

Fair enough, what is the complexity?

As far as I remember, once you make these hashes, you have reduced the number of string comparisons. But, you still need to compare the strings having equal hashes in order to be sure.

But yeah average case, it should be something like 0(n + 3) which is again O(n)
Correct me if I am wrong.