The 37% Rule

September 21, 2018

You have to hire a new programmer from a pool of 100 applicants. One method is to interview all 100 and hire the best, but that takes a while. Mathematicians have developed the 37% rule:

Examine 37% of the candidates, knowing in advance you will not select any of them. Then examine the remaining candidates one-by-one, choosing the first of them that is better than any of the first 37%.

Your task is to simulate this process and determine how close you get to the optimal candidate. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

1-800-PPRAXIS

September 18, 2018

I hate businesses with telephone numbers that spell words; it’s awkward to type letters at a telephone, and often the words are abbreviated or spelled wrong so they are no longer mnemonic, which defeats the purpose. So this morning when I had to call one of those businesses, I wrote a program to translate letters to numbers after I had been waiting on hold long enough to get really annoyed.

Your task is to write a program to translate telephone numbers specified as words. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Nth From The End

September 11, 2018

Counting from the end of the list, the third-last item in the list (1 2 3 4 5 6 7 8 9) is 7.

Your task is to write a program to find the nth-last item in a list; you must provide at least three fundamentally different solutions. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

List Homework

September 7, 2018

For many students, school started a few weeks ago, so today’s exercise is typical of homework:

  1. Write a program to determine the length of a linked list.
  2. Write a program to reverse a linked list.

Your task is to write the two list exercises described above; write them as if you are three weeks into your first data structures class. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Mind-Boggling Card Trick

September 4, 2018

Today’s exercise is a mind-boggling card trick:

Create a pack of 52 cards, half red, half black, and shuffle them. With the cards face down, turn over the top card. If it is black, add the next card, unseen, to the black stack; if it is red, add the next card, unseen, to the red stack. Add the original top card to the discard stack. Repeat these steps for all the cards in the pack. Now, randomly choose a number less than the size of the smaller of the black and red stacks, choose that many cards randomly from each of the two stacks, and swap those randomly-chosen cards from one stack to the other. The number of black cards in the black stack will equal the number of red cards in the red stack.

Your taks is to write a program to simulate the card trick and confirm that the number of black cards in the black stack equals the number of red cards in the red stack. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Sum Of Perfect Powers

August 31, 2018

I think this must be somebody’s homework:

Write a program to determine if a number x can be written as the sum of two perfect powers. This is, given x determine if there exist non-negative integers a, b, m and n such that am + bn = x where 1 ≤ x ≤ 106 and m > 1 and n > 1.

Your task is to write a program that determines if a number is a sum of two perfect powers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Array Of Integers

August 28, 2018

Today’s exercise is an interview question from Amazon:

You are given an array of integers, not necessarily unique. Your goal is to transform the array of integers so that the smallest number does not differ from the largest number by more than two times by removing integers from the array; thus, if x is the smallest element in the array, and y is the largest, then y ≤ 2x. You need only find the number of items to be removed from the array, not make a list of the items. As an example, given the array [4,5,3,8,3,7], you can remove the 2 smallest integers, leaving [4,5,7,8], so that 8 ≤ 2 × 4, or you can remove the 2 largest integers, leaving [3,4,5,6], so that 5 ≤ 2 × 3.

Your task is to write a function to determine how many items to remove from the array. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Data Structures Homework

August 24, 2018

Today’s exercise is from a programming student taking a Data Structures course, using Java.

Given a text file, print a list of the ten most common words in the file, along with their frequency of occurrence. You may not use a HashMap or ArrayList, but you may use regular expressions.

Your task is to write a program to find the ten most common words in an input file. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Mars Rover

August 21, 2018

Today’s exercise is a Microsoft interview question:

Write code using the commands below for two rovers to meet. Two rovers are dropped on Mars. Imagine Mars to be a straight infinite plane. When the rovers are dropped on Mars they are dropped with a parachute, so their initial position on Mars is on the parachute:

The only commands available are:

  1. Go left.
  2. Go right.
  3. No operation.
  4. If on parachute go to label.

A label points to a piece of code with a name where it is possible to transfer execution.

Using ONLY the commands above, write code to enable the rovers to meet.

Your task is to write a program to help the Mars rovers meet. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Matrix Search

August 17, 2018

Today’s exercise is a simple task in matrix manipulation. Given a matrix in which the rows are ordered but the columns or not, efficiently search for a specific item in the matrix. For instance, given the matrix

2 5 8
1 4 7
3 6 9

 

a search for 6 finds it in row 2 column 1, a search for 8 finds it in row 0 column 2, and a search for 0 fails.

Your task is to write a program that searches a matrix. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2