Monday, March 31, 2014

Programming errors cause program crashes in different places every single time

Problem
You are given the source to an application which crashes when it is run. After running it ten times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?
Solution
The question largely depends on the type of application being diagnosed. However, we can give some general causes of random crashes.

General cases
  • Not initialising a variable but attempting to use its value.
  • Dereferencing a null pointer.
  • Reading or writing past the end of an array.
  • disk full, i.e. other processes may delete a different file causing more space to be available
  • memory issue, i.e. other processes allocate and/or free memory. OutOfMemoryException in java can result due to this. But risk of such errors happening in c/c++ are higher, as programmer has to explicitly manage memory. Suppose, you don't free the pointer which will result in memory leak. If you free up the pointer, but you reuse the variable somewhere which results in dangling pointer.
  • a pointer points to a random location in memory that is changed by another process causing some values be "valid" (very rare though)
Specific to C
  • Defining a preprocessor macro that starts with an underscore and either a capital letter or another underscore.

 

Check if array contains duplicates

Problem 
Given an array of n elements, check if it has duplicates

Solution
This problem is similar to following problem :
We can use some of the method used there.

Method 1 - Brute force
Use two loops. In the outer loop, pick elements one by one and count the number of occurrences of the picked element in the inner loop.
This method doesn’t use the other useful data provided in questions like range of numbers is between 1 to n and there are only two repeating elements.

bool hasDuplicates(int arr[], int size)
{
  int i, j;
  printf(" Repeating elements are ");
  for(i = 0; i < size; i++)
    for(j = i+1; j < size; j++)
      if(arr[i] == arr[j])
        return true;
  return false;
}  

Time Complexity: O(n*n)
Auxiliary Space: O(1)

Method 2 - Use Count array (for hashing)
Traverse the array once. While traversing, keep track of count of all elements in the array using a temp array count[] of size n, when you see an element whose count is already set, print it as duplicate.
This method uses the range given in the question to restrict the size of count[], but doesn’t use the data that there are only two repeating elements.
bool hasDuplicates(int arr[], int size)
{
  int *count = (int *)calloc(sizeof(int), (size - 2));
  int i;
  printf(" Repeating elements are ");
  for(i = 0; i < size; i++)
  { 
    if(count[arr[i]] == 1)
      return true;
    else
     count[arr[i]]++;
  }   
  return false;
}  
Time Complexity: O(n)
Auxiliary Space: O(n)

Method 3 - Sorting the array and compare adjacent array

bool hasDuplicates(int arr[], int size)
{
  sort(arr);
  int i, j;
  printf(" Repeating elements are ");
  for(i = 0; i < size; i++)
    for(j = i+1; j < size; j++)
      if(arr[i] == arr[j])
         return true;
  return false;
}

Sorting takes O(n log n) time, but as they are integers we can use counting sort, which takes O(n) time.

Time complexity = O(n log n) OR O(n)

Time complexity = O(n log n)
Space Complexity = O(1)
Sorting takes O(n log n) time, and then comparing takes O(n) times.

Method 4 - Method of negation
As we are told that array of integers are from 1 to n, they are positive. For each element A[i], go to index A[i] , i.e. select array element A[A[i]] and negate it. Continue this process until you find some negative number.

Pseudocode
Traverse the array. Do following for every index i of A[].
{
  check for sign of A[abs(A[i])] ;
  if positive then
     make it negative by   A[abs(A[i])]=-A[abs(A[i])];
  else  // i.e., A[abs(A[i])] is negative
     this   element (ith element of list) is a repetition
}
Example: A[] =  {1, 1, 2, 3, 2}
i=0; 
Check sign of A[abs(A[0])] which is A[1].  A[1] is positive, so make it negative. 
Array now becomes {1, -1, 2, 3, 2}

i=1; 
Check sign of A[abs(A[1])] which is A[1].  A[1] is negative, so A[1] is a repetition.

i=2; 
Check sign of A[abs(A[2])] which is A[2].  A[2] is  positive, so make it negative. '
Array now becomes {1, -1, -2, 3, 2}

i=3; 
Check sign of A[abs(A[3])] which is A[3].  A[3] is  positive, so make it negative. 
Array now becomes {1, -1, -2, -3, 2}

i=4; 
Check sign of A[abs(A[4])] which is A[2].  A[2] is negative, so A[4] is a repetition.
Note that this method modifies the original array and may not be a recommended method if we are not allowed to modify the array.
bool hasDuplicates(int arr[], int size)
{
  int i;  
  
  printf("\n The repeating elements are");
   
  for(i = 0; i < size; i++)
  {
    if(arr[abs(arr[i])] > 0)
      arr[abs(arr[i])] = -arr[abs(arr[i])];
    else
      return true;
  }
  return false;         
}  

Note that solution works only for positive number, and for the ranged array of 0 to n-1 elements.


Find duplicates in the ranged array

Problem
Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times.
Follow UP - Find these repeating numbers in O(n) and using only constant memory space.
Example
Input : array  =  {1, 2, 3, 1, 3, 6, 6}, n = 7
Output = 1,3,6

Solution
This problem is an extended version of following problem.
Find the two repeating elements in a given array

Method 1 and Method 2 of the above link are not applicable as the question says O(n) time complexity and O(1) constant space. Also, Method 3 and Method 4 cannot be applied here because there can be more than 2 repeating elements in this problem. Method 5 can be extended to work for this problem. Below is the solution that is similar to the Method 5.

Algorithm:
traverse the list for i= 0 to n-1 elements
{
  check for sign of A[abs(A[i])] ;
  if positive then
     make it negative by   A[abs(A[i])]=-A[abs(A[i])];
  else  // i.e., A[abs(A[i])] is negative
     this   element (ith element of list) is a repetition
}
Implementation:
void printRepeating(int arr[], int size)
{
  int i;
  printf("The repeating elements are: \n");
  for (i = 0; i < size; i++)
  {
    if (arr[abs(arr[i])] >= 0)
      arr[abs(arr[i])] = -arr[abs(arr[i])];
    else
      printf(" %d ", abs(arr[i]));
  }
}

Note: The above program doesn’t handle 0 case (If 0 is present in array). The program can be easily modified to handle that also. It is not handled to keep the code simple.

Time Complexity: O(n)
Auxiliary Space: O(1)

Please write comments if you find the above codes/algorithms incorrect, or find better ways to solve the same problem.

References
http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/

Find the two repeating elements in ranged array

Problem
You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers.
Example
Input : array = {4, 2, 4, 5, 2, 3, 1} and n = 5, array.length = n+2 = 7
Output : 4,2

Solution
This can be achieved by various methods.

Method 1 - Brute force
Use two loops. In the outer loop, pick elements one by one and count the number of occurrences of the picked element in the inner loop.
This method doesn’t use the other useful data provided in questions like range of numbers is between 1 to n and there are only two repeating elements.
void printRepeating(int arr[], int size)
{
  int i, j;
  printf(" Repeating elements are ");
  for(i = 0; i < size; i++)
    for(j = i+1; j < size; j++)
      if(arr[i] == arr[j])
        printf(" %d ", arr[i]);
}  
Time Complexity: O(n*n)
Auxiliary Space: O(1)

Method 2 - Use Count array (for hashing)
Traverse the array once. While traversing, keep track of count of all elements in the array using a temp array count[] of size n, when you see an element whose count is already set, print it as duplicate.
This method uses the range given in the question to restrict the size of count[], but doesn’t use the data that there are only two repeating elements.
void printRepeating(int arr[], int size)
{
  int *count = (int *)calloc(sizeof(int), (size - 2));
  int i;
  printf(" Repeating elements are ");
  for(i = 0; i < size; i++)
  { 
    if(count[arr[i]] == 1)
      printf(" %d ", arr[i]);
    else
     count[arr[i]]++;
  }   
} 

Time Complexity: O(n)
Auxiliary Space: O(n)

Method 3 - Sorting the array and compare adjacent array
void printRepeating(int arr[], int size)
{
  sort(arr);
  int i, j;
  printf(" Repeating elements are ");
  for(i = 0; i < size; i++)
    for(j = i+1; j < size; j++)
      if(arr[i] == arr[j])
        printf(" %d ", arr[i]);
}

Time complexity = O(n) Sorting takes O(n log n) time if we use comparison based sort, but as they are integer we can use counting sort.And then comparing takes O(n) times.

Method 4 - Make two equations
Let the numbers which are being repeated are X and Y. We make two equations for X and Y and the simple task left is to solve the two equations.
We know the sum of integers from 1 to n is n(n+1)/2 and product is n!. We calculate the sum of input array, when this sum is subtracted from n(n+1)/2, we get X + Y because X and Y are the two numbers missing from set [1..n]. Similarly calculate product of input array, when this product is divided from n!, we get X*Y.
Given sum and product of X and Y, we can find easily out X and Y.
Let summation of all numbers in array be S and product be P
X + Y = S – n(n+1)/2
XY = P/n!

Using above two equations, we can find out X and Y. 
For array = 4 2 4 5 2 3 1, we get S = 21 and P as 960.
X + Y = 21 – 15 = 6
XY = 960/5! = 8
X – Y = sqrt((X+Y)^2 – 4*XY) = sqrt(4) = 2

