Interview Brain Teasers (Repost)

References: Sharing some interesting programmer interview brain teasers A collection of programmer interview brain teasers

Game Theory (Choosing Strategies)

Consider a two-player game played at a round table. Each player has plenty of coins. They take turns placing coins on the table; each turn exactly one coin must be placed, fully within the tabletop (no part may hang over the edge), and it may not overlap previously placed coins. Whoever has no place to put a new coin loses. Does the first or second player have a winning strategy? What is it?

Answer: The first player places a coin at the table’s center; afterwards he always places his coin at the position symmetric to where the second player just placed. This way, whenever the second player can place, the first player certainly has a place too. The first player must win.

A and B are on two different islands. B is sick, and A has the medicine B needs. C has a small boat and a lockable box. C is willing to carry things between A and B, but things can only go in the box. Whenever the box is unlocked, C steals whatever is inside, no matter what it is. If A and B each have a lock and a key that opens only their own lock, how should A safely deliver the item to B?

Answer: A puts the medicine in the box and locks it with his own lock. After B receives the box, he adds his own lock to it. When the box returns to A, A removes his own lock. When the box reaches B again, B removes his own lock and gets the medicine.

Two robots initially sit at different positions on a number line. Give both robots the same program so that they are guaranteed to meet. The program may contain only “move left n units”, “move right n units”, the conditional statement If, the loop statement while, and two Boolean-returning functions “at my own start” and “at the other’s start”. You cannot use other variables or counters.

Answer: Both robots start moving right at unit speed until one robot reaches the other robot’s start point. Then that robot chases the other at double speed. The program is as follows.
1
2
3
4
5
6
while(!at_other_robots_start) {
  move_right 1
}
while(true) {
  move_right 2
}

If asked to choose one of the following two games, which would you choose? Why? a. Write a sentence. If the sentence is true, you get 10 dollars; if false, you get less than or more than 10 dollars (but never exactly 10). b. Write a sentence. Regardless of its truth, you get more than 10 dollars.

Answer: Choose the first game and write “I will get neither 10 dollars nor 10000000 dollars”. (Can’t follow the answer??)

There are 25 horses, all of different speeds, but each horse’s speed is constant. There are only 5 tracks and no timing, i.e. each race tells you only the relative order of at most 5 horses. What is the minimum number of races to find the top 3 fastest of the 25 horses? (a 2008 Baidu interview question)

Answer: Every horse must race at least once, so dividing the 25 horses into 5 groups, the first 5 races are unavoidable. Finding the champion is then easy: race each group’s champion together (race 6). Finally we need the 2nd and 3rd places. Name the groups A, B, C, D, E by their champions’ order in race 6. That is: group A’s champion is race 6’s 1st, group B’s champion is race 6’s 2nd… Number each group’s 5 horses from fast to slow by their recorded results:

Group A: 1, 2, 3, 4, 5 Group B: 1, 2, 3, 4, 5 Group C: 1, 2, 3, 4, 5 Group D: 1, 2, 3, 4, 5 Group E: 1, 2, 3, 4, 5

From the information so far, we can tell which horses are already excluded from the top 3. Once 3 or more horses are confirmed faster than a horse, it is eliminated. You can see that only the 5 bold horses in the table above could possibly be 2nd or 3rd: namely group A’s 2nd and 3rd; group B’s 1st and 2nd; group C’s 1st. Race these 5 horses in race 7; race 7’s top two are the 2nd and 3rd of the 25 horses. So the minimum total is 7 races.

This problem has variants, e.g. finding the top 4 of 64 horses. The method is the same: after obtaining 1st place, find the candidate competitors for the remaining 3 places.

Coin game: 16 coins; A and B take turns removing some, each removal being exactly 1, 2, or 4 coins. Question: does A or B have a strategy guaranteeing a win?

Answer: In this problem, whoever takes first loses. If the first takes 1, the second takes 2; if the first takes 2, the second takes 1; if the first takes 4, the second takes 2. As long as the second player keeps the sum with the first player’s take a multiple of 3, the win is certain.

Hat problem 2:

There is a prison cell holding 3 prisoners. Because the glass is thick, the 3 can only see each other, not hear each other speak. One day the king devised a plan: he put a hat on each of their heads, telling them only that the hat colors are either white or black, not telling them their own hat colors. Under these conditions, the king announced two rules:

