Friday, March 13, 2015

Searching words in a dictionary [Tries]

Given a dictionary, on which the below operations are required 

1. Update the dictionary
2. Find a word in a dictionary.

What are the possible options?
One of the most intuitive approach is to store the strings in a sorted manner.
Lets have a look at the complexity of the operations

Thursday, March 12, 2015

[Flipkart Interview] Compress the string

Given a string you are provided with the possible operations.
We can group the adjacent substrings, for e.g ABCABCBC can be compressed as
2ABC1BC or 1ABCA2BC

Among all the possible options, task is to find the resultant string with the minimum length.


In case if there are multiple solutions return the lexicographically smallest string.
So for the above example the solution would be 2ABC1BC

Another example would be
FLFLAFLAFLAF
Solution: 1FLF3LAF