Given an Array of Strings . Write a program to find the longest word made of other words efficiently ?

Given two arrays [5 6 2 8 1] or [4 7 9 2 4]. you have to find possible pairs where sum of numbers in both arrays of a pair is equal....eg for the first case it will be [5 6] and [2 8 1] efficiently .

Use Google Chrome For Better View of Contents on Blog :)

Dear Readers,

                              I am getting regular suggestion & useful comments from many geeks to re-arrange the question according to type, i will try to do this asap i get time as i have to edit HTML Code & also some  people are saying that contents are good but unable to view them. for this problem try Google Chrome Until I change the GUI & edit Html Code.

Thanks  For Giving Suggestion to Solving Problems Efficiently 

Happy Coding

Shashank !!!

Find the smallest number expressible as the sum of cubes of two numbers in two different ways. Indeed, 10^3 + 9^3 =12^3+1^3=1729 , Do It Efficiently

Problem:
A mathematician G. H. Hardy was on his way to visit his collaborator S. Ramanujan an who was in the hospital. Hardy remarked to Ramanujan that he traveled in taxi cab number 1729 which seemed a dull one and he hoped it was not a bad omen. To this, Ramanujan replied that 1729 was a very interesting number-it was the smallest number expressible as the sum of cubes of two numbers in two different ways. Indeed,
103 + 93 =123 + 1 3 二1729.

Hint: This problem is very similar to another very popular problem that is asked in interviews. You are given a  η ×η matrix in which both rows and columns are sorted in ascending order and you are supposed
to find a given number in the matrix.


Algorithm:
In this case, we are essentially looking for an implicit matrix A such that A(i,j) =i^3十j^3. In our case, the matrix will have n^1/3 rows and columns and this matrix of size n^1/3 * n^1/3 we try to search k=i^3+j^3 isn't it  ans algorithms for searching for a number in such a matrix that are linear in the number of rows.

One approach is to start by comparing x to An,1. If  x = An ,l , stop.Otherwise, there are two cases:
- x < A1,n in which case x is less than element at Column n at 1,n position. which mean we can escape whole row itself . we decrement column pointer to left.e.g. previous column.
- x > A1,n , in which case if x > a[1][n] is greater than it will be greater then all elements in Row 1.. we increment the row pointer to next row.


Efficient Solution:
Here is the Pseudo Code For The Same.
int IsNumberEqualstoSumeTwoCubes(int n)
{
       int row=Ceil(Pow(n,1/3));// Pow Has Complexity of O(logn) Ceil(1729)=577
       int column=row;
       int i=0;int j=column;
      while(i<row && j>=0)
     {
               int m=i*i*i+j*j*j;
               if(m==n)
                   return 1; // print i^3 and j^3 these are two such numbers
              else if ( m < n)
               i++;
              else
               j--;
      }
return 0; //such number DNE
}

Complexity Analysis:
In either case, we have a matrix with η fewer elements to search. In each iteration, we remove a row or a column, which means we inspect 2η-1 elements.


We claim that our algorithm that solves the matrix search problem will have to compare x with each of the 2n-l elements shown (i.e the diagonal elements (in case of column element matching )and  the elements immediately below them (in case of row elements matching )and this is obvious just draw a diagram in which both row & column are in sorted order & try to run the above algorithm ).
Call these elemmts the # elements..
Comparing x with any other elements in matrix does not eliminate the any of the # elements.we can easily Proof this by Contradiction:Suppose X algorithm doesn't compare x with  any of the above # elements.
then we could make that element x ( instead of x-1 got to prev. column  or x+1 go to next row.).hence we will get wrong result.

Above Algorithm Really Requires Deep Understanding of Young_tableau :)

Time Complexity O(row+column)=O(N^1/3+N^1/3)=O(2*N^1/3)=O(N^1/3)
Space Complexity O(1)

Get Rid Off Suffix Tree !!!!! An Online Compilation of Helpful Tutorial

Excellent Study Material For Understanding Algorithms & implementing Suffix Tree

1.Suffix Tree Wikipedia

2. A Good Explication

3. Its Awesome Suffix Tree By Sahni

4. Check These Strings

5. String Search Algorithms

6.http://apps.topcoder.com/forums/?module=RevisionHistory&messageID=1171511

7.http://www.stanford.edu/class/cs97si/suffix-array.pdf

Application of Suffix Tree

1.Longest repeated substring problem:

http://en.wikipedia.org/wiki/Longest_repeated_substring_problem

The longest repeated substring problem is finding the longest substring of a string that occurs at least twice. This problem can be solved in linear time and space by building a suffix tree for the string, and finding the deepest internal node in the tree. The string spelled by the edges from the root to such a node is a longest repeated substring. The problem of finding the longest substring with at least k occurrences can be found by first preprocessing the tree to count the number of leaf descendants for each internal node, and then finding the deepest node with at least k descendants.

