## Two Swaps

### October 23, 2015

Today we have one of those tricky interview questions that are easy once you know the answer:

You are given an array of three elements, in some random order. You must sort the array into increasing order, but may only use two swaps. How can you do it?

Your task is to write a program that sorts a three-element array with only two swaps. 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

## Longest Sequence Of Consecutive Odd Integers

### October 20, 2015

Today’s exercise is to find the longest sequence of consecutive odd integers that add to a given sum. For instance, given the target 160701, the three consecutive odd integers 53565, 53567 and 53569 sum to 160701, but the 391 consecutive odd integers from 21 to 801 also sum to 160701, and are the longest sequence of consecutive odd integers to do so, so they are the correct answer.

Your task is to write a program to find the longest sequence of consecutive odd integers that add to a given sum. 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

## Largest Possible Remainder

### October 16, 2015

The result of dividing a number n by a divisor d is a quotient q and a remainder r. Given a fixed n and a divisor d in the range 1 ≤ d < n, find the divisor that produces the largest possible remainder. For instance, given n = 20 and 1 ≤ d < 10, the largest remainder is 6 when the divisor d is 7.

Your task is to write a program that finds the largest possible remainder. 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

## Double Double Words

### October 13, 2015

Today’s task is to write a program that reads a file and reports any instances of doubled words, which is a useful program for anyone that does a lot of writing, as I do in this blog.

Your task is to write a program to find doubled 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

## Searching For Hypotenuses

### October 9, 2015

Hypotenusi?

Your task is to write a program that returns all the numbers less than some limit (think somewhere in the millions or tens of millions) that can be the hypotenuse of a right triangle with integer sides; strive for the minimum possible run time for your program. 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

## The Iron Bar

### October 6, 2015

Three physicists recently published an article showing that an inert iron bar is capable of making decisions. They attach the bar between two slot machines, repeatedly play one of the machines, pull the bar toward the machine when it winds and push the bar away from the machine when it loses. After enough plays, the iron bar can decide whether to play one machine or the other in hopes of a better payoff. Then they say “The most important implication that we wish to claim is that the proposed scheme will provide a new perspective for understanding the information-processing principles of certain lower forms of life.” The physicists also claim the iron bar can determine the probabilities of winning on both slot machines even though it only plays one. I’m not sure I understand the article, though I will happily agree that an inert iron bar has more intelligence than the spammers that regularly bedevil my blog.

The iron bar recalls an old-time method for calculating the median of a stream; for instance, consider finding the median of a list of a thousand occurrences of the numbers 1 to 100. Initialize the median to the first number in the list. Then, at each subsequent number, increase the median by 1 if the number is higher than the current median and decrease the median by 1 if the number is lower than the current median. At the end of the list, the approximate median calculated in this way ought not to significantly differ from the actual median. This is essentially the same calculation as that of the iron bar.

Your task is to write a program that calculates approximate medians in the manner of an iron bar. 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

## The Hot Hand

### October 2, 2015

A recent article in the Wall Street Journal discusses the “hot hand” paradox. Basketball players especially believe in the hot hand, when making a shot you can suddenly have a hot hand and make several more shots in a row. The Wall Street Journal proposes this experiment:

Toss a coin four times. Write down the percentage of heads on the flips coming immediately after heads. Repeat that process one million times. On average, what is that percentage?

The article claims that the correct percentage is 40%, not the 50% that you would expect from an unbiased coin, and that this is proof that the hot hand exists, even from such a random source as coin flips. If you’re interested, you can read the academic article that the Wall Street Journal account is based on, or see discussion of it at Hacker News.

Your task is to write a program to confirm the 40% figure. 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

## Making A Palindrome

### September 29, 2015

We have today a small exercise in string manipulation: Given an input string, either return a string containing the same characters but arranged to form a palindrome, or indicate that no such rearrangement is possible.

Your task is to write the program that creates a palindrome. 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

## Multiply Perfect Numbers

### September 25, 2015

As regular readers know, I greatly enjoy problems at the intersection of recreational mathematics and number theory. Today’s exercise is an example of that.

As was known to the ancient Greeks, perfect numbers such as 6 and 28 are equal to the sum of their aliquot divisors (those divisors less than the number itself); for instance, 6 = 1 + 2 + 3 and 28 = 1 + 2 + 4 + 7 + 14. Mathematicians refer to these as P2 numbers the sum of the divisors, including the number itself, is twice the number.

Multiply perfect numbers are numbers such that the sum of their divisors are some multiple of the number; perfect numbers have divisor-sums twice the number, triply perfect numbers P3 have divisor-sums thrice, the number, and so on.

Your task is to write a program that finds multiply perfect numbers. 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

## Three More Homework Problems

### September 22, 2015

I can tell from my statistics that people like the homework problem exercises, I suppose because they are short and provide simple drill. I can also tell, from reading some of the beginning-programmer message boards, that students seem to be quicker that they used to be to post their homework problems on-line rather than figuring out the solutions themselves, either because they are lazy or because their teachers aren’t providing sufficient help. So today we have three more homework problems:

1) Given a list of integers, return a list in which all the duplicates have been removed. For instance, given the input list [3, 2, 4, 2, 7, 3, 5, 1, 3] return the output list [3, 2, 4, 7, 5, 1].

2) Given two lists of integers, each sorted in ascending order, return a list of the integers common to the two lists; the output list must also be in ascending order. For instance, give the input lists [2, 3, 5, 5, 6, 7, 8, 9] and [1, 2, 4, 5, 5, 7] return the output list [2, 5, 5, 7].

3) Given a positive integer, determine if it is a perfect cube. For instance, the integer 125 is a perfect cube, 5*5*5, but the integer 121 is not.

Your task is to write programs that solve the three homework problems. 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