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;
  }
 }
}

Find the 8digit number

Find a 8-digit number, where the first figure defines the count of zeros in this number, the second figure the count of numeral 1 in this number and so on....  

Start with 8 digit number, starting from left to right, 
first digit indicate number of 0's in 8 digit number, 
second digit indicate number of 1's in 8 digit number. 
Similary 7th digit indicate number of 7's in 8 digit number.


70000000 //8 digit number 7 indicate number of 0's in the number.
70000001 //As number of 7's = 1 so 7th place is 1
60000001 //As due to 1 on 7th place number of zeros = 6
60000010 //As 6 is present so 7th place, number of 6's = 1; number of 7's = 0
61000010 //As 1 is present on 7th place ; number of 1's = 1 so 2nd place there should be 1
51000010 //As number of 0's = 5 
51000100 //As 5 is present so 6th place is 1 number of 6's = 0; number of 7's = 0 
52000100 //As number of 1's = 2  
52100100 //As 2 is present on 1st place so 3rd place is 1
42100100 // As number of  0's = 4 so 1st place is 4
42101000 // As 4 is present so 5th place is 1; number of 5's, 6's and 7's = 0;
We got the answer as 4210 1000.


Source : http://anandtechblog.blogspot.com/2011/07/find-8digit-number-microsoft-interview.html

What really happens when you navigate to a URL

As a software developer, you certainly have a high-level picture of how web apps work and what kinds of technologies are involved: the browser, HTTP, HTML, web server, request handlers, and so on.

In this article, we will take a deeper look at the sequence of events that take place when you visit a URL.

http://igoro.com/archive/what-really-happens-when-you-navigate-to-a-url/

Trim Binary Search Tree

Given the root of a binary search tree and 2 numbers min and max, trim the tree such that all the numbers in the new tree are between min and max (inclusive). The resulting tree should still be a valid binary search tree. So, if we get this tree as input:

and we’re given min value as 5 and max value as 13, then the resulting binary search tree should be:

We should remove all the nodes whose value is not between min and max. We can do this by performing a post-order traversal of the tree. We first process the left children, then right children, and finally the node itself. So we form the new tree bottom up, starting from the leaves towards the root. As a result while processing the node itself, both its left and right subtrees are valid trimmed binary search trees (may be NULL as well).

http://www.ardendertat.com/2012/01/17/programming-interview-questions-26-trim-binary-search-tree/

Find Next Palindrome Number

Given a number, find the next smallest palindrome larger than the number. For example if the number is 125, next smallest palindrome is 131.
Java program : 

public class NextPalindrome {
 public static void main(String[] args) {
  int n = 2133;

  // temp variable to perform operations on n
  int temp = n;
  // calculate the number of digits
  int digits = 0;
  while (temp != 0) {
   temp = temp / 10;
   digits++;
  }

  // edge case if the given number contains all 9 s like 9 or 99 or 999
  // or...,round off to next number
  int divider = (int) Math.pow(10, digits);
  if ((n + 1) % divider == 0) {
   n = n + 1;
   digits++;
  }
  if (digits == 0)
   return;

  // handling the special case of single digit numbers
  if (digits == 1) {
   System.out.println("Next higher palindrome is : " + n + 1);
   return;
  }

  // create array of size digits to store the digits of the given number
  int[] a = new int[digits];
  temp = n;
  for (int i = digits - 1; i >= 0 && temp != 0; i--) {
   a[i] = temp % 10;
   temp = temp / 10;
  }

  // now array contains the digits in same order as of number
  int nextPalindrome = 0;
  boolean isPalindrome = false;// used for track whether we got palindrome
  // or not
  while (!isPalindrome) {
   // create mirror image of the given number
   createMirrorImage(a);
   nextPalindrome = constructNumber(a);
   if (nextPalindrome <= n) {
    int middle = (int) Math.ceil(digits / 2);
    // if the middle digit is 9 then round off to the next higher
    // number
    if (digits % 2 == 0) {
     if (a[digits / 2] == 9) {
      a[middle] = 0;
      a[middle - 1] = 0;
      a[middle - 2] += 1;
     } else {
      a[middle] += 1;
      a[middle - 1] += 1;
     }
    } else {
     if (a[middle] == 9) {
      a[middle] = 0;
      a[middle - 1] = a[middle - 1] + 1;
     } else {
      a[middle] += 1;
     }

    }
   } else {
    isPalindrome = true;
   }
  }
  System.out.println("Next higher palindrome is : " + nextPalindrome);
 }

 private static int constructNumber(int[] a) {
  int num = 0;
  for (int i = 0; i < a.length; i++) {
   num = num * 10 + a[i];
  }
  return num;
 }

 private static void createMirrorImage(int[] a) {
  int length = a.length;
  for (int i = 0, j = length - 1; i <= j; i++, j--) {
   a[j] = a[i];
  }
 }
}

Refer :  http://www.ardendertat.com/2011/12/01/programming-interview-questions-19-find-next-palindrome-number/