Kth Smallest element in an array in O(N) average time.

Given N elements in an array. Find the ith smallest element (element of rank i).

Maximum Contiguous Sum in an Array.

Maximum value of a contiguous subsequence.
This problem is only interesting if there are -ve values in the array. We can solve this problem in linear time using Dynamic Programming. There are O(N) subproblems each taking O(1) time. The basic strategy is whenever a subsequence is found which has a -ve sum, the next subsequence can begin after the end of the subsequence which produced the -ve sum.

Code:

Valid combinations of "N" pairs of round brackets

Write a method to print all the valid combinations of "N" pairs of round brackets.
Sample Input:
3
Sample output:
((()))
(()())
(())()
()(())
()()()

Consecutive Groups of Integers

Divide a list of numbers into group of consecutive numbers but their original order should be preserved?
e.g.
8,2,4,7,1,0,3,6

2,4,1,0,3 and 8,7,6

Approach:

we can use a technique called "index sorting", C#, Java, etc. all have overloads of the sort call which can tandem sort two arrays. So essentially you have two arrays

int[] numbers = {2, 9, 0, 7, 3, 8, 1, 6} or whatever
int[] indices = {0, 1, 2, 3, 4, 5, 6, 7}

sort indices and numbers by the elements in numbers.

numbers = {0, 1, 2, 3, 6, 7, 8, 9}
indices = {2, 6, 0, 4, 7, 3, 5, 1}

Then divide numbers/indices into consecutive groups.

Re-Sort numbers/indices but sort by indices. Then just walk through numbers printing out the values.

Sample Input:
8 6 4 2 0 4 1 3

Sample output:
Printing Map::
2 -> 4
3 -> 2
4 -> 0
5 -> 4
6 -> 1
7 -> 3

Printing Map::
1 -> 6

Printing Map::
0 -> 8

Index of substring match.

Method to return the index of first matching instance of pattern string in a text string.

Reverse String

Method to reverse the words in a string.
"who are you" -> "you are who"

Remove Duplicate characters from String

Function that removes duplicate characters from a string.

Binary String Sum

Function that takes in two binary strings and returns their sum (also a binary string).
Approach:
1. Reverse the strings, and pad the smaller string so that length of the strings are equal.
2. Calculate the binary sum by reading each character of the string starting from index 0 and keeping track of the carry.
3. Reverse the resultant string to get the final binary string sum.


Code (*edge cases are not handled):

Permutation of String.

Permutation of n characters - Recursive approach.



Alternative Approach:

Reversing Singly Link List

Recursive and iterative approach for reversing a singly link list.

Find all subsets of a given set

Power set of a given Set.

Event Scheduling for N Employees in a month

You are given N ranges of date offsets when N employees are present in an organization. Something like
1-4 (i.e. employee will come on 1st, 2nd, 3rd and 4th day )
2-6
8-9
..
1-14
You have to organize an event on minimum number of days such that each employee can attend the event at least twice.


APPROACH:
All employees have to attend atleast 2 times.
So I keep a count of 2 for every employee initially.


Then I initialize an array (days) of 30 days maintaining a count of number of employees who can attend on a particular day.


I take the maximum of the days array. For all the employees, who can attend on that day I reduced their counts in the first array.
When the count becomes zero for any employee, I delete him from the days array.


I keeping running this loop until all employees have count <=0.
Input via console: N (no. of Employees) and then N rows of ranges corresponding to the N employees.
Sample Input:

15
2 4
3 8
5 20
24 30
1 10
9 15
19 23
20 30
1 5
2 10
1 15
1 10
5 25
15 30
7 17
Sample output:

Printing event days: 
5
7
15
20
21
3
4
25
24
9

LCM of Array of Numbers

Finding LCM of all the elements of an array.

public static long calcLCM(int[] numArray) {
  if (null == numArray) {
   return -1;
  }
  int len = numArray.length;

  if (len < 2) {
   return -1;
  }
  int maxInArray = findMaxInArray(numArray);

  int countOnes = 0;
  boolean iFactor = true;
  long lcmOfNumbers = 1;

  for (int i = 2; i <= maxInArray; i++) {
   countOnes = 0;
   iFactor = true;
   while (iFactor) {
    iFactor = false;
    for (int j = 0; j < len; j++) {
     if ((numArray[j] > 1) && (numArray[j] % i == 0)) {
      numArray[j] = numArray[j] / i;
      iFactor = true;
     }
     if (numArray[j] == 1) {
      countOnes += 1;
     }
    }
    if (iFactor) {
     lcmOfNumbers *= i;
    }
   }
   if (countOnes == len) {
    break;
   }
  }

  return lcmOfNumbers;
 }

Approach:

