## Balanced Delimiters

### June 10, 2014

I heard today’s exercise as an interview question — you have five minutes to solve this task, while I watch — but it could equally be a homework problem:

Write a function to return true/false after looking at a string. Examples of strings that pass:

`{}, [], (), a(b)c, abc[d], a(b)c{d[e]}`

Examples of strings that don’t pass:

`{], (], a(b]c, abc[d}, a(b)c{d[e}]`

Your task is to write the function 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:

## Remove Singleton

### June 6, 2014

I’m not sure if this is a homework exercise or an interview questions, but it’s a fun little exercise to get your creative juices flowing on a Friday morning:

Given a string and a character, remove from the string all single occurrences of the character, while retaining all multiple consecutive instances of the character. For instance, given string “XabXXcdX”, removing singleton Xs leaves the string “abXXcd”.

Your task is to write the program given above; be sure to properly test your work. 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.

## Roman Numerals, Revisited

### June 3, 2014

We studied the problem of converting between integers and roman numerals in a previous exercise. We’ll do it again today because it’s a fun exercise, it appears frequently in lists of interview questions, we have an improved algorithm, and it lets us highlight a useful piece of the Standard Prelude.

Your task is to write functions that convert an integer to its equivalent in roman numerals and vice versa. 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.

## Subset Sum CLRS 35.5, Part 2

### May 30, 2014

In the previous exercise we implemented the subset sum algorithms of CLRS 35.5. In today’s exercise we solve exercise 35.5-5, which asks us to return the subsets as well as their sums. The algorithm is exactly the same. The difference is that set members are stored along with their partial sums.

Your task is to write a program that solves the subset sum problem 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.

## Subset Sum CLRS 35.5, Part 1

### May 27, 2014

We studied the subset sum problem — find the subset of a set of integers that sum to a given target — in two previous exercises; in both cases, we produced an exact answer, but took exponential time to do so. In today’s exercise, we will study a variant of the subset sum problem — find the subset of a set of integers that have the largest sum not exceeding a given target — that admits both exact and approximate answers; the exact answer runs in exponential time, though it is typically quite fast, but the approximate answer runs in linear time in the number of integers in the input set. Our solution is given by CLRS 35.5.

The exact solution uses two auxiliary functions. The function denoted by *L* + *x* adds *x* to each element of a list *L*. The function `merge-lists`

takes two sorted input lists and returns the merge of the two lists with duplicates removed. Then CLRS gives the algorithm as follows, where *S* is a sorted list of integers and *t* is the target:

EXACT-SUBSET-SUM(*S*,*t*)

1 *n* = |*S*|

2 *L*_{0} = ‹0›

3 **for** *i* = 1 **to** *n*

4 *L _{i}* = MERGE-LISTS(

*L*

_{i−1},

*L*

_{i−1}+

*x*)

5 remove from

*L*every element that is greater than

_{i}*t*

6

**return**the largest element in

*L*

_{n}The approximation algorithm adds a trimming step to the exact algorithm. The trimming step removes from the accumulating *L* list partial sums that are within a factor of 0 < δ < 1 such that any partial sum that is less than 1 + δ times its predecessor is removed. For instance, given *L* = ‹10, 11, 12, 15, 20, 21, 22, 23, 24, 29› and δ = 0.1, the trimmed *L*‘ = ‹10, 12, 15, 20, 23, 24›, where 11 is removed because it is within 10% of 10 and 21 and 22 are removed because they are within 10% of 20; `trim`

assumes that *L* = ‹*y*_{1}, *y*_{2},… *y*_{m}› is sorted:

TRIM(*L*,δ)

1 let *m* be the length of *L*

2 *L*‘ = ‹*y*_{1}›

3 *last* = *y*_{1}

4 **for** *i* = 2 **2** *m*

5 *if* *y*_{i} > *last* · (1 + δ) // *y*_{i} ≥ *last* because *L* is sorted

6 append *y*_{i} onto the end of *L*‘

7 *last* = *y*_{i}

8 **return** *L*‘

Then the `approx-subset-sum`

algorithm is the same as the `exact-subset-sum`

algorithm except that step *L _{i}* = TRIM(

*L*, ε/2

_{i}*n*) is inserted between steps 4 and 5, where the solution is within 0 < ε < 1 percent of the desired target.

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

## Aliquot Sequences

### May 23, 2014

We studied amicable chains in the previous exercise. Today we look at aliquot sequences, which are closely related to amicable chains. The aliquot sequence of *n* is the sequence that starts with *n* as its zero’th element and *s*(*k*−1) as its *k*‘th element, where *s* is the sum-of-divisors function of the previous exercise. For instance, the aliquot sequence of 10 is 10, 8, 7, 1, 0 because *s*(10) = 1 + 2 + 5 = 8, *s*(8) = 1 + 2 + 4 = 7, *s*(7) = 1, and *s*(1) = 0.

