Longest Increasing Subsequence

Input:
arr = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

 1. list  = {0} - Initialize list to the empty set
 2. list  = {0,8} - New largest LIS
 3. list  = {0, 4} - Changed 8 to 4
 4. list  = {0, 4, 12} - New largest LIS
 5. list  = {0, 2, 12} - Changed 4 to 2
 6. list  = {0, 2, 10} - Changed 12 to 10
 7. list  = {0, 2, 6} - Changed 10 to 6
 8. list  = {0, 2, 6, 14} - New largest LIS
 9. list  = {0, 1, 6, 14} - Changed 2 to
 10. list = {0, 1, 6, 9} - Changed 14 to 9
 11. list = {0, 1, 5, 9} - Changed 6 to 5
 12. list = {0, 1, 6, 9, 13} - Changed 3 to 2
 13. list = {0, 1, 3, 9, 11} - New largest LIS
 14. list = {0, 1, 3, 9, 11} - Changed 9 to 5
 15. list = {0, 1, 3, 7, 11} - New largest LIS
 16. list = {0, 1, 3, 7, 11, 15} - New largest LIS

 So the length of the LIS is 6 (the size of list).

Output:
Longest Increasing Subsequence is:  [0, 1, 3, 7, 11, 15]

Find all unique pairs of element in an array that sum to S

Find all unique pairs of element in an array that sum to S

For ex. If array = {2,4,6,4,6} and S = 8 then answer is {<2,6>, <4,4>}

Input:
   values = { 2, 4, 6, 4, 4, 6, 5, 3 } and
   S = 8

Output:
    <5,3>   <4,4> <2,6>

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

Sorting Using Reversing Array Element ( PanCake Sorting)

In this sorting method, elements are flipped and added in the last of the list. This is also known as PanCake Sorting.

Input:
{1, 2, 5, 4, 3, 10, 9, 8, 7}

Output:
Including all intermediate results
10 3 4 5 2 1 9 8 7

9 8 7 1 2 5 4 3 10

8 7 1 2 5 4 3 9 10

7 1 2 5 4 3 8 9 10

5 4 3 2 1 7 8 9 10

4 3 2 1 5 7 8 9 10

3 2 1 4 5 7 8 9 10

2 1 3 4 5 7 8 9 10

1 2 3 4 5 7 8 9 10

1 2 3 4 5 7 8 9 10 (final Result)

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