By from Sartaj Sahni

Find the longest substring of S that appears at least m > 1 times. This query can be answered in O(|S|) time in the following way:
(a) Traverse the suffix tree labeling the branch nodes with the sum of the label lengths from the root and also with the number of information nodes in the subtrie. (b) Traverse the suffix tree visiting branch nodes with information node count >= m. Determine the visited branch node with longest label length.
Note that step (a) needs to be done only once. Following this, we can do step (b) for as many values of m as is desired. Also, note that when m = 2 we can avoid determining the number of information nodes in subtries. In a compressed trie, every subtrie rooted at a branch node has at least two information nodes in it.
Note that step (a) needs to be done only once. Following this, we can do step (b) for as many values of m as is desired. Also, note that when m = 2 we can avoid determining the number of information nodes in subtries. In a compressed trie, every subtrie rooted at a branch node has at least two information nodes in it.
2. Pattern Searching/Sub-String Searching 
Searching for a substring, pat[1..m], in txt[1..n], can be solved in O(m) time (after the suffix tree for txt has been built in O(n) time).
3. Longest Repeated Substring 
4. Longest Common Subsequence 
5. Longest Palindrome
http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

http://www.allisons.org/ll/AlgDS/Tree/Suffix/

Add a special ``end of string'' character, e.g. `$', to txt[1..n] and build a suffix tree; the longest repeated substring oftxt[1..n] is indicated by the deepest fork node in the suffix tree, where depth is measured by the number of characters traversed from the root, i.e., `issi' in the case of `mississippi'. The longest repeated substring can be found in O(n) time using a suffix tree.
The longest common substring of two strings, txt1 and txt2, can be found by building a generalized suffix tree for txt1 andtxt2: Each node is marked to indicate if it represents a suffix of txt1 or txt2 or both. The deepest node marked for both txt1and txt2 represents the longest common substring.
Equivalently, one can build a (basic) suffix tree for the string txt1$txt2#, where `$' is a special terminator for txt1 and `#' is a special terminator for txt2. The longest common substring is indicated by the deepest fork node that has both `...$...' and `...#...' (no $) beneath it.
(Try it using the HTML FORM above.)