Using below two equations, we easily get X = (6 + 2)/2 and Y = (6-2)/2
X + Y = 6
X – Y = 2

Note that there can be addition and multiplication overflow problem with this approach.
The methods 3 and 4 use all useful information given in the question 
// function to get factorial of n 
 
void printRepeating(int arr[], int size)
{
  int S = 0;  // S is for sum of elements in arr[] 
  int P = 1;  // P is for product of elements in arr[]  
  int x,  y;   // x and y are two repeating elements 
  int D;      // D is for difference of x and y, i.e., x-y
  int n = size - 2,  i;
 
  // Calculate Sum and Product of all elements in arr[] 
  for(i = 0; i < size; i++)
  {
    S = S + arr[i];
    P = P*arr[i];
  }       
   
  S = S - n*(n+1)/2;  // S is x + y now 
  P = P/fact(n);         // P is x*y now 
   
  D = sqrt(S*S - 4*P); // D is x - y now 
   
  x = (D + S)/2;
  y = (S - D)/2;
   
  printf("The two Repeating elements are %d & %d", x, y);
}    
 
int fact(int n)
{
   return (n == 0)? 1 : n*fact(n-1);
}   

Time Complexity: O(n)
Auxiliary Space: O(1)

Method 5 - Use XOR
Thanks to neophyte for suggesting this method.
The approach used here is similar to method 2 of this post.
Let the repeating numbers be X and Y, if we xor all the elements in the array and all integers from 1 to n, then the result is X xor Y.

The 1’s in binary representation of X xor Y is corresponding to the different bits between X and Y. Suppose that the kth bit of X xor Y is 1, we can xor all the elements in the array and all integers from 1 to n, whose kth bits are 1. The result will be one of X and Y.

void printRepeating(int arr[], int size)
{
  int xor = arr[0]; // Will hold xor of all elements 
  int set_bit_no;  // Will have only single set bit of xor 
  int i;
  int n = size - 2;
  int x = 0, y = 0;
   
  // Get the xor of all elements in arr[] and {1, 2 .. n} 
  for(i = 1; i < size; i++)
    xor ^= arr[i];  
  for(i = 1; i <= n; i++)
    xor ^= i;   
 
  // Get the rightmost set bit in set_bit_no 
  set_bit_no = xor & ~(xor-1);
 
  // Now divide elements in two sets by comparing rightmost set
   bit of xor with bit at same position in each element. 
  for(i = 0; i < size; i++)
  {
    if(arr[i] & set_bit_no)
      x = x ^ arr[i]; //XOR of first set in arr[] 
    else
      y = y ^ arr[i]; //XOR of second set in arr[] 
  }
  for(i = 1; i <= n; i++)
  {
    if(i & set_bit_no)
      x = x ^ i; //XOR of first set in arr[] and {1, 2, ...n }
    else
      y = y ^ i; //XOR of second set in arr[] and {1, 2, ...n } 
  }
   
  printf("\n The two repeating elements are %d & %d ", x, y);
}     
 

Method 6 - Use array elements as index and negation

Traverse the array. Do following for every index i of A[].
{
check for sign of A[abs(A[i])] ;
  if positive then
     make it negative by   A[abs(A[i])]=-A[abs(A[i])];
  else  // i.e., A[abs(A[i])] is negative
     this   element (ith element of list) is a repetition
}
Example:
 A[] =  {1, 1, 2, 3, 2}
i=0; 
Check sign of A[abs(A[0])] which is A[1].  
A[1] is positive, so make it negative. 
Array now becomes {1, -1, 2, 3, 2}

i=1; 
Check sign of A[abs(A[1])] which is A[1].  
A[1] is negative, so A[1] is a repetition.

i=2; 
Check sign of A[abs(A[2])] which is A[2].  
A[2] is  positive, so make it negative. '
Array now becomes {1, -1, -2, 3, 2}

i=3; 
Check sign of A[abs(A[3])] which is A[3].  
A[3] is  positive, so make it negative. 
Array now becomes {1, -1, -2, -3, 2}

i=4; 
Check sign of A[abs(A[4])] which is A[2].  
A[2] is negative, so A[4] is a repetition.
Note that this method modifies the original array and may not be a recommended method if we are not allowed to modify the array.
void printRepeating(int arr[], int size)
{
  int i;  
  
  printf("\n The repeating elements are");
   
  for(i = 0; i < size; i++)
  {
    if(arr[abs(arr[i])] > 0)
      arr[abs(arr[i])] = -arr[abs(arr[i])];
    else
      printf(" %d ", abs(arr[i]));
  }         
}  

Thanks.
References
http://www.geeksforgeeks.org/find-the-two-repeating-elements-in-a-given-array/

Find the two non-repeating elements in a ranged array of repeating elements

Problem
Given an array in which all numbers except two are repeated once. (i.e. we have 2n+2 numbers and n numbers are occurring twice and remaining two have occurred once). Find those two numbers in the most efficient way.
Example
Input : {2,4,7,9,2,4}
Output : 7,9

Solution
Method 1 - Use Sorting
First sort all the elements. In the sorted array, by comparing adjacent elements we can easily get the non-repeating elements. Time complexity of this method is O(nLogn)

Method 2 - Use XOR
Let x and y be the non-repeating elements we are looking for and arr[] be the input array. First calculate the XOR of all the array elements.
     xor = arr[0]^arr[1]^arr[2].....arr[n-1]
All the bits that are set in xor will be set in one non-repeating element (x or y) and not in other. So if we take any set bit of xor and divide the elements of the array in two sets – one set of elements with same bit set and other set with same bit not set. By doing so, we will get x in one set and y in another set. Now if we do XOR of all the elements in first set, we will get first non-repeating element, and by doing same in other set we will get the second non-repeating element.
Let us see an example.
   arr[] = {2, 4, 7, 9, 2, 4}
1) Get the XOR of all the elements.
     xor = 2^4^7^9^2^4 = 14 (1110)
2) Get a number which has only one set bit of the xor.   
   Since we can easily get the rightmost set bit, let us use it.
     set_bit_no = xor & ~(xor-1) = (1110) & ~(1101) = 0010
   Now set_bit_no will have only set as rightmost set bit of xor.
3) Now divide the elements in two sets and do xor of         
   elements in each set, and we get the non-repeating 
   elements 7 and 9. Please see implementation for this   
   step.

Implementation:
class Pair{
 public int x;
 public int y;
}
 
// This finction sets the values of *x and *y to nonr-epeating
// elements in an array arr[] of size n
public Pair get2NonRepeatingNos(int arr[], int n)
{
  int xor = arr[0]; // Will hold xor of all elements 
  int set_bit_no;  // Will have only single set bit of xor 
  int i;
  int x = 0;
  int y = 0;
 
  // Get the xor of all elements 
  for(i = 1; i < n; i++)
   xor ^= arr[i];
 
  // Get the rightmost set bit in set_bit_no 
  set_bit_no = xor & ~(xor-1);
 
  // Now divide elements in two sets by comparing rightmost set
   bit of xor with bit at same position in each element. 
  for(i = 0; i < n; i++)
  {
    if(arr[i] & set_bit_no)
     x = x ^ arr[i]; //XOR of first set 
    else
     y = y ^ arr[i]; //XOR of second set
  }
  
  return new Pair(x,y);
}

Time Complexity: O(n)
Auxiliary Space: O(1)

References
http://www.geeksforgeeks.org/find-two-non-repeating-elements-in-an-array-of-repeating-elements/

Sunday, March 30, 2014

Find the kth number with prime factors 3, 5 and 7

Problem
Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7.
Solution
We have already solved the similar problem for ugly numbers, where the factor was 2,3 5 here.
 

Find a line which passes the most number of points

Problem
Given a two dimensional graph with points on it, find a line which passes the most number of points.
Solution
Method 1 - Naive solution
This is the brute force solution. We take point 1, and then point 2 and make a line. Now in the third nested loop, check if point 3 is existing on the same line or not.
Pseudocode
Line findLineWithMaxPoint(Set points){
   foreach Point p1 in points
      foreach Point p2  in (points - {p1}){
         Line l = makeLine(p1,p2);
         int count = 2 //line contains p1 and p2
         foreach(Point p3 in (points-{p1,p2})){
            if(l.contains(p3))
               count++;
         }
         if(maxCount<count){
            count = maxCount;
            resultLine = l;
         }
      }
return resultLine;
}
As we can see there are 3 nested loops, and hence time complexity : O(n^3).

Java code
public class Line {
    private double slope;
    private double intercept;
 
    private final double THRESHOLD = Math.pow(10, -8);
 
    public Line(double slope, double intercept) {
        super();
        this.slope = slope;
        this.intercept = intercept;
    }
 
    public Line(Pair<Double> p1, Pair<Double> p2) {
        this.slope = (p2.getY() - p1.getY()) / (p2.getX() - p1.getX());
        this.intercept = (p2.getX() * p1.getY() - p1.getX() * p2.getY())
                / (p2.getX() - p1.getX());
    }
 
    public boolean contains(Pair<Double> p) {
        double x = p.getX();
        double y = p.getY();
        return Math.abs(y - (slope * x + intercept)) < THRESHOLD;
    }
}
 