In 1888 Eugène Charles Catalan conjectured that all aliquot sequences end either at a prime number (the aliquot sequence for 10 shown above is usually considered to end at the prime 7, since once a member of an aliquot sequence is prime, the next two steps are 1 and 0) or at an amicable chain (either a perfect number which is an amicable chain of length 1, or an amicable pair which is an amicable chain of length 2, or a longer amicable chain). For instance, the aliquot sequence for 95 is 95, 25, 6, 6, …, where 6 is a perfect number. All numbers for which the entire aliquot sequence has been determined fit the conjecture, but there are many numbers for which the entire aliquot sequence is not known, of which the smallest is 276.

Your task is to write a function that computes aliquot sequences; it should return either the prime number or the amicable chain (smallest number first) that terminates the sequence. 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.

## Amicable Chains

### May 20, 2014

A perfect number is equal to the sum of its proper divisors; for instance, the divisors of 28 are 1, 2, 4, 7, and 14, and 1 + 2 + 4 + 7 + 14 = 28, so 28 is a perfect number. Two numbers m and n form an amicable pair if the sum of the divisors of m equals n and the sum of the divisors of n equals m; for instance, 220 has divisors 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 which sum to 284, and 284 has divisors 1, 2, 4, 71, 142 which sum to 220, so 220 and 284 form an amicable pair. An amicable chain is a list of numbers, each the sum of the divisors of the previous number, that loops so that the sum of the divisors of the last number in the list is the first number in the list; for instance, the numbers 12496, 14288, 15472, 14536, and 14264 form an amicable chain of length 5, since sum-div(12496) = 14288, sum-div(14288) = 15472, sum-div(15472) = 14536, sum-div(14536) = 14264, and sum-div(14264) = 12496. We discussed amicable numbers in a previous exercise.

Your task is to write programs to locate perfect numbers, amicable numbers and amicable chains; use it to find all of those objects for which all of their elements are less than a million. 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.

## Rolling Code

### May 16, 2014

In the early days of automatic garage door openers, all openers shared a single code, so that every garage door opener worked with every garage door; you could open your neighbor’s garage door and walk into his garage whenever you wanted to. The next generation of garage door openers had 8 DIP switches, and thus 256 codes, which solved the problem of casually preventing your neighbor from opening your garage but was hardly a deterrent to thieves.

Nowadays garage door openers and car lock keychain fobs use rolling codes, sometimes called hopping codes, for security. Each fob has a unique serial number; each garage door opener or car lock is programmed to recognize only signals from specific fobs. The signals themselves are randomized and encrypted by the rolling code.

It works like this: Each time a button on the fob is pressed, the requested signal is sent to the receiver along with the serial number of the fob and the rolling code, which is an encrypted random number. The receiver ensures the fob has a recognized serial number, decrypts the rolling code, compares it to the receiver’s synchronized random number generator, and performs the requested action if everything agrees or denies the requested action if it doesn’t.

It’s possible for the fob to send a signal when it is out of range of the receiver. To allow that, the receiver checks the next 256 numbers in the random sequence, instead of just one number, and accepts the signal if any of the 256 numbers agree. Additionally, in case the fob sends more than 256 consecutive signals out of range, the receiver performs the requested action and resynchronizes its copy of the random number sequence if the fob sends two successive numbers from the random sequence.

Your task is to write programs that simulate the actions of the fob and the receiver. 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.

## Three Interview Questions

### May 13, 2014

One of the sites that I watch from time to time is Career Cup, which publishes coding questions that have been asked in actual job interviews. These questions came through this morning:

1) Consider a sorted singly-linked list having the following nodes: 10 -> 30 -> 50 -> 70 -> NULL. You are given a pointer to node 50 and a new node having the value 40. Can you insert node 40 correctly in the list maintaining the ascending order?

2) Given a linked list 5 -> 4 -> 3 -> 2 -> 1 produce a linked list 4 -> 2 -> 0 -> 2 -> 1 by subtracting the last node of the list from the first, the next-to-last node from the second, and so on, stopping at the midpoint of the list.

3) Write a program to output the number of consecutive trailing zeros in the factorial of a number. For example, if the number is 5, then 5! = 120, and there is one trailing zero.

Your task is to write programs to answer the three interview questions posed 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.

## Cluster

### May 9, 2014

Clustering is the process of collecting in groups all of the items from an input collection that share some common feature; for instance, the `GROUP BY`

operator of SQL performs clustering. We will define `cluster(proc, lt?, lst)`

as a function that takes an input list and returns a list of lists; `proc`

computes a signature of each item in the input list, and each sub-list in the output list contains all those elements of the input list with identical signatures, with sub-lists in increasing order of signature according to `lt?`

. The type of `cluster`

is (α → β) × (β × β → `boolean`

) × (`list`

α) → (`list`

(`list`

α)).

Your task is to write the function `cluster`

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