csTechie

Given an array of positive and negative numbers. Find the contiguous sub array of maximum sum.

   public static void subArraySum(int a[])
  {
    int i=0;
    int j=0;
    int start=0;
    int end=0;
    int maxSum = -99999;
    int cSum = 0;
    while(j < a.length)
    {
       cSum +=a[j];
       if(cSum>maxSum)// Set this as the new result
       {
          start=i;
          end = j;
          maxSum=cSum;
       }else if(cSum < 0)
       {
         cSum=0;
         i=j+1;
       }
       j++;
    }
    System.out.println("start="+start+" end="+end+" maxSum="+maxSum);

  }

  public static void sort(int[] a)
  {
    for (int i = 1; i < a.length; i++)
    {
       int current_val= a[i];
       int j= i;
       while(j > 0 && a[j-1] > current_val)
       {
          a[j]=a[j-1];
          j--;
       }
       a[j]=current_val;

    }

  }

Write a program to merge  two binary search trees, in O(n) time with O(1) space

Given a tree with only children pointing to the parents, find the least common ancestor of 2 nodes.

How would you find a cycle in a linked list? Optimize for speed.

Multiple by 8 without using multiplication or addition. Now do the same with 7

Write a program to reverse the words in a string.String is represented as an array.

Input: hello my world

Expected Output: world my hello

One of the common, yet tricky interview question is to find the lowest common ancestor node for given 2 nodes in

A. Binary Tree

B. N-ary tree

Find the maximum rectangle completely contained inside a histogram where each bars has a width of 1 unit. The heights of the bars of the histograms are given in an array e.g. {4,2,10,8,12,13,15,8,6} and they have a fixed width w = 1, say. The rectangles formed here are: 4X1, 2X9, 10X1, 8X6, 12X3, 13X2, 15X1, 8X6, 6X7 Thus, max-area rectangle = 8X6 = 48

Find the longest palindrome in a given string