Cormen solutions

Go to This link :

http://aiou.academia.edu/MuhammadAhmad/Books/429715/SOLUTIONS_MANUAL_Introduction_to_Algorithms_2nd_edition_by_T._Cormen_C._Leiserson_R._Rivest_C._Stein

Finding elements near median

Q : Given an unsorted array A of n distinct numbers and an integer k where
1 <= k <= n, design an algorithm that finds the k numbers in A that
are closest in value to the median of A in O(n) time.


Sol :

1. Find the median, M: O(n)
2. Form a second array containing y(i) = abs(x(i) - M): O(n)
3. Find the kth smallest element of this array, K: O(n)
4. Scan the original array and locate the first k elements such that
abs(x(i) - M) <= K: O(n)

Total algorithm: O(n).

Largest BST in Binary Tree

• Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

         Refer : http://www.leetcode.com/2010/11/largest-binary-search-tree-bst-in.html

• Given a binary tree, find the largest Binary Search Tree (BST), where largest means BST with largest number of nodes in it. The largest BST may or may not include all of its descendants.

         Refer : http://www.leetcode.com/2010/11/largest-binary-search-tree-bst-in_22.html

Check whether n is power of x

Write the given number in base of x.
If it contains only one 1,it is power of x.

ex : Given M, find if M = 3^x for some positive integer x efficiently. Do not use log, pow etc..

3^n contains only one 1 in the 3-base representation.So write number M in base-3, and check if it contains only one digit(1).

Excel sheet question

Q:Given a series A,B,C .......Z, AA, AB,AC,AD....AZ,BA,BB...BZ,CA....(Open excel sheet. The names of column represent the series). Given input as number 'n'. Output the 'n' th string of the series. & also vice versa if given string prints its corrsponding string...e.g given AC then its interger is 29 & given 40774 its string value is ABZ..


Sol :base 26 conversion with digits being A-Z

Code :

public static String ExcelMapIntToStr(int n)
{
 StringBuilder sb = new StringBuilder();
 while(n>0)
 {
  sb.append((char)(('A' - 1) + (n-1)%26 + 1)); 
  n = (n-1)/26;
 }
 return sb.reverse().toString();
}
 
public static int ExcelMapStrToInt(String str)
{
 int val = 0;
 int base = 1;
 for(int i = str.length() - 1; i>=0; i--)
 {
  val += (str.charAt(i) - ('A' - 1))*base;
  base *= 26;
 }
 return val;
}

Refer : http://geeksforgeeks.org/forum/topic/amazon-interview-question-for-software-engineerdeveloper-fresher-about-algorithms-data-structure-strings

Array division

Q: Divide a list of numbers into groups of consecutive numbers but their
original order should be preserved.
Example:
<8,2,4,7,1,0,3,6>
Two groups:
<2,4,1,0,3> <8,7,6>


Algorithm :
We can so this in O(nlogn),if we maintain index along with every element


(copied from google algo group post)
One will be to find the bfs (there will be many and this will lead to
a forest )
This , in turn can be done in O(e+v) , using adjancy list or matrix .
Whenever , we cannot go further , start from any new uncovered node ,
and keep exploring recursively .Keep a boolean flag array for the
elements you have already covered .

Also , this looks like a union find problem .So one can also do this
using disjoint set data structure .

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure

Powerset or Combination problem

Given an array containing both positive and negative numbers.Program to find the set of elements whose sum is equal to given number
Ex :  array is : { -1, 2, -3, 4, 5, 6 };
sum : 5

Java code :

public class PowerSetProblem {

 private static final int size = 6;
 private static int[] arr = { -1, 2, -3, 4, 5, 6 };

 static void generate_powerset(int[] temparr, int level, int start, int k) {
  int i, j;
  for (i = start; i < size; i++) {
   temparr[level] = arr[i];

   int sum = 0;

   for (j = 0; j <= level; j++)

    sum += temparr[j];

   if (sum == k) {
    for (j = 0; j <= level; j++)
     System.out.print("  " + temparr[j] + "  ");
    System.out.println();
   }
   if (i < size - 1)
    generate_powerset(temparr, level + 1, i + 1, k);
  }
 }

 public static void main(String[] args) {
  int[] temparr = new int[size];
  generate_powerset(temparr, 0, 0, 5);
 }

}

problem2 :finding two elements whose sum is equal to given umber Algorithm 1) Sort all the elements of the array. 2) Find the index of first positive element, this is initial value of right index r. 3) Initialize: left index l = r – 1. min_sum = INT_MIN 4) In a loop, look for the candidates by comparing sum with minimum sum. If arr[l] + arr[r] becomes negative then increment the right index r, else decrement left index l. refer :http://geeksforgeeks.org/?p=4034