Interview Puzzle - Equal heads

Puzzle:

There are 50 coins on the table out of which 43 are tail-face up and 7 are head face up. You are blind folded and there is no way to determine which side is up by rubbing, etc. You have to divide the 50 coins in two sets (not necessarily equal) such that both have equal number of coins with heads face up.

Solution:

Divide the 50 coins into two sets - once set with 43 coins and the other set with 7 coins. Thus, the first set will contain 'x' heads and '43-x' tails and the second set will contain '7-x' heads and 'x' tails. The possibilities can be tabulated as shown in the left table.

Now, flip the coins in the second set, so that both will contain 'x' heads. The result after flipping can be seen on the right table. You can see that both sets have equal number of heads whatever be the distribution.

Cheers!!
Jack

Print a Matrix in diagonal zig zag order

Problem:
Given a square matrix, write a program to print the items in zig zag diagonal order.

Following is an example,

So the output expected for the above example is,

1 -> 2 -> 6 -> 3 -> 7 -> 11 -> 4 -> 8 -> 12 -> 16 -> 5 -> 9 -> 13 -> 17 -> 21 -> 10 -> 14 -> 18 -> 22 -> 15 -> 19 -> 23 -> 20 -> 24 -> 25

Solution:

This program is a bit tricky and is very hard to solve immediately when asked in an interview. People who try to attack problems involving matrices always think they need at least two loops to arrive at the solution. But the surprise here is the problem can be solved in just a single loop with a very simple logic. I have provided the solution in C++ below, you may also try to solve the same in the language of your choice!!


Cheers!!
Jack