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.

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 Kth Largest Element

I think code is self explanatory, please refer comments available for more details in the code.

Intersection Of Unsorted Arrays

There are two arrays, find the elements which for which there is an intersection.

Input:
  arr1 = { 12, 4, 17 }
  arr2 = { 1, 12, 7, 17 }

Output:
 Intersection Using Simple Comparison
 12 17
 Intersection Using Sort and Binary Search
 12 17

There are two approaches for solving the problem:

• A simple approach or 
• Approach based on sorting and searching. ( Sorting which we have learned in some of the previous posts).

Selection Sort

Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

Following gif image which is referenced from wiki helps to understand the Selection Sort quickly.

Insert a node into the circular list

Quick Sort

Quick soft is a very efficient algorithm for sorting.
It has two phases:
a) Partition phases
b) Sort phase.

Follwoing gif image which is referenced from wiki helps to understand the quicksort quickly.

Quick Sort Simulation

Insertion Sort

Insertion sort, unlike the other sorts, passes through the array only once.
It is much less efficient on large elements when compared to more advanced algorithms such as quicksort, heapsort, or merge sort.
The insertion sort is commonly compared to organizing a handful items like arranging playing cards based on insertion sort.

Reference following gif image which makes it much easier to understand:

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

Binary Search Tree

Binary Search Tree(BST) is a hierarchical data structure which is tree with a single reference to root node where each node has at most two child nodes (a left and a right child)

Nodes are organized by the Binary Search property:
• Every node is ordered by some key data field(s)
• For every node in the tree, its key is greater than its left child’s key and less than its right child’s key

Following implementation of BST

Input:
BinaryTree<String> tree = new BinaryTree<String>();
tree.add("Python");
tree.add("Java");
tree.add("Node.js");
tree.add("Angular.js");

Output:
[Angular.js, Java, Node.js, Python]

Breadth First Search

Tree and Graph traversal are one of the important topics in computer science.
In fact many social networking companies are using graph based database (nosql db) specially Facebook, Twitter, Linkedin, etc.

Traversing is all about visiting the vertices in some systematic order.

There are two types of traversal:

• Depth First Search (DFS)
• Breadth First Search (BFS)

If you don't have memory constraint, DFS is a good choice, as BFS takes up a lot of space. So, choosing between these two depends on user's requirement.

Following are traversal methods for trees using DFS:

• preorder : visit each node before its children.
• postorder: visit each node after its children.
• inorder : visit left subtree, node, right subtree. (applicable for binary trees only)

When to use DFS :

• When you want to find the (strongly/)connected components of the graph to
• To Solve the maze or sudoku problems.

When to use BFS:

• When you want to test if a graph is bipartite or 
• To find the shortest path between two nodes or applications that require such tasks.

I found following video very easy to understand about BFS.

Following code is for the BFS

Above code consider the following tree as input and output is ABSCGDEFH