crossing the bridge

Four friends A,B,C and D are at one end of bridge and it's night. They have one torch to be used while crossing the bridge. All four have different speeds of walking and they take 1, 2, 5 and 10 minutes respectively to cross the bridge. At a time, at most two people can be crossing the bridge (walking on either of the sides). If say A and D walk together, A has to slow down because they have to go together using just one torch. Let them show how they can cross the bridge given that the torch battery will last only for 17 minutes.

\via{Prashant}, \thanks_for_hint{Prashant}

The starting approach could be trivial in which we try to send 2 of them on other side, let one of them come back with torch and take another guy from first side to second side. Initially we may think that A will be the speediest person to go back to give torch back. With this we will always end up in using torch for at least 3 times for A's back journey.
For example->
A,B,C,D ------------------ None
B,C ---------------------- A,D
A,B,C -------------------- D
....
....
and so on.
But this is not the optimal way because the time when two of them go together is lower bounded by the person who is slower amongst the two. If every time, A takes one of them to the other side, each trip will take 2,5 and 10 minutes respectively. Note that this itself sums up to 17 minutes, but as we saw earlier, at least 3 minutes are required for A's back journey. Thus, this kind of approach will not work.

The quick hint that helps solving this is let C and D go together and keep them steady, as in don't let them come back. If that is to be done, we can send C and D initially itself; but that will require one of them (of course C) to come back which we don't want. So, let's send A and B first and let A_the_speediest come back. Now it can wait and let C and D cross the bridge with the torch. This way C and D cross together and B already on other side can quickly take torch back.

Thus, the scheme will be->
A,B,C,D --------------- None
C,D ------------------- A,B (takes 2 mins)
A,C,D ----------------- B (takes 1 min)
A --------------------- B,C,D (takes 10 mins)
A,B ------------------- C,D (takes 2 mins)
None ------------------ A,B,C,D (takes 2 mins)
Total takes 17 mins.

measure 4L water

You have to measure 4L water with 2 measuring cups, one that can contain 3L water and other that can contain 5L water. Measuring cups obviously don't have per liter markings! :)
\via{Prashant}

My idea was as follows. It is not possible to directly have 4L in 1 measurement as 3 and 5 don't in any way make up 4. So, we have to somehow come up with method which will keep 4L in measuring cups themselves - either separately or combined - say 1+3, 2+2, 0+4 etc. But, it is not possible to have 4L divided up in 2 cups, because in say we want to achieve 1 in 3L and 3 in 5L, we don't have empty cups to measure anything at this point. This indicates that we can only have 0+4 or 4+0 in cups. Obviously, 3L cup cannot contain 4L, so we have to somehow have 4L kept in 5L cup in the end. Starting with this final step backwards, what keeps 4L in 5L cup? One way is to have 5L filled in completely and pour just 1L from it to 3L cup. This means to be able to do this, 3L cup should be already having 2L water in it, so that it can accommodate only 1L more. Getting 2L in 3L cup is fairly easy. So, overall following are the steps- (let A = 3L cup, B = 5L cup)
0. A = B = 0 \\ Both empty initially
1. A = 0, B = 5 \\ Fill in 5Lcup
2. A = 3, B = 2 \\ Pour 3L in A, 2L remains in B
3. A = 0, B = 2 \\ Empty 3L cup
4. A = 2, B = 0 \\ Pour 2L from B to A
5. A = 2, B = 5 \\ Fill B cup again
6. A = 3, B = 4 \\ Pour 1L from B to A, B has 4L remaining

spiral matrix

Note: Code snippet loading may take few seconds.
Generate a square matrix of size n, such that

1. it has elements from 1 to n*2 (or 0 to n*2-1)
2. lowest element is at [n,n] (or [n-1,n-1])
3. elements are arranged in a spiral order as shown in Figure.

For instance, when n=2 and n=3
M2 =           M3=
| 3 4 |           | 5   6   7 |
| 2 1 |           | 4   9   8 |
                     | 3   2   1 |

This is really simple when we consider pattern of filling these elements at an abstract level. Our general approach is to find position for element in order {1, 2, 3, ..., n*n}