Whoever sees the other two prisoners both wearing white hats may be released;
Whoever knows he wears a black hat may be released. Actually, the king gave them all black hats. Being bound, they simply can’t see their own. So the 3 stared at each other in silence. But soon, the sharp-witted A used reasoning to conclude he wore a black hat. How do you think he deduced it?

Answer: If A wore a white hat, then B would know his own hat was black, because if B wore white, C would see two white hats — but C didn’t see that, so……..

A cell holds two prisoners. Each day the prison provides this cell a jar of soup for the two prisoners to divide themselves. At first the two often argued, because each always thought the other’s soup was more. Later they found a mutually satisfying method: one divides the soup, the other chooses first. The dispute was thus solved. But now a new prisoner has been added to the cell — now three people divide the soup. A new method must be found to keep the peace among them. What to do?

Answer: A psychological problem, not a logic one. Let A divide the soup; after dividing, B and C pick for themselves in any order, and the remaining bowl goes to A. This way B and C’s combined total is certainly the maximum the two can get. Then mix their two portions and divide again by the two-person method.

5 pirates seized 100 buried gold coins and plan to divide the loot. These are democratic pirates (their own peculiar democracy, of course); their custom divides as follows: the fiercest pirate proposes a distribution plan, then all pirates (including the proposer) vote on it. If 50% or more approve, the plan passes and the loot is divided accordingly. Otherwise the proposer is thrown into the sea, and the next fiercest pirate repeats the process. All pirates are happy to see a comrade thrown into the sea, but given a choice they’d rather have cash. Of course they don’t want to be thrown in themselves. All pirates are rational and know the others are rational. Moreover, no two pirates are equally fierce — they are ranked strictly top-down, and everyone knows his own and everyone else’s rank. The gold bars cannot be divided further, and pirates may not share bars, because no pirate trusts his comrades to honor any bar-sharing arrangement. This is a crew where everyone looks out only for himself. What distribution plan should the fiercest pirate propose to get the most gold?

Answer: If it’s the fourth pirate’s turn to divide: 100, 0 Third’s turn: 99, 0, 1 Second’s turn: 98, 0, 1, 0 First’s turn: 97, 0, 1, 0, 2 — this is the first pirate’s optimal plan.

Algorithm Problems

Reverse the words (not characters) of an article in linear time and constant extra space.

Answer: First reverse all characters of the whole article (repeatedly swapping symmetric characters from both ends); then reverse the characters within each word the same way. Thus the article’s word order is reversed, but the words themselves are turned back.

How to quickly find how many “1”s are in the binary representation of a 32-bit integer? In time linear in the number of “1”s? (Give a one-line C expression determining whether a given integer is a power of 2.)

b & (b-1) turns the rightmost 1 of the number into 0

You’re on a spaceship whose computer has n processors. Suddenly the ship is attacked by alien laser weapons and some processors are damaged. You know more than half the processors are still good. You can ask one processor whether another processor is good or bad. A good processor always tells the truth; a bad one always lies. Find a good processor with n-2 questions.

A voting problem

For a batch of lights numbered 1~100 all initially switched on, perform the following: every multiple of 1 flips its switch once, every multiple of 2 flips again, every multiple of 3 flips again. Which numbered lights end up off?

Prime sieving Reference answer: primes are off, the rest are on.

From consecutively increasing data, two numbers are removed and the order shuffled; find the two removed numbers.

Estimation

A diamond is placed at each elevator door from floor 1 to floor 10, all of different sizes. You ride the elevator from floor 1 to floor 10; each floor’s door opens once, and you may take a diamond only once. How can you get the largest one?

Reference answer: Her answer was: don’t take any on the first five floors — observe the diamond sizes on each floor to get a feel; then choose on the last five floors, picking a diamond close in size to the largest seen in the first five floors. She still doesn’t know this problem’s exact answer: “Maybe there is no exact answer; it just tests your thinking,” she said.

Similar questions include “How many bus stops do you think Beijing has?” — you can give any answer, 5 or 5000, but you must have reasons.

How many gas stations (cars) are there in the US?

Reference answer: Facing this seemingly bewildering question, you might start by asking how many small cars the country has. The interviewer may tell you the number, or may say: “I don’t know — you tell me.” Then you say to yourself: the US population is 275 million. You can guess that if the average household (including singles) is 2.5 people, your calculator tells you there are 110 million households. You recall hearing somewhere that each household owns on average 1.8 cars, so the US has roughly 198 million cars. Then, as long as you compute how many gas stations are needed to serve 198 million cars, you’ve solved the problem. What matters isn’t the number of gas stations, but the method by which you derive it.

