## Next To Last Item In A List

### July 28, 2015

Today’s exercise is a reminder about the importance of writing good test code. We have two tasks. The first is to extract the next-to-last item from a linked list; for instance, given the list (1 2 3 4 5) the next-to-last item is 4. The second task is to extract the nth-from-last item from a linked last; for instance, given the same list, the second-from-last item is 4. In addition to writing the two functions, you should write test code that exercises the functions thoroughly.

Your task is to write the two functions and test code. 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.

## One-Swappable Array

### July 24, 2015

Today’s exercise helps somebody with their homework:

Given an array of unique integers, determine if it is possible to sort the array by swapping two elements of the array. For instance, the array [1,2,6,4,5,3,7] can be sorted by swapping 3 and 6, but there is no way to sort the array [5,4,3,2,1] by swapping two of its elements. You may use O(

n) time, where the array hasnintegers, and constant additional space.

Your task is to write a program that determines if an array can be sorted with a single swap. 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.

## A Number Puzzle

### July 21, 2015

In last week’s exercise we had a word puzzle, so today’s exercise will be a number puzzle:

Find a 10-digit number, with all digits unique, such that the first

ndigits of the number are divisible byn. For instance, in the 3-digit number 345, the 1-digit prefix, 3, is divisible by 1, the 2-digit prefix, 34, is divisible by 2, and the 3-digit prefix, 345, is divisible by 3.

Your task is to write a program that finds a 10-digit number as defined above. 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.

## The Gas Station Problem

### July 17, 2015

Today’s exercise is a classic problem in computer science courses:

There is a truck driving clockwise on a circular route; the truck has a gas tank with infinite capacity, initially empty. Along the route are gas stations with varying amounts of gas available: you are given a list of gas stations with the amounts of gas they have available and the amounts of gas required to drive to the next gas station. You must find a gas station that, for a trip starting from that gas station, will be able to return to that gas station.

For instance, consider a route with eight gas stations having 15, 8, 2, 6, 18, 9, 21, and 30 gallons of gas; from each of those gas stations to the next requires 8, 6, 30, 9, 15, 21, 2, and 18 gallons of gas. Obviously, you can’t start your trip at the third gas station, with 2 gallons of gas, because getting to the next gas station requires 30 gallons of gas and you would run out of gas reaching it.

Your task is to write a program that determines a suitable starting point for the truck; your algorithm should be linear in the number of gas stations and require constant space. 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.

## Ordered Words

### July 14, 2015

An ordered word is one in which the letters in the word appear in alphabetic order; for instance, *dirt* and *knotty* are ordered words, *praxis* is not.

Your task is to write a program to find the longest ordered word in a dictionary. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Partitioning The Telephone Book

### July 10, 2015

The city where I live used to publish a telephone directory; the “white pages” were distributed to all telephone customers once a year. Now my city no longer prints the directory; it is available on the internet, or you can pay an operator to look up a telephone number for you.

But there are still cities that print telephone directories, and some of those cities are big enough that the directory must be partitioned into multiple volumes. Consider this distribution of the first letters of customer’s last names:

A B C D E F G H I J K L M N 0 P Q R S T U V W X Y Z 16 4 17 10 15 4 4 6 7 14 9 17 27 6 1 9 0 12 20 8 0 3 4 0 3 4

I’m not sure what the units are (probably tens of thousands of telephone customers), but the total is 220, and the telephone company has decided to print 4 volumes, so each should be about 55 units. One possible partitioning is A-D, E-J, K-O, P-Z, with counts of 47, 50, 60 and 63 units, differences of 8, 5, 5 and 8 from the ideal of 55, and a total difference of 26. Another partitioning is A-E, F-K, L-O, P-Z, with counts of 62, 44, 51, and 63 units, differences of 7, 11, 4 and 8, and a total difference of 30, which is worse. Before continuing, you might want to work out the optimal solution by hand, finding a minimum score of 18.

Your task is to write a program that determines the partitioning of the telephone book that minimizes the total difference. 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.

## Powerset

### July 7, 2015

Sets are ubiquitous in programming; we have discussed sets in several previous exercises. One of the operations that can be performed on a set is to compute its powerset, which is a set of all the subsets of the original set. For instance, the powerset of (1 2 3) is the set (() (1) (2) (3) (1 2) (1 3) (2 3) (1 2 3)) where neither the order of the subsets nor the order of the elements of the individual subsets matters.

Your task is to write a program that computes the powerset of a set. 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.

## Assign Y

### July 3, 2015

I’m sorry I missed Tuesday’s exercise; I’ve been very busy at work. Today’s exercise is an interview question of the kind I don’t like: it’s tricky, you either know the answer or you don’t, and it’s unlikely to be useful in any real programming situation:

You are give four integers

x(which must be either 0 or 1),y,aandb. Your first task is to assignatoyifx= 0, or assignbtoyifx= 1, without using any conditional operator, including the ternary operator. Your second task is to perform the same assignment without using any arithmetic operators.

Your task is to complete the two-part puzzle given above. 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.

## Find The Missing Number

### June 26, 2015

Today’s exercise is a tricky little homework problem:

Given a string consisting only of digits, find the missing number. For instance, given the string 596597598600601602 the missing number is 599. You may assume all the numbers are positive integers and the sequence increases by one at each number except the missing number. The numbers will have no more than five digits and the string will have no more than two hundred characters.

Your task is to write a program to find the missing number. 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.

## Closest Two-Sum To Zero

### June 23, 2015

Given a random array of integers, both positive and negative, find the pair with sum closest to zero. For instance, in the array [45, -29, -96, -7, -17, 72, -60], the two integers with sum closest to zero are -60 and 72.

Your task is to write a program that finds the two-sum closest to zero. 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.