We start with rightmost bottom position and put first element there. Then we decide direction to proceed in, which is horizontal in this case. For every next element, we seek a position for it in following way-
We consider adjacent positions of current position in the direction we are in, i.e. here we consider [n,n-1] and [n,n+1] (with [n,n] as our rightmost bottom position. We see if any of this is free. We generalize any position outside matrix dimensions to be non-free and thus next position we have is [n,n-1]. We fill next element in this position and keep going.
At some point, we will find no position free for next element in the direction we are in, which is signal for us to change direction. We switch to vertical direction now and keep going with same logic. This w
ay, we keep moving ahead, find a free slot and change direction if we don't find one.
Note that when we fill in last element, we no longer find free position in either direction and we are done.

Following is the C code.

// generates a spiral square matrix of n*n
// @author Girija

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    int i, j, num;
    int pi, pj;
    bool pfound;

    // setup
    int n = atoi(argv[1]);
    bool horizontal = true;
    int max_num = num*num; // starts at 1

    // allocate
    int **matrix = (int **) malloc(sizeof(int) * n * n);

    // initialize
    for(i=0; i<n; i++) {
     matrix[i] = (int *) malloc(sizeof(int) * n);
      for(j=0; j<n; j++) {
        matrix[i][j] = -1;
      }
    }

    pi = pj = n-1;

    // generate spiral matrix
    num = 1;
    while(1) {
      // place current number at pi,pj
      matrix[pi][pj] = num;
      // get position to place next number
      pfound = false;
      if(horizontal) {
        // we are following horizontal direction, check left-right empty slots first
        // check if empty slot, reset pj
        if(pj-1 >=0 && matrix[pi][pj-1] == -1) {
            pj--;
            pfound = true;
        }
        else if(pj+1 <= n-1 && matrix[pi][pj+1] == -1) {
            pj++;
            pfound = true;
        }
        if(!pfound) {
            // time to change direction
            horizontal = false;
            // reset pi
            if(pi-1 >= 0 && matrix[pi-1][pj] == -1) {
              pi--;
              pfound = true;
            }
            else if(pi+1 <= n-1 && matrix[pi+1][pj] == -1) {
              pi++;
              pfound = true;
            }
        }
      } else {
        // we are following vertical direction, check up-down empty slots first
        // check if empty slot, reset pi
        if(pi-1 >=0 && matrix[pi-1][pj] == -1) {
            pi--;
            pfound = true;
        }
        else if(pi+1 <= n-1 && matrix[pi+1][pj] == -1) {
            pi++;
            pfound = true;
        }
        if(!pfound) {
            // time to change direction
            horizontal = true;
            // reset pj
            if(pj-1 >= 0 && matrix[pi][pj-1] == -1) {
              pj--;
              pfound = true;
            }
            else if(pj+1 <= n-1 && matrix[pi][pj+1] == -1) {
              pj++;
              pfound = true;
            }
        }
      }
      // not found? we are done!
      if(!pfound)
        break;
      num++;
    }

    for(i=0; i<n; i++) {
      printf("n");
      for(j=0; j<n; j++) {
        printf("%dt", matrix[i][j]);
      }
    }
    printf("n");
}

Thanks to Template changes to add code snippet in blog and Parsing code to add to html (blog)

top k from n (k << n)

Bhai was asked this problem in one of the interviews he faced.

Given n objects and associated scores, find top k objects s.t. k is much smaller compared to n.

The most trivial approach is of course to sort n objects based on their scores and pick top k. The best known comparison based sort will do this in O(n log n) with additional pass to pick top k. And of course, this is not what is expected! We need complexity to be lower than O(n log n).

Let's focus on last part of the problem statement. What additional benefit does it give us to know that k << n? One obvious thing that comes to mind is, we are interested in correct ordering of just top k objects, remaining n-k could be unordered at the benefit of having lower complexity. Thinking in the same direction, one can try to pick k such objects such that remaining n-k are virtually ignored! But, there has to be some mechanism to pick top k. The same thing considered in opposite way will give us better insights - i.e. we get lower complexity at the expense of neglecting ordering of non-top n-k objects; meaning we don't care about them, specifically their position in ordered list.

So, is there any way where we can selectively pick elements s.t. the highest score is picked first then the second highest scored and so on? well.. this suggests none other than a max-heap! a max-heap allows you to get maximum element one at a time with delete operation. Let's see the algorithm.

1. Build heap of n objects given.
2. for i=1 to k do
1. get max element (delete from heap)

Let's see the complexity if we are doing any better than O(n log n). Step 1 above takes O(n). Refer Complexity of building heap for analysis. Step 2.1 takes O(log n) and thus step 2 takes O(k log n). In first read, one might think the complexity is O(n) + O(k log n). Let's analyze more with examples.

• n = 1024, k = 10
• n+k log n ~ 1024 + 10 * 10 ~ 1024 -> O(n)

• n = 1024, k = 200
• n+k log n ~ 1024 + 200 * 10 ~ 2000 -> O(k log n) which will approach O(n log n) as k -> n

Of course, if k -> n, this algorithm will degenerate to O(n log n)  but in given setting where k << n, case 1 above will result in linear time algorithm.
:)

for loop in C

Following code has a bug. Can you find that out? Hint: Well, this code is intended to print "hi " **20** times, does it?
   int i, n=20;
   for (i=0; i < n; i--) {        printf("hi ");    }

If you have found the bug, can you now make it print "hi " 20 times by replacing one character.

Well, the answer is too simple (once known :D). Just a hint: Make sure you understand how for loop works, specially at the beginning of the loop.

(Spoiler alert: Solution in comment)

Rotated sorted array

Part A: Given a sorted array which is rotated either to the left or to the right by k positions (0<=k<=n-1), find the maximum element. Trivial solution:
Check for each possible k, whether it is the maximum element by checking adjacent values i.e. a[k-1], a[k] and a[k+1] circularly (meaning, for k=0, check a[n-1], a[0] and a[1]). This is obviously O(n) due to k's range and because 3 comparisons per k can be considered as O(1) being constant time access to array elements. Thus, of course we aim at sub linear time.