Suppose the clock strikes 12. Note the hour and minute hands overlap. During one day, how many times do the hour and minute hands overlap in total? Do you know the exact times they overlap?

Reference answer: This reduces to a meeting problem with a speed difference — the minute hand meets the hour hand once per lap, i.e. it meets once per hour of the day. The key is computing the exact meeting times. After 12 o’clock, in the minute hand’s and hour hand’s first lap, their distance is one lap (60 minutes) and the speed difference is 55 minutes, so the time is 60/55. That is, they first meet at about five-past-one. In the second lap their distance is 120 minutes, the speed difference is still 55 minutes, so they meet at about ten-past-two. And so on.

22 times. Once at 0:00, once a bit after 1:05 (exactly 1×60/11 minutes, i.e. 5 minutes 27.27 seconds), once a bit before 2:11 (2×60/11 minutes) ……………… once a bit before 10:55 (10×60/11 minutes), once at 11:60 (i.e. 12:00), then once a bit before 13:06…… the last time is 22:54:32.73. The next overlap is at 0:00 the following day.

A hypothetical derivation about “what times exactly”: let a, b be the angles the hour and minute hands travel in equal time; represent the hour and minute hands by A B, n means the minute hand has crossed the hour hand for the n-th time, m[1, +∞), m an integer, X”m means X to the m-th power. b=12a a=b/12 => When A B overlap for the n-th time: b=30(n+1)+30(n+1)*1/12+30(n+1)*1/12*1/12+……+30(n+1)*1/12”m (there’s an assumption here: when 30(n+1)/12”m approaches 0 infinitely, we conjecture A and B coincide.) After rearranging: b=30(n+1)+30(n+1)/12+30(n+1)/(12”2)+……+30(n+1)/12”m. The A B overlap time: (n+1) hours b/6 minutes. But since “minutes” are usually expressed as positive integers, you can round to the unit digit or multiply the decimals by 60 to convert to seconds.

Once after 1:05, once after 2:10, once after 3:15, once after 4:20, once after 5:25, once after 6:30, once after 7:35, once after 8:40, once after 9:45, once after 10:50, once exactly at 12:00. 22 times in total across 24 hours.

How many digits does 1000! have, and why?

Reference answer:

Lg(1000!)=sum(Lg(n)) n=1 Using 3 polyline segments instead of the curve gives 10(0+1)/2+90(1+2)/2+900(2+3)/2=2390 As an approximation, anything from 1500~3000 counts as right

How long does it take to sort one trillion numbers? Give a reliable estimate.

Answer: This is another problem with no standard answer. The purpose is examining the interviewee’s creativity. We favor the simple answer given by two readers: sort with Merge Sort. On average O(1,000,000,000,000 Log 1,000,000,000,000). Worst case O(1,000,000,000,000 Log 1,000,000,000,000). A billion operations per second is achievable now, so it should take about 3000 seconds.

How many software engineer resumes does Google receive each year? This also examines whether candidates can simplify and clarify problems and propose creative solutions.

Answer: A candidate for a “quantitative compensation analyst” position should know Google hired 3400 people in 2008. Estimate 75% of them, i.e. 2550, were engineers, and Google’s acceptance rate resembles Harvard’s — taking 3% of applicants. From this, roughly 85000 resumes were received (85000 x 3% = 2550).

Method Problems

A prescription is very strict: you must take one pill each of medicines A and B simultaneously every day — no more, no less. The medicine is very expensive; you don’t want the slightest waste. One day you open the bottle of pills A, pour one pill into your palm; then open the other bottle, but accidentally pour out two pills. Now your palm holds one pill A and two pills B, and you cannot tell which is A and which is B. How can you strictly follow the prescription while wasting nothing?

Answer: Cut each of the three pills in your hand in half, arranged in two piles. Take out one more pill A, cut it in half too, then add half of the A to each pile. Now each pile contains exactly two half-A’s and two half-B’s. Take one pile per day.

Burning one non-uniform rope takes an hour. How can you use it to measure half an hour? Burning one non-uniform rope from end to end takes 1 hour total. Now you have several ropes of the same material; how can you time one hour and fifteen minutes by burning ropes?

