RC40

March 7, 2017

We examined the Solitaire Cipher of Bruce Schneier in a previous exercise. In an article on his blog, Ted Unangst complains that the cipher is too complicated for manual use, and proposes instead RC40, a variant of RC4 that uses only 40 characters instead of 256. Unangst’s alphabet is the 26 lower-case letters, the ten digits 0 through 9, the characters period, question mark, and space, and a “shift” character that gives an upper-case version of those 39 characters; two consecutive shift characters enter or leave caps-lock mode. Otherwise, RC40 is exactly the same as RC4, except that all references to 256 are changed to 40.

Your task is to write a program that enciphers and deciphers strings based on the RC40 cipher; use that program to decipher the string “5cxaxlfrfhy6kh38fbplm0mDko58xs.l9Hkz8” with key “tedunangst”. 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 story exploded across the intertubes a few days ago: A software engineer trying to enter the United States on a work visa was asked to prove his occupation by writing a program for the Customs and Border Protection agent:

Write a function to check if a Binary Search Tree is balanced.

Let’s help him.

Your task is to write a function to check if a binary search tree is balanced. 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

A Fun Little Task

February 28, 2017

Today’s exercise is a fun little task:

Given two strings a and b, with a no longer than b, determine if there is any permutation of a that appears in b. For instance, a permutation of string xyz appears starting at the fourth character (counting from zero) of string afdgzyxksldfm.

Your task is to write a program to determine is any permutation of a string is a substring of another string. 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

A binary search tree is a binary tree in which all nodes in the left subtree are less than the current node and all nodes in the right subtree are greater than the current node. Items arrive in random order, are inserted into the binary search tree, and an in-order traversal produces the items in ascending order.

Your task is to write a program that finds the nth smallest item in a binary search tree, without enumerating all of the items in the tree. 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

It Was A Beautiful Weekend

February 21, 2017

It was a beautiful three-day weekend here in St Louis, with temperatures in the 70s all three days. It’s supposed to be winter here, with high temperatures around 50 and lows in the 30s, or colder, but the weatherman goofed and gave us beautiful weather.

I took the opportunity to do things other than write an exercise. I apologize. I’ll be back with another exercise on Friday. Probably. The beautiful weather is supposed to last another few days. . . .

In the meantime, pick an exercise you have done yet, and solve it. Or, enjoy the weather where you are.

Zeroing A Matrix

February 17, 2017

Today’s exercise is a simple interview question from ADP:

Given a two-dimensional matrix of integers, for any cell that initially contains a zero, change all elements of that cell’s row and column to zero.

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.

Pages: 1 2

Stock Prices

February 14, 2017

Today’s exercise is a classic of both algorithm classes and corporate interviews:

Given a list of daily stock prices for a month, find the day on which you can buy a stock and the day on which you can sell the stock that gives the maximum gain.

Your task is to write a program that finds the optimal starting and ending dates for stock purchase and sale. 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

In the comments to the previous exercise, reader Kevin gave a beautiful solution in Haskell; it sorts the input items, groups them into sub-lists of like items, transposes the rows and columns of the sub-lists, and concatenates the sub-lists back into a single list:

import Data.List
sortwodup :: (Ord a) => [a] -> [a]
sortwodup = concat . transpose . group . sort

Here’s the pipeline of functions applied to the sample input (2 9 1 5 1 4 9 7 2 1 4):

Sort converts the input list to (1 1 1 2 2 4 4 5 7 9 9).

Group converts the output of sort to a list of sub-lists: ((1 1 1) (2 2) (4 4) (5) (7) (9 9)).

Transpose swaps rows and columns, ignoring missing items, like this:

    1 1 1        1 2 4 5 7 9
    2 2          1 2 4 9
    4 4          1
    5
    7
    9 9

Thus, the output from transpose is ((1 2 4 5 7 9) (1 2 4 9) (1)). Finally, concatenate removes the sub-list structure, producing (1 2 4 5 7 9 1 2 4 9 1).

Your task is to write a Haskell-style program to solve the problem of sorting a list, moving duplicates to the end. 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

Sorting Without Duplicates

February 7, 2017

I think this is somebody’s homework problem:

Given an array of n integers, partition the array into sub-arrays, each in ascending order, and each without duplicates. For instance, given the array [2, 9, 1, 5, 1, 4, 9, 7, 2, 1, 4], the desired output is the array [1, 2, 4, 5, 7, 9,   1, 2, 4, 9,   1], where the intent is to have as many sub-arrays as the maximum frequency of any element, each sub-array as long as possible before starting the next sub-array of duplicates. If possible, perform the work in-place, in time either O(n) or O(n log n).

Your task is to solve the sorting problem 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.

Pages: 1 2

Jump!

February 3, 2017

Jump is a simple one-player game:

You are initially at the first cell of an array of cells containing non-negative integers; at each step you can jump ahead in the array as far as the integer at the current cell, or any smaller number of cells. You win if there is a path that allows you to jump from one cell to another, eventually jumping past the end of the array, otherwise you lose. For instance, if the array contains the integers [2, 0, 3, 5, 0, 0, 3, 0, 0, 3, 1, 0], you can win by jumping from 2, to 3, to 5, to 3, to 3, then past the end of the array.

Your task is to write a program that determines if a given game is winnable. 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