So the main issue is - how to reduce problem size so that we solve smaller and smaller problems, discarding some part of the input and get quickly to the problem of size small enough (ideally 1). What if we have the middle element, i.e. a[m]? In order to decide which part to discard, one must be able to visualize the rotated sorted array, which is shown as follows. Let the new index of maximum element be k.


Now, one can see that m will always lie on upward slope and thus slope trick will not work. But, we can now distinguish between left and right part around k as follows. If m<=k, m will always be more than the first element in the rotated array, because the sorted order is retained. Thus, by comparing a[m] and a[i], one can easily decide which part to throw. If a[m] >= a[i] we can throw left half else right half. Once we reduce problem size to 1, m and k collide. This works in O(log n).

Array with a mountain shape

Given an array in which initially elements start increasing till some index k and then they decrease. Find k.

Of course this asks us to find k in sub linear time. Otherwise, the most obvious solution is to check every element till elements increase and then at first drop in value, you get k. Sub linear acts as a hint for logarithmic. Logarithmic gives hint for dividing and throwing away some part, so that we reach a singleton or small enough set quickly. Let's see whether we can discard some part of the array. What if we pick the middle as we do in binary search? This gives us m=(i+j)/2 and m<=k or m>k. If we can somehow establish this relation between m and k (note: k is unknown, we have to find it), we can throw away the remaining part. How can we do this then? We know that k is the index such that on its left, the line plot of the array is ascending and on its right, it is descending. This means, if we are on left of k, we are on upward slope as against when we are on the right part of k. This hint is enough I guess. Once we get m, check a[m-1], a[m] and a[m+1] to get an indication about the region of slope where m belongs to, by comparison. Once we know that we are on upward slope, we know that m<=k, so we discard this part. Similarly for the case when m>k. Once we reduce problem size from n to n/2 at every iteration, we are in logarithmic space. Thus the algorithm performs in O(log n).

Missing number in an array

Given an array of N elements which contain numbers from 1 to N+1 in random order, each only once and one of them missing, find the missing number in the best way you can.

Let's first see with an example that we have understood the question correctly. The array size is say, N=5, it contains numbers from {1,2,..,6} each except one exactly once, in random order - e.g. {2,3,1,5,6}. Given this, we have to find the missing number i.e. 4 here.
This problem seems quite easy and indeed it is! You know beforehand what the value of N is and you can traverse the array one by one, keeping track of which element you have seen till now. This requires additional storage and setting of flags per element i.e. theta(N) space. But, logically this works correct. At the end, you emit that number for which the "saw it" flag is not set.
Can we somehow eliminate this extra storage? This needs some extra insight in the problem statement. What if I tell you, the array has numbers from {2,5,7,9,15} and one of them is missing. The above approach of setting flags will work here also as long as you know the numbers that you expect to see. So, what is the difference that makes original problem a special case of this generic problem? As you might have noticed, the given array has a nice property. The elements are not arbitrary chosen but they all come from {1,..N}. Now, in order to remove the need of extra space, one has to think of aggregating the results in some way. Thus instead of storing per value, one flag and setting it, can we aggregate the information we have seen so far? Such aggregation will eliminate extra space requirement. One obvious way to aggregate is : take sum. And here comes the above mentioned property handy! We know that sum of first N numbers can be easily calculated as given in this. Call this S. Now traverse the array and keep the track of sum seen, call this S'. The missing number is S-S'!

Multiply given number by 7..

Multiply given number by 7 without using multiplication operator.

Obvious answer: Add number to itself 7 times!
But, then think - why the Que asks you multiplying specifically by 7. The above trick of adding numbers is generic and can be applied for any multiplier other than 7. The trick here is as follows. If the given number is 'x', x*7 = x*(8-1) = x*8 - x. At this point, you might note that this involved multiplication again. But here is the main step - Multiplication by any number which is a power of 2, can be done easily by shifting the bits in the binary representation of the number. For binary representation, see this. And this gives the answer - Shift x's bits 3 positions to left and subtract x from it!

Delete the given node in an SLL

Given a node in a singly linked list, and given no other node - not even header, can you delete this node?

Ans.- While deleting a node from a linked list, we need to point 'next' of previous node to the 'next' of current node and make the current node isolated and then free it. With singly linked list, we need to keep track of previous node in order to make above mentioned modifications. This is possible only when header node is provided so that we can traverse the list till this node. As header is not available and the list being singly linked, main point to note is: we can only traverse from the given node in forward direction. This leads us to the solution. We target next node. Copy next node's data to the current node and make current node point to next of next of current node. This way we have removed data to be deleted and next node is isolated in this process, so we then free it up.
Trick- This will not work for all cases. The constraint is in terms of the input. Can you identify it?
Ans.- Think what happens when the given node is the last node in the singly linked list.