Interviewstreet Amazon India - Meeting Schedule

Given M busy-time slots of N people, You need to print all the available time slots when all the N people can schedule a meeting for a duration of K minutes.

Event time will be of form HH MM ( where 0 <= HH <= 23 and 0 <= MM <= 59 ), K will be in the form minutes
An event time slot is of form [Start Time, End Time ) . Which means it inclusive at start time but doesn’t include the end time.

Sample Input:                                                       Sample Output:

5 120                                                                    00 00 09 00

16 00 17 00                                                          17 00 20 45

10 30 15 30

20 45 22 15

10 00 13 25

09 00 11 00

Approach

The time is expressed as hh mm, and we have 1440 minutes in a day. So we can create a integer array of size 1440, with elements initialized to 0. Now read each value of the busy-time and set the corresponding slot in the integer array to 1s. For instance 01:28 is at array position 88. Since its 1 hour and 28 minutes. 

Once all the busy-time slots are mapped to the integer array, then you can find the free slot of given duration. So to find a free slot, start from integer array position 0 and search for consecutive 0s of length atleast 'duration'. All such durations are the free durations. 

Solution

	import java.text.DecimalFormat;
	import java.text.NumberFormat;
	import java.util.ArrayList;
	import java.util.List;
	/**
	* Meeting Schedule calculator
	*
	* Output
	* 0000 - 0900
	* 1700 - 2045
	* @author raju rama krishna
	*
	*/
	public class MeetingPlanner {
	/**
	* @param args
	*/
	public static void main(String[] args) throws Exception {
	List<String> slots = CalendarSlot.getBusySlots();
	int n = 24 * 60; // 24 hours * 60 min
	int[] watch = new int[n];
	String[] sArr = new String[2];
	for( String s: slots ) {
	sArr = s.split(" ");
	String start = sArr[0];
	int startMin = Integer.parseInt(start.substring(2)) + Integer.parseInt(start.substring(0, 2))*60;
	String end = sArr[1];
	int endMin = Integer.parseInt(end.substring(2)) + Integer.parseInt(end.substring(0, 2))*60;
	for(int i=startMin; i <= endMin; i++) {
	watch[i] = 1;
	}
	}
	int duration = 120;
	int curr = watch[0];
	boolean free = ( curr == 0 )? true: false;
	int i = 0;
	int j = 0;
	while( i < n-1 ) {
	i++;
	if(watch[i] == curr ) {
	continue;
	} else {
	if( free && (i-j) >= duration ) {
	System.out.println(getTime(j) + " - " +getTime(i));
	}
	j = i-1;
	curr = watch[i];
	free = !free;
	}
	}
	}
	private static String getTime( int val ) {
	int h = val/60;
	int m = val%60;
	NumberFormat formatter = new DecimalFormat("00");
	return formatter.format(h) + formatter.format(m);
	}
	}
	class CalendarSlot {
	private static List<String> filledSlot = new ArrayList<String>();
	public static List<String> getBusySlots() {
	filledSlot.add("1600 1700");
	filledSlot.add("1030 1530");
	filledSlot.add("2045 2215");
	filledSlot.add("1000 1325");
	filledSlot.add("0900 1100");
	return filledSlot;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Interview Street - pairs of numbers that have a difference of K

Given N numbers , [N<=10^5] we need to count the total pairs of numbers that have a difference of K

Input Format:
1st line contains N & K (integers).
2nd line contains N numbers of the set. All the N numbers are assured to be distinct.
Output Format:
One integer saying the no of pairs of numbers that have a diff K.

Sample Input #00:
5 2
1 5 3 4 2

Sample Output #00:3

Solution
This problem can be solved with hashing or by sorting.I have taken the sorting approach.
Sort the contents of the array in (n log n) time. Then for each number in the array, do a binary search to see if the num+k exists in the array.

In hashing approach, maintain a hashtable. As you iterate each number X, check if X+k exists in the hashtable with 1 value. If its there then you have a pair. Else put the key (X+k) and value '0'. 

	import java.io.BufferedReader;
	import java.io.InputStreamReader;
	import java.util.ArrayList;
	import java.util.Collections;
	import java.util.List;
	/**
	* Interview Street - Find pairs of numbers whose difference is k
	* Given N numbers , [N<=10^5] we need to count the total pairs of numbers that have a difference of K. [K>0 and K<1e9]
	*
	* @author raju rama krishna
	*
	*/
	public class DiffNumbers {
	/**
	* @param args
	*/
	public static void main(String[] args) throws Exception {
	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	String line1 = in.readLine();
	String line2 = in.readLine();
	int n = Integer.parseInt(line1.split(" ")[0]);
	int k = Integer.parseInt(line1.split(" ")[1]);
	List<Integer> list = new ArrayList<Integer>();
	String[] sArr = line2.split(" ");
	for( String s : sArr ) {
	list.add(Integer.parseInt(s));
	}
	//Sort the array
	Collections.sort(list);
	int num = list.get(0);
	int l = 1;
	int h = n-1;
	int i = 1;
	int count = 0;
	while( i < n ) {
	while( l < h ) {
	int mid = (l+h)/2;
	int val = list.get(mid);
	if( val-num < k ) {
	break;
	}
	if( val == num+k) {
	count++;
	break;
	} else if( val < num+k ) {
	l = mid;
	} else {
	h = mid;
	}
	}
	num = list.get(i);
	i++;
	l = i;
	h = n-1;
	}
	System.out.println(count);
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Interview Street - Indian Startup - Matrix Multiplication

Mr. Evan has given to his students an assignment where they need to multiply two boolean matrices and write the resultant matrix. Boolean matrix multiplication is done in the same way as standard matrix multiplication except for in the resultant matrix any entry which is not zero is treated as one.

Mr. Evan is tired of checking the correctness of their results, so he has asked you for help.

Given three N X N boolean matrices A, B and C, you need to write a code to determine whether A x B = C.

NOTE: There need not be a deterministic algorithm so you need to come up with a better probabilistic algorithm to get accepted.

Matrix A

0 0 0 0 0

1 0 0 0 0

0 1 0 0 0

0 0 1 0 0

0 0 0 0 1

Matrix B 

1 0 0 0 0

0 0 0 0 0

0 1 0 0 0

1 0 0 0 0

0 0 0 0 0

Matrix C 

0 0 0 0 0

1 0 0 0 0

0 0 0 0 0

0 1 0 0 0

0 0 0 0 0

Approach-

Here we don't need to do actual multiplication. We can identify all matrix A elements having 1's and matrix B elements having 1's. So in the above - A has 1 in (4, 3) and B in (3, 2). Here A col and B row are same (3). So the resultant matrix C would have 1 in (4, 2). 

Solution

	import java.util.ArrayList;
	import java.util.List;
	/**
	* Interview Street - Indian Startups
	*
	* @author raju rama krishna
	*
	*/
	public class MatrixMultiplication {
	/**
	* @param args
	*/
	public static void main(String[] args) {
	int n = 5;
	int a[][] = { {0, 0, 0, 0, 0},
	{1, 0, 0, 0, 0},
	{0, 1, 0, 0, 0},
	{0, 0, 1, 0, 0},
	{0, 0, 0, 0, 1} };
	int b[][] = { {1, 0, 0, 0, 0},
	{0, 0, 0, 0, 0},
	{0, 1, 0, 0, 0},
	{1, 0, 0, 0, 0},
	{0, 0, 0, 0, 0} };
	int c[][] = { {0, 0, 0, 0, 0},
	{1, 0, 0, 0, 0},
	{0, 0, 0, 0, 0},
	{0, 1, 0, 0, 0},
	{0, 0, 0, 0, 0} };
	List<Integer> aRows = new ArrayList<Integer>();
	List<Integer> bRows = new ArrayList<Integer>();
	List<Integer> cRows = new ArrayList<Integer>();
	List<Integer> aCols = new ArrayList<Integer>();
	List<Integer> bCols = new ArrayList<Integer>();
	List<Integer> cCols = new ArrayList<Integer>();
	for( int i = 0; i < 5; i++ ) {
	for ( int j = 0; j < 5; j++ ) {
	if( a[i][j] == 1 ) {
	aRows.add(i);
	aCols.add(j);
	}
	if( b[i][j] == 1 ) {
	bRows.add(i);
	bCols.add(j);
	}
	if( c[i][j] == 1 ) {
	cRows.add(i);
	cCols.add(j);
	}
	}
	}
	boolean result = true;
	int total = 0;
	for( int i = 0; i < aCols.size(); i++ ) {
	int col = aCols.get(i);
	if( bRows.contains(col)) {
	int x = aRows.get(i);
	int y = bCols.get(bRows.indexOf(col));
	if( cRows.contains(x) && cCols.indexOf(y) == cRows.indexOf(x)) {
	total++;
	} else {
	result = false;
	break;
	}
	}
	}
	if( result && cRows.size() == total ) {
	System.out.println("True");
	} else {
	System.out.println("False");
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

InterviewStreet Puzzle for Startups India

This question was posted in the InterviewStreet for India Startups. InterviewStreet regularly runs contests were the topics are related to coding, algorithms and puzzles. The toppers of the contest get a chance to apply for a job with the startups. This question is taken from the Indian startups round.

Alice and Bob are playing a game. This game starts with two piles of n1 and n2 chips. They play alternatively and Alice starts first.
In his/her turn a person has to remove one of the piles and split the other pile into two piles, these two new piles need not be of same size. The person who cannot make a move in his turn loses.
Write a program which given n1 and n2 finds the winner. Assume both the players play optimally.

Approach

Visualizing this kind of a puzzle is easy with Mathematical Induction. So take a smaller value and gradually build up. 

Example 1:-

Start with (2, 1).

Alice keeps 1, and splits the 2.

Bob gets (1,1). Since he can keep 1, but cannot keep the other 1, he looses.

Example 2:-

Start with (2, 2)

Alice keeps 2, and splits the other 2.

Bob gets (1,1). Since he can keep 1, but cannot keep the other 1, he looses.

Example 3:-

Start with (3, 2)

Alice keeps 3, and splits the 2.
Bob gets (1,1). Since he can keep 1, but cannot keep the other 1, he looses.

Example 4:-

Start with (3, 3)

Alice keeps 3, and splits the other 3.
Bob gets (2,1). Bob keeps 1 and splits 2.
Alice gets (1,1) she looses.

Example 5:-
Start with (8, 1)
Alice keeps 1, and splits the 8
Bob gets (5, 3). He cannot keep 5 and split 3, since in that case he will have to provide (2, 1) in which case he will loose immediately. So he splits 5. To split 5, he cannot split it to (3, 2) as Alice will keep 3 and split the 2 as (1,1). In this case again Bob will loose. So to keep the game going he will split 5 as (4,1).
Alice gets (4,1). She keeps 1 and splits 4. There are 2 options (2, 2) and (3,1). But if she gives (2,2), in the next move Bob will provide her (1,1) and she will loose. So she splits (3,1).
Bob gets (3,1). He keeps 1 and has to split (2,1). So again he looses.

In example 5, instead of Alice splitting (5, 3), what if she split (4,4) or (6, 2). Well (6,2) is not possible, as she will loose immediately. Assume she splits (4, 4)
Bob gets (4, 4). He can split as (2, 2) which he won't do. So he will split (3, 1).
Alice gets (3,1). She keeps 1 and splits ( 2, 1). She will loose.

So splitting 8 as (5, 3) was a better move.

Example 6:-
Start with (10, 1).
Bob (5, 5)
Alice ( 4, 1)
Bob (3, 1)
Alice ( 2, 1) and wins

Start with (10, 1)
Bob (6, 4)
Alice (3, 1)
Bob (2, 1) and wins

Start with (10, 1)
Bob (6, 4)
Alice (3, 3)
Bob (2, 1) and wins

Solution:-
I have provided a solution which ensures the highest chances for Alice to win. Alice winning chances are when she gets atleast one input as even. For instance (10, 1) here 10 was even. She will split it into 2 odds - 5 and 5. This way she can ensure her winning. If she got (8, 1) then she can split (5, 3). If she got (8, 12) still she can split (5, 3). This way she can ensure the game is finished early.
If she gets (13, 1) that is the only option available is an odd, then Bob stands a winning chance. Still she can keep the game on by splitting into (12, 1).
The program prints the most optimized path favoring Alice.

	/**
	* Puzzle - india startup (interview street)
	*
	* @author raju rama krishna
	*
	*/
	public class Puzzle {
	static int i = 0;
	/**
	* @param args
	*/
	public static void main(String[] args) {
	String input = "7 9";
	int a = Integer.parseInt(input.split(" ")[0]);
	int b = Integer.parseInt(input.split(" ")[1]);
	printWinner( a, b);
	}
	private static void printWinner(int a, int b) {
	if( a > 0 && b > 0 ) {
	if(i % 2 == 0) {
	System.out.println("Alice Playing :" +a+"," +b);
	} else {
	System.out.println("Bob Playing :" +a+"," +b);
	}
	if( a == 1 && b == 1 ) {
	String winner = (i% 2 == 0)? "Bob" : "Alice";
	System.out.println("Winner: " +winner);
	}
	i++;
	// 1 value cannot be split
	if( a == 1 ) {
	if( b % 2 == 1 ) {
	printWinner( b-1, 1);
	} else {
	if( b == 2 ) {
	printWinner(1, 1);
	} else {
	if( (b/2)% 2 == 1 ) {
	printWinner(b/2, b/2);
	} else {
	printWinner( b/2+1, b/2-1);
	}
	}
	}
	} else if( b == 1 ) {
	if( a % 2 == 1 ) {
	printWinner( a-1, 1);
	} else {
	if( a == 2 ) {
	printWinner(1, 1);
	} else {
	if( (a/2)% 2 == 1 ) {
	printWinner(a/2, a/2);
	} else {
	printWinner( a/2+1, a/2-1);
	}
	}
	}
	}else if( a % 2 == 1 && b % 2 == 1 ) {
	//Both are odd
	int min = Math.min(a, b);
	printWinner( min-1, 1);
	} else if( a % 2 == 0 ) {
	if( a == 2 ) {
	printWinner(1, 1);
	} else {
	if( (a/2)% 2 == 1 ) {
	printWinner(a/2, a/2);
	} else {
	printWinner( a/2+1, a/2-1);
	}
	}
	} else if( b % 2 == 0 ) {
	if( b == 2 ) {
	printWinner(1, 1);
	} else {
	if( (b/2)% 2 == 1 ) {
	printWinner(b/2, b/2);
	} else {
	printWinner( b/2+1, b/2-1);
	}
	}
	}
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Facebook Question - Find the longest increasing subsequence

Problem
You are given an unsorted array of integers. In that array, find the longest increasing subsequence.
For eg. {1, 5, 3, 4, 6, 1, 2, 4, 8, 5 }
In the above, there are multiple increasing sequences:
{1,5}
{3,4}
{3,4,6}
{1,2}
{1,2,4}
{1,2,4,8}
Of the above, last one is the longest sequence.
Write a program to solve the above. It should be linear O(N) time.

Approach
Initialize an array of same length as input. Call it current array. Read the first element and store it in this array. Keep navigating the input array and if the current element is greater than the last element in the current array, then put the value into the current array. If the value is less than the last current array element, then we need to start again. So we need to reset the current array. But hold on, the current array that we have might be the  longest subsequence. So before resetting the array check if the current length of current array is the biggest we found ever. If so copy the array elements into the result array.

current array: {1, 0, 0, 0, 0, 0, 0, 0, 0, 0}
length: 1
maxlength:1

i=1, a[1] = 5 (increasing)
current array: {1, 5, 0, 0, 0, 0, 0, 0, 0, 0}
length: 2
maxlength: 2

i=2, a[2] = 3 (decreasing)
current array: {3, 0, 0, 0, 0, 0, 0, 0, 0, 0}
result: {1, 5}
length: 1
maxlength: 2

i=3, a[3] = 4 (increasing)
current array: {3,4, 0, 0, 0, 0, 0, 0, 0, 0}
result:{1,5}
length: 2
maxlength:2

Solution

	/**
	* Longest Increasing SubSequence
	* Input: 1 5 3 4 6 4 Output: 3 4 6
	*
	* @author raju rama krishna
	*
	*/
	public class LongestIncreasingSequence {
	/**
	* @param args
	*/
	public static void main(String[] args) {
	int[] a = {1, 5, 3, 4, 6, 1, 2, 4, 8, 5 };
	int[] b = new int[a.length];
	int[] c = new int[a.length];
	b[0] = a[0];
	int maxlen = 1;
	int len = 1;
	for(int i=1; i < a.length; i++) {
	if(a[i] > b[len-1]) {
	b[len++] = a[i];
	} else {
	if( len > maxlen ) {
	maxlen = len;
	c = b;
	b = new int[a.length];
	len = 1;
	b[0] = a[i];
	} else {
	b = new int[a.length];
	len = 1;
	b[0] = a[i];
	}
	}
	}
	//Found the maximum length subsequence
	if(len > maxlen) {
	c = b;
	}
	System.out.println("Longest Increasing Subsequence is of length :" +maxlen);
	for( int i = 0; i < maxlen; i++ ) {
	if( i == 0 ) {
	System.out.print("{" +c[i]+ ",");
	} else if( i == maxlen-1) {
	System.out.print( c[i] + "}");
	} else {
	System.out.print( c[i] + ",");
	}
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

FaceBook Question - Find a missing number in 1 Billion numbers

Problem -
Facebook has over 1 Billion users and each user is assigned a unique FacebookID. Assume that each FacebookID is a valid int. These FacebookIDs are written in a text file sequentially. When an user de-activates his account on Facebook, the corresponding FacebookID is deleted from the file.
Write a program to find a user who has deactivated his account.

Approach -
Assuming int is 32 bits the total number of positive values supported are - 4,294,967,296. So it can support 4.2 billion numbers. 

1. Bit Map approach - We use a BitMap (or a boolean array in java) with values initialized to 0 (or false). The size of the bitMap is 2^32. Read each FacebookID and set the corresponding bitMap index to 1 (or true). Once all the 1 billion numbers are read and the bitMap updated - search for a bitMap value which is 0 and that is the missing number. 
So lets analyze the memory requirement for this approach. To store a bitMap of 2^32 size means 2^29 bytes (since 1 byte is 2^3 bits). This 2^29 bytes translates to 512 MB RAM. How did I arrive at this number?  2^29 = 536,870,912
or 536,870,912/1024 KB = 524,288 KB
or 524,288/1024 MB = 512 MB
So what if we didn't have this much RAM capability?

2. Bucket Partition Method - Take square-root of 2^32, which translates to 2^16 (=65,536). Create an int[] of size 65,536. Lets call these buckets. So there are 65,536 buckets. Each bucket is responsible for 65,536 values. So the bucket0 manages values (0,1,2... 65535). And bucket1 manages (65536, 65537 .... 131,071). and so on. This way the last bucket which is bucket65535 manages the last set of numbers.
Read each FacebookID and find the corresponding bucket. So for instance if the id is 9 it translates to bucket0. Do not store the value in the bucket, just increment the bucket value. So essentially each bucket just holds a count of numbers that it encountered in its limit. Once all the facebookIDs are read and the bucket counts set, identify a bucket which is not equal to 65,536. Lets say the bucket number is 1. Which means, the missing number is between 65536 to 131071. Lets call this TargetBucket.
Now reset the bucket values to 0. Next, read the faceBookIDs once again, but this time check if the value is between 65536 to 131071. If it is set the corresponding bucket to 1. This time our bucket0 manages 65536, bucket1 manages 65537, bucket2 manages 65538 and so on. Once all the values are read and the buckets populated, find a bucket which has 0. That is the missing number.
So what was the memory requirement for this one? 
2^16 bits or 2^13 bytes or 8,192 bytes or 8 KB. Woow, amazingly less!!

Solution
I have created a program which basically simulates the bucket partition method but limits itself to 16 Million numbers (16,777,216 or 2^24). It generates a text file of 16 million numbers with a few numbers skipped. So my bucket size is 4096 (or 2^12).

	import java.io.BufferedReader;
	import java.io.BufferedWriter;
	import java.io.File;
	import java.io.FileReader;
	import java.io.FileWriter;
	/**
	* Find a missing number
	*
	* @author raju rama krishna
	*
	*/
	public class NumberGenerator {
	/**
	* @param args
	*/
	public static void main(String[] args) throws Exception {
	// TODO Auto-generated method stub
	File f = new File("c:\\tmp\\tmp.txt");
	BufferedWriter bw = new BufferedWriter(new FileWriter(f));
	int[] buckets = new int[4096]; //2^16
	int end = (int)Math.pow(2, 24) - 1;
	for( int i = 0; i <= end; i++ ) {
	if( i == 9837274 || i == 12778621 || i == 433667) {
	continue;
	}
	int j = getBucket( i );
	buckets[j] = buckets[j] + 1;
	bw.write(String.valueOf(i));
	bw.write("\n");
	}
	bw.close();
	// Get bucket which is not full
	int bucket = getTargetBucket( buckets );
	buckets = new int[4096];
	BufferedReader br = new BufferedReader(new FileReader(f));
	String s = br.readLine();
	int val = Integer.parseInt(s);
	boolean flag = false;
	int index = 0;
	while( s != null ) {
	val = Integer.parseInt(s);
	flag = isTargetBucket( bucket, val );
	if( flag ) {
	index = val - bucket*4096;
	buckets[ index ] = 1;
	}
	s = br.readLine();
	}
	br.close();
	for( int i=0; i<buckets.length; i++ ) {
	if( buckets[i] == 0 ) {
	System.out.println(bucket*4096 + i);
	break;
	}
	}
	}
	private static boolean isTargetBucket(int bucket, int val) {
	int start = bucket*4096;
	int end = start + 4096 - 1;
	if( val >= start && val <= end ) {
	return true;
	} else{
	return false;
	}
	}
	// Get the bucket number which contains less than 4096 numbers
	private static int getTargetBucket(int[] buckets) {
	int bucket = 0;
	for(int i = 0; i < buckets.length; i++) {
	if( buckets[i] < 4096 ) {
	bucket = i;
	break;
	}
	}
	return bucket;
	}
	private static int getBucket( int i ) {
	return (i/4096);
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Page Hits for WebSites and Blogs

Assume that you are building an Analytics Tool for a very popular site (like facebook). And the tool should capture the real time hits for the site and maintain a cumulative frequency. The site will be hit every second and you have to capture the details and show a summary like last 1 month 45,000 hits, last 1 week 20,000 hits, yesterday 1,200 hits and so on. You should also support range queries like 22,000 hits between 02/10/2012 to 21/02/2012.

Assume that you have stored the hits sequentially in an array. For eg.

3, 2, 0, 9, 2, 5, 1 

The above is the page hits for a 1 week period. The most natural way of calculating the total cumulative frequency is to sum up. It becomes-

3, 5, 5, 14, 16, 21, 22

So we know we received 22 hits in 1 week. Lets say we have data for last every hour like this and the data is stored for last 5 years. This is pretty huge data. Now if for some reason the frequency for day 2 is updated from 2 to 5. This impacts our frequency results table, so we have to recalculate the cumulative values for the 2nd day to 7th day. 

A better solution for this is Fenwick Tree (or Binary Indexed Tree). In this data structure each index position is expressed as a binary number. Lets consider 12. Its represented in binary as 0000 1100. The last set bit (from right to left) is at position 2 (with 0-indexed). Lets call this last set index of idx as lsi(idx). Each idx manages in the range [ idx to idx - 2^lsi(idx) + 1]. So in case of idx 12, the lsi(12) was 2. So it manages 9..12. The following chart provides the indexes and ranges.

1=1

2=1..2

3=3

4=1..4

5=5

6=5..6

7=7

8=1..8

9=9

10=9..10

11=11

12=9..12

13=13

For the below input:

{1,0,2,1,1,3,0,4,2,5,2,2,3}

The output tree is:

[1, 1, 2, 4, 1, 4, 0, 12, 2, 7, 2, 11, 3]

So if you observe, 12 is managing 9 to 12. So the values its managing are 2,5,2,2 (The tree is 1-indexed and not 0-indexed). The total sum is 11. Similarly, index 6 manages 5..6. So its values are 1,3 summing up 4.

There is an easy way to find this - which is bit manipulation ( i have used left shift and right shift ).

Updating an index value is simple. Identify the impacted indexes and add the value.

To calculate the range values, use Tree[j] - Tree[i]. Please see the code snippet below.

	/**
	* Utility to compute cummulative page hits for a site
	* Each site has n pages and the pages will be continously accessed.
	* In real-time get the page hits and total hits for the site.
	*
	* This uses Bit Indexed Tree or Fenwick tree
	*
	* @author raju rama krishna
	*
	*/
	public class PageHits {
	/**
	* @param args
	*/
	public static void main(String[] args) {
	int hits[] = {1,0,2,1,1,3,0,4,2,5,2,2,3};
	int tree[] = createFenwickTree( hits );
	//output: [1, 1, 2, 4, 1, 4, 0, 12, 2, 7, 2, 11, 3]
	System.out.println( read( tree, 12));
	System.out.println(read( tree, 6) - read( tree, 2));
	update( tree, 7, 9);
	System.out.println( read( tree, 12));
	}
	private static void update( int tree[], int idx ,int val){
	while (idx <= tree.length){
	tree[idx-1] = tree[idx-1] + val;
	idx += (1 << ctz(idx));
	}
	}
	private static int read(int tree[], int idx) {
	int sum = 0;
	while (idx > 0){
	sum = sum + tree[idx-1];
	idx -= (1 << ctz(idx));
	}
	return sum;
	}
	/**
	* Create the FenWick Tree
	* @param a
	* @return
	*/
	private static int[] createFenwickTree(int[] a) {
	int[] tree = new int[a.length];
	for (int i = 1; i <= a.length; i++) {
	int start = getStart( i );
	if( start == i ) {
	// System.out.println(i + "=" +i);
	tree[i-1] = a[i-1];
	} else {
	// System.out.println(i + "=" +start + ".." +i);
	for( int j = start; j <= i; j++ ) {
	tree[i-1] = tree[i-1] + a[j-1];
	}
	}
	}
	return tree;
	}
	public static int getStart( int n) {
	return n - (int)Math.pow(2, ctz(n)) + 1;
	}
	/**
	* Find the last set bit from left to right
	*
	* 1. Take two's complement of the given no as all bits are reverted
	* except the first '1' from right to left (10111)
	* 2 Do an bit-wise & with original no, this will return no with the
	* required one only (00010)
	* 3 Extract the right most 1 bit position using shift operation
	*
	*/
	public static int ctz(int n)
	{
	return shift(n&-n, 1);
	}
	/**
	* Shift operation
	* @param n
	*/
	private static int shift( int n, int k ) {
	int i = 0;
	while( n > 0 ) {
	n = n >> k;
	i++;
	}
	return i-1;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Facebook - Calculate Birthday's this week

Facebook provides a notification service to inform users that one or more of their friend's birthday is lined up  this week. Design a data structure to efficiently fetch the birthday's in the given range.
There is another Facebook interview question similar to this - Facebook maintains a log of when somebody logged in and when somebody logged out. Read this data and store it in a data structure. Now find how many users were logged into Facebook at a given time (say 10:25 am today).

Solution:-
I have used a Segment Tree. It is very efficient in performing range based queries. For the birthday problem, i have used a range of 1 to 366 (total number of days in a year). The Segment tree is similar to a binary tree, but it stores range values instead of single value. Each node will contain a range [i, j]. In that case the left node would contain range [i, (i+j)/2]. The right node will contain [(i+j)/2+1, j]. This way it would go on. Once the Segment tree is created, reach each user and store it in the Segment tree. Search is very efficient as it only have to match the given range value.

The same data structure can be used to create bar charts. In  a few bar charts that we see, the bar chart range can be gradually decreased. For instance, it shows people between 1-100 years old, then click on it to show 1-50 range and 51-100 range. Then click again to show 1-25, 26-50, 51-75, 76-100...so on. It can go upto single level values. This is an ideal use case for Segment Tree.

	import java.text.SimpleDateFormat;
	import java.util.ArrayList;
	import java.util.Calendar;
	import java.util.Date;
	import java.util.HashMap;
	import java.util.List;
	import java.util.Map;
	import java.util.Set;
	/**
	* Birthday notification using Segment Tree
	*
	* @author Raju Rama Krishna
	*
	*/
	public class BirthdayCalculator {
	/**
	* @param args
	*/
	public static void main(String[] args) throws Exception {
	String pattern = "dd/MM/yyyy";
	SimpleDateFormat format = new SimpleDateFormat(pattern);
	Calendar cal = Calendar.getInstance();
	Map<String, String> map = BirthdayHolder.getBirthdayMap();
	SegmentTree tree = new SegmentTree();
	tree.create(1, 366);
	Set<String> set = map.keySet();
	Date date = null;
	for( String s: set ) {
	date = format.parse(map.get(s));
	cal.setTime(date);
	tree.add( s, cal.get( Calendar.DAY_OF_YEAR));
	}
	date = format.parse("27/02/2012");
	cal.setTime(date);
	int start = cal.get(Calendar.DAY_OF_YEAR);
	date = format.parse("03/05/2012");
	cal.setTime(date);
	int end = cal.get(Calendar.DAY_OF_YEAR);
	List<String> list = tree.find( start, end );
	System.out.println("People celebrating birthday :");
	System.out.println(list);
	}
	}
	class SegmentTree {
	Element root;
	public void create( int start, int end ) {
	root = new Element( start, end );
	create( root );
	}
	private void create( Element e ) {
	int start = e.start;
	int end = e.end;
	if( start < end ) {
	Element l = new Element( start, (start+end)/2 );
	e.left = l;
	Element r = new Element( (start+end)/2+1, end );
	e.right = r;
	create( e.left );
	create( e.right );
	}
	}
	public void add( String s, int val ) {
	add( root, s, val );
	}
	private void add( Element e, String s, int val ) {
	if( e != null && val >= e.start && val <= e.end) {
	e.add(s);
	add( e.left, s, val );
	add( e.right, s, val );
	}
	}
	public List<String> find( int start, int end ) {
	return find( root, start, end );
	}
	private List<String> find( Element e, int start, int end ) {
	if( e == null || e.end < start ) {
	return new ArrayList<String>();
	}
	if( e.start == start && e.end == end ) {
	return e.list;
	} else if( e.left.start <= start && e.left.end >= end ) {
	return find( e.left, start, end );
	} else if( e.right.start <= start && e.right.end >= end ) {
	return find( e.right, start, end);
	} else {
	List<String> list1 = find( e.left, start, e.left.end);
	List<String> list2 = find(e.right, e.right.start, end);
	if( list1 != null ) {
	if( list2 != null) {
	list1.addAll( list2 );
	}
	} else {
	if( list2 != null ) {
	list1 = list2;
	}
	}
	return list1;
	}
	}
	}
	class Element {
	int start;
	int end;
	List<String> list;
	Element left;
	Element right;
	public Element( int start, int end ) {
	this.start = start;
	this.end = end;
	}
	public void add( String s ) {
	if( list == null ) {
	list = new ArrayList<String>();
	}
	list.add(s);
	}
	public String toString() {
	return "[" + start + "-" +end + "]";
	}
	}
	class BirthdayHolder {
	private static Map<String, String> map = new HashMap<String, String>();
	public static Map<String, String> getBirthdayMap() {
	map.put("Rogers", "11/12/1979");
	map.put("Susan", "02/05/1978");
	map.put("Pratap", "11/11/1975");
	map.put("Maddy", "04/08/1992");
	map.put("Dia", "09/08/2008");
	map.put("Mohan", "14/02/1999");
	map.put("Patrick", "28/02/1952");
	map.put("John", "01/01/2002");
	map.put("Francis", "29/02/1982");
	map.put("Carol", "01/03/2000");
	return map;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Microsoft: Find biggest number that can be formed from a list of unsorted numbers

  Microsoft Interview - Given an array of unsorted numbers (1 or 2 digits),
  Find the biggest number that can be created using these numbers
  For e.g. {6, 83, 12, 7, 16, 35}
  The biggest number that can be made is 83,7,6,35,16,12
 
Solution
  The idea is to create 2 maxheaps - one for one digit numbers
  The other for 2 digit numbers. Then compare and create final string.
 
  Extending this to any arbitary length is simple. Instead of using 2 maxheaps,
  use n maxheaps, where n is the length of the number with the maximum length.
  Compare and create can use N-way merge then, instead of simple if-else.

	/**
	* Microsoft Interview - Given an array of unsorted numbers (1 or 2 digits),
	* Find the biggest number that can be created using these numbers
	* For e.g. {6, 83, 12, 7, 16, 35}
	* The biggest number that can be made is 83,7,6,35,16,12
	*
	* The idea is to create 2 maxheaps - one for one digit numbers
	* The other for 2 digit numbers. Then compare and create final string.
	*
	* Extending this to any arbitary length is simple. Instead of using 2 maxheaps,
	* use n maxheaps, where n is the length of the number with the maximum length.
	* Compare and create can use N-way merge then, instead of simple if-else.
	*
	* @author raju rama krishna
	*
	*/
	public class MaxNumberGen {
	public static void main(String[] args) {
	int[] a = {6, 83, 12, 7, 16, 35}; //{4, 1, 94, 9, 14, 5};
	String res = getMaxNumber( a );
	System.out.println("Value = " +res);
	}
	private static String getMaxNumber(int[] a) {
	String s = "";
	MaxHeap h1 = new MaxHeap(50);
	MaxHeap h2 = new MaxHeap(50);
	//Create the heaps
	for( int val: a) {
	int len = getLength(val);
	if( len == 1 ) {
	h1.add(val);
	} else {
	h2.add(val);
	}
	}
	//Compare and create the string;
	int x = h1.getMax();
	int y = h2.getMax();
	while( true ) {
	String s1 = x + "" + y;
	String s2 = y + "" + x;
	if(Integer.parseInt(s1) > Integer.parseInt(s2)) {
	s = s + x;
	if(h1.getSize() == 0 ) {
	x = -1;
	break;
	}
	x = h1.getMax();
	} else {
	s = s + y;
	if(h2.getSize() == 0 ) {
	y = -1;
	break;
	}
	y = h2.getMax();
	}
	}
	if( x != -1 ) {
	s = s + x;
	} else if( y != -1 ) {
	s = s + y;
	}
	while( h1.getSize() > 0 ) {
	s = s + h1.getMax();
	}
	while( h2.getSize() > 0 ) {
	s = s + h2.getMax();
	}
	return s;
	}
	private static int getLength( int num ) {
	int len = 0;
	while( num > 0 ) {
	num = num/10;
	len++;
	}
	return len;
	}
	}
	class MaxHeap {
	int[] a;
	int size;
	int n;
	public int getVal( int pos ) {
	return a[pos];
	}
	public MaxHeap( int size ) {
	this.size = size;
	a = new int[size];
	}
	public int parent( int pos ) {
	return (pos-1)/2;
	}
	public void add( int val ) {
	int curr = n++;
	a[curr] = val;
	while( curr != 0 && a[curr] > a[parent(curr)]) {
	int t = a[curr];
	a[curr] = a[parent(curr)];
	a[parent(curr)] = t;
	curr = parent(curr);
	}
	}
	public int getMax() {
	if( n == 0 ) {
	return a[0];
	}
	int max = a[0];
	a[0] = a[n-1];
	a[n-1] = 0;
	n--;
	int pos = 0;
	while( !leaf(pos) && ( a[pos] < a[left(pos)]) || a[pos] < a[right(pos)]) {
	if( a[left(pos)] > a[right(pos)]) {
	int t = a[pos];
	a[pos] = a[left(pos)];
	a[left(pos)] = t;
	pos = left(pos);
	} else {
	int t = a[pos];
	a[pos] = a[right(pos)];
	a[right(pos)] = t;
	pos = right(pos);
	}
	}
	return max;
	}
	public boolean leaf( int pos ) {
	return pos >= n/2;
	}
	public int left( int pos ) {
	return (2*pos + 1);
	}
	public int right( int pos ) {
	return (2*pos + 2);
	}
	public int getSize() {
	return n;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Sum of elements in unsorted array

 Given an unsorted array.
 With each number, we can associated a sum which is equal to the sum of all the numbers, less than the   current number.
  We've to find the total sum of all those numbers.
  e.g. unsorted array :1, 5, 3, 6, 4.
  for a[0]=1, sum[0]=0
  for a[1]=5, sum[1]=1
  for a[2]=3, sum[2]=1
  for a[3]=6, sum[3]=1+5+3
  for a[4]=4, sum[4]=1+3
  total sum =sum[0]+sum[1]+sum[2]+sum[3]+sum[4] = 15

Solution:
Read each element in the array and put it into a Binary Search Tree. Each node of the BST will hold the value of the element,  and also the sum of the left subtree. As the elements are inserted, calculate the sum of the left subtree. At the end of inserting all the elements, the total sum is calculated

	/**
	* Given an unsorted array.
	* With each number, we can associated a sum which is equal to the sum of all the numbers, less than the current number.
	* We've to find the total sum of all those numbers.
	* e.g. unsorted array :1, 5, 3, 6, 4.
	* for a[0]=1, sum[0]=0
	* for a[1]=5, sum[1]=1
	* for a[2]=3, sum[2]=1
	* for a[3]=6, sum[3]=1+5+3
	* for a[4]=4, sum[4]=1+3
	* total sum =sum[0]+sum[1]+sum[2]+sum[3]+sum[4] = 15
	*
	* @author raju rama krishna
	*
	*/
	public class CalculateSum {
	/**
	* @param args
	*/
	public static void main(String[] args) {
	int[] a = { 1, 5, 3, 6, 4 };
	BST tree = new BST();
	// Create Tree
	int sum = 0;
	for( int val: a ) {
	sum = sum + tree.sum(val);
	}
	System.out.println("sum = " +sum);
	}
	}
	class BST {
	Node root;
	public int sum( int val ) {
	int result = 0;
	if( root == null ) {
	root = new Node( val );
	} else {
	result = insertAndSum(root, val);
	}
	return result;
	}
	public int insertAndSum(Node node, int val)
	{
	int sum = 0;
	if( node == null ) {
	node = new Node( val );
	} else {
	if(node.val > val) {
	//insert on left
	node.sumLeft += val;
	if(node.left != null) {
	sum = insertAndSum(node.left, val);
	}
	else {
	Node temp = new Node(val);
	node.left = temp;
	}
	}
	else {
	//insert on right
	if(node.right != null) {
	sum = insertAndSum(node.right, val);
	}
	else {
	Node temp = new Node(val);
	node.right = temp;
	}
	sum += node.val + node.sumLeft;
	}
	}
	return sum;
	}
	}
	class Node {
	int val;
	int sumLeft;
	Node left;
	Node right;
	public Node( int val ) {
	this.val = val;
	}
	public String toString() {
	return String.valueOf( val );
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Least Common Ancestor in Binary Tree

Given a Binary Tree (not Binary Search Tree), and two nodes A and B. Find the closest common ancestor for both the nodes.

Solution

	import java.util.ArrayList;
	import java.util.LinkedList;
	import java.util.List;
	/**
	* This class represents a Binary Tree and finds Least Common Ancestor b/n two nodes.
	*
	* 1. First consider the root of the tree as Temp.
	* 2. Check whether N1 and N2 are in same side of Temp or else in different sides of Temp.
	* 3. If N1 and N2 are on different sides of Temp, then return Temp is the least common ancestor.
	* Else if N1 and N2 are on the left side of Temp, set Temp=Temp->left.. else if they are right side, Temp=Temp->right. Goto step 2.
	*
	* @author raju rama krishna
	*
	*/
	public class BinaryTree {
	/**
	* @param args
	*/
	public static void main(String[] args) {
	Tree tree = new Tree();
	for( int i=0; i < 26; i++ ) {
	tree.add((char)('a' +i));
	}
	char a = 'r';
	char b = 'u';
	char c = tree.ancestor(a, b);
	System.out.println(c);
	}
	}
	class Tree {
	Node root;
	List<Character> list = new ArrayList<Character>();
	public void add( char c ) {
	if( root == null ) {
	root = new Node(c);
	} else {
	add( root, c );
	}
	}
	public char ancestor(char a, char b) {
	List<Character> list = inorder();
	char x = 0;
	Node node = root;
	int aPos = -1;
	int bPos = -1;
	int xPos = -1;
	int i = 0;
	for( char c: list ) {
	if( c == a ) {
	aPos = i;
	} else if( c == b ) {
	bPos = i;
	} else if( c == node.c ) {
	xPos = i;
	}
	if( aPos != -1 && bPos != -1 && xPos != -1 ) {
	break;
	}
	i++;
	}
	while( true ) {
	if( (aPos < xPos && bPos > xPos) || (bPos < xPos && aPos > xPos ) ) {
	x = node.c;
	break;
	} else {
	if( aPos < xPos && bPos < xPos ) {
	node = node.left;
	} else {
	node = node.right;
	}
	i = 0;
	for( char c: list ) {
	if( c == node.c ) {
	xPos = i;
	break;
	}
	i++;
	}
	}
	}
	return x;
	}
	private void add( Node node, char c ) {
	if( node != null ) {
	if( node.left == null ) {
	Node temp = new Node( c );
	node.left = temp;
	} else if( node.right == null ) {
	Node temp = new Node( c );
	node.right = temp;
	} else {
	List<Node> list = new LinkedList<Node>();
	list.add(node.left);
	list.add(node.right);
	Node curr = list.remove(0);
	while( curr != null ) {
	if( curr.left == null ) {
	Node temp = new Node( c );
	curr.left = temp;
	break;
	} else if( curr.right == null ) {
	Node temp = new Node( c );
	curr.right = temp;
	break;
	} else {
	list.add(curr.left);
	list.add(curr.right);
	if( list.isEmpty() ) {
	break;
	}
	curr = list.remove(0);
	}
	}
	}
	}
	}
	public List<Character> inorder() {
	inorder(root);
	return list;
	}
	private void inorder( Node node ) {
	if( node != null ) {
	inorder(node.left);
	list.add(node.c);
	inorder(node.right);
	}
	}
	}
	class Node {
	char c;
	Node left;
	Node right;
	public Node( char c ) {
	this.c = c;
	}
	public String toString() {
	return String.valueOf(c);
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Binary Tree - Microsoft Interview Questions

This one contains 3 different problems on a complete Binary Tree.
1. Create and Print a Binary Tree in the same input order.
2. Print the tree in a zig-zag fashion. Even levels right to left and Odd levels left to right
3. Take a snapshot of the tree and put it on a co-ordinate system with left-most node as (0,0)

Solution

	import java.util.LinkedList;
	import java.util.List;
	/**
	* This class represents a Binary Tree and provides operations on it.
	*
	* bfs mode => iterate level by level and print left to right.
	*
	* zigzag mode => iterate level by level and print even level nodes
	* in right to left, odd level nodes in left to right
	*
	* co-ordinates mode =>
	* Assume that a binary tree is drawn over a Cartesian coordinate system (with X & Y axis)
	* where the leftmost node is placed at point (0,0). So, we need to traverse the nodes and
	* print in following manner:
	* For e.g., for this tree
	* a
	* b c
	* d e f g
	* Output should be:
	* d,0,0
	* b,1,1
	* e,2,0
	* a,3,2
	* f,4,0
	* c,5,1
	* g,6,0
	*
	* @author raju rama krishna
	*
	*/
	public class BinaryTree {
	/**
	* @param args
	*/
	public static void main(String[] args) {
	Tree tree = new Tree();
	for( int i=0; i < 26; i++ ) {
	tree.add((char)('a' +i));
	}
	//print a-z
	System.out.println("BFS");
	tree.bfs();
	//Microsoft Interview Question
	//print tree in zig-zag
	System.out.println("ZigZag Pattern");
	tree.zigzag();
	//Microsoft Interview Question
	//print values on co-ordinate systems
	System.out.println("Co-ordinate Values");
	tree.coord();
	}
	}
	class Tree {
	Node root;
	int count = 0;
	public void add( char c ) {
	if( root == null ) {
	root = new Node(c);
	} else {
	add( root, c );
	}
	}
	private void add( Node node, char c ) {
	if( node != null ) {
	if( node.left == null ) {
	Node temp = new Node( c );
	node.left = temp;
	} else if( node.right == null ) {
	Node temp = new Node( c );
	node.right = temp;
	} else {
	List<Node> list = new LinkedList<Node>();
	list.add(node.left);
	list.add(node.right);
	Node curr = list.remove(0);
	while( curr != null ) {
	if( curr.left == null ) {
	Node temp = new Node( c );
	curr.left = temp;
	break;
	} else if( curr.right == null ) {
	Node temp = new Node( c );
	curr.right = temp;
	break;
	} else {
	list.add(curr.left);
	list.add(curr.right);
	if( list.isEmpty() ) {
	break;
	}
	curr = list.remove(0);
	}
	}
	}
	}
	}
	public void zigzag() {
	zigzag( root );
	}
	private void zigzag( Node node ) {
	if( node != null ) {
	System.out.println(node.c);
	List<Node> list = new LinkedList<Node>();
	if( node.left != null ) {
	list.add( node.left );
	}
	if( node.right != null ) {
	list.add( node.right );
	}
	if( !list.isEmpty() ) {
	int i = 1;
	while(!list.isEmpty() ) {
	if( i % 2 == 1 ) {
	for( int j = 0; j < list.size(); j++ ) {
	System.out.println( list.get(j));
	}
	} else {
	for( int j = list.size()-1; j >= 0; j-- ) {
	System.out.println(list.get(j));
	}
	}
	int size = list.size();
	for( int j = 0; j < size; j++ ) {
	if(list.get(j).left != null)
	list.add( list.get(j).left);
	if(list.get(j).right != null)
	list.add( list.get(j).right);
	}
	for( int j = 0; j < size; j++ ) {
	list.remove( list.get(0));
	}
	i++;
	}
	}
	}
	}
	public void bfs() {
	bfs( root );
	}
	private void bfs( Node node ) {
	if( node != null ) {
	System.out.println(node.c);
	List<Node> list = new LinkedList<Node>();
	if( node.left != null ) {
	list.add( node.left );
	}
	if( node.right != null ) {
	list.add( node.right );
	}
	if( !list.isEmpty() ) {
	Node curr = list.remove(0);
	while(curr != null ) {
	System.out.println(curr.c);
	if( curr.left != null ) {
	list.add(curr.left);
	}
	if( curr.right != null ) {
	list.add(curr.right);
	}
	if( !list.isEmpty() ) {
	curr = list.remove(0);
	} else {
	break;
	}
	}
	}
	}
	}
	public int depth() {
	int i = 0;
	Node node = root;
	while( node != null ) {
	node = node.left;
	i++;
	}
	return i;
	}
	public void coord() {
	int res = depth();
	coord( root, res, res-1 );
	}
	private void coord( Node node, int l, int i ) {
	if( node != null ) {
	coord( node.left, l, i-1 );
	System.out.println(node + "(" + (count++) + "," +i+ ")");
	coord( node.right, l, i-1 );
	}
	}
	}
	class Node {
	char c;
	Node left;
	Node right;
	public Node( char c ) {
	this.c = c;
	}
	public String toString() {
	return String.valueOf(c);
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Sort array of 0,1,2

Given an array of 0s, 1s and 2s only in a mixed fashion. The task is to seperate out them such that 0s are on the left, 1s in the middle, and 2s on the right. The algorithm should run in linear time.

This problem is called "Dutch National Flag". There are lot of puzzles asked in the interview based on this.

Solution

	/**
	* Sort an array containing 0, 1, and 2 in a O(N) time
	* This algorithm uses dutch national flag algorithm
	*
	* @author diya
	*
	*/
	public class SortOneTwo {
	/**
	* @param args
	*/
	public static void main(String[] args) {
	// TODO Auto-generated method stub
	int[] a = {2,1,1,0,2,2,1,1,0,0,0,2};
	a = sort(a, a.length);
	System.out.println();
	}
	public static int[] sort(int[] a, int n) {
	int low=0, mid=0, high = n-1;
	while (mid<=high) {
	switch(a[mid]) {
	case 0:
	int t = a[low];
	a[low] = a[mid];
	a[mid] = t;
	low++;
	mid++;
	break;
	case 1:
	mid++;
	break;
	case 2:
	t = a[mid];
	a[mid] = a[high];
	a[high] = t;
	high--;
	break;
	}
	}
	return a;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Google Search - Prototype

Implement a basic web search. It should load a document list into memory. Each document contains text data of variable length. When the user searches for a particular text, it should find all matching patterns for the complete word list (in the same sequence) he entered.
For. e.g
If my documents are -

"where is the house",
"my house is where the mountain is",
"it is my house",
"my dog is a pet",
"where is the horse"

And I search for - "where is the house". The exact pattern should be matched. It should only return "where is the house". It should not return the 2nd string "my house is where the mountain is", even though it contains all the 4 words (where, is, the, house) in a jumbled fashion.

The user should be able to search for substring as well e.g. "my house". It will return "my house is where the mountain is" and also "it is my house".

Design:

If we did not have to support substring search, it could have been a scenario for storing key-value pair. 

With this requirement, we can only implement it with a Tree or a TRIE. I have choosen a Binary Search Tree since I can search for words in Log(N). 

Read documents one by one. For every document read the words. Check if the word is in the BST. If not add a node to the BST with value as the word. The index for it would be a linked list with one key-value pair (key is document-id and value is word-id in the document). If there is a node already with the word, then append the key-value index to the end of the linked-list. This way, the document1's index would be stored before the document-2's index. 

Search - "x y z".

First search for word "x". Get the indexes for the word. Lets say we got (1,4), (3,9). Then search for word "y". If it returned (1,5), (2,1), (3,11). Then we are only interested in document 1. Since neither 3 nor 2 fit in our criteria. It is because in document 1, word x was at position 4 and word y is at position 5. We continue the same with word "z". But this time our focus is only on index (1,5).

Conclusion
As always, this is just a prototype i came up with and it can have a lot of additional features like document ranking, suggestion, completion, etc. In an actual web search engine, there would be a complex algorithm and processing involved.

Solution

	import java.util.HashSet;
	import java.util.LinkedList;
	import java.util.List;
	import java.util.Set;
	/**
	* This class performs a subset of web search functionality.
	* It can search the words in the same order as input.
	*
	* @author Raju Rama Krishna
	*
	*/
	public class WebSearch {
	private String[] documents = {
	"where is the house",
	"my house is where the mountain is",
	"it is my house",
	"my dog is a pet",
	"where is the horse"};
	private BST tree;
	//Singleton Cache instance
	private static WebSearch _instance = null;
	private WebSearch() {
	// no access
	}
	public static WebSearch getInstance() {
	if( _instance == null ) {
	synchronized (WebSearch.class) {
	if(_instance == null) {
	_instance = new WebSearch();
	}
	}
	}
	return _instance;
	}
	public void load() {
	tree = new BST();
	int i = 0;
	for(String s: documents) {
	String[] sArr = s.split(" ");
	int j = 0;
	for( String s1: sArr ) {
	tree.addWord(s1, i, j++);
	}
	i++;
	}
	}
	public void search( String s ) {
	Set<Integer> matchingDocs = new HashSet<Integer>();
	String[] sArr = s.split(" ");
	List<DocIndex> currList = null;
	for( String s1: sArr ) {
	Node node = tree.search(s1, tree.root);
	List<DocIndex> list = node.indexes;
	if( currList == null ) {
	currList = list;
	} else {
	List<DocIndex> newList = new LinkedList<DocIndex>();
	int k = 0;
	int j = 0;
	while( k < currList.size() ) {
	DocIndex currDoc = currList.get(k);
	while(j < list.size()) {
	DocIndex doc = list.get(j);
	if( currDoc.docId == doc.docId) {
	if(currDoc.index == doc.index-1) {
	j++;
	newList.add(doc);
	break;
	} else {
	break;
	}
	} else if(currDoc.docId < doc.docId) {
	break;
	} else {
	j++;
	}
	}
	k++;
	}
	currList = newList;
	if( newList.isEmpty() ) {
	System.out.println("Could not find the document");
	return;
	}
	}
	}
	for( DocIndex doc: currList ) {
	matchingDocs.add(doc.docId);
	}
	System.out.println("RESULTS:");
	for(Integer i: matchingDocs) {
	System.out.println(documents[i]);
	}
	}
	/**
	* @param args
	*/
	public static void main(String[] args) {
	WebSearch webSearch = WebSearch.getInstance();
	webSearch.load();
	String s = "my house";
	webSearch.search(s);
	}
	}
	class BST {
	Node root = null;
	public void addWord( String s, int docId, int docIndex ) {
	root = add( s, docId, docIndex, root );
	}
	public Node add( String s, int docId, int docIndex, Node node ) {
	if( node == null ) {
	node = new Node( s );
	node.set(docId, docIndex);
	} else {
	Node curr = node;
	while(true) {
	if( curr.val.compareTo(s) < 0 ) {
	if(curr.right == null) {
	Node newNode = new Node(s);
	newNode.set(docId, docIndex);
	curr.right = newNode;
	break;
	} else {
	add( s, docId, docIndex, curr.right );
	break;
	}
	} else if( curr.val.compareTo(s) > 0 ) {
	if(curr.left == null) {
	Node newNode = new Node(s);
	newNode.set(docId, docIndex);
	curr.left = newNode;
	break;
	} else {
	add( s, docId, docIndex, curr.left );
	break;
	}
	} else {
	curr.set(docId, docIndex);
	break;
	}
	}
	}
	return node;
	}
	public Node search( String s, Node node ) {
	if( node == null )
	return null;
	if( node.val.compareTo(s) < 0 ) {
	return search( s, node.right);
	} else if( node.val.compareTo(s) > 0 ) {
	return search( s, node.left );
	} else {
	return node;
	}
	}
	}
	class Node {
	String val;
	Node left;
	Node right;
	//I chose linkedlist, so that the document ids are maintained.
	List<DocIndex> indexes = new LinkedList<DocIndex>();
	public Node( String val ) {
	this.val = val;
	}
	public void set( int docId, int index ) {
	DocIndex docIndex = new DocIndex( docId, index );
	indexes.add(docIndex);
	}
	public String toString() {
	return val;
	}
	}
	class DocIndex {
	int docId;
	int index;
	public DocIndex( int docId, int index ) {
	this.docId = docId;
	this.index = index;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Tour a city - Puzzle

 There is a one-way circular route from City A to City X. In between these 2 cities,
  there are a number of cities separated by any distance. Each city has a petrol pump
  and holds a different storage capacity. The total petrol available in all the cities
  put together is say 'Z' litres. The total distance between City A to City X will be
  'Z' kilo meters. Assume the bike has a mile-age of 1 litre per KM.
  Your goal is to around the circle, starting with no petrol. Find which city you will
  start first, to ensure you wont run out of petrol mid-way.  
 
Solution

	import java.util.ArrayList;
	import java.util.List;
	/**
	* There is a one-way circular route from City A to City X. In between these 2 cities,
	* there are a number of cities separated by any distance. Each city has a petrol pump
	* and holds a different storage capacity. The total petrol available in all the cities
	* put together is say 'Z' litres. The total distance between City A to City X will be
	* 'Z' kilo meters. Assume the bike has a mile-age of 1 litre per KM.
	* Your goal is to around the circle, starting with no petrol. Find which city you will
	* start first, to ensure you wont run out of petrol mid-way.
	*
	* e.g. Cities: A -> B -> C -> D -> E -> A
	* Distances: 7 3 5 12 4
	* Capacity: 5 4 7 8 7
	*
	* output: City E
	*
	* @author raju rama krishna
	*
	*/
	public class PetrolPump {
	// Number of Cities
	int n = 0;
	// Distance between cities, starting from A
	List<Integer> distances = new ArrayList<Integer>();
	// Petrol available at each city, starting from A
	List<Integer> capacities = new ArrayList<Integer>();
	public static void main(String[] args) {
	PetrolPump pump = new PetrolPump();
	pump.setup();
	pump.findCity();
	}
	public void findCity() {
	int max = 0;
	int city = 0;
	for( int i = 0; i < n; i++ ) {
	//This is the petrol saved or deficit for covering the journey
	//from city i to (i+1);
	int petrol = capacities.get(i) - distances.get(i);
	if(petrol > max) {
	max = petrol;
	city = i;
	}
	}
	//Transform index to City name
	char cityNm = (char)('A' +city);
	System.out.println("Start from city : " +cityNm);
	}
	private void setup() {
	n = 5;
	distances.add(7);
	distances.add(3);
	distances.add(5);
	distances.add(12);
	distances.add(4);
	capacities.add(5);
	capacities.add(4);
	capacities.add(7);
	capacities.add(8);
	capacities.add(7);
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Book Store: Auto Suggest and Auto Completion

Implement a Book Store to maintain a catalog of Books. Currently i am only storing the title of the book. Users should be able to add a book, and search . The search should be exact or partial. Implement auto-suggest and auto-completion as well. The search operation is user centric, so it should be extremely fast. 

Usually 90% of spelling correction is done for 2 edits. An edit is one of the following - missing letter, misplaced letter, extra letter. This algorithm can be tuned for further spell check.

Solution

	/**
	* This class mimics a book store and provides utility methods on it.
	*
	* Input: java
	* SEARCH EXACT: RESULTS
	* java for beginners
	* enterprise java book
	* hello world in java
	* a progmatic approach to java
	* beginners guide to java language
	*
	* Input: prog
	* SUGGEST: RESULTS
	* a progmatic approach to java
	* programmers heaven
	* programming in a nutshell
	* systems programming
	* progressive hadoop
	*
	* Input: hadoob (***NOTE I am inputing a wrong spelling "hadob" instead of "hadoop".
	* It has both - a missing letter and a wrong letter)
	* SUGGEST: RESULTS
	* hadoop in action
	* learning hadoop
	* progressive hadoop
	*
	* @author raju rama krishna
	*
	*/
	public class BookStore {
	private static final String FILTER = "on,in,a,the,for,with,vol,book";
	private String[] books = {"programming in a nutshell", "java for beginners", "hadoop in action", "enterprise java book", "hello world in java", "systems programming", "a progmatic approach to java", "learning hadoop", "beginners guide to java language", "programmers heaven", "progressive hadoop"};
	private TST tst = new TST();
	/**
	* @param args
	*/
	public static void main(String[] args) {
	BookStore store = new BookStore();
	store.loadData();
	System.out.println("***LOADED Catalogue");
	String s = "java";
	store.searchExact(s);
	s = "hadob";
	store.suggest(s);
	}
	public void searchExact( String s ) {
	List<Integer> list = tst.searchExact( s );
	if( list == null ) {
	System.out.println("Sorry!! Book Not found");
	} else {
	System.out.println("RESULTS");
	for( Integer j: list ) {
	System.out.println(books[j]);
	}
	}
	}
	public void suggest( String s ) {
	List<Integer> list = tst.searchPartial( s );
	if( list == null ) {
	System.out.println("Sorry!! Book Not found");
	} else {
	System.out.println("RESULTS");
	for( Integer j: list ) {
	System.out.println(books[j]);
	}
	}
	}
	public void loadData() {
	int i = 0;
	for( String s: books ) {
	addBook( s, i++ );
	}
	}
	public void addBook( String s, int i ) {
	s = s.toLowerCase();
	String[] sArr = s.split(" ");
	for( String w: sArr ) {
	if(!FILTER.contains(s)) {
	tst.addWord( w, i);
	}
	}
	}
	}
	class Book {
	String title;
	}
	class TST {
	Node root = null;
	public List<Integer> searchExact( String s ) {
	Node node = root;
	int i = 0;
	while( i < s.length()) {
	if( node == null ) {
	return null;
	}
	if(node.val == s.charAt(i)) {
	node = node.middle;
	i++;
	if( i == s.length() - 1 ) {
	return node.indexes;
	}
	} else if( node.val < s.charAt(i)) {
	node = node.right;
	} else {
	node = node.left;
	}
	}
	return null;
	}
	public List<Integer> searchPartial( String s ) {
	Node node = root;
	int i = 0;
	while( i < s.length()) {
	if( node == null ) {
	return null;
	}
	if(node.val == s.charAt(i)) {
	node = node.middle;
	i++;
	if( i == s.length() - 1 ) {
	return depthSearch( node );
	}
	} else if( node.val < s.charAt(i)) {
	node = node.right;
	} else {
	node = node.left;
	}
	}
	return null;
	}
	public List<Integer> depthSearch( Node node ) {
	List<Integer> res = new ArrayList<Integer>();
	if( node != null ) {
	res.addAll(node.indexes);
	res.addAll(depthSearch(node.left));
	res.addAll(depthSearch(node.middle));
	res.addAll(depthSearch(node.right));
	}
	return res;
	}
	public void addWord( String s, int indx ) {
	if( root == null ) {
	root = new Node( s.charAt(0));
	Node node = root;
	Node temp = null;
	for( int i = 1; i < s.length(); i++ ) {
	temp = new Node(s.charAt(i));
	node.middle = temp;
	node = temp;
	if( i == s.length()-1) {
	temp.set(indx);
	}
	}
	} else {
	Node node = root;
	int i = 0;
	Node temp = null;
	char val = 0;
	while( i < s.length() ) {
	val = s.charAt(i);
	if( node.val == val ) {
	if( i == s.length()-1) {
	node.set(indx);
	i++;
	} else {
	i++;
	if( node.middle == null ) {
	while( i < s.length()) {
	val = s.charAt(i);
	temp = new Node( val );
	node.middle = temp;
	node = temp;
	if( i == s.length()-1) {
	temp.set(indx);
	}
	i++;
	}
	} else {
	node = node.middle;
	}
	}
	} else if( val < node.val ) {
	if( node.left == null ) {
	temp = new Node( val );
	node.left = temp;
	node = temp;
	if( i == s.length()-1) {
	temp.set(indx);
	} else {
	i++;
	while( i < s.length()) {
	val = s.charAt(i);
	temp = new Node( val );
	node.middle = temp;
	node = temp;
	if( i == s.length()-1) {
	temp.set(indx);
	}
	i++;
	}
	}
	} else {
	node = node.left;
	}
	} else {
	if( node.right == null ) {
	temp = new Node( val );
	node.right = temp;
	node = temp;
	if( i == s.length()-1) {
	temp.set(indx);
	} else {
	i++;
	while( i < s.length()) {
	val = s.charAt(i);
	temp = new Node( val );
	node.middle = temp;
	node = temp;
	if( i == s.length()-1) {
	temp.set(indx);
	}
	i++;
	}
	}
	} else {
	node = node.right;
	}
	}
	}
	}
	}
	}
	class Node {
	char val;
	Node left;
	Node middle;
	Node right;
	List<Integer> indexes = new ArrayList<Integer>();
	public Node( char val ) {
	this.val = val;
	}
	public void set( Integer i ) {
	if(!indexes.contains(i)) {
	indexes.add(i);
	}
	}
	public String toString() {
	return String.valueOf(val);
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Implement Mobile T9 using TRIE

T9's objective is to make it easier to type text messages. It allows words to be entered by a single keypress for each letter. T9's objective is to make it easier to type text messages. It allows words to be entered by a single keypress for each letter.  For instance, in English, 4663 matches "good", "home", "gone", "hood", etc. 

This program takes in a dictionary file as input, reads it and creates a Ternary Search Trie (TST). Once the Trie is created, any word can be searched. The matching words for a given sequence are stored in ascending order (instead of word ranking). This code can be modified to accomplish word ranking and machine learning. 

The above code can be implemented with HashMap. However hashing does not provide efficient searching. 

For the purpose of benchmarking, I have enabled the runtime stats in this class. I have tested with 3 types of dictionaries. The biggest dictionary I could get hold off was containing 3.7 million words. The program currently accepts only alphabets. 

Solution

	import java.io.BufferedReader;
	import java.io.File;
	import java.io.FileReader;
	import java.util.Date;
	import java.util.HashMap;
	import java.util.LinkedList;
	import java.util.List;
	import java.util.Map;
	/**
	* T9 for Mobile messaging.
	* @author raju rama krishna
	*
	*/
	public class T9Dictionary {
	private static final Runtime s_runtime = Runtime.getRuntime();
	public static void main(String[] args) throws Exception {
	runGC();
	long heap1 = usedMemory();
	long start = new Date().getTime();
	Trie trie = Trie.getInstance();
	System.out.println("Creating Dictionary");
	File f = new File(args[0]);
	BufferedReader br = new BufferedReader(new FileReader(f));
	String s = br.readLine();
	int i = 0;
	do {
	i++;
	trie.add(s);
	s = br.readLine();
	} while(s != null);
	br.close();
	long end = new Date().getTime();
	long time = (end - start);
	System.out.println("Loaded Dictionary with " +i+ " words in " +time+ " msec");
	runGC();
	long heap2 = usedMemory(); // take an "after" heap snapshot:
	System.out.println("Memory used = " +(heap2-heap1));
	String pattern = "4663";
	start = new Date().getTime();
	String word = trie.getWord(pattern);
	end = new Date().getTime();
	time = (end - start);
	System.out.println("Found word : " +word+ " in " +time+ " msec");
	}
	private static void runGC() throws Exception {
	// for whatever reason it helps to call Runtime.gc()
	// using several method calls:
	for (int r = 0; r < 4; ++r) {
	_runGC();
	}
	}
	private static void _runGC()
	throws Exception {
	long usedMem1 = usedMemory();
	long usedMem2 = Long.MAX_VALUE;
	for (int i = 0; (usedMem1 < usedMem2) && (i < 1000); ++i) {
	s_runtime.runFinalization();
	s_runtime.gc();
	Thread.currentThread().yield();
	usedMem2 = usedMem1;
	usedMem1 = usedMemory();
	}
	}
	private static long usedMemory() {
	return s_runtime.totalMemory() - s_runtime.freeMemory();
	}
	}
	class Trie {
	private static final String regex = "[a-zA-Z]*";
	private static Trie instance = null;
	Node root = null;
	Map<Character, Integer> map = new HashMap<Character, Integer>();
	private Trie() {
	map.put('a',2);
	map.put('b',2);
	map.put('c',2);
	map.put('d',3);
	map.put('e',3);
	map.put('f',3);
	map.put('g',4);
	map.put('h',4);
	map.put('i',4);
	map.put('j',5);
	map.put('k',5);
	map.put('l',5);
	map.put('m',6);
	map.put('n',6);
	map.put('o',6);
	map.put('p',7);
	map.put('q',7);
	map.put('r',7);
	map.put('s',7);
	map.put('t',8);
	map.put('u',8);
	map.put('v',8);
	map.put('w',9);
	map.put('x',9);
	map.put('y',9);
	map.put('z',9);
	}
	private int getVal( char c ) {
	return map.get( c );
	}
	public static Trie getInstance() {
	if( instance == null ) {
	synchronized( Trie.class ) {
	instance = new Trie();
	}
	}
	return instance;
	}
	public String getWord( String pattern ) {
	String s = null;
	Node node = root;
	int i = 0;
	int num = 0;
	while( i < pattern.length() ) {
	num = pattern.charAt(i) - '0';
	if(num == node.val) {
	i++;
	if( i == pattern.length() ) {
	s = node.list.get(0);
	}
	node = node.middle;
	} else if( num < node.val ) {
	if( i == pattern.length() ) {
	s = node.list.get(0);
	}
	node = node.left;
	} else {
	if( i == pattern.length() ) {
	s = node.list.get(0);
	}
	node = node.right;
	}
	}
	return s;
	}
	public void add( String s ) {
	if(s.length() > 0 && s.matches(regex)) {
	s = s.toLowerCase();
	// System.out.println("Adding : " +s);
	if( root == null ) {
	root = new Node( getVal(s.charAt(0)));
	Node node = root;
	Node temp = null;
	for( int i = 1; i < s.length(); i++ ) {
	temp = new Node(getVal(s.charAt(i)));
	node.middle = temp;
	node = temp;
	if( i == s.length()-1) {
	temp.set(s);
	}
	}
	} else {
	Node node = root;
	int i = 0;
	Node temp = null;
	int val = 0;
	while( i < s.length() ) {
	val = getVal( s.charAt(i) );
	if( node.val == val ) {
	if( i == s.length()-1) {
	node.set(s);
	i++;
	} else {
	i++;
	if( node.middle == null ) {
	while( i < s.length()) {
	val = getVal( s.charAt(i) );
	temp = new Node( val );
	node.middle = temp;
	node = temp;
	if( i == s.length()-1) {
	temp.set(s);
	}
	i++;
	}
	} else {
	node = node.middle;
	}
	}
	} else if( val < node.val ) {
	if( node.left == null ) {
	temp = new Node( val );
	node.left = temp;
	node = temp;
	if( i == s.length()-1) {
	temp.set(s);
	} else {
	i++;
	while( i < s.length()) {
	val = getVal( s.charAt(i) );
	temp = new Node( val );
	node.middle = temp;
	node = temp;
	if( i == s.length()-1) {
	temp.set(s);
	}
	i++;
	}
	}
	} else {
	node = node.left;
	}
	} else {
	if( node.right == null ) {
	temp = new Node( val );
	node.right = temp;
	node = temp;
	if( i == s.length()-1) {
	temp.set(s);
	} else {
	i++;
	while( i < s.length()) {
	val = getVal( s.charAt(i) );
	temp = new Node( val );
	node.middle = temp;
	node = temp;
	if( i == s.length()-1) {
	temp.set(s);
	}
	i++;
	}
	}
	} else {
	node = node.right;
	}
	}
	}
	}
	}
	}
	}
	class Node {
	int val;
	Node left;
	Node middle;
	Node right;
	List<String> list = new LinkedList<String>();
	public Node( int val ) {
	this.val = val;
	}
	public void set( String s ) {
	list.add(s);
	}
	public String toString() {
	return String.valueOf(val);
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Unimodal array has an increasing sequence followed by decreasing sequence, find the number at which the transition happens

  Unimodal array contains a list of 'N' integers. There exists M < N, such that
  a[0] to a[M] are in increasing series
  a[M+1] to a[N] are in decreasing series
  The problem is to find a[M] in O(Log N)
  E.g. {2, 4, 8, 10, 13, 18, 12, 7, 5, 4}. Here M is 18 as the switch happens after it

 Solution

	/**
	* Unimodal array contains a list of 'N' integers in which integers. There exists M < N, such that
	* a[0] - a[M] are in increasing series
	* a[M+1] - a[N] are in decreasing series
	* The problem is to find a[M] in O(Log N)
	*
	* @author raju rama krishna
	*
	*/
	public class UnimodalSearch {
	/**
	* @param args
	*/
	public static void main(String[] args) {
	int[] a = {3, 7, 9, 12, 15, 17, 18, 19, 20, 30, 33, 20, 16, 8, 6, 5, 1};
	int res = find(a);
	System.out.println(res);
	}
	private static int find(int[] a) {
	int l = 0;
	int h = a.length-1;
	int m = (l+h)/2;
	int res = 0;
	while( l < h ) {
	if(h == l+1) {
	res = Math.max(a[l], a[h]);
	break;
	}
	if(a[m] < a[m+1]) {
	l = m+1;
	} else {
	h = m;
	}
	m = (l+h)/2;
	}
	return res;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Pairs of numbers whose sum is "S"

In a given sorted array of integers, print the pairs of numbers which give a sum "S" in O(N) time.

The problem like this can be solved with 2 pointers.

Solution:-

	/**
	* In a given sorted array of integers, print the pairs of numbers which give a sum "S" in O(N) time.
	*
	* @author raju rama krishna
	*
	*/
	public class SumOfPair {
	/**
	* @param args
	*/
	public static void main(String[] args) {
	int[] a = {3, 4, 8, 9, 11, 12, 15, 16, 18};
	int s = 20;
	printPairs( a, s );
	}
	private static void printPairs( int[] a, int s ) {
	int i = 0;
	int j = a.length - 1;
	while(i < j) {
	int val = a[i] + a[j];
	while( val > s ) {
	j--;
	val = a[i] + a[j];
	}
	if( val == s) {
	System.out.println(a[i] + "," +a[j]);
	}
	i++;
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Suffix Tree - Common pattern in 'N' strings

Given 'n' number of strings, find the common pattern among all of them in O(N) time.
For e.g. "sparrows", "tomorrow", "borrower". In the above 3 strings, the common pattern is "rrow".
Problems like this can be solved in linear time. The main point to note it is, this can be achieved at the cost of additional space. Searching will be linear time.

Solution

	import java.util.ArrayList;
	import java.util.List;
	/**
	* This class finds the common pattern in 'N' words in O(N) time using Suffix Tree.
	* I could also use this to do auto-completion and word suggestion
	*
	* @author raju rama krishna
	*
	*/
	public class SuffixTree {
	private static int n_words = 0;
	public static void main(String[] args) {
	String[] words = {"tommorrow", "sparrows", "rowing", "borrow"};
	n_words = words.length;
	System.out.println(SuffixTree.printCommon( words ));
	}
	public static String printCommon( String[] sArr) {
	Node root = new Node(' ', 0);
	int i = 1;
	for( String s: sArr ) {
	createTree( s, i++, root );
	}
	return commonPattern( root );
	}
	public static String commonPattern( Node root ) {
	String res = "";
	List<Node> children = root.children;
	for(Node temp: children ) {
	String word = getMatch( temp );
	if( word.length() > res.length() ) {
	res = word;
	}
	}
	return res;
	}
	private static String getMatch( Node node ) {
	if( node.indexes.size() == n_words) {
	String res = "";
	for( int i = 0; i < node.children.size(); i++ ) {
	String temp = node.c + getMatch( node.children.get(i));
	if( temp.length() > res.length() ) {
	res = temp;
	}
	}
	return res;
	} else {
	return "";
	}
	}
	public static void createTree( String s, int idx, Node root ) {
	do {
	addBranch( s, root, idx );
	s = s.substring(1, s.length());
	} while( s.length() > 0 );
	}
	private static void addBranch( String s, Node root, int idx ) {
	Node node = null;
	for(int i=0; i < s.length(); i++) {
	boolean found = false;
	char c = s.charAt(i);
	if( i == 0 ) {
	node = new Node( c, idx );
	List<Node> children = root.children;
	if( children == null ) {
	children = new ArrayList<Node>();
	} else {
	for( Node temp: children ) {
	if(temp.c == c) {
	node = temp;
	List<Integer> indexes = node.indexes;
	if(!indexes.contains(idx)) {
	indexes.add(idx);
	}
	found = true;
	break;
	}
	}
	}
	if( !found ) {
	children.add( node );
	root.children = children;
	}
	} else {
	Node node1 = new Node( c, idx );
	if( i == s.length()-1) {
	node1.isEnd = true;
	}
	List<Node> children = node.children ;
	if( children == null ) {
	children = new ArrayList<Node>();
	} else {
	for( Node temp: children ) {
	if(temp.c == c) {
	node = temp;
	List<Integer> indexes = node.indexes;
	if(!indexes.contains(idx)) {
	indexes.add(idx);
	}
	found = true;
	break;
	}
	}
	}
	if( !found ) {
	children.add( node1 );
	node.children = children;
	node = node1;
	}
	}
	}
	}
	}
	class Node {
	char c;
	List<Node> children;
	boolean isEnd;
	int idx;
	List<Integer> indexes;
	public Node( char c, int idx ) {
	this.c = c;
	indexes = new ArrayList<Integer>();
	indexes.add(idx);
	}
	public String toString() {
	return String.valueOf(c);
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Kth Largest using MaxHeap

Find the Kth largest element in an unsorted array of integers, using MaxHeap

Solution

	/**
	* Find Kth Largest element in an unsorted array using Max-Heap
	* 1) Build a Max Heap tree in O(n)
	* 2) Use Extract Max k times to get kth maximum element. O(klogn)
	* Time complexity: O(n + klogn)
	*
	* @author raju rama krishna
	*
	*/
	public class MaxHeap {
	int[] a;
	int size;
	int n;
	public int getVal( int pos ) {
	return a[pos];
	}
	public MaxHeap( int size, int[] e ) {
	this.size = size;
	a = new int[size];
	createHeap(e);
	}
	public int parent( int pos ) {
	return (pos-1)/2;
	}
	public void createHeap( int[] e ) {
	for( int val : e ) {
	int curr = n++;
	a[curr] = val;
	while( curr != 0 && a[curr] > a[parent(curr)]) {
	int t = a[curr];
	a[curr] = a[parent(curr)];
	a[parent(curr)] = t;
	curr = parent(curr);
	}
	}
	}
	public int getMax() {
	int max = a[0];
	a[0] = a[n-1];
	a[n-1] = 0;
	n--;
	int pos = 0;
	while( !leaf(pos) && ( a[pos] < a[left(pos)]) || a[pos] < a[right(pos)]) {
	if( a[left(pos)] > a[right(pos)]) {
	int t = a[pos];
	a[pos] = a[left(pos)];
	a[left(pos)] = t;
	pos = left(pos);
	} else {
	int t = a[pos];
	a[pos] = a[right(pos)];
	a[right(pos)] = t;
	pos = right(pos);
	}
	}
	return max;
	}
	public int getMax( int k ) {
	int max = 0;
	for( int i=0; i < k; i++ ) {
	max = getMax();
	}
	return max;
	}
	public boolean leaf( int pos ) {
	return pos >= n/2;
	}
	public int left( int pos ) {
	return (2*pos + 1);
	}
	public int right( int pos ) {
	return (2*pos + 2);
	}
	public static void main(String[] args) {
	int[] a = {88, 30, 11, 17, 22, 16, 39, 8, 31, 55, 29, 63, 77, 69, 99, 90, 81, 2, 20, 53, 62, 5, 33, 44, 6};
	int k = 5;
	MaxHeap heap = new MaxHeap(50, a);
	int res = heap.getMax( k );
	System.out.println(k +"th maximum element from end is : " +res);
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Median of Medians to find Kth Smallest

Given an array of unsorted integers find the Kth smallest element using "Median of Medians".
This method is guaranteed to work in max linear time

Solution

	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.List;
	/**
	* Calculate Kth biggest element in an unsorted array using Median of Medians. Worst case is O(N)
	*
	* @author raju rama krishna
	*
	*/
	public class MedianOfMedians {
	public static void main(String[] args) {
	Integer[] a = {88, 30, 11, 17, 22, 16, 39, 8, 31, 55, 29, 63, 77, 69, 99, 90, 81, 2, 20, 53, 62, 5, 88, 33, 44, 6};
	int n = 22;
	int res = select(a, n);
	System.out.println(res);
	Arrays.sort(a);
	System.out.println(a[n-1]);
	}
	private static int select(Integer[] a, int k)
	{
	if (a.length <= 10)
	{
	Arrays.sort(a);
	return a[k-1];
	}
	int n = a.length;
	//partition L into subsets S[i] of five elements each
	// (there will be n/5 subsets total).
	List<Integer[]> list = new ArrayList<Integer[]>();
	int cnt = 0;
	int m = n/5;
	for( int i = 0; i < m; i++ ) {
	Integer[] arr = new Integer[5];
	for( int j = 0; j < 5; j++ ) {
	if( cnt == n )
	break;
	arr[j] = a[cnt++];
	}
	Arrays.sort(arr);
	list.add(arr);
	}
	Integer[] x = new Integer[m];
	for (int i = 0; i< m; i++ ) {
	x[i] = list.get(i)[2];
	}
	int v = x[0];
	if(x.length > 2) {
	v = (x.length%2 == 0)? x[x.length%2-1]: x[x.length/2];
	}
	// partition L into L1<M, L2=M, L3>M
	Integer[] l = partition_l( a, v );
	Integer[] r = partition_r( a, v );
	if( k == l.length+1 ) {
	return v;
	} else if( k <= l.length ){
	return select(l,k);
	} else {
	return select(r,k-l.length-1);
	}
	}
	private static Integer[] partition_l( Integer[] a, int pivot ) {
	if( a.length == 0)
	return a;
	int j = 0;
	Integer[] b = new Integer[a.length];
	for( int i = 0; i < a.length; i++ ) {
	if(a[i] < pivot) {
	b[j++] = a[i];
	}
	}
	Integer[] l = new Integer[j];
	System.arraycopy(b, 0, l, 0, j);
	return l;
	}
	private static Integer[] partition_r( Integer[] a, int pivot ) {
	if( a.length == 0)
	return a;
	int j = 0;
	Integer[] b = new Integer[a.length];
	for( int i = 0; i < a.length; i++ ) {
	if(a[i] > pivot) {
	b[j++] = a[i];
	}
	}
	Integer[] r = new Integer[j];
	System.arraycopy(b, 0, r, 0, j);
	return r;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Kth smallest element in an unsorted array

Given an array of unsorted numbers, find the Kth smallest element in the array.
Input:  10, 8, 5, 7, 14, 3
K = 4
Output: 8

Solution

	/**
	* Find the Kth largest element in an unsorted array. Best case O(N) and worst case O(N*2)
	*
	* @author raju rama krishna
	*
	*/
	public class KthLargest {
	/**
	* @param args
	*/
	public static void main(String[] args) {
	int[] a = {30, 16, 34, 10, 17, 22, 18, 56, 7, 33, 50, 47};
	int k = 6;
	int res = find( a, k );
	System.out.println(res);
	}
	private static int find( int[] a, int k ) {
	int index = 0;
	for(;;) {
	int p = a.length/2;
	int[] l = partition_l(a, p);
	int[] r = partition_r(a, p);
	if( k == index + l.length+1 ) {
	index += p;
	return a[p];
	} else if( k <= index + l.length ){
	a = l;
	} else {
	a = r;
	index += l.length + 1;
	}
	}
	}
	private static int[] partition_l( int[] a, int p ) {
	if( a.length == 0)
	return a;
	int pivot = a[p];
	int j = 0;
	int[] b = new int[a.length];
	for( int i = 0; i < a.length; i++ ) {
	if(a[i] < pivot) {
	b[j++] = a[i];
	}
	}
	int[] l = new int[j];
	System.arraycopy(b, 0, l, 0, j);
	return l;
	}
	private static int[] partition_r( int[] a, int p ) {
	if( a.length == 0)
	return a;
	int pivot = a[p];
	int j = 0;
	int[] b = new int[a.length];
	for( int i = 0; i < a.length; i++ ) {
	if(a[i] > pivot) {
	b[j++] = a[i];
	}
	}
	int[] r = new int[j];
	System.arraycopy(b, 0, r, 0, j);
	return r;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

Count occurrence of an element in a Sorted Array

Given an array of sorted elements, count the number of times a given element is repeated. The solution cannot be linear.

Solution:- Have given 2 solutions, both are modifications to binary search

	/**
	* This program counts the occurrence of a number in a sorted array - O(log N)
	* @author raju rama krishna
	*
	*/
	public class OccuranceCountUnsorted {
	/**
	* @param args
	*/
	public static void main(String[] args) {
	int[] a = new int[] {1, 3, 4, 6, 9, 10, 11, 14, 15, 16, 17, 18, 20, 22, 23, 27, 27, 27, 27, 27, 27, 28, 29, 33, 33, 41, 49, 55};
	int h = a.length-1;
	int res1 = count( a, 27, 0, h);
	System.out.println("result="+res1);
	int res2 = search( a, 27, 0, h);
	System.out.println("result="+res2);
	}
	/**
	* Using method1
	* @param a
	* @param key
	* @param l
	* @param h
	* @return
	*/
	private static int count( int[] a, int key, int l, int h ) {
	System.out.println("call between " +a[l] + " and " +a[h]);
	if( l < h ) {
	if(a[l] == key && a[h] == key)
	return (h-l)+1;
	int m = (l+h)/2;
	if( key < a[m] )
	return count( a, key, l, m);
	else if( key > a[m] )
	return count( a, key, m+1, h);
	else {
	return count( a, key, l, m ) + count( a, key, m+1, h);
	}
	} else {
	if(a[l] == key)
	return 1;
	else
	return 0;
	}
	}
	/**
	* Using method2
	* @param a
	* @param key
	* @param l
	* @param h
	* @return
	*/
	private static int search( int[] a, int key, int l, int h ) {
	System.out.println("call between " +a[l] + " and " +a[h]);
	int m = (l+h)/2;
	if( key < a[m] ) {
	return search( a, key, l, m);
	} else if( key > a[m]) {
	return search( a, key, m+1, h);
	} else {
	int i = m-1;
	int count = 1;
	while(a[i] == key ) {
	i--;
	count++;
	}
	i = m+1;
	while( a[i] == key ) {
	i++;
	count++;
	}
	return count;
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub