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

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
Solution: 1FLF3LAF

Sunday, March 2, 2014

Find the pivot element in the rotated sorted array

A sorted array is rotated around a pivot element. Find the pivot element in the rotated sorted array.

Lets start with an example
Original array:           2, 4, 6, 8, 9, 10, 12, 15
Rotated array:           10, 12, 15, 2, 4, 6, 8, 9
Output:                      3

Sunday, February 23, 2014

Remove the duplicate elements in the string

Given a string, inplace remove the duplicate elements form the string.
For e.g. the given string is "codersstop is  a programming blog"
Result: "coderstp iagmnbl"


Maintain a lookup table of the 256 entries to mark the occurrence of each of the characters, and only copy the elements which are occurring for the first time.
Below snippet of code removes the duplicate elements from the string

void removeDuplicate(char * s) {
    char a[256] = {0}, c = 0;
    int len = strlen(s);
    for(int i = 0; i < len; i++) {
        if(a[s[i]] == 0) s[c++] = s[i];
        a[s[i]] = 1;
    s[c] = '\0';

Overall time complexity is O(n) and space complexity O(1)