Anagrams

There are millions of string in the database. How would you store them for efficient searching. You also need to print all anagrams together many times, now how would you store them and insert if a new string is added to database ?

Anagram: A word or phrase spelled by rearranging the letters of another word or phrase

Input:
"My one ym neo game ym"

Output:
{22231=[one, neo], 15334=[game], 3977=[My, ym]}

Intern Allocation To Manager Based On The Best Preference Match

Design a intern allocation system based on the preference of interns and managers.
For e.g. 5 intern gives their preferences for 5 manager and vice versa.
The match should be done based on the best possible match.

Intern 1 Chooses
        Manager 1, Manager 3, Manager 4, Manager 2 and Manager 5 as the preference.
Manager 1 Chooses 
        Intern 2, Intern 3, Intern 4, Intern 5 and Intern 1 as the preference.

Similarly for all other 4 interns and 4 manager.

Expected Output:
Intern 1 works with Manager 3

Intern 2 works with Manager 2

Intern 3 works with Manager 1

Intern 4 works with Manager 4

Intern 5 works with Manager 5

1) Based on the problem description we can have matrix for interns and managers with the weights as preferences.
2) Do a customized matrix multiplication of both the matrix
3) Sort them using Tree Set to get the sorted records and find the first five or find a unique allocation with intermediate matrix.

Input:
Interns Weighted Preference

5  2  4  3  1
2  5  4  3  1
5  4  3  2  1
2  5  4  3  1
2  1  5  4  3

Managers Weighted Preference

2  1  5  4  3
2  5  4  3  1
2  1  5  4  3
5  4  3  2  1
2  5  4  3  1

Intermediate Output:

Multiplied Matrix
---------------------
10  2     20  12  3
4    25  16    9  1
10  4    15    8  3
10  20  12    6  1
4    5    20  12  3

Intern Allocation
---------------------
0   0   20  0  0
0   25  0   0  0
10  0   0   0  0
0    0   0   6  0
0    0   0   0  3

Ouput:

Intern 1 works with Manager 3

Intern 2 works with Manager 2

Intern 3 works with Manager 1

Intern 4 works with Manager 4

Intern 5 works with Manager 5
-------------------------------------------------------------------

InternAllocation.java

InternAllocationDemo.java

Blocking Queue Using ReentrantLock To Do Operations As Producer And Consumer

ReEntrant Blocking Queue


Producer And Consumer To do enqueue and dequeue operations

Input:
{ 1, 4, 66, 9, 677, 2435, 45, 2, 3, 667, 23,73260, 100, 400 }

Output:
enqueue(1) returning counter:1
enqueue(4) returning counter:2
dequeue() returning, value = 1
enqueue(66) returning counter:2
dequeue() returning, value = 4
enqueue(9) returning counter:2
dequeue() returning, value = 66
enqueue(677) returning counter:2
dequeue() returning, value = 9
enqueue(2435) returning counter:2
dequeue() returning, value = 677
enqueue(45) returning counter:2
dequeue() returning, value = 2435
enqueue(2) returning counter:2
dequeue() returning, value = 45
enqueue(3) returning counter:2
dequeue() returning, value = 2
enqueue(667) returning counter:2
dequeue() returning, value = 3
enqueue(23) returning counter:2
dequeue() returning, value = 667
enqueue(73260) returning counter:2
dequeue() returning, value = 23
enqueue(100) returning counter:2
dequeue() returning, value = 73260
enqueue(400) returning counter:2
Exiting from producer
dequeue() returning, value = 100
dequeue() returning, value = 400

Search Value Into Two Dimensional Sorted Array

Search an integer in a two dimensional integer array, in which each row and column are in sorted ascending order

Input:
    1   5   7    9
    4   6   10   15
    8   11  12   19
  14  16  18   21

findNumber: 11

Output:
Number is at index 2,1

Find The Maximum Multiplication In An Given Array

For e.g.
Input:
 {6,7,-8,9,8,-7,6};
Output:
  Maximum Product: 72

Find The Next Greatest Element In Array

Finding the next greatest element from the current position in the array
 For e.g. if
 Input is {16, 17, 4, 3, 5, 2}
 Expected Output 16 ->17 , 17 ->-1, 4 ->5, 3 ->5, 5 ->-1 ,2 ->-1

  -1 is for which there is no greatest element in the next series of elements.


  

Find If Sum Of Any Three Elements Is Equal To Given Value

Find if some of any of the three elements equals to the given value,
For e.g. Input is as follows:
 {-7, -3, 2, 10, 3, 4, 6, 7,0};

 And value is 0 then expected output is:

Sum Of Zero from three array elements :
-7, -3, 10
-3, 0, 3
0, 3, -3
3, 4, -7


Sum Of Five from three array elements :
-7, 2, 10
-3, 2, 6
0, 2, 3

Find Sub-String Of A String

Finding a substring of a string without using any of the helper class.

Find Kth Non Repeating Character

Given a string find the Kth non repeating character from it.
Given a string find the first non repeating character from it.


For example if input is "deepaksinghvi", expected output is:

hashtable: {p=1, n=1, k=1, i=2, h=1, g=1, e=2, d=1, a=1, v=1, s=1}
d

linkedhashmap: {d=1, e=2, p=1, a=1, k=1, s=1, i=2, n=1, g=1, h=1, v=1}
d

linkedhashmap: {d=1, e=2, p=1, a=1, k=1, s=1, i=2, n=1, g=1, h=1, v=1}
p

Find If Array Elements Are Consecutive

Finding if the array elements are consecutive in terms of values in the array.
 {100,101,102} elements in the array are consecutive because of 100,101,102
{5, 2, 3, 1, 4,0,-1} elements in the array are consecutive because of -1,0,1,2,3,4,5

Finding total number of elements in a array of consecutive elements is
maximum element value - minimum element value + 1, i.e.
n= (max - min) + 1.

or 

sumofvalues = numberofelements*(min+max)/2;

303 = 3 * (100+102)/2

If the first condition matches we can check for avoiding other cases of repeating or not appearing elements.

Convert To Sorted Array Using Decrement or Delete

Program to convert the positive array using either decrement or delete operation based on the cost involved for the operation.

1) Decrement -> cost = 1

2) Delete an element completely from the array -> cost = value of element

For example:

4,3,5,6, -> cost 1 //cost is 1 to make 4->3

10,3,11,12 -> cost 3 // cost 3 to remove 3

Following cases were tried and produced the expected result:

Input:
4 3 5 6
Output:
3 3 5 6
------------------
Input:
10 3 11 12
Output:
10 11 12
------------------
Input:
3 10 7 9 1
Output:
3 7 7 9
------------------
Input:
1 1 1 1000 1
Output:
1 1 1 1000
------------------
Input:
10 2 3
Output:
10
------------------

Longest Common Subsequence

The longest common subsequence (or LCS) of groups T and S is the longest group of elements from T and S that are common between the two groups and in the same order in each group.
One of the use for this algorithm can be in file comparison utility for difference in content.
We can solve this problem by dynamic programming as we can easily break the problem into smaller sub-problems.
Following recursive version of the code computes the LCS value.

Following image has the explanation on the how LCS for two string
T = G T A T A T A T A T A C C
S = G T T C C T A A T A

Following code computes the LCS value which is 8 in this case.

Find Maximum Sum In Binary Tree Path

Following program does all the below mentioned work:
1) Print all nodes
2) Find if a value exists in a tree or not
3) Find value sum in any of the path
4) Find maximum sum in any of the path