public static Line findLine(Set<Pair<Double>> points) {
    int maxNumber = -Integer.MAX_VALUE;
    int number = 0;
    Line result = null;
    for (Pair<Double> p1 : points) {
        for (Pair<Double> p2 : points) {
            if (!p1.equals(p2)) {
                number = 0;
                Line line = new Line(p1, p2);
                for (Pair<Double> p : points) {
                    if (line.contains(p))
                        number++;
                }
                if (number > maxNumber) {
                    maxNumber = number;
                    result = line;
                } 
            }
        }
    }
    return result;
}


Method 2 - Use hashtable
Problem with above approach is that the lines may be duplicate. And if we have points p1, and p2 already covered as part of line, which helped us find p3, when we select p1 and p3, we will again select p2.

We have a bunch of line segments, represented as a slope and y-intercept, and we want to find the most common slope and y-intercept. How can we find the most common one? This is really no different than the old "find the most common number in a list of numbers" problem. We just iterate through the lines segments and use a hash table to count the number of times we've seen each line.

This can be solved in O(n^2) time and O(m) space. where m is the distinct number of lines among all given points.

  1. Use a hash table - key is line and number of appearance of line as value.
  2. For each pair of points find the line in slope y intercept form
  3. if the line is not there in hash table, add it to the hash table with appearance value 1
  4. if the line is already in hash table, increment the appearance value
  5. line with the max number of appearance in the hash table is the result.

Java code
In java we have to implement a hashCode() method to make the class object uniquely identifiable by the hashtable.
public static Line findBestLine(GraphPoint[] points) {
    Line bestLine = null;
    HashMap<Line, Integer> line_count = new HashMap<Line, Integer>();
    for (int i = 0; i < points.length; i++) {
        for (int j = i + 1; j < points.length; j++) {
            Line line = new Line(points[i], points[j]);
            if (!line_count.containsKey(line)) {
                line_count.put(line, 0);
            }
            line_count.put(line, line_count.get(line) + 1);
            if (bestLine == null
                    || line_count.get(line) > line_count.get(bestLine)) {
                bestLine = line;
            }
        }
    }
    return bestLine;
}
 
public class Line {
    private static double epsilon = .0001;
    public double slope;
    public double intercept;
    private boolean infinite_slope = false;
 
    public Line(GraphPoint p, GraphPoint q) {
        if (Math.abs(p.x - q.x) > epsilon) { // if x’s are different
            slope = (p.y - q.y) / (p.x - q.x); // compute slope
            intercept = p.y - slope * p.x; // y intercept from y=mx+b
        } else {
            infinite_slope = true;
            intercept = p.x; // x-intercept, since slope is infinite
        }
    }
 
    public boolean isEqual(double a, double b) {
        return (Math.abs(a - b) < epsilon);
    }
 
    @Override
    public int hashCode() {
        int sl = (int) (slope * 1000);
        int in = (int) (intercept * 1000);
        return sl | in;
    }
 
    @Override
    public boolean equals(Object o) {
        Line l = (Line) o;
        if (isEqual(l.slope, slope) && isEqual(l.intercept, intercept)
                && (infinite_slope == l.infinite_slope)) {
            return true;
        }
        return false;
    }
}


  • Be careful about the calculation of the slope of a line. The line might be completely vertical. We can keep track of this in a separate flag (infinite_slope). We need to check this condition in the equals method.
  • Remember that when we perform division to calculate the slope, division is not exact. Therefore, rather than checking to see if two slopes are exactly equal, we need to check if they’re different by greater than epsilon, in our case 10-8.
Method 3 - Hough transform
Not really sure how hough transform works, but you can read more here.

References
http://tianrunhe.wordpress.com/2012/04/03/find-a-line-which-passes-the-most-number-of-points/

Find a line to cut two squares in half

Problem: 

Given two squares on a two dimensional plane, find a line that would cut these two squares in half.

Solution:

Any Line passing the centers of the two squares will cut them in halves. So, we have to connect the lines between the center of the 2 squares. The straight line that connects the two centers of the two squares will cut both of them into half.

Code in java
public class Square {
   public double left;
   public double top;
   public double bottom;
   public double right;
   public Square(double left, double top, double size) {
          this.left = left;
          this.top = top;
          this.bottom = top + size;
          this.right = left + size;
   }

   public Point middle() {
          return new Point((this.left + this.right) / 2,
                                       (this.top + this.bottom) / 2);
   }

   public Line cut(Square other) {
          Point middle_s = this.middle();
          Point middle_t = other.middle();
          if (middle_s == middle_t) {
                 return new Line(new Point(left, top),
                 new Point(right, bottom));
          } else {
                 return new Line(middle_s, middle_t);
          }
   }
}

Note specific to java  - If == operator between the 2 point objects in cut method. I am not sure if it will work, as == operator in java compares references. So, better approach is Point should implement equals() method and compare the 2 point object like this:
if(middle_s.equals(middle_t)){
    ....
}

Thanks.
References :
http://tianrunhe.wordpress.com/2012/04/02/find-a-line-to-cut-two-squares-in-half/
http://stackoverflow.com/questions/6886836/can-i-use-the-operator-to-compare-point-objects-in-java 

Implement *, -, and / operators using only +

Problem
Write a method to implement *, – , / operations You should use only the + operator.
Solution
IF we have 2 numbers a, b
  • a * b can be implemented as adding a for b times.Take care of overflow as a*b may result in overflow.
  • a – b can be implemented as addition of a and -b.
  • a / b can be implemented as finding how many times you need to add b, until getting a.
 Here is the solution in java:
public static int negate(int number) {
    return ~number + 1;
}
 
public static int abs(int number) {
    return number < 0 ? negate(number) : number;
}
 
public static int multiply(int a, int b) {
    int multiplier = Math.min(abs(a), abs(b));
    int multiplicant = (multiplier == abs(a) ? abs(b) : abs(a));
    if(multiplier==0 || multiplicant==0)
        return 0;
    int result = 0;
    for (int i = 0; i < multiplier; i = i + 1) {
        long holdResult = result+multiplicant;
        if(holdResult>Integer.MAX)
            throw new java.lang.ArithematicException("Overflow in integer");
        result = (int)holdResult;
    }
    if (abs(a) == a) { // a >= 0
        if (abs(b) == b) // b >= 0
            return result;
        else
            // b < 0;
            return negate(result);
    } else { // a < 0
        if (abs(b) == b) // b >= 0
            return negate(result);
        else
            // b < 0;
            return result;
    }
}
 
public static int substract(int a, int b) {
    return a + negate(b);
}
 
public static int divide(int a, int b) {
    if (b == 0) {
        throw new java.lang.ArithmeticException("Divide by 0.");
    }
 
    int divident = abs(a);
    int divisor = abs(b);
    int quotient = 0;
 
    while (divident >= divisor) {
        divident = substract(divident, divisor);
        quotient = quotient + 1;
    }
 
    if (abs(a) == a) { // a >= 0
        if (abs(b) == b) // b >= 0
            return quotient;
        else
            // b < 0;
            return negate(quotient);
    } else { // a < 0
        if (abs(b) == b) // b >= 0
            return negate(quotient);
        else
            // b < 0;
            return quotient;
    }
}

Thanks.

Determine whether two lines would intersect on a Cartesian plane

Problem
Given two lines on a Cartesian plane, determine whether the two lines would intersect.
Solution
 On a Cartesian plane, if two lines do not intersect, they must be parallel with each other. Hence, their slopes must be the same. If their slopes are different, they would intersect. A line is represented as ax+by+c=0 on a Cartesian plane and the slope is given by -\frac{a}{b}. Therefore if -\frac{a_{0}}{b_{0}} \neq -\frac{a_{1}}{b_{1}} for two lines, they will intersect.


public class Line {
    static final double epsilon = 0.000001;
    public double slope;
    public double yintercept;
 
    public Line(double s, double y) {
        slope = s;
        yintercept = y;
    }
 
    public boolean intersect(Line line2) {
        return Math.abs(slope - line2.slope) > epsilon
                || Math.abs(yintercept - line2.yintercept) < epsilon;
    }
}

Two lines can be the same. In that case, we assume they intersects (overlap). We need to consider the floating system in a computer. Never use == to compare two floating numbers in java.

One shot or at least two shots in three games?

Problem:

You have a basketball hoop and someone says that you can play 1 of 2 games.
Game #1: You get one shot to make the hoop.
Game #2: You get three shots and you have to make 2 of 3 shots.
If p is the probability of making a particular shot, for which values of p should you pick one game or the other?

Solution:

 For game #1, you have probability p of winning.
 For game #2, you can either make 2 shots of 3, with probability 3p^2(1-p), or make all of the three shots, with probability p^3.

 Therefore, to choose game #1, you need to have: p  > 3p^2(1-p)+p^3

p > 3p^2 - 2p^3
2p^3 - 3p^2 + p > 0

p(2p^2 - 3p + 1) > 0
p(2p-1)(p-1) & gt;0

here p>0 is obvious as probability cannot be negative. Also, p-1 > 0 is not correct as p cannot be greater than 1. hence p>1/2 is correct.

Answer:

So, if p > 1/2 I will take game 2, else if it is less than I will take game 1.

Three Gods - God of Truth, Lies and Chaos

Problem:

