Sort an array having 0,1,2 without counting

1.Use 3 pointers low,mid & hi.
2.low will point to first element from left which is not 0
3. hi will point to first element from right which is not 2
4.low will not point to 2, except when low==mid
5.mid will move from 0 to hi and if it is 2, moves it to hi
and if it is 1 moves it to low.


public int[] group012(int[]arr)
{
int low=0,mid=0,hi=arr.length-1,temp=0;

while(mid<=hi)
{


switch(arr[mid])
{
case 0:
arr[mid++]=arr[low];
arr[low++]=0;
break;
case 1:
mid++;
break;
case 2:
arr[mid]=arr[hi];
arr[hi--]=2;
}

}

return arr;
}

To find nth element from the end in a linked list

Use two pointers.
Start the second pointer when the first pointer reaches nth element.

Middle of a linked list in one traversal

Problem

       Find the middle element of a linked list, with just one traversal.


Solution.

Use 1 slow pointer and one fast pointer.
When the fast pointer reaches the end,
slow pointer will be at the middle

Sieve of Eratosthenes

To find all the prime numbers less than or equal to a given integer n:
1. Create a list of consecutive integers from two to n: (2, 3, 4, ..., n).
2. Initially, let p equal 2, the first prime number.
3. Starting from p, count up by p and cross out thus found numbers in the list (which will be 2p,
3p, 4p, etc.).
4. Find the first number not yet crossed out after p; let p now equal this number (which is the
next prime).
5. Repeat steps 3 and 4 until p is greater than n.
All the numbers in the list which are not crossed out are prime.

Queue using Stack

Enqueue():
Pop() all elements from StackA to StackB one by one - O(n)
Push() new element in StackA, so it stays at the bottom- O(1).
Pop() all elements from StackB back to StackA - O(n)
So, enqueue is O(n).


Dequeue():
Just Pop().
O(1)

Find the inorder successor of all nodes

Store the nodes to an array.
For each element, tne next element is the inorder successor.

All possible bracket combinations