Reference answer:

Half hour: burn both ends simultaneously. One hour fifteen minutes: burn one normally, one from both ends.

The instant the two-ended one burns out, light the other end of the normally burning one. After it burns out, 45 minutes have passed. The instant it burns out, burn another rope from both ends. Total: one hour fifteen minutes.

With one 7-gram and one 2-gram weight and a balance scale, how can you divide 140 grams of salt into portions of 50 and 90 grams using only these items in three weighings?

Reference answer:

First use the balance to divide 140g into two equal portions of 70g each.

Then use the balance to divide one 70g portion into two equal portions of 35g each.

Put one 35g portion on one side of the balance, put the 7g weight on the same side, and put the 2g weight on the other side. Move salt from the 7g-weight side to the 2g-weight side until the balance levels. Now the salt on the 2g-weight side is 20g. Put this 20g together with the untouched 70g portion already divided — that’s 90g; put the remaining salt together — that’s 50g.

You have four jars of pills; each pill has a certain weight, and contaminated pills weigh one unit more than uncontaminated ones. With a single weighing, how do you determine which jar’s pills are contaminated?

Reference answer:

Take one pill from the first jar, two from the second, three from the third, and so on; weigh the total. Then judge the contaminated jar by how much the total weight is increased.

If you have infinite water, a 3-quart pail and a 5-quart pail, how do you measure exactly 4 quarts of water?

Reference answer:

A. First fill the 3-quart pail and pour into the 5-quart (abbreviated 3->5 below); mark b1 on the 5-quart pail (abbreviated b1). B. Use 3 to keep filling 5; empty 3; pour the water from 5 into 3 until b1; mark b2 on 3. C. Use 5 to keep filling 3; empty 5; pour the water from 3 into 5 until b2. D. Empty 3; pour the water from 5 into 3; mark b3. E. Fill 5; empty 3; pour from 5 into 3 until the water in 3 reaches b3. Done — the water now in 5 is a standard 4 quarts.

You have a bucket of jelly beans in yellow, green and red. With eyes closed, pick out two of the same color — grab two of one color. How many must you grab to be certain you have two jelly beans of the same color? (pigeonhole principle)

Reference answer: 4. Except for the first case, in all other cases you can be certain of having two of the same color. When grabbing the fourth, whatever color it is, your question is settled. So the minimum is four jelly beans.

A room has one door (closed) and 3 electric lights. Outside are 3 switches, each connected to one of the 3 lights. You may operate the switches freely, but once you open the door you can no longer change switches. Determine which switch controls which light.

Reference answer: First turn on one switch outside, wait a while, then turn it off, turn on another switch, and walk into the room. The bulb that is hot but unlit is controlled by the first switch; the lit one by the second; the one neither lit nor hot by the third.

Suppose you have 8 balls, one slightly heavier, and the only way to find it is comparing two balls on a balance. What is the minimum number of weighings to find the heavier ball?

Reference answer: Two. First weighing: take 3 balls on each side of the balance. If balanced, the heavy one is among the other two — put those two on the balance; whichever side is heavier holds the heavy ball. Second weighing: in the unbalanced case, take two balls from the slightly heavier side onto the balance; if balanced, the other one is the heavier; if unbalanced, the heavier side holds it.

The gold bar division problem:

You had some people work for you seven days, paying them with one gold bar. The bar must be divided into seven pieces. You must hand over one piece after each day’s work. If you may cut the bar only twice, how do you pay these workers?

Answer: Cut twice, dividing the bar into 1/7, 2/7, 4/7 portions, labeled a, b, c. Day 1: give a Day 2: give b, take back a Day 3: give a Day 4: give c, take back a and b Day 5: give a Day 6: give b, take back a Day 7: give a

The monkey moving bananas problem: A little monkey has 100 bananas beside it; it must walk 50 meters to get home. Each trip it can carry at most 50 bananas, and every meter walked eats one banana. What is the maximum number of bananas it can bring home?

Answer: The monkey first carries 50 bananas to the 25-meter mark, having eaten 25; it leaves them there, goes back for the other 50 bananas, carries them to the 25-meter mark, then rests five minutes, picks up the 50 bananas at the 25-meter mark and walks home, arriving with 25 bananas left.

