Programming Praxis

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

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

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

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