How can we generate all possibilities on braces ?
N value has given to us and we have to generate all possibilities.
**Examples:**
1) if N == 1, then only one possibility () .
2) if N==2, then possibilities are (()), ()()
3) if N==3, then possibilities are ((())), (())(),()()(), ()(()) ...
Note: left and right braces should match. I mean )( is INVALID for the N==1


The below recursion tree shows the flow:

public static void allValidBrackets(int n, int open, int closed, String str) {

if (closed == n) {
System.out.println(str);
return;
}

if (open < n) {
allValidBrackets(n, open+1, closed, str + "{");
}

if (closed < open) {
allValidBrackets(n, open, closed+1, str + "}");
}
}

Cycle detection in a directed graph

Next smaller in array

For each number, find the next smaller number in the array. If next smaller number does not exists, put 0.
Eg.
Input:   1  5 7 6 3 1  6  2  9  2 7
Output: 0 3  6 3 1 0  2  0  2  0 0

Path in binary tree

There is a binary tree(Not a BST) in which you are given three nodes x,y,z .Write a function which finds whether y lies in the path b/w x
and z.
Assume z is a descedant of x, then y need to satisfy two conditions:
(1) y need to be ancester of z
(2) y need to be descendant of x

Determine all non concentric palindromes in a String

In m"ala"yalam  is a non-concentric palindrome where as malayalam, alayala, aya are concentric palindromes.




Solution:
    For each i in the string
    Find the largest palindrome having i as the center

Finding pairs

Two integer arrays, write a function to get pairs of number
Ex:
input: [2,5,6,8,10,2,3,5] & [4,7,3,5,2,10,2,4] output:[2,2,3,5,10]
input: [2,2,2,3,4,5,6,7] & [2,2,5,5,7,10] output: [2,2,5,7]


Sol.
1. Sort the smaller array.
2. Use a pointer on the unsorted array to search from beginng to end.

Pairing

Give an unsorted array of integers A and and an integer I, find out if any two members of A add up to I.

For example:
A = < 3, 25, 9, 15>
I = 12 returns true
but I = 19 returns false.

Can you find the answer in O(n*log(n)) time?
Can you find the answer in O(n) time?

O(n):
-Create array B by subtracting A[i] from I for each i
-If B[i] exists in A return true.

Deleting current node in a singly linked list

Given a singly linked list with a pointer p pointing to some node(not the first or last node), how will you delete that node? You have no access to the head of the node

Solution:

Copy next node to current node and delete next node

Merge Array

Two sorted arrays A[X] and B[Y+X]. in B array contains Y sorted elements and B can accommodate A[] X elements.

W.A.P to Merge two arrays and store resultant in B[] array.



Solution:
Merge A and B from back to front

Tree Mirror Image

Check if the left subtree is a mirror image of the right subtree.

Solution 1:
Do an inorder traversal. If result is a pallindrom then symmetric else not symmetric

Solution 2:
A solution that may work is - Preorder is reverse to its postorder

most frequent character

Given an array of characters (not sorted), how do you find the most frequent character?

Given a binary search tree find the its least depth.

LRU implementation

Use a Doubly Linked list + Hashtable, similar to the implementation of LinkedHAshMap in Java.
The Hash table will point to a node in the linked list.
Every time a page block, n,  is accessed,
  Go to the hashtable with n
  Get the node pointer
  Bring that node to the head of the doubly linked list

Find out the first non-repeating character in a given input string

Use a count sort based approach.

Check if a number is power of 2

public boolean isPowerOf2(int num)
{
if((num&(num-1))==0 && num>0)
return true;
else
return false;
}

Pairing

Given an array of size 2N, such that its elements are as follows:

{a1,a2,a3,...,an,b1,b2,b3...,bn}

You have to rearrange this array, without using any extra array such that resulting array would be:

{a1,b1,a2,b2,...,an,bn}


1. Swap a2,b1 ;  a4,b3...so that pairs  a1b1,a3b3,a2b2,a4b4 are created.
2. Now swap the pairs a3b3 with a2b2

Count leaf and non-leaf

Using recursion return the number of leaf nodes and non leaf nodes from a single method without any global variables for a given BST?

reverse pair of elements in a linked list

Lowest common ancestor in binary tree

Given a binary search tree and 2 values find the lowest common ancestor. 


The main idea of the solution is — While traversing Binary Search Tree from top to bottom, the first node n we encounter with value between n1 and n2, i.e., n1 < n < n2 is the Lowest or Least Common Ancestor(LCA) of n1 and n2 (where n1 < n2). So just traverse the BST in pre-order, if you find a node with value in between n1 and n2 then n is the LCA, if it's value is greater than both n1 and n2 then our LCA lies on left side of the node, if it's value is smaller than both n1 and n2 then LCA lies on right side

Find kth largest integer from an unsorted array of integers. Provide O(n) algorithm

Merge two sorted linked lists

Stack - getMin() in O(1)

Use two stacks, s1 and s2.
Push: Always push in s2, push in s1 too if value is less than top.
Pop:Pop from s2, if popped value is equal to top of s1, pop from s1 too.
Min: Top of s1.

Write A Program to Remove Duplicates from BST

Find the hight of a tree

Recursive solution:


Termination condition : treenode==null


1. Find the height of left subtree
2. Find the height of the right sub tree


if height of left subtree is larger
height=height of left subtree +1
else
height=height of right subtree +1

Integer Palindrome

given an integer. Check whether its binary equivalent is a palindrome or not

Find Gap

Given an unsorted array of numbers. Find if the array consists of consecutive numbers after sorting. Do this in linear time.

Example 1: If array has 5,2,3,1,4
after sorting we get 1,2,3,4,5 which represents consecutive numbers

Counter Example:
If the array has 34,23,52,12,3 after sorting we get 3,12,23,34,52 which are not consecutive

Find first n sorted elements

Describe an algorithm to find the largest 1 million numbers in 1 billion numbers. Assume
that the computer memory can hold all one billion numbers

Swap children of a tree

write a program that implements a function Swap_Tree() that takes a binary tree and swaps left and the right children of every node .

Median of a stream

Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.

Write code to check whether given tree is BST or not

Write code to check whether given tree is BST or not. Time O(n) and space O(1)

Copy Doubly Linked List

The head pointer of a doubly linked list points to a random node.
Copy the DLL by traversal the nodes just once.

Binary Search

public int binarySearch(int[]a,int key)
{
int low,mid,high;

low=0;
high=a.length;
mid=high/2;

while(low<=high) { if(a[mid]>key)
{
high=mid-1;
mid=(low+high)/2;
}
else if(a[mid] {
low=mid+1;
mid=(low+high)/2;
}
else
return mid;
}

return -1;


}

Searching in an Up Down Array

There is an array and the distance between any two consequent
elements is one(+1 or -1) and given a number. You have to check whether the
number is in array or not with minimum complexity

Missing and Duplicated

I have a array which has numbers from 1 to n one number is missing and one number is duplicated. find those in O(n)

Recursion to iteration

/recursive
void f()
{
if(cond == false)
return;
f();
g();
}
//iterative


public void iterative_f() {
int count = 0;
while (cond == false)
{
count++;
}

while(count > 0)
{
g();
count--;
}

Find an element in a partially rotated sorted array in O(log n)

O(1) Insert, delete and Get

Design a Data Structure with following operations
1.Insert(X) -> insert X if X not present
2.Delete(X) -> delete X if X present
3.Get() -> return any element if it is present
all operations in O(1).
No memory constraint.

Use an array, which has size equal to the maximum size of the key

Find the k-th Smallest Element in the Union of Two Sorted Arrays in (logn)

resource lock

Given an n-ary tree of resources arranged hierarchically. A process needs to lock a resource node in order to use it. But a node cannot be locked if any of its descendant or ancestor is locked. You are supposed to:
-> write the structure of node
-> write codes for
* Islock()- returns true if a given node is locked and false if it is not
* Lock()- locks the given node if possible and updates lock information
* Unlock()- unlocks the node and updates information.
Codes should be :
* Islock –O(1)
* Lock()- O(log n)
* unLock()- O(log n)

Check if Anagram

How do you determine to strings are anagram.

Keep an integer array of size 26.
Go through the first string and increment the array location corresponding to the character.
Go through the second string and decrement the array location corresponding to the character.
At the end, if the array contains any non-zero element, then the strings are not anagrams.

Minimum Distance in an array

Given an unsorted array and two numbers, find the minimum distance between them. For example, if the array is {1,2, 10, 2, 3, 5, 2, 1, 5} distance between 2 and 5 is 1.

Given an infix expression convert into postfix

Given a doubly linked list with just 3 numbers 0,1,2 . Sort it

1) Take 2 pointers at starting and at the end of list.
2) traverse list blindly push all the 2s at end of list.---> O(n)
3) move end pointer just before first two and sort normally by two pointer trick in O(n)

Zig Zag Order To Doubly linked list

Given a binary tree,convert into a doubly linked list,The list must be as if the tree is traversed in zig-zag order from top to botton.. (left to right in one level and right to level in the next)

Minimum number of Coins

You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount

Implement a double linked list with only one pointer

Use XOR

Common Ancestor

How to find the common ancestor of two nodes in a binary tree

mplement a function that, given a linked list that may be circular, swaps the first two elements, the third with the fourth, etc

Check if String is a number

Write a method that takes a string, and returns true if that string is a number

Recursive function for reversing linked list

Java program to reverse a number

Write a program to reverse a number. For example if 3652 is the input, the output should be 2563.

Java program for Breadth First Search of a Binary Tree

The below program uses Binary Search Tree implementation
and Queue implementation

public void BFS()
{
Queue queue=new Queue();
Processable info;
TreeNode temp,temp1;

if(root!=null)
{
queue.enqueue(root);
}

while(true)
{
if(queue.isEmpty())
break;

temp=(TreeNode)queue.dequeue();
info=(Processable)temp.data;
info.process();

temp1=temp.left;
if(temp1!=null)
queue.enqueue(temp1);
temp1=temp.right;
if(temp1!=null)
queue.enqueue(temp1);

}


}