Meet the robots

Problem:

Two robots land with their parachutes on an infinite one-dimensional number line. They both release their parachutes as soon as they land and start moving. They are allowed only to make use of the following functions.

I.   moveLeft() // robot moves to left by 1 unit in 1 unit time
II.  moveRight() // robot moves to right by 1 unit in 1 unit time
III. noOperation() // robot does not move and takes 1 unit time
IV.  onTopOfParachute() // returns true if the robot is standing on top of either of the parachute, else false
V.   didWeMeet() // returns true if the robot meets to the other robot, else false

Write a function in order to make the robots meet each other. Robots will be executing the same copy of this function.

Solution:

void meetRobots(Robot r1,Robot r2) {

       r1.moveLeft(), r2.moveLeft();

       while(!r1.onTopOfParachute() && !r2.onTopOfParachute()) {

           r1.moveLeft(), r2.moveLeft();

       }

       if(r1.onTopOfParachute()) {

           while(!r2.didWeMeet()) {

               r2.moveRight(),r1.noOperation();

           }

        } else {

           while(!r1.didWeMeet()) {

               r1.moveRight(),r2.noOperation();

           }

        }

           

There is a N*N integer matrix Arr[N][N]. From the row r and column c, we can go to any of the following three indices: (r+1,c-1), (r+1,c) or (r+1,c+1). Find the maximum sum that can be generated from any path starting from any column in first row

Problem:

There is a N*N integer matrix Arr[N][N]. From the row r and column c, we can go to any of the following three indices:

I.                Arr[ r+1 ][ c-1 ] (valid only if c-1>=0)
II.               Arr[ r+1 ][ c ]
III.              Arr[ r+1 ][ c+1 ] (valid only if c+1<=N-1)
So if we start at any column index on row 0, what is the largest sum of any of the paths till row N-1.

Solution

Solution below is O(n^2) solution. We will update all array entries. Starting from last row and moving till first row. Each array entry will be maximum sum that can be generated when starting from that point. At the end we will find entry in first row that has maximum value.

Pseudo code:

void calculateSum(int[][] a,int n,int row) {
       if(row == n-1) {
           return;
       }
       calculateSum(a,n,row+1);
       for(int j=0;j<n;j++) {
           // calculate a[row][j]
           int max = a[row+1][j];
           if(j-1 >=0 && a[row+1][j-1] > max) {
                 max = a[row+1][j-1];
           }
           if(j+1 <= n-1 && a[row+1][j+1] > max) {
                 max = a[row+1][j+1];
           }
           a[row][j] += max;
        }
 }

void maxSumPath(int[][] a,int n) {
      calculateSum(a,n,0);
      int max = a[0][0];
      for(int j=1;j<n;j++) {
          if(a[0][j] > max)max = a[0][j];
      }
      System.out.println(max);
} 

        

There is a binary tree of size N. All nodes are numbered between 1-N(inclusive). There is a N*N integer matrix Arr[N][N], all elements are initialized to zero. So for all the nodes A and B, put Arr[A][B] = 1 if A is an ancestor of B (NOT just the immediate ancestor).

Problem:
There is a binary tree of size N. All nodes are numbered between 1-N(inclusive). There is a N*N integer matrix Arr[N][N], all elements are initialized to zero. So for all the nodes A and B, put Arr[A][B] = 1 if A is an ancestor of B (NOT just the immediate ancestor).

Solution:

The below solution is O(n^2) solution. Each array entry is visited exactly once.

The basic idea is to make current node ancestor for all the nodes except for itself and it's own ancestors.

For any node, it's own ancestors  are maintained in set.
Pseudo code:

void fill(int[][] a,int n, Node root,Set<Integer> parents) {
     if(root == null)return;
     for(int j=0;j<n;j++) {
        if(!parents.contains(j) && j != root.value) {
                  a[root.value][j] = 1;
        }
     }
     parents.add(root.value);
     fill(a,n,root.left,parents);
     fill(a,n,root.right,parents);
     parents.remove(root.value);
}

A 2D array is such that each row in it is in ascending order and each column is in ascending order. How will you search for an element in this array?

Problem:

A 2D array is such that each row in it is in ascending order and each column is in ascending order. How will you search for an element in this array?

Solution:

The solution described below is O(n) solution.

Start from top right element,

• If the element is equal to element we are searching for return the element.
• If the element is greater than the element we are searching for, then all the element in the column below can be discard. Move to element left of current element. Repeat the steps with new current element.
• If the element is less than the element we are searching for, then all the element in the row of current element can be discard. Move to element below of current element. Repeat the steps with new current element.

Pseudo code:

Pair find(int[][] a,int top, int bottom, int left, int right,int key) 

       if (top > bottom || left > right) return null;

       int current = a[top][right]

       if (current == key)

              return Pair(top,right)

       else if (current < key)

              return find(a,top+1,bottom,left,right,key)

       else

              return find(a,top,bottom,left,right-1,key)

 

Call find(0,n-1,0,m-1,key) to search for key.

A tree is represented in a matrix form such that A[i,j] = 1 if j is the ancestor of i. Otherwise A[i,j] = 0. Given this construct a normal binary search tree.

Problem:

A tree is represented in a matrix form such that A[i,j] = 1 if j is the ancestor of i. Otherwise A[i,j] = 0. Given this construct a normal binary search tree.

Solution:

Iterate over the array A and build array P, such that P[i] = # ancestor of node i. Thus, sum of A[i][j] for 0<=j<n

This will take O(n^2) time. While building the array P, keep track of node for which P[i] is 0. Certainly there can be only 1 such element i.e. root of the binary tree.

Now Node [0..i-1] will be in left sub tree of root and Node [i+1...n-1] will be right sub tree of root.

There can be only one node in 0..i-1 for which P[i] is 1, that will be root of left sub tree. Similar hold true for Nodes i+1...n-1. let index of node for which  P[j] is 1, 0<=j<=i-1, be k.

Node 0..k-1 will be in left sub tree of Node k which is left child of Node i. we need to find node x, 0<=x<=k-1 for which P[x] is 2. Hence we keep building our binary search tree.

Pseudo code

for i in 0..n-1
  p[i] = 0;
  for j in 0..n-1
     p[i] += a[i][j];
  return buildTree(p,0,n-1,0)

Node buildTree(int[] a,int left,int right,int rootIndex)
         for i in left...right
             if a[i] == rootIndex
                   Node root = new Node(i)
                   root.left = buildTree(a,left,i-1,rootIndex+1)
                   root.right = buildTree(a,i+1,right,rootIndex+1)
                   break;
          return root

The worst case complexity of this solution will be O(n^2) + O(n^2) which is O(n^2).
For average cases, where the binary tree is balanced complexity will be O(n^2) + O(n log n). This will be still be O(n^2) however second step will be faster in this case.

There are n petrol bunks arranged in circle. Each bunk is separated from the rest by a certain distance. You choose some mode of travel which needs 1litre of petrol to cover 1km distance.

Problem

There are n petrol bunks arranged in circle. Each bunk is separated from the rest by a certain distance. You choose some mode of travel which needs 1litre of petrol to cover 1km distance. You can’t infinitely draw any amount of petrol from each bunk as each bunk has some limited petrol only. But you know that the sum of litres of petrol in all the bunks is equal to the distance to be covered.
ie let P1, P2, … Pn be n bunks arranged circularly. d1 is distance between p1 and p2, d2 is distance between p2 and p3. dn is distance between pn and p1.Now find out the bunk from where the travel can be started such that your mode of travel never runs out of fuel.

Solution:

To understand the solution of problem first understand the below inequalities.
if a >= 0, a+b >=0, a+b+c>=0 and a+b+c+d < 0
Then following inequalities also hold true
b+c+d < 0, c+d<0 and d < 0

This would mean that when we start from any point (say P) and after moving through some tanks we run out of fuel at point (Say Q), then any points between P and Q cannot be starting point (including Q) so our next search has to start from Q+1. We will save this point as our starting point.
Note: We only need to consider till end point (assuming non-circular) because, the sum of all values would be zero, so we will be able to reach our current starting point from first point if we can reach end point from current starting point.

Now using array P[1..N]: Petrol capacity and D[1..N]: Distance between tanks
Compute array C[1..N] such that C[i] = P[i] - D[i], C[i] can be +ve, -ve or zero.

We start with C[1] and keep a variable sum to store sum of C[i]s so far. At any stage if C[k] makes are sum < 0, we start from k+1 and set sum = C[K+1]

Psuedo code:
index = 1;
sum = 0
result = index;
while(index <= N) {
     sum += C[index];
     if(sum < 0) {
         sum = 0;
         result = index + 1;
     }
     index++;
 }
 if(index >= N) {
     NO SOLUTION POSSIBLE;
 } else {
     result store our starting point
 }


         

Given an array of integers, find Pythagorean triplets. i.e. find a,b and c which satisfies a^2 + b^2 = c^2. Integers could be positive or negative.

Problem:

 Given an array of integers, find Pythagorean triplets. i.e. find a,b and c which satisfies a^2 + b^2 = c^2. Integers could be positive or negative.

Solution:

To solve this problem in naive approach, we can simply run O(n^3) solution by iterating over all triplets and then checking if Pythagorean property is indeed satisfied.

Can we optimize the solution? Answer is yes!! If we make use of sorting technique then we can make it O(n^2 * log(n)). 

If we square all the elements (all storing actual elements along side and storing all duplicates as well) and then sort the array of squares of the elements. Then for each pair (O(n^2)) we just need to find if sum of the square of these values exist in sorted array. Here come our life saving handy technique Binary Search into play which will can find if element exists in array in O(log n) so overall complexity becomes

 O(n^2 * log(n)).

Can we still do better???? Answer is again YES!! We can!!

We can maintain hash map for squares of elements therefore searching part of above can be done in O(1) making overall complexity O(n^2). But this would depend on choice of very good hash function and also may not be allowed in most of problems.

Then what next??? We will still use same sorting technique but with different flavor. We will sort the elements in such a way that a[i] will be before a[j] if a[i]*a[i] is less than a[j]*a[j].

Something similar to -1, 1, 2, 3 ,-5, 5 ....

Note that this array is actually sorted in terms of squares of values.

For each element of this array, we can find pair such that a[i]*a[i] + a[j]*a[j] = a[k]*a[k], where K is current element. 

Finding a pair can be done in O(n). This is similar to problem of finding X + Y = K in any sorted array in O(n).

Complexity:

Sorting step: O(nlogn)

Finding triplet : O(n^2)

Overall complexity O(n^2)

Working Code for O(n^2) solution

 import java.util.Arrays;  
 import java.util.Comparator;  
 import java.util.Scanner;  
 public class FindTriplet {  
      public static void main(String[] args) {  
           Scanner s = new Scanner(System.in);  
           int n = s.nextInt();  
           Integer[] a = new Integer[n];  
           for (int i = 0; i < n; i++) {  
                a[i] = s.nextInt();  
           }  
           Arrays.sort(a, new SquareSorter());  
           for (int i = 0; i < n; i++) {  
                for (int j = 0, k = n - 1; j < k;) {  
                     if (j == i) {  
                          j++;  
                     } else if (k == i) {  
                          k--;  
                     } else {  
                          int lhs = a[j] * a[j] + a[k] * a[k];  
                          int rhs = a[i] * a[i];  
                          if (lhs == rhs) {  
                               System.out.println("[" + a[j] + "(" + j + ")," + a[k]  
                                         + "(" + k + ")," + a[i] + "(" + i + ")," + "]");  
                               j++;  
                               k--;  
                          } else if (lhs > rhs){  
                               k--;  
                          } else {  
                               j++;  
                          }  
                     }  
                }  
           }  
      }  
 }  
 class SquareSorter implements Comparator<Integer> {  
      @Override  
      public int compare(Integer o1, Integer o2) {  
           return o1 * o1 - o2 * o2;  
      }  
 }  

Test case

Input:

8

-3 6 7 3 4 -5 4 5

Output:

[-3(0),4(3),-5(4),]

[3(1),4(2),-5(4),]

[-3(0),4(3),5(5),]

[3(1),4(2),5(5),]