A method using a table
This method works for any number of factors. One begins by listing all of the numbers vertically in a table (in this example 4, 7, 12, 21, and 42):
4
7
12
21
42
The process begins by dividing all of the factors by 2. If any of them divides evenly, write 2 at the top of the table and the result of division by 2 of each factor in the space to the right of each factor and below the 2. If they do not divide evenly, just rewrite the number again. If 2 does not divide evenly into any of the numbers, try 3.
x 2
4 2
7 7
12 6
21 21
42 21
Now, check if 2 divides again
x 2 2
4 2 1
7 7 7
12 6 3
21 21 21
42 21 21
Once 2 no longer divides, divide by 3. If 3 no longer divides, try 5 and 7. keep going until all of the numbers have been reduced to 1.
x 2 2 3 7
4 2 1 1 1
7 7 7 7 1
12 6 3 1 1
21 21 21 7 1
42 21 21 7 1
Now, multiply the numbers on the top and you have the LCM. In this case, it is 2 × 2 × 3 × 7 = 84. This is a variation on Euclid's algorithm, as common factors are essentially divided out along the way of dividing all of the numbers at once by each successive factor. You will get to the LCM the quickest if you use prime numbers and start from the lowest prime, 2.

Check if 2 strings are anagrams

Method to check if two given strings are anagrams or not.
public boolean isAnagram(String first, String second) {
if (null == first || null == second) {
return false;
}
int firstLen = first.length();
int secondLen = second.length();

if (firstLen != secondLen) {
return false;
}

char [] firstArr = first.toLowerCase().toCharArray();
char [] secondArr = second.toLowerCase().toCharArray();

Arrays.sort(firstArr);
Arrays.sort(secondArr);

for (int i=0; i<firstLen; i++) {
if (firstArr[i] != secondArr[i]) {
return false;
}
}
return true;
}

Level Order traversal of a Binary Tree

Simple level order traversal:

private void levelOrder(Node node) {
if (null == node) { return ; }
Queue<Node> queue = new LinkedList<Node>();
queue.add(node);

while (!queue.isEmpty()) {
Node tempNode = queue.remove();
System.out.print(tempNode.data + " -> ");

if (tempNode.left != null) {
queue.add(tempNode.left);
}
if (tempNode.right != null) {
queue.add(tempNode.right);
}
}
System.out.println("null");
}

Level Order Binary Tree traversal using marker node:


private void printLevelOrderBT(Node root) {
if (null == root) { return ; }
Queue<Node> queue = new LinkedList<Node>();
Node marker = new Node(Integer.MIN_VALUE);
queue.add(root);
queue.add(marker);

while (!queue.isEmpty()) {
Node node = queue.remove();

if (node.equals(marker)) {
System.out.println();

if (!queue.isEmpty()) {
queue.add(marker);
}

} else {
System.out.print(node.data + " ");
}

if (node.left != null) {
queue.add(node.left);
}

if (node.right != null) {
queue.add(node.right);
}
}

}

Level Order Binary Tree traversal using Two Queues:


private void levelOrderTwoQ(Node root) {
if (null == root) { return ;}

Queue<Node> firstQ = new LinkedList<Node>();
Queue<Node> secondQ = new LinkedList<Node>();

firstQ.add(root);

while (!firstQ.isEmpty() || !secondQ.isEmpty()) {
while (!firstQ.isEmpty()) {
Node node = firstQ.remove();
System.out.print(node.data + " ");
if (node.left != null) {
secondQ.add(node.left);
}
if (node.right != null) {
secondQ.add(node.right);
}
}
System.out.println();

while (!secondQ.isEmpty()) {
Node node = secondQ.remove();
System.out.print(node.data + " ");
if (node.left != null) {
firstQ.add(node.left);
}
if (node.right != null) {
firstQ.add(node.right);
}
}
System.out.println();
}
}

Iterative Binary Tree Traversals

Iterative PreOrder traversal of a Binary Tree:

private void preOrderIterative(Node node) {

Stack stack = new Stack();

while (node != null || !stack.isEmpty()) {

if (null == node) {

node = stack.pop();

}

System.out.print(node.data + " -> ");

if (node.right != null) {

stack.push(node.right);

}

node = node.left;

}

}

Iterative InOrder traversal of a Binary Tree:

private void inorderIterative(Node node) {

Stack stack = new Stack();

while (node != null || !stack.isEmpty()) {

if (null == node) {

node = stack.pop();

System.out.print(node.data + " -> ");

node = node.right;

}

if (node != null) {

stack.push(node);

node = node.left;

}

}

}

Iterative PostOrder traversal of a Binary Tree:

private void preorderIterative(Node node) {

Stack stack = new Stack();

while (node != null || !stack.isEmpty()) {

if (node == null) {

while (!stack.isEmpty() && (node == stack.peek().right)) {

node = stack.pop();

System.out.print(node.data + " -> ");

}

node = stack.isEmpty()? null : stack.peek().right;

}

if (node != null) {

stack.push(node);

node = node.left;

}

}

}