You are stranded on an Island and on that island are 3 all knowing all powerful gods. One god is the god of truth, who always tells the truth and can never lie. The second god is the god of lies, he always lies and never tells the truth. The 3rd god is the god of chaos, he tells both lies and truths, however, completely randomly. The gods appear as identical twins, they all look the same. The gods also speak a language that you do not understand, except that you know that "uga" and "booga" are the responses yes and no (you however do not know which word is yes and which is no). You can only ask 3 yes or no questions to the gods in order to figure out which god is which. What 3 questions do you ask? 

 Solution

 We have to take advantage of the fact, that even the all-knowing god of truth doesn't know what God of chaos will answer to any question. Once, we find of god of truth, we can easily find of god of chaos or god of lies.

Lets denote god of truth by T, lies by F and god of chaos by C.

If we ask one of the 3 gods, about answer what C will answer, and he remains silient, its god of Truth, T.

Example


Lets order gods by 1,2, 3

Question # 1
Ask god 1 and 2 : “if I ask 3rd god of chaos 'you are one god of truth, who always tells the truth, right?' what would 3rd God
say?"
Case 1
God 1 : reply = Yes or No
God 2 : reply = Yes or No

Case 2
God 1 : silent
God 2 : yes or no

If its case 1, we know that both are answering and hence god 3 is T. In case 2, god 1 is silent so he is T, and god 3 may or may not be C.


Question #2
After case 1 of Question 1, ask god 3 : "f I ask 3rd god of chaos 'you are one god of truth, who always tells the truth, right?' what would 3rd God say?"

Case 11 : God 3 : = Can't reply.He is god of truth T.

After case 2 of Question 1, ask god 1 "if I ask 3rd god of chaos 'you are one god of truth, who always tells the truth, right?' what would 3rd God say?"
God 1 - Cant reply, god 3 is C

if god 1 replies, 2nd god is C.

Now we know who is  which god, but still don't know what is Uga and Booga.

Question #3
Ask God 3 : " is god 2 god of lies,who always lies ? "

God 3 : = Yes.(or whatever answer he tells, that means he is Uga or Booga is equal to yes)


hence, god 1 = god of chaos
god 2 = god of lies
god 3 = god of truths

Please let me know if you have some other solution.

Labour and work problem - 20 women replaced by a men and boy alternatively

Problem:

20 women can finish a job in 20 days. After each day, one woman is replaced by a man or a boy alternatively starting with a man. Man is twice efficient and boy is half efficient as a woman. On which day does the job get completed?

Solution:

Lets treat man as 2 women and boy as half woman. Starting 1st day 1 W is removed and 1M added. So, we have 21W at work. Next day, 1B is added and 1W is removed, so, we have 20.5 W now.

Now add there units of work daily, and check if it is just greater than 400, because total unit of work is 20X20 = 400.

So, each alternative day when man is added, we do following unit of work
21,21.5,22 and so on. So, an AP with d=0.5, a = 21

Similarly for alternative day when a boy is added we have following unit of work:
20.5,21,21.5 and so on.

Now, by hit and trial, we get 9 days of man add and 9 days of boy add and total is 18 days.

Answer :

                18 days

Saturday, March 29, 2014

3 bags of 2 marbles

Problem:

You have three bags, each containing two marbles. Bag A contains two white marbles, Bag B contains two black marbles, and Bag C contains one white marble and one black marble. You pick a random bag and take out one marble. It is a white marble. What is the probability that the remaining marble from the same bag is also white?

Solution:

Reasoning:

A = {W,W}
B = {B, B}
C = {B, W}


We have already selected a bag, which has a white marble, so randomly at first we have selected bag A or C. Now we have to take the marble from the same selected bag.

Let A, B, C denotes the event that bag A, B, C is picked. Let W_k denotes the event that the kth marble picked is white. By the law of total probability and Bayes' theorem,
P(W_2|W_1)
= P(W_2|A,W_1)*P(A|W_1)+P(W_2|C,W_1)*P(C|W_1)
= P(W_2|A,W_1)*P(W_1|A)*P(A)/P(W_1)+0
= (1)(1)*(1/3)/P(W_1)
= (1/3)/P(W_1).
By the law of total probability again,
P(W_1)
= P(W_1|A)*P(A)+P(W_1|B)*P(B)+P(W_1|C)*P(C)
= (1)(1/3)+0+(1/2)(1/3) = 1/2.
Therefore
P(W_2|W_1)
= (1/3)/(1/2)
= 2/3.

In simpler terms : 
Now there are 3 probabilities :

You chose Bag A, first white marble. The other marble will be white
You chose Bag A, second white marble. The other marble will be white
You chose Bag C, the white marble. The other marble will be black

So 2 out of 3 possibilities are white.

Why not 1/2? You are selecting marbles, not bags.Because in bags A and C, we have 3 marbles left (2W and 1 B) and probability of selecting 1W ball is 2/3.

Answer:

                  2/3 (not 1/2)

Frog leaping 3m and slipping 2m

Problem:

A frog is at the bottom of a 30 meter well. Each day he summons enough energy for one 3 meter leap up the well. Exhausted, he then hangs there for the rest of the day. At night, while he is asleep, he slips 2 meters backwards. How many days does it take him to escape from the well?

Solution:

Each day he makes it up another meter, and then on the twenty seventh day he can leap three meters and climb out. On the 28th day, he will leap and get out.

Answer:

                 28 Days

Circus tower sorting problem

Problem
A circus is designing a tower routine consisting of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.

EXAMPLE:
Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom: (56, 90)
(60,95) (65,100) (68,110) (70,150) (75,190)
Solution

Proposed solution by the book:
  1. Sort all items by height first, and then by weight. This means that if all the heights are unique, then the items will be sorted by their height. If heights are the same, items will be sorted by their weight. Example: »»Before sorting: A(60, 100),  B(70, 150), C(56, 90) D(75, 190) E(60, 95) F(68,110). »After sorting:
    C (56, 90),
    E (60, 95),
    A (60,100),
    F (68, 110),
    B (70,150),
    D (75,190).
    
  2. Find the longest sequence which contains increasing heights and increasing weights. To do this, we:
    • Start at the beginning of the sequence. Currently, max_sequence is empty.
    • If, for the next item, the height and the weight is not greater than those of the previous item, we mark this item as "unfit"
      (60,95)         (65,100)         (75,80)         (80, 100)
                                     (unfit item)
      
    • If the sequence found has more items than “max sequence”, it becomes “max sequence”.
    • After that the search is repeated from the “unfit item”,
      until we reach the end of the original sequence.

Time Complexity
  • Sort the data according to height. Denote it as D1. That is O(nlog n). 
  • Sort the data according to weight. Denote it as D2. That is O(nlog n). 
  • Find the length of the Longest Common Sub-sequence of D1 and D2. Using dynamic programming, it's O(n^2).
Here is the code in java
public static int highestTower(List<Pair<Integer>> data) {
 
    class HeightComparator implements Comparator<Pair<Integer>> {
        private int which;
 
        public HeightComparator(int which) {
            this.which = which;
        }
 
        @Override
        public int compare(Pair<Integer> p1, Pair<Integer> p2) {
            if (which == 0) {
                if (!p1.getX().equals(p2.getX()))
                    return p1.getX() - p2.getX();
                else {
                    return p1.getY() - p2.getY();
                }
            } else {
                if (!p1.getY().equals(p2.getY()))
                    return p1.getY() - p2.getY();
                else {
                    return p1.getX() - p2.getX();
                }
            }
        }
    }
 
    List<Pair<Integer>> copy = new ArrayList<Pair<Integer>>();
    copy.addAll(data);
    Collections.sort(data, new HeightComparator(0));
    Collections.sort(copy, new HeightComparator(1));
    return LCSLength(data, copy);
}
 
private static int LCSLength(List<Pair<Integer>> X, 
        List<Pair<Integer>> Y) {
    int[][] array = new int[X.size() + 1][Y.size() + 1];
    for (int i = 0; i < X.size(); ++i)
        array[i][0] = 0;
    for (int j = 0; j < Y.size(); ++j)
        array[0][j] = 0;
    for (int i = 0; i < X.size(); ++i) {
        for (int j = 0; j < Y.size(); ++j) {
            if (X.get(i).equals(Y.get(j)))
                array[i + 1][j + 1] = array[i][j] + 1;
            else
                array[i + 1][j + 1] = 
                    Math.max(array[i + 1][j], array[i][j + 1]);
        }
    }
    return array[X.size()][Y.size()];
}


References
http://tianrunhe.wordpress.com/2012/04/01/circus-tower-sorting-problem/
http://stackoverflow.com/questions/6893041/dynamic-programming-question
http://martinm2w.wordpress.com/2012/06/06/9-7-sort-search-circus-tower-largest-possible-number-of-ppl/

Searching in a sorted array of strings with empty strings

