3 Math Problems

Recently I was exploring the job market like all the regular programmer should. Along the way, I encountered a very interesting company which still have the good old “problem solving / IQ test” phone interview. I thought I would share that experience here.

First of all, lets state the 3 questions out first:

1. Algebra: You have 9 digits 1–9. Partition them into two sets S1 and S2. Make a number (any) using the digits of partition S1. Call this x. Similarly do it for S2. Call it y. the product p=xy. What should the numbers x and y be to maximize p.

2. Statistic: In Starcraft, your rating start at 1000 points. Winning a game gives you 100 points, losing and 50 will be deducted. What is the probability of you having 2000 points after having played 20 games?

3. Tower of Hanoi: What is the minimum of move would it take to move a stack of 5 disks? n disks?

Tower of Hanoi

This should be where you stop reading and trying to solve the above 3 by yourself. Here is some Jazz to help you focus.

— — — — — — — — — — — — — — — — —

Well lets tackle these problems shall we?

Algebra problem:

This was actually not in my interview. I came across this question when I researched about this firm prior to my interview. But I thought I would include it in because its a good brain tease.

Step 1: Analyze the problem

You have a set of 9 digits { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

This set will be divided in 2 smaller sets A={ a1, a2, a3,… } and B={ b1, b2, b3,… } such that:

  • A∪B = { 1, 2, 3, 4, 5, 6, 7, 8, 9 } and
  • A∩B = { } (empty set)

So far so good… Here come the hard part:

  • Somehow the digits in A set will make number x
  • Somehow the digits in B set will make number y
  • We have to ensure that x*y will be as high as it possibly can

This means that we will have to customize the 2 following processes:

  • The process of dividing { 1, 2, 3, 4, 5, 6, 7, 8, 9 } into A and B
  • The process of arranging A and arranging B into x and y respectively

so that P (which equal to x*y) is maximized.

Step 2: Institutional guessing:

Recall a similar problem where given a rectangle of width w and height h where w + h = some CONST_A. Find w and h so that rectangle’s area is maximized.

The solution is that w=h which is a square.

Quick check to see the solution could be applied here: take a pair of x_far and y_far which are extremely far away and compare the product of 2 numbers with a pair of x_near and y_near which are relatively closer.

Let x_far = 9,876,543 and y_far = 12 this we have P_far ~= 9,000,000 * 10 = 90,000,000

Keep in mind that this is a phone interview, time is at the essence.

Let x_near = 94321 and y_near = 8765 then our P_near ~= 90000 * 9000 = 810,000,000

There we quickly concluded that x and y should be relatively near so P can be big.

Since x and y are made up out of 9 digits, 1 should be 5 digits and 1 should be 4 digits.

From now on we will assume x is the 5 digits number and y is the 4 digits.

Step 3: Solving it

Another observation from experiment above was that P is largely determined by the leading digits.

The reason for this is the leading digit will determine the size of x and y.

Here is why:

Lets x = abcde and y = fghi such that { a, b, c, d, e, f, g, h, i } = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

This makes

x = a*(10⁴) + b*(10³) + c*(10²) + d*(10¹) + e*(10⁰)

y = f*(10³) + g*(10²) + h*(10¹) + i*(10⁰)

So if P = x*y then the large part of P will be determined by this value a*(10⁴) * f*(10³).

Note how there is a trap here: a lot of people will jump to conclusion that a = 9 and f = 8 immediately.

That’s a mistake because note that in a product, a and f are interchangeable.

Our goal was not to maximize x nor y but to ensure (x-y) is minimized following the initial observation concluded.

With this we could safely conclude that { a, f } = { 8, 9 }

So now we have [ x, y ] could either be [ 90000, 8000 ] or [ 80000, 9000 ].

As stated, our original goal was to minimized (x-y) so the obvious selection here would be [ 80000, 9000 ].

But since we don’t have time to prove that our original thesis was correct, it’s worth to keep the other pair so that we could use it as unit test against our proposed solution.

So now with x = 8bcde and y = 9ghi, we just solve the problem recursively using the above method with the rest of the pair:

{ b, g } = { 6, 7 }

{ c, h } = { 4, 5 }

{ d, i } = { 2, 3}

e = 1

So we simply try out quickly what we have

86421 * 9753 = 842864013

87531 * 9642 = 843973902

And to cover our base, lets try out [ 90000, 8000 ] as mentioned.

96421 * 8753 = 843973013

97531 * 8642 = 842862902

Here we observed that for pair { b, g } = { 6, 7 }, we cannot simply apply the same rule with { a, f } = { 8, 9 }.

The reason is that { b, g } apart from having to produce the b*g*(10^(3+2)), they also produce g*a*(10^(4+2)) and b*f*(10^(3+3)) as well…

Here I ran out of time thus concluded the answer is 87531 * 9642 = 843973902

Step 4: Retrospective

Looking back, once established that P = abcde * fghi

We could further expand that P = (abcd * 10 + e) * fghi

Thus P = abcd * fghi * 10 + e * fghi

Since we have concluded that e = 1 then P’s value will largely be determined by (abcd * fghi)

This quickly simplify the problem to the 2 nearest, largest numbers thus we find

9642–8753 = 889

9753–8642 = 1111

This further more secure our original finding.

Next Episode: Problem 2 and 3