Note that the `longest common substring problem' is different to the `longest common subsequence problem' which is closely related to the `edit-distance problem': An instance of a subsequence can have gaps where it appears in txt1 and in txt2, but an instance of a substring cannot have gaps.
A palindrome is a string, P, such that P=reverse(P). e.g. `abba'=reverse(`abba'). e.g. `ississi' is the longest palindrome in `mississippi'. The longest palindrome of txt[1..n] can be found in O(n) time, e.g. by building the suffix tree for txt$reverse(txt)# or by building the generalized suffix tree for txt and reverse(txt).
(Try it.)

Others 

--

Some Awesome Algorithms/Codes For Suffix Tree Implementation

1.by Dr. Sartaj Sahni (CISE Department Chair at University of Florida)

2. by Lloyd Allison

3. NIST Dictionary

4.  ANSI C implementation of a Suffix Tree

5.  Generic suffix tree library written in C

6.Perl binding to libstree

7.# a faster generic suffix tree library written in C (uses arrays instead of linked lists)

8. Python binding to Strmat

Given an array A[] and a integer num. Find four no.s in the array whose sum is equal to given num.

Algorithm :

Naive Algorithm Will O(N^4) Use Four Loop & keep Checking for all four elements.its so Naive ,easily understood-able..

Algorithm:
Little Efficient O(N^3).
Sort the input array. O(nlogn)
Then take 4 pointers p1,p2,p3,p4 where
0<=p1<=n-3               1st loop
p1+1<=p2<=n-2       1st inner loop                                                    

in loop set p3=p1+ & p4=n-1
( e.g. Take 3 Pointer Pointing to three successive indexes from starting  & 4th Pointer pointing to n-1th position. )
Now use same algo we used to check for two elements in sorted array whose sum equals to given element or not 3rd Inner Loop

Most Efficient O(N^2)

Algorithm:
Create an array of all possible PAIR sums..that would be done in O(n^2)
Sort the Above array of size n^2 that can be done in.O(n^2log(n)) .
Then Search this array for two pairs..that sum to the required value..this can be done by maintaining two pointer One at the starting index..and other at the highest index..and moving them accordingly..(if sum of pair exceeds given value..move up highest value pointer..else move down..lowest value pointer) .it Will take O(n)

Total Time Complexity Will be O(n^2logn) +O(nlogn) +O(n)=O(n^2logn).
Space Complexity O(N^2).

find the minimum number of platforms so that all the buses can be placed as per their schedule.

At a bus-station, you have time-table for buses arrival and departure. You need to find the minimum number of platforms so that all the buses can be placed as per their schedule.


Example

Bus         Arrival         Departure 
BusA        0900 hrs        0930 hrs
BusB        0915 hrs        1300 hrs
BusC        1030 hrs        1100 hrs
BusD        1045 hrs        1145 hrs

Algorithm

Its simple dynamic programming question that calculate the 

number of buses at station at any time(when a bus comes or 

leaves). Maximum number in that pool will be nothing but 

the maximum number of buses at the bus-station at any time

,which is same as max number of platforms required.

So first sort
all the arrival(A) and departure(D) time in an int array. 

Please save the corresponding arrival or departure in the 

array also.Either you can use a particular bit for this 

purpose or make a structure. After sorting our array will

look like this: 

0900    0915    1930    1030    1045    1100    1145    1300
A       A       D       A       A       D       D       D

Now modify the array as put 1 where you see A and -1 where you see D.
So new array will be like this:
1              1            -1              1               1            -1            -1              -1


And finally make a cumulative array out of this:
1            2              1               2                3            2               1                0


Your solution will be the maximum value in this array. Here it is 3.


I think that code for this will not be complex so I am skipping that part.
The complexity of this solution depends on the complexity of sorting.


Also we don not need to create a cumulative array or an array with 1 and -1;
you just need a counter (cnt) initialized at '0'. Whenever, you find an 'A' in
arrival-departure array, increment cnt by 1. Compare it with maximum value (max);
if it is greater than max, make max equal to cnt. If you get a 'D' in arrival-departure
array, decrement cnt by 1. At the end, return 'max'.

Time Compelxity O(nlogn)

Space Complexity O(1) 

find at what time the maximum number of people will be in the party .

Found This Question on One of the Forum :D & posting here as thought it  seems to be something interesting :) There is a list containing the checkin and checkout time of every person in a party . The checkin time is in ascending order while the checkout is random .

Eg:

                       Check_in                Check_out

Person 1             8.00                          9.00

Person 2             8.15                          8.30

Person 3             8.30                          9.20

and so on ...Now , give an optimized solution to find at what time the maximum number of people will be in the party . 

Algorithm

It has the same Algorithm  That  We have been used to solve Bus-Station Problem :)

Time Compelxity O(nlogn)

Space Complexity O(1) 

Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen.

Basic Idea is run around random number generator & we need to take care of that so before moving forward we need to understand how random number generation works 

lets say you wants to generate random number between i to j e.g. [ i,j ). One standard pattern for accomplishing this is:

   (int)(Math.random() * ((Max - Min) 

This returns a value in the range [0,Max-Min).

Now you need to shift this range up to the range that you are targeting. You do this by adding the Min value.

     Min + (int)(Math.random() * ((Max - Min)

But, this is still doesn't include Max and you are getting a double value. In order to get the Max value included, you need to add 1 to your range parameter (Max - Min) and then truncate the decimal part by casting to an int. This is accomplished via:
And there you have it. A random integer value in the range [Min,Max], or per the example [5,10]:

Min + (int)(Math.random() * ((Max - Min) + 1)) 

The java Math library function Math.random() generates a double value in the range [0,1). Notice this range does not include the 1.

In order to get a specific range of values first you need to multiply by the magnitude of the range of values you want covered.
For example if you want [5,10] you need cover 5 integer values so you use
You now will get a value in the range [Min,Max). Following our example, that means [5,10):
Math.random() * ( Max - Min )
Math.random() * 5 This would return a value in the range [0,5)
Min + (Math.random() * (Max - Min))
5 + (Math.random() * (10 - 5))
Min + (int)(Math.random() * ((Max - Min) + 1))
5 + (int)(Math.random() * ((10 - 5) + 1))

Algorithm:
 
Our first instinct on this problem might be to randomly pick elements 
from the array and put them into our new subset array. But then, what 
if we pick the same element twice? Ideally, we’d want to somehow “shrink” 
the array to no longer contain that element. Shrinking is expensive though
because of all the shifting required.
 
Instead of shrinking / shifting, we can swap the element with an element 
at the beginning of the array and then “remember” that the array now only 
includes elements j and greater. That is, when we pick subset[0] to be 
array[k], we replace array[k] with the first element in the array. When 
we pick subset[1], we consider array[0] to be “dead” and we pick a random
element y between 1 and array.size(). We then set subset[1] equal to 
array[y], and set array[y] equal to array[1]. Elements 0 and 1 are
Solution:
 
class Uniform_RandomNumberGenerator
{
 /* Random number between lower and higher, inclusive */
  public static int rand(int lower, int higher)
 {
     return lower + (int)(Math.random() * (higher - lower + 1));
 }

 /* pick M elements from original array. Clone original array so that
 * we don’t destroy the input. */

 public static int[] pickMRandomly(int[] original, int m)
{
 int[] subset = new int[m];
 int[] array = original.clone();
  for (int j = 0; j < m; j++)
  {
   int index = rand(j, array.length - 1);
   subset[j] = array[index];
   array[index] = array[j]; // array[j] is now “dead”
  }
   return subset;
}

public static void main(String a[])

{  int ar[]=new int[]{2,5,3,1,4};
   int br[]=new int[5];
   br=pickMRandomly(ar,5);//n-1
      System.out.println();
   for(int i=0;i<br.length;i++)
   System.out.print(br[i] + " " );
}

}
Time Complexity: O(N)
Space Complexity: O(N)
Run Here https://ideone.com/RcBmx 
 

Write a method to shuffle a deck of cards. It must be a perfect shuffle - in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect.

Basic Idea is run around random number generator & we need to take care of that so before moving forward we need to understand how random number generation works 

lets say you wants to generate random number between i to j e.g.
[ i,j ) excluding upper limit. One standard pattern for accomplishing this is:

Min + (int)(Math.random() * ((Max - Min) + 1))

The java Math library function Math.random() generates a double value in the range [0,1). Notice this range does not include the 1.


In order to get a specific range of values first you need to multiply by the magnitude of the range of values you want covered.

Math.random() * ( Max - Min )

This returns a value in the range [0,Max-Min).


For example if you want [5,10] you need cover 5 integer values so you use

Math.random() * 5 This would return a value in the range [0,5)

Now you need to shift this range up to the range that you are targeting. You do this by adding the Min value.

Min + (Math.random() * (Max - Min))

You now will get a value in the range [Min,Max). Following our example, that means [5,10):

5 + (Math.random() * (10 - 5))

But, this is still doesn't include Max and you are getting a double value.
In order to get the Max value included, you need to add 1 to your range parameter (Max - Min) and then truncate the decimal part by casting to an int. This is accomplished via:

Min + (int)(Math.random() * ((Max - Min) + 1))

And there you have it. A random integer value in the range [Min,Max],
or per the example [5,10]:

5 + (int)(Math.random() * ((10 - 5) + 1))

Algorithm:

This is a very well known algorithm known as Knuth-Shuffle. If you aren’t one

of the lucky few to have already know this algorithm, read on.Let’s start 

with a brute force approach: we could randomly selecting items and put them 

into a new array. We must make sure that we don’t pick the same item twice 

though by somehow marking the node as dead.
 

Array: [1] [2] [3] [4] [5]
Randomly select 4: [4] [?] [?] [?] [?]
Mark element as dead: [1] [2] [3] [X] [5]
 

The tricky part is, how do we mark [4] as dead such that we prevent that 

element from being picked again? One way to do it is to swap the now-dead [4]

with the first element in the array:
 

Array: [1] [2] [3] [4] [5]
Randomly select 4: [4] [?] [?] [?] [?]
Swap dead element: [X] [2] [3] [1] [5]
 

Array: [X] [2] [3] [1] [5]
Randomly select 3: [4] [3] [?] [?] [?]
Swap dead element: [X] [X] [2] [1] [5]
 

By doing it this way, it’s much easier for the algorithm to "know" that the 

first k elements are dead than that the third, fourth, nineth, etc elements 

are dead. We can also optimize this by merging the shuffled array and the 

original array.
 

Randomly select 4: [4] [2] [3] [1] [5]
Randomly select 3: [4] [3] [2] [1] [5]

Working Solution: Its Totally Worthy & Pure Shuffle Used in Our Music Player

class random
{
 
public static void shuffleArray(int[] cards) 
{
 int temp, index;int ar[]=new int[cards.length];
 int count=0;
 for (int i = 0; i < cards.length; i++)
 {
 index = (int) (Math.random() * (cards.length - i)) + i; 
//generate random index between i to n here we don't need to add 1 in last 
//to range as array indexes start at 0 if we add 1 to cards.length-i then 
//we might get index > n-1 which throws array out of index bound exception
 ar[count++]=index;
 temp = cards[i];
 cards[i] = cards[index];
 cards[index] = temp;
 }
  
 for(int i=0;i<ar.length;i++)
   System.out.print(ar[i] + " ");
}
 
public static void main(String a[])
 
{  int ar[]=new int[]{1,2,3,4,5};
    shuffleArray(ar);
      System.out.println();
   for(int i=0;i<ar.length;i++)
   System.out.print(ar[i] + " " );
}
 
}
 

Time Complexity: O(N)

Space Complexity: O(1)

Run Here https://ideone.com/UTk9V 

               https://ideone.com/B0YEn - Read from Consol