## 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.

## 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 byn. For instance, givenn= 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 total*n*. 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.

## Leonardo Numbers

### June 9, 2015

The Leonardo numbers A001595 are defined as L_{0} = 1, L_{1} = 1, L_{n} = L_{n−2} + L_{n−1} + 1; Dijkstra discusses Leonardo numbers in EWD797, and uses them in the analysis of smoothsort. Leonardo numbers are similar to Fibonacci numbers, and are related by the formula L_{n} = 2 F_{n+1} − 1.

Your task is to write a function that computes Leonardo 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.

## Most Living People

### June 5, 2015

We have today an exercise inspired by those “programming challenge” websites where you upload code and an automated judge tells if you pass or fail and how your time compares to other programmers. I haven’t seen this particular problem at one of those sites, but it feels like something they would do; this would also make a good interview question:

You are given a list of people’s lifespans with birth and death years; for instance, a person lived from 1924 to 1991. Some people have only a birth year because they are still living. You are to find the year in which the most people of a set of people were alive.

Input: A number

non a line by itself indicating the number of input cases, followed bynsets of lines containing a numbermindicatingthe number of people in this particular input case, followed bymlines indicating birth and, possibly, death years.Output: For each input case, the year (or years) in which the most people were alive.

Example: For the input:

2 3 1910 1948 1948 2011 1927 1995 3 1910 1948 1927 1995 1945You should produce the following output:

1948 1945 1946 1947 1948

Your task is to write the indicated 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.

## Heavy Hitters (The Britney Spears Algorithm)

### June 2, 2015

We’ve looked at algorithms to process a stream of data in previous exercises (streaming median, streaming knapsack, reservoir sampling), and we also looked at an algorithm that finds the most frequent items (the “heavy hitters”) in a file. Today’s exercise combines the two to find the most frequent items in a stream; it’s called the “Britney Spears” algorithm because it is the algorithm used to cull the most frequently-seen items in Twitter feeds and other social media, and the pop starlet always seems to be on that list.

There are two similar algorithms used to find the *n* most frequently-appearing items in a stream. The first, due to Jayadev Misra and David Gries, uses an initially-empty associative array of items and their associated counts and processes each item in the input stream according to the following algorithm:

if the new item is already in the array increment the associated count else if there are less thannitems in the array add the new item to the array with a count of 1 else for each item in the array decrement the associated count and remove any items whose count becomes zero

The other algorithm, called the “space-saving” algorithm, is due to Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. The first to parts of the algorithm are the same as the Misra-Gries algorithm. But, when a new item is found and there is no space to store it, the item already in the array that has the smallest associated count is replaced by the new item, and its count is incremented; thus, the counts are never reset, only the item is replaced.

With either algorithm, the array can be queried at any time to see the current list of most-frequent items in the array.

Your task is to implement the two heavy hitter algorithms. 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.