Unmix My Strings

Unmix My Strings

lPaeesh le pemu mnxit ehess rtnisg! Oh, sorry, that was supposed to say: Please help me unmix these strings! Somehow my strings have all become mixed up; every pair of characters has been swapped. Help me undo this so I can understand my strings again. 

 unmix("123456") ➞ "214365" 
 unmix("hTsii  s aimex dpus rtni.g") ➞ "This is a mixed up string." 
 unmix("badce") ➞ "abcde" 

Input: hTsii s aimex dpus rtni.g, Output: This is a mixed up string. 

Input: 214365, Output: 123456 

Input: badce, Output: abcde 

Question Reference: https://edabit.com/challenge/XRAGxXj4KtakkvD3F

Largest Gap

Given an array of integers, return the largest gap between the sorted elements of the array.

For example, consider the array:

[9, 4, 26, 26, 0, 0, 5, 20, 6, 25, 5] ... in which, after sorting, the array becomes:

[0, 0, 4, 5, 5, 6, 9, 20, 25, 26, 26] ... so that we now see that the largest gap in the array is between 9 and 20 which is 11.

Maximum Loot Problem

Maximum Loot Problem

More details about the problem are mentioned at:

https://practice.geeksforgeeks.org/problems/stickler-theif/0

Input:
5 5 10 100 10 5

Output:
110

Input:
1 2 3

Output:
4

Maximum sum of hour glass in matrix

Rather than explaining something more in detail, following sample input, output and explanation would help to understand what do we need to do for this problem.

Input:

int[][] input1 = {
    {1, 2, 3, 4, 5},
    {0, 5, 1, 5, 2},
    {0, 0, 0, 1, 3},
    {4, 1, 1, 0, 1},
    {0, 0, 0, 0, 3},
};

Output:
3   4   5
    5
0   1   3

Max Sum for input1 is: 21

Input:
int[][] input2 = {
    {3, 0, 0, 5},
    {2, 5, 5, 5},
    {0, 0, 0, 1},
    {4, 4, 0, 0},
    {0, 0, 3, 0},
};
Output:
2   5   5
    0
4   4   0

Max Sum for input2 is: 20

Input:
int[][] input3 = {
    {-1, -1, 0, -9, -2, -2},
    {-2, -1, -6, -8, -2, -5},
    {-1, -1, -1, -2, -3, -4},
    {-1, -9, -2, -4, -4, -5},
    {-7, -3, -3, -2, -9, -9},
    {-1, -3, -1, -2, -4, -5}
};

Output:
-1   -1   0
    -1
-1   -1   -1

Max Sum for input3 is: -6

Stack and Queue using Deque

Deque is double ended queue, which like the doubly linked list with having frond/head in the start and last/tail in the end of the list.

Stack using Deque

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

Output:
4
3->2->1



Queue using Deque

Input:
enqueue(1)
enqueue(2)
enqueue(3)
enqueue(4)

Output:
1
2->3->4

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

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

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 Largest Sum Of Contiguous Integers In The Array

Returns the largest sum of contiguous integers in the array
For e.g.
If the input is (-2, -3, 4, -1, -2, 1, 5, -3), the largest sum is 7.
It is the largest and not the biggest, i.e. consider taking more number of elements continuously.

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.