Problem
Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.
Example: find “ball” in ["at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""] will return 4
Example: find “ballcar” in ["at", "", "", "", "", "ball", "car", "", "", "dad", "", ""] will return -1

Solution
The worst we can do is O(n) where we just do a linear search.

I tried to do better in the sense that we do a binary search, however if we encounter “”, we have to exam both sides. In this way, worst case we still do a O(n) search but in average, it’s better off.
public static int findLocation(String[] array, int i, int j, String str) {
    int mid;
    while (i <= j) {
        mid = (i + j) / 2;
        if (array[mid].equals("")) {
            int leftIndex = findLocation(array, i, mid - 1, str);
            if (leftIndex == -1)
                return findLocation(array, mid + 1, j, str);
            else
                return leftIndex;
        } else {
            if (str.compareTo(array[mid]) == 0)
                return mid;
            if (str.compareTo(array[mid]) < 0)
                j = mid - 1;
            if (str.compareTo(array[mid]) > 0)
                i = mid + 1;
        }
    }
    return -1;
}

References 
http://tianrunhe.wordpress.com/2012/03/31/searching-in-a-sorted-array-of-strings-with-empty-strings/

Friday, March 28, 2014

Sorting a 2GB file with one string per line

Problem
If you have a 2GB file with one string per line, which sorting algorithm would you use to sort the file and why?
Solution
When an interviewer gives a size limit of 2GB, it should tell you something – in this case, it suggests that they don’t want you to bring all the data into memory.
So what do we do? We only bring part of the data into memory..

Method 1 - K way external merge sort
Because 2GB size of strings are way too huge to be put into main memory, I came up with two ways:
  1. K-way merge sort. Divide the file into K pieces, transfer them into main memory and sort them.
  2. Bucket sort. Sort each character in order.
Algorithm:
  1. Divide the file into K chunks of size X, where X * K = 2 GB. Bring each chunk into memory and sort the lines as usual using any O(nlogn) algorithm. Save the lines back to the file.
  2. Now bring the next chunk into memory and sort.
  3. Once we’re done, merge them one by one.This is called K-way merge.
The above algorithm is also known as external sort. The last step depends on the size of the main memory available. We can either merge 2 at a time or proper K way merge.

Example - Merge 2 (or 3) at a time
Suppose we have 3 sets of data - A,B,C. K = 3.
Now we can merge A and B together , such that X = A + B. Then we can merge X and C. Y = X+C.
This method is uses 2 merges at a time and requires less memory.

Example - Proper K way merge
where you select the next element from any of the groups. With that you would check the lowest value in every list to see which one comes next:
Y = A + B + C.

Which of these you choose depends on the available memory and the element size.

For example, if you have 100M memory available to you and the element size is 100K, you can use the latter. That's because, for a 2G file, you need 20 groups (of 100M each) for the sort phase which means a proper N-way merge will need 100K by 20, or about 2M, well under your memory availability.
Alternatively, let's say you only have 1M available. That will be about 2000 (2G / 1M) groups and multiplying that by 100K gives 200M, well beyond your capacity.

So you would have to do that merge in multiple passes. Keep in mind though that it doesn't have to be multiple passes merging two lists.
You could find a middle ground where for example each pass merges ten lists. Ten groups of 100K is only a meg so will fit into your memory constraint and that will result in fewer merge passes.

Method 2 - Caching
Here what we can do is we can again divide the 2G file into K chunks of X memory. So, the chunks become X1,X2,X3 and so on. Now we load chunk X1, iterate over chunk X2,  merge X1 and X2, and only keep lowest element in Memory. So, now we have  Y = X1 + X2. But, only Y/2 is kept in memory and likewise we will continue. Of-course this method can be improved upon to bring upon deterministic-ness.

Sort an array of strings so that anagrams are next to each other

Problem
Write a method to sort an array of strings so that all the anagrams are next to each other.
Example
INPUT : "xyz", "ca", "ab", "ac", "ba", "zyx" 
OUTPUT: "ab", "ba", "ac", "ca", "xyz", "zyx"

Lets see the solutions now.
Solution

Method 1 - Using bubble sort
Check if two pairs of strings are anagrams or not, if yes, swap.

Java code
private static boolean areAnagrams(String s1, String s2) {
    if (s1.length() != s2.length() || s1 == null || s2 == null)
        return false;
    s1 = s1.toLowerCase();
    s2 = s2.toLowerCase();
    int[] table = new int[26];
    for (int i = 0; i < s1.length(); ++i) {
        int index = s1.charAt(i) - 'a';
        table[index]++;
    }
    for (int i = 0; i < s2.length(); ++i) {
        int index = s2.charAt(i) - 'a';
        if (table[index] <= 0)
            return false;
        table[index]--;
    }
    for (int i = 0; i < 26; ++i) {
        if (table[i] > 0)
            return false;
    }
    return true;
}
 
private static void swap(String[] strings, int i, int j) {
    String temp = strings[i];
    strings[i] = strings[j];
    strings[j] = temp;
}
 
public static void sortAnagrams(String[] strings) {
    for (int i = 0; i < strings.length - 1; ++i) {
        for (int j = i + 1; j < strings.length; ++j) {
            if (areAnagrams(strings[i], strings[j]))
                swap(strings, i + 1, j);
        }
    }
}

Here sort anagrams is the main method.
Time complexity - O(n^2).

Method 2 - Use hashtable
Calculate the hash value of each word in such a way that all anagrams have the same hash value. Populate the Hash Table with these hash values. Finally, print those words together with same hash values. A simple hashing mechanism can be modulo sum of all characters. With modulo sum, two non-anagram words may have same hash value. This can be handled by matching individual characters

Method 3 - Sort the individual words and compare
Take two auxiliary arrays, index array and word array. Populate the word array with the given sequence of words. Sort each individual word of the word array. Finally, sort the word array and keep track of the corresponding indices. After sorting, all the anagrams cluster together. Use the index array to print the strings from the original array of strings.

Let us understand the steps with following input Sequence of Words:
"cat", "dog", "tac", "god", "act"
1) Create two auxiliary arrays index[] and words[]. Copy all given words to words[] and store the original indexes in index[]
index[]:  0   1   2   3   4
words[]: cat dog tac god act
2) Sort individual words in words[]. Index array doesn’t change.
index[]:   0    1    2    3    4
words[]:  act  dgo  act  dgo  act
3) Sort the words array. Compare individual words using strcmp() to sort
index:     0    2    4    1    3
words[]:  act  act  act  dgo  dgo
4) All anagrams come together. But words are changed in words array. To print the original words, take index from the index array and use it in the original array. We get
"cat tac act dog god"
Following is C implementation of the above algorithm. In the following program, an array of structure “Word” is used to store both index and word arrays. DupArray is another structure that stores array of structure “Word”.

So, though we are using indexing based on array indices, but we can achieve same thing via hashmap(pseudocode):

    Loop through the array of strings
    For each string,
        first sort its characters,
        using the sorted string as key and original string as value,
        put into a hash table. 
        you will end up with a hash table that with keys as sorted strings,
            and values being all anagrams, meanwhile, those values are ordered.
        You may use map<string, set<string> > to serve for this purpose.
    iterate over the hash-table and output all anagrams together for a given key, 
        they should be next to each other


Time Complexity: Let there be N words and each word has maximum M characters. The upper bound is O(NMLogM + MNLogN).

Method 4 - Non-agnostic solution in java
A simple solution in java is to use Comparable or Comparator interface. Here is the solution:
public class AnagramComparator implements Comparator<String> {
    public String sortChars(String s) {
        char[] content = s.toCharArray();
        Arrays.sort(content);
        return new String(content);
    }
 
    public int compare(String s1, String s2) {
        return sortChars(s1).compareTo(sortChars(s2));
    }
}
 
public static void main(String[] args) {
    String[] strings = { "xyz", "ca", "ab", "ac", "ba", "zyx" };
    AnagramComparator comparator = new AnagramComparator();
    Arrays.sort(strings, comparator);
}

References 
http://tianrunhe.wordpress.com/2012/03/28/sort-an-array-of-strings-so-that-anagrams-are-next-to-each-other/
http://stackoverflow.com/questions/15515324/how-to-sort-an-array-of-strings-with-anagrams-next-to-each-other
http://www.geeksforgeeks.org/given-a-sequence-of-words-print-all-anagrams-together/


Merge two sorted arrays - One having big enough buffer to hold another

Problem

You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.
Another way to ask same question
Given a sorted array of size n with n elements (array1) and a sorted array of size 2n with n elements (array2), merge them to get a sorted array of size 2n. Do this in linear time and in-place.

Example

array1 = {1, 3, 6}
array2 = {2, 4, 5, _, _, _}
sortedArray = {1, 2, 3, 4, 5, 6}

Solution

Method 1 - Merge sort
This is part of the merge-sort. Let the position of the last element located in the 2 arrays is called tail. Also, for array B, end is same as tail of the array. We start with tails of the 2 arrays, and compare the 2 elements and put them at the end of the array A, whichever is maximum.

Code in java
public static void bufferMerge(int[] A, int[] B, int sizeAdata) {
    // Assume sizeAdata + sizeB = A.length
    // i.e., B exactly fits into the buffer at the end of A
    int aEnd = A.length - 1; // Index of last location of array A
    int aTail = sizeAdata - 1;// Index of last element in array A
    int bTail = B.length - 1;// Index of last element as well as 
       //last location in array B

    // Start comparing from the last element and merge A and B
    while (aTail >= 0 && bTail >= 0) {
        if (A[aTail] > B[bTail]) {
            A[aEnd--] = A[aTail--];
        } else {
            A[aEnd--] = B[bTail--];
        }
    }
    while (bTail >= 0) {
        A[aEnd--] = B[bTail--];
    }
}

