Back to the EFNet #compsci Resource Page.

EFNet #compsci Cute Problems

Editor: Albert Y. C. Lai, trebla [at] vex [dot] net

You may send suggestions for more entries to the editor.

Solutions are being slowly added. You are invited to discuss the problems and solutions on the EFNet #compsci channel.

Dijkstra's Articles

Dijkstra wrote a lot of short articles on computer science, programming, and problem-solving. Thus they include a lot of cute problems, simple solutions, and effective methods. They are available at the EWD Archive.

Rustan Leino's Puzzles

Rustan Leino has a collection of puzzles.

Longest Palindrome

Find the longest palindrome in a string of length n. Time complexity should be O(n3) for beginners, O(n2) for advanced.

Common Ancestor in BST

In a binary search tree, find the closest common ancestor to two nodes of depth at most d. Time complexity should be O(d). Space complexity should be O(1).

Java Threading

What's wrong with this code?

The Length Function

Here are some implementations of the length function. How do they differ?

Number of Set Bits

Count the number of set bits in a binary number. You may use the standard arithmetic and bitwise operations, each assumed to take unit time. Time complexity should be O(b), where b is the number of set bits (not the number of bits). Example: if the number happens to be 2k, your algorithm should finish in O(1) time rather than O(k) time.

Rectangle Test

You are given a list of n points on the plane with integer x-y coordinates. Determine in O(n) time if the points describe a filled in rectangle. A rectangle is filled in if all integer-coordinate points on its interior are present.

Sorting Phone Numbers

You are given a file of up to 10 million 7-digit phone numbers (they were 1-800 numbers, but the 1-800 part has been removed for you). Each phone number cannot appear twice or more. Sort them, and output the sorted list to another file. You can use only 1 megabyte of memory, though you may also use extra files and disk space as much as you wish. Running time: as fast as possible, preferably on the order of seconds.

This problem is taken from Dr. Dobb's Journal, December 1999, Algorithm Alley column, “Programming Pearls: Cracking the Oyster”, by Jon Bentley. Bentley in turn took it from his book Programming Pearls, second edition (link).

solution

Number Order with Minimum Hamming Distance

Given n, output the numbers from 0 to 2n-1 (inclusive) in n-bit binary form, in such an order that adjacent numbers in the list differ by exactly 1 bit. Examples:

Tree Re-construction

  1. Consider trees with these extra structures: Given the pre-order and post-order traversals of a tree, re-construct the tree.
  2. Consider binary trees with these extra structures: Given two of the following three: re-construct the tree.
  3. Consider binary trees with these extra structures: Given the in-order traversal and one of the following: re-construct the tree.

Lexicographical Number Sequence

Given positive integers k and n, find the kth integer in the lexicographical sequence of all integers between 1 and n (inclusive).

Lexicographical Permutation

Consider the letters from A through M. If all possible 13-letter permutations (no repeated letters) of these letters are arranged in alphabetical order, what is the 1,234,567,890th permutation in the list?

Two Paratroopers

You have the following four instructions available:

where labels are allowed. Each of the four instructions take a single clock tick to execute. Two paratroopers land along a straight road that extends infinitely in both directions. Their parachutes are at their respective landing locations. The walk instructions make the paratrooper walk one unit in the specified direction. Write a program using the above four instructions that will allow the paratroopers to meet each other. The same program will be executed for the two paratroopers. The program is executed in parallel for the paratroopers. The program stops when and only when they meet.

Digital Factorial Sum

Find a 3-digit number such that the sum of the factorials of its digits equals itself.

Now for any n, find an n-digit number such that the sum of the factorials of its digits equals itself, or determine that it does not exist.

Pirates Divide Gold

There are 5 perfectly logical pirates. They are numbered from 1-5. They just completed a mission and have 100 gold pieces which they now need to divide. It is pirate #1's responsibility to determine how they are going to divide the gold. There is a catch however. If more than half of the pirates disagree with his dividing scheme, then they will kill him and the responsibility of dividing the gold will fall on pirate #2. If #2's proposal is unacceptable to more than half, then #3 will come up with a scheme and so on. How can #1 divide the gold in such a way that he maximizes his profit and doesn't die?

Securing Unsecure Courier

