Binary search tree with constant random element functionality - PrismoSkills

Binary search tree with constant random element functionality - PrismoSkills
Problem: Design an advanced data structure which has all the functionalities of a binary search tree and
additionally it is also able to return a random number from the BST in logN time.


Solution: This is very similar to the previous problem.
Create a class containing a TreeNode<Object, Integer> and an ArrayList<Object>

Tree will provide the default functionality of a BST but will additionally store the index of the object in the array.
The ArrayList will store references to the objects in the map.

Insert operations: If the value was not present before, add it to the end of the ArrayList.
Then insert the object in the BST with key=object and value=ArrayList.size-1 (this gives the index of the object in the array).

Delete operations: Lookup index of object in the ArrayList from the BST.
Delete from the BST and then nullify the index in the ArrayList where the object was present.
To prevent developing holes in the ArrayList, move the last element of the ArrayList to the deleted index and update the index in the BST.  ///??? it's more complexity

Related: Set with constant random element functionality
Read full article from Binary search tree with constant random element functionality - PrismoSkills

Find K most frequent word in a really huge file - PrismoSkills

Find K most frequent word in a really huge file - PrismoSkills
Problem: Given a very huge file (one that may not fit into several computer's hard disk), find the top K most frequent words in that file.

Solution (Case 1): If the file was a regular one, following steps would have given the top K most frequent words:

1) Load the given file into RAM.
2) Split the big string into words using white-space and punctuation-marks as separator.
3) Put each word into a hash-map where word is key and frequency is value.
4) Find the top K most frequent words by using a min-heap, sorted on frequency.
   (Note: A min-heap is required here, not max-heap)
   Heap usage will give N*logK performance.

File not fitting in RAM
If the file is extremely large such that it cannot be loaded into RAM of one machine, then multiple threads may be launched to load small parts of file into memory and then apply the above algorithm.
Assumption here is that the entire dictionary of words in the file is small enough to be loaded into RAM.


Dictionary not fitting in RAM
Now if the dictionary is also so huge that it cannot fit one machine's RAM, then this problem cannot be solved with one machine.

Multiple machines are required which will count the word frequency after loading pieces of file.
But if the file is equally divided among different machines, then results of individual machines will need to be merged.
This is so because same word may be present in different pieces of the file.

Plus, the full dictionary would be required on each machine which is again not possible due to huge size of dictionary.


This can be solved by using distributed hashing.
Use word.hashCode() % numProcessingMachines to get the machine number which will process that word.
This approach will evenly distribute all the words on all the processing machines and can even be done in parallel on chunks of file.
Each machine will roughly receive an equal number of words and will also contain only a chunk of the dictionary.

After this step, we need to find K most frequent words whose frequencies are already present on the processing machines.
Take 2 machines at a time and find their K most frequent words by using a max-heap.
numProcessingMachines/2 tasks can do this in parallel.
Then again merge these K heaps, 2 at a time until only one heap is left.

You have the K most frequent words of this extremely huge file and a comparably huge dictionary.

Related: Find the k most frequent words from a file
Read full article from Find K most frequent word in a really huge file - PrismoSkills

Three increasing numbers such that i<j<k and arr[i]<arr[j]<arr[k] - PrismoSkills

Three increasing numbers such that i
Puzzle: Given an array of integers, find three indexes i,j,k such that i<j<k and arr[i]<arr[j]<arr[k]


Solution: 
As always, solving a smaller problem always sheds more light on solving the bigger problem.
If only two such variables were to be found, then its pretty simple.
Just keep track of the minimum element till now and whenever a higher element is found, print the pair.
Note that the problem is to find just any one such pair, not all the pairs.

Similarly, to find any one such triplet, we have to keep track of two minimums - arr[i] and arr[j] till arr[k] is found.
However, after two minimums have been selected and a new all-time minimum is found, how to handle that?
It is important to handle this all-time minimum because all the remaining numbers may be smaller than the current two minimums but may be larger than this all-time minimum.
For example:

    [ 20, 30, 5, 6, 1, 7 ]
               ¶cursor
    current-series = 20,30
    new minimum    = 5

This is solved by storing this new minimum as a potential start of a new series.
If another number is found which is less than the series started by current two minimums but is larger than potential minimum, then we can discard the current series in favor of current number and the previous all-time minimum.
Read full article from Three increasing numbers such that i

All permutations of a string - PrismoSkills

All permutations of a string - PrismoSkills
static void permute(char[] s, int i)
{
    if (i==s.length-1)
    {
        count++; // count no of words output and print the permutation.
        System.out.println(count + ") " + new String(s));
        return;
    }
    int curr = i;
    for (; i<s.length; i++)
    {
        swap (s, i, curr);
        permute (s, curr+1);
        swap (s, i, curr);
    }
}
Code to handle duplicate characters

To handle duplicate characters, we need to use a hash-set which will make sure a character already used in an index does not come there again.
This code works for non-repeated characters too.