Time Complexity - O (m+n) where size of A as m and size of B as n. So , a linear time algorithm.

Similar Problem:

Question : Given a sorted array of size n with n elements (array1) and a sorted array of size 2n with n elements (array2) which are scattered throughout the array, merge them to get a sorted array of size 2n. Do this in linear time and in-place.

Example:
array1 = {1, 3, 6}
array2 = {2, _,4 , 5, _, _}
sortedArray = {1, 2, 3, 4, 5, 6}

Again solution is same as above, but first make array 2 to skip all the whitespaces and make it like this:
array2 = {2, ,4 , 5, _, _,_}



Eight Queen Puzzle (likewise N Queen)

Problem
Write an algorithm to print all ways of arranging eight queens on a chess board so that none of them share the same row, column or diagonal.
(image courtesy)

Solution
This is a classic problem to implement using backtracking. It has 92 distinct solutions. If solutions that differ only by symmetry operations (rotations and reflections) of the board are counted as one, the puzzle has 12 fundamental solutions.Also, when we say N queen problem, we have a NXN board. so, here we have 8X8 board implicitly.

Method 1 - Backtracking
We will start from the first row and move down to the last row placing a queen at each row and checking that each queen satisfies the following two conditions:

  • The column number must be different from the already placed queens.
  • It should not share a diagonal with already placed queens. 
Here is the code in java
private static int BOARD_SIZE = 8;

public static void eightQueenProblem(int row, int[] columnForRow,
        int[][] solution) {
    if (row == BOARD_SIZE) {
  printBoard(solution);
    } else {
        for (int i = 0; i < solution[0].length; ++i) {
            columnForRow[row] = i;
            if (check(row, columnForRow)) {
                solution[row][i] = 1;
                eightQueenProblem(row + 1, columnForRow, solution);
                solution[row][i] = 0;
            }
            columnForRow[row] = -1;
        }
    }
}
 
private static boolean check(int row, int[] columnForRow) {
    for (int i = 0; i < row; ++i) {
        int diff = Math.abs(columnForRow[row] - columnForRow[i]);
        if (diff == 0 || diff == row - i)
            return false;
    }
    return true;
}

private static void printBoard(int[][] solution)
{
 for (int i = 0; i < solution.length; ++i) {
  for (int j = 0; j < solution[i].length; ++j) {
                System.out.print(solution[i][j]);
  }
            System.out.println();
    }
    count++;
    System.out.println();
}

Note :
  • Use of columnForRow[] should be marked. It simplifies 2-D problem to 1-D.
  • It is simply try and error approach with backtracking. It tries to assign position line by line therefore eliminating the duplicate solution. However, solutions are not unique in terms of rotations. 
Here is the pseudocode
1) Start in the leftmost column
2) If all queens are placed
    return true
3) Try all rows in the current column.  Do following for every tried row.
    a) If the queen can be placed safely in this row then mark this [row, 
        column] as part of the solution and recursively check if placing  
        queen here leads to a solution.
    b) If placing queen in [row, column] leads to a solution then return 
        true.
    c) If placing queen doesn't lead to a solution then umark this [row, 
        column] (Backtrack) and go to step (a) to try other rows.
3) If all rows have been tried and nothing worked, return false to trigger 
    backtracking.

Dry running the above code
(to come soon)
Here is  wikipedia image showing how it is solved:
Time complexity - exponential
You can refer the time complexities here. Of-course recursion take O(N!), which is really slow.

References
http://puddleofriddles.blogspot.in/2011/07/write-algorithm-to-print-all-ways-of.html
http://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf
http://en.literateprograms.org/Eight_queens_puzzle_%28C%29
http://en.wikipedia.org/wiki/Eight_queens_puzzle
http://www.geeksforgeeks.org/backtracking-set-3-n-queen-problem/
http://tianrunhe.wordpress.com/2012/03/28/eight-queen-puzzle/
http://stackoverflow.com/questions/17926069/puzzled-about-backtracking-in-eight-queen
http://www.chegg.com/homework-help/questions-and-answers/poor-man-s-n-queens-problemn-queens-arranged-n-x-n-chessboard-way-queen-checks-another-que-q1009394

Number of ways of representing n cents using quarters, dimes, nickels and pennies

Problem
Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.
Solution

Method 1 - Recursion
This is a recursive problem, so let’s figure out how to do makeChange(n) using prior solutions (i.e., sub-problems).
Let’s say n = 100, so we want to compute the number of ways of making change of 100 cents. What’s the relationship to its sub-problems?
We know that makeChange(100):
= makeChange(100 using 0 quarters) + makeChange(100 using 1 quarter) + makeChange(100 using 2 quarter) + makeChange(100 using 3 quarter) + makeChange(100 using 4 quarter)
Can we reduce this further? Yes!
= makeChange(100 using 0 quarters) + makeChange(75 using 0 quarter) + makeChange(50 using 0 quarters) + makeChange(25 using 0 quarters) + 1
Now what? We’ve used up all our quarters, so now we can start applying our next biggest denomination: dimes.
This leads to a recursive algorithm that looks like this:
public static int makeChange(int n, int denom) {
    int next_denom = 0;
    switch (denom) {
    case 25:
        next_denom = 10;
        break;
    case 10:
        next_denom = 5;
        break;
    case 5:
        next_denom = 1;
        break;
    case 1:
        return 1;
    }
    int ways = 0;
    for (int i = 0; i * denom <= n; i++) {
        ways += makeChange(n - i * denom, next_denom);
    }
    return ways;
}

References
http://tianrunhe.wordpress.com/2012/03/27/number-of-ways-of-representing-n-cents-using-quarters-dimes-nickels-and-pennies/

Implement the “paint fill” function

Problem
Implement the “paint fill” function that one might see on many image editing programs. That is, given a screen (represented by a 2-dimensional array of Colors), a point, and a new color, fill in the surrounding area until you hit a border of that color.
Solution
Again, the solution falls in the bucket of recursion, backtracking.


Method 1 - Recursion

First, let’s visualize how this method works. When we call Paint Fill (eg, “click” paint fill in the image editing application) on, say, a green pixel, we want to “bleed” outwards. Pixel by pixel, we expand outwards calling PaintFill on the surrounding pixel. When we hit a pixel that is not green, we stop. Surrounding green pixels may still be painted if they are touched by another Paint Fill operation.

  • Base case: the point is at the border. Do nothing.
  • Recursion: check the up, down, left and right point to see if we can fill in.

Java code
public static void paintFillRecur(Color[][] screen,
        int x, int y, Color origin, Color toBeFilled) {
    if (screen[x][y].equals(origin)) {
        screen[x][y] = toBeFilled;
 
        if (x - 1 >= 0)
            paintFillRecur(screen, x - 1,
                    y, origin, toBeFilled);//left
        if (x + 1 < screen.length)
            paintFillRecur(screen, x + 1,
                    y, origin, toBeFilled);//right
        if (y - 1 >= 0)
            paintFillRecur(screen, x,
                    y - 1, origin, toBeFilled);//top
        if (y + 1 < screen[0].length)
            paintFillRecur(screen, x,
                    y + 1, origin, toBeFilled);bottom
    }
}

References 
http://tianrunhe.wordpress.com/2012/03/27/implement-the-paint-fill-function/

Print all combinations of n balanced parentheses

Problem
Implement an algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses.

Example
Input     3 (i.e., 3 pairs of parentheses)
Output    ()()(), ()(()), (())(), ((()))

Solution

This is a classic combinatorial problem that manifests itself in many different ways. Such kind of strings are called Dyck strings (see more here), which contain n X's and n Y's such that no initial segment of the string has more Y's than X's. example:
XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY

These problems are essentially identical:
  • Generating all possible ways to balance N pairs of parentheses (i.e. this problem)
  • Generating all possible ways to apply a binary operator to N+1 factors
  • Generating all full binary trees with N+1 leaves
  • Many others...
Such problems can be solved by recursion, backtracking, dynamic programming.


Method 1 - Recursion
We have to keep track of open and close parentheses. So we track how many open and close parentheses are "on stock" for us to use as we're building the string recursively.
  • If there's nothing on stock, the string is fully built and you can just print it out
  • If there's an open parentheses available on stock, try and add it on.
    • Now you have one less open parentheses, but one more close parentheses to balance it out
  • If there's a close parentheses available on stock, try and add it on.
    • Now you have one less close parentheses

Code
    static void printAllParenthesesCombination(int openStock, int closeStock, String s) {
        if (openStock == 0 && closeStock == 0) {
            System.out.println(s);
        }
        if (openStock > 0) {
            printAllParenthesesCombination(openStock-1, closeStock+1, s + "(");
        }
        if (closeStock > 0) {
            printAllParenthesesCombination(openStock, closeStock-1, s + ")");
        }
    }
    public static void main(String[] args) {
        brackets(3, 0, "");
    }

