Implementing Stack Using Queue

Implementing stack using two queues, where we push element to q2 and then move pop and add all the to q1. Swap q2 to q1 to proceed with pop or another push operation.

Input:
push(1)
push(2)
push(3)

pop()
pop()
pop()
pop()

Output:
1 :3
2 :2
3 :1
Queue Empty
4 :null

Queue Using Stack Data Structure

Implementing Queue Using Stack


Two approaches
1) Using Multiple Stacks

Input:
enque(4)
dequeue()
enque(2)
dequeue()
enque(7)
dequeue()

Output:
1: 4
2: 2
3: 7




2) Using Single Stack and Recursive Method

Input:
enque(4)
dequeue()
enque(8)
enque(2)
dequeue()
enque(7)
dequeue()

Output:
1: 4
2: 2
3: 7
4: 8

Find the first circular tour that visits all gas station or petrol bunks

Find the first circular tour that visits all gas station or petrol bunks where there are N gas stations are there in a circle. 

You are given two sets of data:

1. The amount of gas/petrol that every petrol pump has.
2. Distance from that gas/petrol pump to the next petrol pump.

Node node1 = new Node("1", 6, 4);

"1" is the gas station name.

6 is amount of gas can be filled at gas station "1"

4 is the distance from current gas station to next one.

Calculate the first point from where a truck will be able to complete the circle 

Input 1

Node node1 = new Node("1", 6, 4);
Node node2 = new Node("2", 3, 6);
Node node3 = new Node("3", 7, 3);

Output
Execution 1: 3

Input 2

Node node1 = new Node("1", 4, 6);
Node node2 = new Node("2", 6, 5);
Node node3 = new Node("3", 7, 3);
Node node4 = new Node("4", 4, 5);

Output

Execution 2: 2

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