Interleavings of two strings

Given two strings str1 and str2, write a function that prints all interleavings of the given two strings. You may assume that all characters in both strings are different

Example :
Input: str1 = "AB",  str2 = "CD"
Output:
    ABCD
    ACBD
    ACDB
    CABD
    CADB
    CDAB

public class InterLeavedStrings {
 public static void main(String[] args) {
  String str1 = "abc";
  String str2 = "def";

  if (str1 != null && str1.length() != 0 && str2 != null
    && str2.length() != 0) {
   getInterLeavedStrings(str1, str2);
   getInterLeavedStrings(str2, str1);
  } else if (str1 == null || str1.length() == 0) {
   System.out.println(str2);
  } else {
   System.out.println(str1);
  }
 }

 private static void getInterLeavedStrings(String str1, String str2) {
  int m = str1.length();
  int n = str2.length();
  for (int i = 1; i < m; i++) {
   for (int j = 0; j < n; j++) {
    System.out.println(str1.substring(0, i) + str2.substring(0, j)
      + str1.substring(i, m) + str2.substring(j, n));
   }
  }
 }
}

Another variant of interleaving : Check a given string is interleaving of other two strings
 http://www.geeksforgeeks.org/archives/17750


Refer : http://www.geeksforgeeks.org/archives/17743

Minimum number of jumps to reach last element

Problem: Given an array of integers, each element represents the max number of jumps can make forward. What is the minimum number of element selections to reach the end of the array (starting from the first element).
Example: arr = 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9
Here the min # of selections is : 3
with the sequence : 1-> 3 -> 8 ->9
First element is 1, so can only go to 3.
Second element is 3, so can make at most 3 jumps: eg to 5 or 8 or 9.
If an element is 0, then cannot make any jumps

public class MinNumberOfJumps {
 private static int MAX = 23234;

 public static void main(String[] args) {
  int[] jumps = { 2, 3, 1, 1, 4 };
  int minJumps = getMinJumps(jumps, jumps.length);

  if (minJumps < MAX)
   System.out
     .println("Minimum number of jumps needed to reach the end of the array is : "
       + minJumps);
  else
   System.out.println("Cannot reach the end position of the array");
 }

 private static int getMinJumps(int[] jumps, int size) {
  //Boundry conditions
  if (jumps == null || size == 0 || jumps[0] == 0)
   return MAX;

  int[] dp = new int[size];
  //Initialization of dp[i]  
  for (int i = 0; i < size; i++)
   dp[i] = MAX;

  dp[0] = 0;//no need to jump at first element
  
  for (int i = 1; i < size; i++) {
   for (int j = 0; j <= i; j++) {
    if (jumps[j] >= (i - j)) {//check if jump is possible from j to is  
     if (dp[j] + 1 < dp[i]) //check if better solution available  
      dp[i] = dp[j] + 1;
    }
   }
  }
  return dp[size - 1];
 }

}

Refer  : http://avidullu.wordpress.com/2011/01/12/dp-after-a-long-time/
http://tech-queries.blogspot.in/2011/08/find-optimal-number-of-jumps-to-reach.html

All logical bit questions

• Geeksforgeeks
• Swap bits in a given number
• **Find missing number in an array 
• ** Find element which occurs only once except it all occurs thrice
• *************Find even occurring element in an array
• Find repeating and missing elemeny
• Count number of set bits in a number
• Count number of set bits in an array
• Swap two nibbles in an array
• **************Find sum of two numbers using bitwise operators
• Left shift fiddle in java
• Infinite stream of bits divisible by 3
• Smallest of three integers without comparison operators
• Boolean array puzzle
• *************Next higher number with same number of bits
• Optimization technique
• *************Add 1 to a given number
• Multiply given integer with 3.5
• Turn off right most set bit
• ***********Find whether given number is power of 4 or not
• ***********Compute integer absolute value with out branching
• Compute modulus division by a power of 2 number
• Compute minimum or maximum of two numbers with out branching
• ***********Rotate bits of a number
• ***********Find the two non repeating elements in an array of repeating elements
• ***********Count the number of bits to be flipped to convert a to b
• Count set bits in a number
• Reverse bits of a number
• Little and big endian
• Check for integer overflow
• Find the number occurring odd number of times
• Position of right most set bit
• Check whether a number is power of two or not
• Efficient way to multiply with 7
• Find parity of an unsigned number
• Check if a number is multiple of 3 or not
• Next power of 2