Method 2 - Dynamic programming
Lets start with the base case

  • base case , i.e. n =1
    if N == 1,
    output : ( )
  • Now for N == 2, we have one more pair of braces. So we will use intuition of adding “(” at the front always(coz for being properly valid the first bracket has to be opening bracket. It’s a must). And then we add “)” at all the indices.

    Let’s simulate it here,

    we have String str = "( )" ;
    
    for(int i = 0; i < str.length(); i++)
    String ans = "("  +  str.substring(0, i) + ")" + str.substring(i);
    
    // the closing brace is used at all the possible positions around the given String ans.
    Thus, for i = 0, ans = "( ) ( )"
    for i = 1, and = "( ( ) )"
    

    That’s it. Given String is of length two only. So, lets go for general n
  • Now for N == n

private static Set<String> set = new HashSet<String>();

public static void printAllParenthesisCombination(int s, int n, String str) {
    if (s == n) {
        set.add(str);
        return;
    }
    if (set.contains(str))
       return;
    for (int i = 0; i < str.length(); i++) {
       String ok = "("+ str.substring(0, i) + ")" + str.substring(i);
       printAllParenthesisCombination(s + 1, n, ok);
    }
}

//Calling method : 
printAllParenthesisCombination(1, n, "()")

In the above code I have used Set, because different parentheses may sometimes lead to same parentheses after insertion of "("‘ and ")". Thus instead of repeatedly calling it, I am prefering memoisation.

See also - http://en.wikipedia.org/wiki/Catalan_number, and good articles by Eric Lipert here and here.

References

Thanks

Thursday, March 27, 2014

LATIN SQUARE” and its implementation

Problem
Understand Latin Square and its implementation
Understanding the latin square
“A Latin square is an n × n array filled with n different Latin letters, each occurring exactly once in each row and exactly once in each column” – Wikipedia. You can find the detail explanation of the properties of this Square here on Wikipedia


In this article we will build a square to match the definition. As the definition suggest Latin square is square in which the row elements do not repeat and the column elements do no repeat.
This article talks about how to fill numbers.Leonhard Euler however initially proposed it to be filled with Latin characters and thus the name.

So we can ask the question is a Latin square unique for a given dimension.NO, the possibilities are many in fact it is not easily computable.One such calculation by van Lint and Wilson is shown in the Wikipedia article. Our interest is to simply build one such Latin square with numbers.

Latin Square have had various application. One such is they can be used as error correcting codes. Perhaps the most well know application is the game of Sudoku. Sudoku is a special case of Latin square where in the additional property is that for a 9×9 square 3×3 sub squares must contain all the 9 numbers. KenKen puzzles are also a variant of Latin square. They are also used to formulate statistical experiments. Dating services can use Latin squares to Organize meeting between n number of boys and girls (marriage problem). Most popular is scheduling of round-robin tournaments.


IMPLEMENTATION:
Following is a C++ program that displays the for a ‘N’ order dimension, Latin squares of the order N,N-1…1
Firstly the Logic.
Step 1. Generate a array randomly. Lets call this Original
for Eg : Original[ 1 , 2 , 4 , 3 ]
We keep the first digit as it is. From this digit find the index from which we can extract the value and place it accordingly
index = (1 – 1) =0
value[0] = 1
So,
place 1 at (1-1) = 0 index of row 0
place 1 at (2-1) = 1 index of row 1
place 1 at (4-1) = 3 index of row 2
place 1 at (3-1) = 2 index of row 3
partial square looks like ( B – not yet found) – You can see the output to match this derivation
1 B B B
B 1 B B
B B B 1
B B 1 B
Step 2: Now rotate the Original array by one position to the left 2 4 3 1
NOTE : However the index and value are with reference to the original array
Let us derive
First digit – 2 . Index needed = (2-1) = 1
Original[1] = 2 (notice it is not 4 , we are still using values from original array)
So,
place 2 at (2-1) = 1 index of row 0
place 2 at (4-1) = 3 index of row 1
place 2 at (3-1) = 2 index of row 2
place 2 at (1-1) = 0 index of row 3
Now square looks like
1 2 B B
B 1 B 2
B B 2 1
2 B 1 B
You can derive further. So this can be implemented by two function shuffle and rotate. Shuffle will use a random generator function to generate the initial permutation and then use rotate method to do the one shift rotate for n times
Here is a code in cpp-
#include <iostream>
#include <stdlib.h>
#include <iomanip>
 
using namespace std;
 
void shuffle(int array1[], int size)
{
     int i, temp, random, last;
 
     for (i = 0; i < size; i++)
           array1[i] = i + 1;
 
     for (last = size; last > 1; last--)
     {
           random = rand() % last;
           temp = array1[random];
           array1[random] = array1[last - 1];
           array1[last - 1] = temp;
     }
}
 
void rotate(int array2[], int size)
{
     int temp, i;
 
     temp = array2[0];
     for (i = 0; i < size - 1; i++)
           {array2[i] = array2[i+1];}
     array2[size - 1] = temp;
}
 
int main()
{
     int sequence[10],jumbled[10];
     int square[10][10];
     int position, value, i, j, size;
 
     srand((unsigned)time(NULL));
     cout<<"Enter the Dimension of Square you need \n";
     cin>>size;   
      
     while (size != 0)
     {
           shuffle(jumbled, size);
           for (i = 0; i < size; i++){
                 sequence[i] = jumbled[i];}
 
           for (i = 0; i < size; i++)
           {
                 position = sequence[0];
                 value = jumbled[position - 1];
 
                 for (j = 0; j < size; j++){
                       square[j][sequence[j] - 1] = value;}
 
                 rotate(sequence, size);
           }
           cout << endl;
           cout << "A Latin Square of Order " << size << " is: " << endl << endl;
        
           for (i = 0; i < size; i++)
           {
                 for (j = 0; j < size; j++)
         {
                       cout << setw(5) << square[i][j];
                 }
         cout << endl;
           }
         size--;
     }
     return 0;
}

OUTPUT:
Used in explanation
laptop:~/code$ ./a.out
Enter the Dimension of Square you need
4
A Latin Square of Order 4 is:
1 2 4 3
4 1 3 2
3 4 2 1
2 3 1 4
A Latin Square of Order 3 is:
2 1 3
1 3 2
3 2 1
A Latin Square of Order 2 is:
1 2
2 1
A Latin Square of Order 1 is:
1
laptop:~/code$ ./a.out
Enter the Dimension of Square you need
4
A Latin Square of Order 4 is:
1 3 4 2
3 2 1 4
2 4 3 1
4 1 2 3
A Latin Square of Order 3 is:
3 1 2
2 3 1
1 2 3
A Latin Square of Order 2 is:
1 2
2 1
A Latin Square of Order 1 is:
1
A detail explanation about Latin squares is found here at cut the knot site.
Also you can refer to code of a simple Latin square using C here

 Reference
http://chinmaylokesh.wordpress.com/category/data-structures/matrix/
http://www.tylo42.com/latin_square 

Permutations of every subset of size K

Problem
Given a array of characters of size N. Devise an algorithm to generate all possible permutations of given size K (K <= N). 
Solution

Method 1 - Append characters till the length K is reached
We first list the combinations using recursive procedure by selecting or not selecting characters until K length has been formed The for each combination we permute them using another recursive procedure

Time : O(N!)
Space : O(N!) when storing results O(1) if directly output the result

Code in c:
void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
void select(char *input, int start, int N, char *selection, int length, int K, stack<string> &combinations){
    if(start <= N){
        if(length == K){
            selection[length] = '\0';
            combinations.push(string(
selection));
        }
        else {
            select(input, start + 1, N, selection, length, K, combinations);
            selection[length] = input[start];
            select(input, start + 1, N, selection, length + 1, K, combinations);
        }
    }
}

void permute(char *input, int index, int N, stack<string> &permutations)
{
   if (index == N)
        permutations.push(string(input));
   else
   {
        for (int i = index; i < N; i++)
       {
            swap(input + index, input + i);
            permute(input, index + 1, N, permutations);
            swap(input + index, input + i);
        }
   }
}

void all_permutations(char *input, int K, stack<string> &permutations){
    int N = strlen(input);
    stack<string> combinations;
    char *selection = new char[K+1];
    char *temp = new char[K+1];
   
    select(input, 0, N, selection, 0, K, combinations);
    while(!combinations.empty()){
        strcpy(temp, combinations.top().c_str());
        permute(temp, 0, K, permutations);
        combinations.pop();
    }
}

Reference -
http://algorithmsforever.blogspot.in/2011/11/permutations-of-string.html
 

Design an OO parking lot

Problem
Design an OO parking lot. What classes and functions will it have. It should say, full, empty and also be able to find spot for Valet parking. The lot has 3 different types of parking: regular, handicapped and compact.


Solution
Lets start with the design.
class ParkingLot
1. ParkingLot keeps array of ParkingSpot
2. Separate array of vacant ParkingSpot 
3. Separate array for HandiCappedDrivers, some x%
3. ParkingSpot FindVacantSpaceNearestEntrance()
4. IsParkingLotFull(), IsEmpty(), IsNormal()

class ParkingSpot
1. distance from ParkingLot entrance
2. Take() - take the ParkingSpot
3. Vacate() - empty the ParkingSpot
 
ParkingSpot has an Entrance.

class HandicappedParkingSpot is a subclass of ParkingSpot.
class RegularParkingSpot is a subclass of ParkingSpot.
class CompactParkingSpot is a subclass of ParkingSpot.

class Parker
1. ParkingSpot it occupies
2. Vehicle he has
3. park() - calls ParkingSpot.take()
4. unPark() - calls ParkingSpot.vacate()

