Sunday, June 28, 2015

Count the number of subsequence divisible by 6

You are provided a string with only digits [0 - 9], your task is to count the number of subsequences of string divisible by 6.

For e.g. The given string is 1234566
The subsequences divisible by 6 are 12, 24, 36, 6, 6, 66
Hence the answer should be 6

The most obvious approach which comes is to generate all the subsequences and do a divisibility check and return the count satisfying the condition.

But it is too expensive and overall complexity is 2^n (where n is the size of the string)

Can we make it better?

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