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, a and b. Your first task is to assign a to y if x = 0, or assign b to y if x = 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.
Nines And Zeros
June 19, 2015
We have today an interview question that so stumped an interviewee that he asked for help on the internet:
Given an integer n, find the smallest number consisting only of the digits zero and nine that is divisible by n. For instance, given n = 23, the smallest number consisting only of the digits zero and nine that is divisible by 23 is 990909.
Your task is to write a program that finds the number described 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.
Karate Chop
June 16, 2015
Dave Thomas has a Code Kata in which he challenges programmers to write five different implementations of binary search (also known as the “binary chop” or, in Thomas’ kata-lingo, the “karate chop”). He doesn’t define “different” except to use phrases such as “totally different technique” and “totally unique implementations” and to suggest the traditional iterative approach, a recursive approach, a functional style passing array slices around, and so on.
Your task is to write five different implementations of binary search, returning the index of a target value in a sorted array of integers, or -1 if the target is not present. 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.
Random Total
June 12, 2015
Our task today is to generate a set of k random positive integers that add up to a given totaln. For instance, if we want 4 random numbers that add up to 9, there are six possible results (not counting permutations of them): {6,1,1,1}, {5,2,1,1}, {4,3,1,1}, {4,2,2,1}, {3,3,2,1} and {3,2,2,2}.
An easy way to do that is to choose k−1 random numbers r with 0 ≤ r < n−k, sort them, calculate the differences between them, calculate the difference between 0 and the smallest, calculate the difference between n−k and the largest, shuffle the differences, and add 1 to each; subtracting k and adding 1 ensures that all the numbers are positive. For our example above, choose three random non-negative integers less than n−k = 5, say 1, 3, and 3, the differences are 1, 2, 0 and 2, and the four resulting numbers are 2, 3, 1 and 3, which form the fifth of the six sets shown above.
Your task is to write the program that generates a random set of integers that adds to a given total, as described 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.
Programming Praxis 