class Valet is a subclass of Parker 
1. calls ParkingLot.FindVacantSpaceNearestEntrance(), which returns a ParkingSpot
   that can call ParkingLot.FindVacantSpaceNearestEntrance(), which returns a ParkingSpot.

class HandiCappedParker is subclass of Parker
class CompactParker a subclass of Parker 
class RegularParker a subclass of Parker

class Vehicle
1. has number


Parker calls Entrance.Entering() and Entrance.Exiting() and ParkingSpot notifies ParkingLot when it is taken or vacated so that ParkingLot can determine if it is full or not. If it is newly full or newly empty or newly not full or empty, it should change the ParkingLotSign.Full() or ParkingLotSign.Empty() or ParkingLotSign.Normal().

HandicappedParker could be a subclass of Parker and CompactParker a subclass of Parker and RegularParker a subclass of Parker. (might be overkill, actually.)

Class diagram and classes in java to come soon


References
http://stackoverflow.com/questions/764933/amazon-interview-question-design-an-oo-parking-lot

Describe the data structures and algorithms that you would use to implement a garbage collector in C++

Problem
Describe the data structures and algorithms that you would use to implement a garbage collector in C++.

Solution
 Have lost touch with cpp, marking this question as incomplete for now. But here 2 good reference


References
http://tianrunhe.wordpress.com/2012/03/24/data-structure-and-algorithms-for-garbage-collection-in-c/
http://stackoverflow.com/questions/5009869/how-to-implement-garbage-collection-in-c

Design a musical juke box using object oriented principles

Problem

Design a musical juke box using object oriented principles.
Solution

We have already discussed the database design of how we will save information in the DB. Please refer this post for the same.

Our OOP design will be incorporating most of the design from there only.

Lets start with the design now.
class Song
1. has a song name, song artist,year,genre and so on.
   Song will be part of playlist 

class Playlist
1. has a track, current song (maybe)
2. has a queue of Songs.
3. constructor, current track and queue of songs.
4. getNextTrackToPlay(), return queue.peek()
5. queueUpTrack(), add to queue.

class CD : is a cd
 
class CD player:
1. playlist, get()
2. which cd, set(), get()
3. construct with either cd, playlist. or both
4. playTrank().

class User - He will play the cd player
1. has a name.
2. has a ID
3. get/set name & ID
4. constructor, given id and name
5. addUser(), given id and name, return new user.
 
class JukeBox:
1. has a CDplayer
2. has a User
3. has a collection of CDs
4. has a TrackSelector
5. construct with all above
6. getCurrentTrack(), return playing track.
7. processOneUser(User u), set the current user.

class TrackSelector
1. has a currentSong.
2. constructor, given current song.
3. setTrack(), set current song.
4. getCurrentSong(), return current song.
 

Now that we have a design lets have a look at the class diagram:
 Here is the code in java:
public class CD { }
public class CDPlayer {
    private Playlist p;
    private CD c;
    public Playlist getPlaylist() { return p; }
    public void setPlaylist(Playlist p) { this.p = p; }
    public CD getCD() { return c; }
    public void setCD(CD c) { this.c = c; }
    public CDPlayer(Playlist p) { this.p = p; }
    public CDPlayer(CD c, Playlist p) { ... }
    public CDPlayer(CD c) { this.c = c; }
    public void playTrack(Song s) { ... }
}
 
public class JukeBox {
    private CDPlayer cdPlayer;
    private User user;
    private Set<CD> cdCollection;
    private TrackSelector ts;
 
    public JukeBox(CDPlayer cdPlayer, User user, Set<CD> cdCollection,
    TrackSelector ts) { ... }
    public Song getCurrentTrack() { return ts.getCurrentSong(); }
    public void processOneUser(User u) { this.user = u; }
}
 
public class Playlist {
    private Song track;
    private Queue<Song> queue;
    public Playlist(Song track, Queue<Song> queue) { ... }
    public Song getNextTrackToPlay(){ return queue.peek(); }
    public void queueUpTrack(Song s){ queue.add(s); }
}
 
public class Song {
    private String songName;
}
 
public class TrackSelector {
    private Song currentSong;
    public TrackSelector(Song s) { currentSong=s; }
    public void setTrack(Song s) { currentSong = s; }
    public Song getCurrentSong() { return currentSong; }
}
 
public class User {
    private String name;
    public String getName() { return name; }
    public void setName(String name) { this.name = name; }
    public long getID() { return ID; }
    public void setID(long iD) { ID = iD; }
    private long ID;
    public User(String name, long iD) { ... }
    public User getUser() { return this; }
    public static User addUser(String name, long iD) { ... }
}

You can download the complete code from github.

Design a database to store music library for your jukebox

Problem
Design a database to store music library for your jukebox
Solution
Basically we have to save everything that has to do anything with organizing digital music
Something like this would be good to start with.
 It specifies a table for artists, albums (with keys into artists and genres), tracks (keyed into albums), and genres. Also, all these tables will have a surrogate key(basically an auto generated primary key id, which will be a primary key, but not a real attribute of the table).


Table artists
----
id (primary key),
name
description
years_active
otherinfo (whatever you need)

Table albums
----
id (primary key)
artistid (foreign key to artists table)
name,
releasedate
genreid (foreign key to genres table)
picture

Table tracks
----
id (primary key)
albumid (foreign key to albums table)
name
override_artist (overrides album artist if not null)
playtime
lyric
otherstuff as needed

Table genres
----
id (primary key)
name
description

Note that override_artist gives us capability of choosing any other artist other than main album artist.

You can refer this diagram(courtesy):

References - stackoverflow

Wednesday, March 26, 2014

Design the classes and data structures for a call center

Problem
Imagine you have a call center with three levels of employees: fresher, technical lead (TL), product manager (PM). There can be multiple employees, but only one TL or PM. An incoming telephone call must be allocated to a fresher who is free. If a fresher can’t handle the call, he or she must escalate the call to technical lead. If the TL is not free or not able to handle it, then the call should be escalated to PM. Design the classes and data structures for this problem. Implement a method getCallHandler().
Solution
 All three ranks of employees have different work to be done, so those specific functions are profile specific. We should keep these specific things within their respective class.
There are a few things which are common to them, like address, name, job title, age, etc. These things can be kept in one class and can be extended / inherited by others.

Finally, there should be one CallHandler class which would route the calls to the concerned person.
NOTE: On any object oriented design question, there are many ways to design the objects. Discuss the trade-offs of different solutions with your interviewer. You should usually design for long term code flexibility and maintenance.
 
CallHandler class:
1. stores all employees in different levels
2. stores all calls in a Queue.
3. getCallHandler() returns a Employee who is suitable for accepting this call.
4. dispatchCall() gets a employeer from 3, then try ReceiveCall(), if return from 3 is null, put call in Queue.

Call class:
1. call have ranks.
2. call can be reply and disconnected.

Employee class:
1. Every Employee have a CallHandler
2. every Employee have a rank.
3. ReceiveCall()
4. CallHandled()
5. CannotHandle(), if can’t handle, handlerObj.dispatchCall(call) and handlerObj.getNextCall()
6. boolean free. is free or not.

 Lets see the class diagram:


You can download the detailed code here on github, but this is the code in java:

public class CallHandler {
    static final int LEVELS = 3; // we have 3 levels of employees
    static final int NUM_FRESHERS = 5; // we have 5 freshers no vars needed for TL and PM cuz only 1.
    ArrayList<Employee>[] employeeLevels = new ArrayList[LEVELS];
    // queues for each call’s rank
    Queue<Call>[] callQueues = new LinkedList[LEVELS];
 
    public CallHandler() { ... }
 
    Employee getCallHandler(Call call) {
        for (int level = call.rank; level < LEVELS - 1; level++) {
            ArrayList<Employee> employeeLevel = employeeLevels[level];
            for (Employee emp : employeeLevel) {
                if (emp.free) {
                    return emp;
                }
            }
        }
        return null;
    }
 
    // routes the call to an available employee, or adds to a queue
    void dispatchCall(Call call) {
        // try to route the call to an employee with minimal rank
        Employee emp = getCallHandler(call);
        if (emp != null) {
            emp.ReceiveCall(call);
        } else {
            // place the call into queue according to its rank
            callQueues[call.rank].add(call);
        }
    }
    void getNextCall(Employee e) {...} // look for call for e’s rank
}
 
class Call {
    int rank = 0; // minimal rank of employee who can handle this call
    public void reply(String message) { ... }
    public void disconnect() { ... }
}

class Employee {
    CallHandler callHandler;
    int rank; // 0- fresher, 1 - technical lead, 2 - product manager
    boolean free;
    Employee(int rank) { this.rank = rank; }
    void ReceiveCall(Call call) { ... }
    void CallHandled(Call call) { ... } // call is complete
    void CannotHandle(Call call) { // escalate call
        call.rank = rank + 1;
        callHandler.dispatchCall(call);
        free = true;
        callHandler.getNextCall(this); // look for waiting call
    }
}
 
class Fresher extends Employee {
    public Fresher() { super(0); } 
}
class TechLead extends Employee {
    public TechLead() { super(1); }
}
class ProductManager extends Employee {
    public ProductManager() { super(2); }
}