Linked list, Stack and queue questions

• Linked List questions in GeeksForGeeks
• ********* Copy a linked list with next and arbitrary pointer
• *********Reverse linked list iteratively and recursively
• Add two numbers stored in linked lists
• Linked list traversal
• ***********Merge two sorted linked lists. code
• Skip Lists
• Remove duplicate nodes in unsorted linked list
• Reverse alternate k nodes of a linked list
• Remove nodes which have greater value on right side in linked list
• Reverse a linked list
• Find intersection of two linked lists
• *******Write queue using stack
• Find 10 maximum numbers from a billion numbers
• ***********Element relationship in an array
• Reverse a stack inplace using recursion
• Design a resource pool which promised FIFO to every client
• Applications of priority heaps
• Delete a given node in linked list under given constraints
• Write a function to modify head pointer of a linked list
• XOR memory efficient doubly linked list
• Memory efficient doubly linked lst 
• *************Detect and remove a loop in linked list
• Detect loop in linked list
• Segregate even and odd nodes in a linked list
• Reverse alternate k nodes in a singly linked list
• ***********Sorted insert for circular linked list
• Linked list vs array
• Reverse a linked list in a group of given size
• Merge sort for linked lists
• Merge two sorted linked lists
• Identical linked lists
• Alternating split of a given linked list
• Delete alternate nodes of a linked list
• Intersection of two sorted linked lists
• Delete a node in doubly linked list
• Pairwise swap elements of given linked list
• Move last element to front of a given linked list
• Split circular linked list into two halves
• ********Reverse doubly linked list
• Recursive function to print reverse of a linked list
• ********Reverse a linked list
• Remove duplicates from an unsorted linked list
• ******Remove duplicates from a sorted linked list
• Intersection point of two linked lists
• *************** Insert a node into sorted linked list
• ***************Great tree list recursion problem
• Check if singly linked list is palindrome
• Given a pointer to a node to be deleted, how will you delete ?
• Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?
• Count number of times a number occurs in a linked list
• Nth node from the end of linked list
• Print middle of a linked list
• Print Nth node of a linked list
• Union and intersection of two linked lists
• A Queue that Supports Enqueue, Dequeue, and GetMin in Constant Time
• A Stack that Supports Push, Pop, and GetMin in Constant Time
• Implement two stacks in an array

All array questions

• Geeksforgeeks
• **Bitonic sub array 
• **Find smallest missing number
• ** Maximal sub array(Largest continuous sum)
• ** Count inversions in an array
• ** Sort an array of 0s, 1s and 2s
• ** Equilibrium index of an array
• **Median of two sorted lists
• ** Print next greater element in unsorted array
• ** Contiguous sub array which sums to zero
• ** Median of integer stream
• *********Min Heap implementation in java
• *********Max heap implementation in java
• Sort elements by frequency
• Given an array and an element x, check for pair in a[] with sum as x
• **************Merge an array of size n into another array of size m+n
• Search an element in a sorted and pivoted array
• Leaders in an array
• Block swap algorithm for array rotation
• Reversal algorithm for array rotation
• Reverse an array
• Program for array rotation
• Maximum and minimum of an array using minimum number of comparisons
• Find smallest and second smallest elements in an array
• ************Find duplicate elements in an array
• ************Floor and ceiling in sorted array
• Union and intersection of two sorted arrays
• Find the minimum length unsorted sub array, sorting which makes the complete array sorted
• **Find the two repeating elements in an array : check code for marking visited node as -ve
• Find k largest or smallest elements in an array
• Check if array elements are consecutive ?
• Find repeating and missing element in an array
• *********Given an array arr[], find the maximum j – i such that arr[j] > arr[i]
• Find fixed point in an array
• Find whether an array is subset of another array
• ********Find next palindrome
• ********Search for an element in unknown length array
• Maximum element in an array which is first increasing and then decreasing
• Find missing element in an array
• Next higher number with the same digits
• Move set of elements to destined location of an array
• Maximum contiguous product in an array
• **********Count number of minimum elements on right side of each element in an array
• Partition array into even and odd parts
• Segregate 0s and 1s
• Maximum number of ones in a row of an array
• Anagrams in a dictionary
• ***********Linear time majority vote algorithm
• *********Majority element(same as above problem)
• Boolean paranthesize
• Minimum element in an rotated array
• ***********Axis aligned rectangles
• 3 sum and 2 sum problem
• Composition of a number
• Selecting k smallest or largest elements
• Find existence of a word in a maze
• *********Maximum difference in an array 
• *********Best day to sell and buy stocks
• Number of occurances of a number in an array
• *********Permutation of digits represented by phone number
• Maximum of all sub arrays of size k
• *********Find triplet whose distance is minimum
• Check given string is anagram or not
• Find product of sub arrays with out using division operator
• Rotating an array in place
• Search for an element in rotated sorted array
• *********Find all unique triplets whose sum is zero
• Two elements whose sum is closest to zero
• ********Find kth smallest element in union of two sorted arrays
• Finding elements near the median
• Array division into groups
• **Triplet with minimum distance