The airplane refueling problem: Each airplane has only one fuel tank; airplanes can refuel each other (note: mutually — no tanker aircraft). One tank lets one plane fly half way around the earth. So that at least one plane can circle the earth and return to its starting airport, what is the minimum number of planes that must be dispatched? (All planes take off from the same airport and must return safely; no mid-course landings allowed, no airports in between.)

Answer: First three planes take off. At 1/8 around the earth, all three still have 3/4 fuel; one gives each of the other two 1/4 of a tank, then flies back — now the other two are full. When these two planes reach 1/4 around the earth, both have 3/4 fuel; one gives the other 1/4 and flies back — now the last plane is full. When the last plane reaches half way around the earth, a plane goes out from the endpoint in the opposite direction; they meet 1/4 from the endpoint. At this point the first plane is out of fuel and the second has 2/4; it gives the first 1/4 and flies back. Meanwhile another plane takes off from the endpoint, flying the opposite way; the three planes meet 1/8 from the endpoint — the first two are empty, the last has 3/4 fuel and gives each of the other two 1/4; they fly back together. OK — if the base can refuel, three planes suffice; if not, five are needed.

Can’t Quite Follow

A couple invites N-1 other couples to a party (so 2N people total). Everyone shook hands once with every person they didn’t know. Then the host asked all the others (2N-1 people) how many hands each had shaken, and all the answers were different. Assuming everyone knows their own spouse, how many hands did the hostess shake?

Answer: The handshake counts can only be the 2N-1 numbers from 0 to 2N-2. Excluding the host, there are 2N-1 people, so each number appears exactly once. One person (0) shook no hands; one person (2N-2) shook hands with all the other couples. These two must be a couple, otherwise the latter would have shaken hands with the former (so the former’s count wouldn’t be 0). Excluding this couple, one person (1) shook hands only with (2N-2); one person (2N-3) shook hands with all other couples except (0). These two must be a couple, otherwise the latter would shake hands with the former (so the former’s count wouldn’t be 1). And so on, until the person who shook N-2 hands pairs with the person who shook N hands. At this point everyone except the host and his spouse has paired up. By elimination, the remaining person with a handshake count of N-1 is the hostess.

Shouldn’t this couple know everyone??

Logic Calculation Problems

On a pasture, it’s known that 27 cows finish the grass in 6 days; 23 cows finish it in 9 days. With 21 cows, how many days to finish the pasture’s grass? And the pasture’s grass keeps growing.”

Answer: Let each cow eat x per day and the grass grow y per day; the original grass amount is a. a=(27x-y)*6=(23x-y)*9 Solving gives y=15x, a=72x, so a=(21x-y)*12 — hence 12 days are needed.

A merchant rides a donkey across a 1000-km desert to sell 3000 carrots. The donkey can carry 1000 carrots at a time, but eats one carrot per kilometer walked. Question: how many carrots can the merchant sell in total?

Answer: The merchant takes the donkey with 1000 carrots, walks 250 km first — the donkey has eaten 250; drop 500, return in place, eating another 250. The merchant again takes the donkey with 1000 carrots to the 250-km point — the donkey has eaten 250 — loads 250 of the 500 dropped there, continues to the 500-km point — the donkey eats another 250 — drops 500, returns to the 250-km point with the remaining 250, loads the 250 left at 250 km and returns to the origin — the donkey eats another 250. The merchant again takes the donkey with 1000 carrots to the 500-km point — the donkey has eaten 500 — loads the 500 previously dropped, and walks out of the desert; the donkey eats 500, leaving 500.

10 boxes of gold, 100 bars per box, one tael per bar. A corrupt official ground one qian off every bar in one box. Find the underweight box with a single weighing.

Answer: Take 1 bar from the first box, 2 from the second, n bars from the n-th box; put them together and weigh. See how many qian are missing — missing n qian means it’s the n-th box.

The car refueling problem A car carrying 500 liters of fuel drives from A to B, 1000 km away. The car consumes 1 liter per km; A has infinite fuel, no other location has any, but the car may deposit fuel anywhere for relay. What is the minimum fuel needed from A to B?

Solution: Strictly proving this model optimal is troublesome, though provable; bold conjecture is the key to solving. The problem reduces to finding when the sum Sn of the sequence an=500/(2n 1), n=0,1,2,3…… first reaches 1000. Solving gives n>6; at n=6, S6=977.57, so the first relay point is 1000-977.57=22.43 km from the start. Thus before the first relay the total fuel consumed is 22.43*(27 1)=336.50 liters; each subsequent relay consumes 500 liters, so total fuel consumption is 7500 336.50=3836.50 liters.