void permute(char[] s, int i)
{
    if (i==s.length-1)
    {
        count++;
        System.out.println(count + ") " + new String(s));
        return;
    }
    HashSet<Character> charsDone =
        new HashSet<Character> (); //  <== initialize a hash-set at each recursion level
    int curr = i;
    for (; i<s.length; i++)
    {
        if (charsDone.contains(s[i])) //  <== if char is used, do not re-process it
            continue;
        charsDone.add(s[i]);
        swap (s, i, curr);
        permute (s, curr+1);
        swap (s, i, curr);
    }
}
http://www.geeksforgeeks.org/permutations-string-using-iteration/

Recursion is always costly and iteration is preferred. Below are steps of iterative approach.

1. Find no of permutations of the string by calculating value of n!. Then use this value to iterate.
2. Store the original string in an auxiliary string and use that string to do the math.
3. Fix the first position(character), and swap all the j’th and (j+1)’th characters till (n-1)!.
4. At the end of first (n-1)! all the (n-1)th characters will be permuted.
5. Now again store the original string to the auxiliary string and swap i’th and (i+1)’th characters and repeat the 3rd and 4th process.

Concept Used : We keep swapping a character only till it reaches the end

1. Fix ‘a’. Swap ‘b’ with its next neighbors till b reaches the end.
   ( “acbd”, “acdb”)
2. Now ‘c’ will be at the 2nd position, do the same thing with it.
   ( “adcb”, “adbc”)
3. Now ‘d’ will be at the 2nd position, do the same thing with it.
   ( “abdc”, “abcd”)
4. All 6 i.e., (4!/4)permutations of the first cycle obtained.
5. Repeat the above process by bringing swapping ‘a’ with ‘b’
6. The new string to “play” will be “bacd”.

int fact(int n)

{

    return (n==1)? 1 : n*fact(n-1);

}

void printPermutation(string s)

{

    // Find length of string and factorial of length

    int n = s.length();

    int fc = fact(n);

 

    // Point j to the 2nd position

    int j = 1;

 

    // To store position of character to be fixed next.

    // m is used as in index in s[].

    int m = 0;

 

    // Iterate while permutation count is

    // smaller than n! which fc

    for (int perm_c = 0; perm_c < fc; )

    {

        // Store perm as current permutation

        string perm = s;

 

        // Fix the first position and iterate (n-1)

        // characters upto (n-1)!

        // k is number of iterations for current first

        // character.

        int k = 0;

        while (k != fc/n)

        {

            // Swap jth value till it reaches the end position

            while (j != n-1)

            {

                // Print current permutation

                cout << perm << "\n";

 

                // Swap perm[j] with next character

                swap(perm[j], perm[j+1]);

 

                // Increment count of permutations for this

                // cycle.

                k++;

 

                // Increment permutation count

                perm_c++;

 

                // Increment 'j' to swap with next character

                j++;

            }

 

            // Again point j to the 2nd position

            j = 1;

        }

 

        // Move to next character to be fixed in s[]

        m++;

 

        // If all characters have been placed at

        if (m == n)

           break;

 

        // Move next character to first position

        swap(s[0], s[m]);

    }

}

http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

Algorithm Paradigm: Backtracking
Time Complexity: O(n*n!) Note that there are n! permutations and it requires O(n) time to print a a permutation.

/* Function to swap values at two pointers */

void swap(char *x, char *y)

{

    char temp;

    temp = *x;

    *x = *y;

    *y = temp;

}

 

/* Function to print permutations of string

   This function takes three parameters:

   1. String

   2. Starting index of the string

   3. Ending index of the string. */

void permute(char *a, int l, int r)

{

   int i;

   if (l == r)

     printf("%s\n", a);

   else

   {

       for (i = l; i <= r; i++)

       {

          swap((a+l), (a+i));

          permute(a, l+1, r);

          swap((a+l), (a+i)); //backtrack

       }

   }

}

    permute(str, 0, n-1);
http://www.geeksforgeeks.org/permutations-of-a-given-string-using-stl/

void permute(string str, string out)

{

    // When size of str becomes 0, out has a

    // permutation (length of out is n)

    if (str.size() == 0)

    {

        cout << out << endl;

        return;

    }

 

    // One be one move all characters at

    // the beginning of out (or result)

    for (int i = 0; i < str.size(); i++)

    {

        // Remove first character from str and

        // add it to out

        permute(str.substr(1), out + str[0]);

 

        // Rotate string in a way second character

        // moves to the beginning.

        rotate(str.begin(), str.begin() + 1, str.end());

    }

}

We can use next_permute() that modifies a string so that it stores lexicographically next permutation. If current string is lexicographically largest, i.e., “CBA”, then next_permute() returns false.

We first sort the string, so that it is converted to lexicographically smallest permutation. Then we one by one call next_permutation until it returns false.

void permute(string str)

{

    // Sort the string in lexicographically

    // ascennding order

    sort(str.begin(), str.end());

 

    // Keep printing next permutation while there

    // is next permutation

    do {

       cout << str << endl;

    } while (next_permutation(str.begin(), str.end()));

}

Read full article from All permutations of a string - PrismoSkills