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

how many zeros in the end of huge number

Note: Came across this Q at TIFR-Ph.D.entrance test.

Let n > 1 be an odd integer. How many zeros are at the end of number S = 99^n+1 (Read as S = 99 raised to the power n and then 1 added to it)

At first glance, this indicates some trick, for two reasons. First, S is going to be huge very fast, even with comparatively small n and second, this was asked in Ph.D test of TIFR! :D

I thought of splitting 99 as 100-1 and getting a generic result form for S.
i.e.

S = 99 ^ n - 1 = P - 1..................... s.t. P = 99 ^ n (n > 1, odd)
so,
P = 99 ^ n = (100 - 1) ^ n = (-1 + 100) ^ n
Using binomial theorem for expansion,
P = \sum_over_k=0_to_k=n {nCk * (-1)^k * 100 ^ (n-k)}
P = nC0 * (-1)^0 * 100 ^ n
   + nC1 * (-1)^1 * 100 ^ (n-1)
   + .....
   + nC{n-1} * (-1) ^ (n-1) * 100 ^ 1  ..................... note n-1 is even
   + nCn * (-1) ^ n * 100 ^ 0              ..................... note n is odd

Solving we get alternate terms positive and negative s.t. first term is positive (due to (-1)^0) and last term negative (due to (-1) ^ n, n being odd)

P = P1 - P2 + P3 - ....... - Pk + 100n - 1

where P1, P2, ..., Pk are terms which are multiples of powers (>=2) of 100.

Thus,
P = a_term_multiple_of_powers>=2_of_hundred +100n - 1

Thus,
S = P + 1 = a_term_multiple_of_powers>=2_of_hundred + 100n - 1 + 1 a_number_multiple_of_powers>=2_of_hundred + 100n = a_number_ending_with_two_zeros.

Thus, S ends with 2 zeros.

cages for pigs

You have to build 4 cages to put 9 pigs in them such that

• each cage can contain odd number of pigs and
• no cage can be empty

\via{Harshada}

You may start with actually making some combinations of numbers in order to get sum as 9. But, as you can expect, it's not that trivial. Another important point to note here is that any two odd numbers will sum up to an even number thus it is not possible to split 9 into 4 additive factors each odd.

The solution is tricky but simple - Build cages such that 3 of them are put inside 4th one and those inner 3 contain pigs like 1,1,7 or 1,3,5 or 3,3,3.
Build cages such that one of those is inside another, i.e. say cage A, cage B and have a cage C inside cage D. Put pigs as follows - 1,1,1,6 (1,1,1-7) or 1,1,3,4 (1,1,1-7), 3,3,1,2(3,3,1-3) and so on. Meaning, here even if we put even number of pigs in D, still with C+D it has odd number of pigs.

(Thanks Hrushikesh for insights on odd+even = odd, that corrected the solution)

Another update-
But, looks like both solutions are half-correct. In first. i.e. cancelled one, we may say that we are violating condition that outermost box should also contain at least 1 pig on it's own. But, if we consider that, in second solution, we violate condition that D should have odd number of pigs on its own. So, basically we give up on one of the "on its own" constraints - either "odd on its own" or "at least one on its own"

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.
:)

Majority element of an array

Given an array of n number, find the majority element (if any)?

(Majority element is the one which occurs more than n/2 number of times)

Example: A = [20, 4, 4, 7, 4, 16, 20, 4, 0, 4, 4], n = 11, '4' occurs 6 times, is the majority elemet.

How to go about it? Simplest method follows. Keep another array of counts and keep track of which number occurs how many times. But, this is possible only when we know the range of numbers. Even though we know that, it is inefficient in space. So, let's rule out that method. What we have to thus look for, is a way to keep counts / track of a possible majority element run time. How to do this?

What if we consider the smaller part of above given A? We start with count=0. At index_0, we assume 20 is the majority element, thus setting count to 1 and also keep track that '20' is our probable majority number so far. At index_1, we find that the number is not 20 and thus we have lost on score, thus decrementing the count, so not it is 0 again. Here, we are kind of sure that from the elements we have seen so far, each appeared with equal counts and thus, we should look for a new start. So, when count hits 0, we change our probable majority element to the current one and again repeat the process.

With above example, count and probable majority element (pme) go as follows.
A        = [20, 4, 4, 7, 4, 16, 20, 4, 0, 4, 4]
count = [  1, 0, 1, 0,  0,  0,   0, 0, 0, 0, 1]
pme   = [20, 4, 4, 7, 4, 16, 20, 4, 0, 4, 4]

Thus, in O(n) we can find the majority element.