A little monkey has 100 bananas beside it; it must walk 50 meters to get home. Each trip it carries at most 50 bananas, and every meter walked eats one. What is the maximum number of bananas it can bring home?

Solution: Let the little monkey walk from 0 to 50; at point A it can directly carry the bananas home. But reaching point A it has consumed at least 3A bananas (to A, back to 0, to A). One constraint: the monkey can carry only 50 bananas, so at point A the monkey has at most 49 bananas. 100-3A=49, so A=17. After all this shuttling, arriving home the bananas left are 100-3A-(50-A)=50-2A=16.

Tencent interview question (counting digit occurrences):

0 1 2 3 4 5 6 7 8 9

Fill in digits on the lines to meet the requirement. The requirement: the number filled under each digit represents how many times that digit above appears below — e.g. under 3 is 1, meaning 3 must appear once below.

The correct answer is:

1 2	0 1 2 3 4 5 6 7 8 9 6 2 1 0 0 0 1 0 0 0

Some Awkward Questions

How many points on Earth are such that walking one mile south, one mile east, then one mile north returns you exactly to the starting point?

Answer: “The North Pole” is a traditional answer, but the question actually has other answers. In fact, infinitely many points satisfy it. All places 1 + 1/(2π) miles from the South Pole qualify: after walking one mile south you reach a point 1/(2π) miles from the South Pole; walking one mile east circles the latitude line exactly once; walking north returns along the original path to the start. In fact this still isn’t all the qualifying points. Places 1 + 1/(2kπ) miles from the South Pole all work, where k can be any positive integer.

1, 11, 21, 1211, 111221 — what is the next number?

Answer: Each line describes the previous one, so the new one should be three 1s, two 2s, one 1: 312211

A group holds a dance party; everyone wears a hat. The hats come only in black and white, with at least one black. Everyone can see others’ hat colors but not their own. The host first lets everyone look at what hats others wear, then turns off the lights: anyone who believes they wear a black hat slaps their own face. At the first lights-off, no sound. Lights on again, everyone looks once more; at lights-off still dead silence. Only at the third lights-off does the sound of slaps crackle out. How many people wear black hats?

Answer: 3. If only 1 person wore black, he’d slap himself at the first lights-off; if 2 people, they’d slap themselves at the second lights-off; with n people wearing black hats, they slap themselves at the n-th lights-off.

Logic Problems

The two-person number guessing problem A professor picks two numbers from 2 to 9, tells student A their sum and student B their product, and has them take turns guessing the two numbers. A says: “I can’t guess it.” B says: “I can’t guess it.” A says: “I’ve got it.” B says: “I’ve got it too.” What are the two numbers?

Solution: 3 and 4. Let the two numbers be n1, n2, n1 >= n2. A heard n = n1+n2; B heard m = n1*n2. Prove n1=3, n2=4 is the unique solution. Proof: to prove the proposition true, first prove n=7.

Necessity:

n > 5 is obvious, since n < 4 is impossible and for n=4 or n=5 A couldn’t answer “don’t know”

n > 6 because if n=6, although A doesn’t know (unsure whether 2+4 or 3+3), whether it’s 2, 4 or 3, 3, B couldn’t say “don’t know” (with m=8 or m=9, B saying “don’t know” makes no sense)

n < 8 because if n >= 8, n could decompose as n=4+x and n=6+(x-2), so m could be 4x or 6(x-2), and 4x=6(x-2) requires x=6, i.e. n=10; then n could also decompose as 8+2, so in short when n >= 8, n can decompose into at least two different sums of composites — this way when B says “don’t know”, A has no reason to immediately say “know”. The above proves necessity.

Sufficiency When n=7, n can decompose into 2+5 or 3+4. Obviously 2+5 doesn’t fit the problem — discard; it’s easy to judge 3+4 fits, m=12. QED

Thus n=7, m=12, n1=3, n2=4 is the unique solution.

n people form a circle for handshakes — no crossing, no one left out. How many handshake arrangements are there in total? (Catalan number derivation)
From 54 playing cards, remove the jokers and deal evenly to 4 people. What is the probability the Ace of Hearts and Ace of Spades are in the same person’s hand?