You are on an island with a box, a chain, a padlock with key, and a diamond. You have a friend on another island with a box, a chain, and a padlock with key. Only your key opens your lock; only your friend's key opens your friend's lock. You need to get your diamond to your friend, and you need to use the Pirate Courier Service (tm). The only problem is the pirates are thieves, and they will steal anything without a locked lock on it. How can you get your diamond to your friend?

solution

Friends

Prove that the people you know are exactly those known by all who know all whom you know. Generalize.

Hats in a Row

Ten gnomes are lined up. Each has either a red or blue hat placed on their head. Each can see all hats of all gnomes in front of him, but not of himself or those behind him. They are required from back to front to tell what color hat they are wearing. If they are wrong they are killed. What is the expected number of gnomes that can survive and what is their strategy?

Card Colour Betting

You have $1, and somebody will flip and reveal one by one all cards in a 52-card deck with 26 blacks and 26 reds. A revealed card will not go back to the deck. At each flip you can bet any fraction (including 0) of your wealth on the colour of the card to be flipped. You lose the amount if you're wrong and double it if you're right. What is the maximum amount that you can guarantee you will have at the end of the exercise?

Halmos Handshake Problem

Hilary and Jocelyn are married. They invite four couples who are friends for dinner. When they arrive, they shake hands with each other. Nobody shakes hands with him or herself or with his or her spouse. Nobody shakes hand with the same person more than once. After there has been some handshaking, Jocelyn jumps up on a chair and says "Stop shaking hands!", and then asks how many hands each person has shaken. All the answers are different. How many hands has Hilary shaken?

Imperative Programming vs. Functional Programming

  1. What does the following program do, i.e., what is the value of r in terms of p and q? Assume the array is large enough.
  2. How large should the array be?
  3. How much time will the program spend?
  4. How much time do you need to figure all this out?
  5. Write a functional program to compute the same r. Compare. :-) 
  a[1] = p;
  a[2] = q;
  n = 2;
  while (n != 1) {
    if (a[n-1] == 0) {
      a[n-1] = a[n] + 1;
      n = n - 1;
    }
    else if (a[n] == 0) {
      a[n-1] = a[n-1] - 1;
      a[n] = 1;
    }
    else {
      a[n+1] = a[n] - 1;
      a[n] = a[n-1];
      a[n-1] = a[n-1] - 1;
      n = n + 1;
    }
  }
  r = a[1];

partial solution (1,5)

Spreading Balls

You have an unlimited collection of boxes indexed by the integers. Initially there are 2n+1 balls in box #0, and all other boxes are empty. You job is to re-distribute the balls so that boxes #-n through #n (inclusive) have one ball each. Your only allowed moves: whenever box #i has at least 2 balls, you may remove 2 balls from it, give 1 to #i-1, and 1 to #i.

Secret Message

A spy in a top-secret weapons research lab is trying to send information to another secret agent. The method of communication is as follows: Each day, the weapons lab sends out an email with a randomly generated 8 pixel x 8 pixel black and white image, and the spy has figured out a way to secretly change any single bit of the image he wishes to modify. He can send information in this way to the other agent; for example, he can answer any yes/no question by making sure the top left bit of the picture is 1 (for yes) or 0 (for no). This would count as transmitting 1 bit of information. But other schemes perhaps allow for transmitting more bits of information. So: what is the maximum number of bits of information which the spy can send in this way? (If possible, prove that your answer is optimal, and give an efficient algorithm for implementing the method).

Optimal Cost with Activation Fees

There is a matrix of n rows and m columns of non-negative numbers. In addition, each column c is also associated with a non-negative number fc (you will think of it as an activation fee). Do this:

  1. from each row choose a number; add them and call it S.
  2. note the columns you use; add up their activation fees and call it F. Thus fc appears once as a summand in F if you use column c once or more; otherwise fc is not involved. (You can think of fc as some kind of activation fee for doing business with company c.)

Minimize S+F.

Rightmost Intersection

Find the rightmost of the pairwise intersections of n straight lines on the plane in O(n log n) time. The lines are specified by slopes and y-intercepts; they are pairwise intersecting.

The Five-Card Trick of William Fitch Cheney

A magician and an assistant perform the following trick. Five cards are drawn from the standard 52-card deck (randomly or by the audience) and shown to the assistant and the audience (but not the magician). The assistant picks four and sequences them to show to the magician, and the magician has to determine the remaining one. Devise a scheme for them.

Back to the EFNet #compsci Resource Page.