All Tree questions

• Geeksforgeeks
• Convert a given tree to a sum tree
• Populate in order successor for all nodes
• **In order successor in BST
• **Connect nodes at same level using constant extra space
• **Connect Nodes at the same level
• **Trie data Structure
• **Decision Tree
• **Construct a tree from in order and pre order traversal
• **In order traversal with out recursion
• **Inorder traversal with out recursion and without stack 
• Convert an arbitrary tree to a tree that holds children sum property
• Check if a given tree is BST or not
• Size of a tree
• Lowest common ancestor
• Tree traversals
• Check if two trees are identical
• Maximum depth of a tree
• Which traversal sequence needed to construct a binary tree
• Find the node with minimum value in BST
• Print all root to leaf paths one per line
• Count leaf nodes in a tree
• Check for children sum property in binary tree
• Check if tree is height balanced ?
• ***********Tournament Tree (Winner Tree) and Binary Heap
• ***********Get Maximum width of a tree
• Root to leaf path sum equal to given number
• Check if a given tree is sum tree or not
• Print ancestors of a node in tree
• Print nodes at K distance from root
• Sorted array to balanced BST
• Sorted order printing of a given array that represents a BST
•  Construct a binary search tree
• Trim binary search tree
• Mirror image of a tree in iterative way
• Mirror image of a tree in recursive way
• Level of a node in a binary search tree
• Peripheral of a tree
• Isomorphic tree
• Quasi isomorphic trees
• Is a tree complete
• Level order tree traversal
• Level order traversal of a tree in spiral form
• Binary search of a tree
• Binary search tree validity
• Saving binary search tree to a file
• Serialization and de serialization of binary tree
• Successor or predecessor rules in a binary tree
• Remove duplicate nodes in a binary search tree
• Is sub tree ? 
• Pint edge(boundary)  nodes of a tree
• Anti clock wise peripheral of a tree
• ************Largest binary search tree in a binary tree*************
• Diameter of a binary tree
• **********Convert binary tree into spiral doubly linked list
• Foldable binary trees
• ***********Convert binary tree into doubly linked list
• Find Kth largest and smallest number in Binary search tree
• Minimum distance between two nodes of a binary tree
• Vertical sum in a binary tree
• Merge two balanced binary search trees
• Maximum sum leaf to root path in binary tree

Construct a Binary search tree

If you are given a number N, build a binary search tree of size N with node values from 1 to N.

public class BuildTree {

 public Node getTree(int n) {
  if (n <= 0) {
   System.out
     .println("Asking for constructing a tree of size zero or negative number.");
   return null;
  }
  return buildTree(1, n);
 }

 public Node buildTree(int left, int right) {
  if (left > right)
   return null;

  int rootValue = (int) Math.floor((left + right) / 2);
  Node node = new Node(rootValue);
  node.left = buildTree(left, rootValue - 1);
  node.right = buildTree(rootValue + 1, right);
  return node;
 }

 public static class Node {

  public int value;
  // member variables will be initialized to null by default.
  public Node left;
  public Node right;

  public Node(int value) {
   this.value = value;
  }

  public Node(int value, Node left, Node right) {
   this.value = value;
   this.left = left;
   this.right = right;
  }
 }
}