Programming Praxis

A multi-way merge takes two or more sorted input lists and creates a single output list that contains all the elements of the various input lists in sorted order.

If there are only two input lists, this is easy; run through the lists in order, at each step moving the smaller of the two elements at the heads of the lists to the output.

Things get harder if there are k input lists with k > 2. The easiest approach is to merge the first two lists, then merge that with the third list, and so on, performing k − 1 merges.

The “tournament” approach first merges input lists pairwise, forming a new set of k / 2 lists each twice as long as the originals, then recurs. Thus input lists 1 and 2 are merged, then 3 and 4 are merged, and so on, then merged list 1/2 is merged with merged list 3/4, and so on, until at the end only one merged list remains.

The best approach is to arrange all the input lists in a priority queue based on their smallest element. At each step the element at the head of the priority queue is written to the output, that element is removed from the list at the head of the priority queue, and the priority queue is reformed to put the new smallest element at its head.

Your task is to write the three versions of multi-way merge 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

Large portions of the internet failed a few days ago when a program called leftpad, which pads a string to a given length by adding spaces or other characters at the left of the string, was suddenly removed from its repository. The whole episode is sad, and brings nothing but shame on everyone involved (though everyone involved seems to think they acted properly throughout), and all of the web sites that broke were created by fools (you don’t rely on unknown third parties to maintain code critical to your application at some unknown place on the internet). You can read more about what happened at these links: good overview of what happened, Azer’s statement, NPM’s statement, and satire. The code that caused the problem is shown below:

module.exports = leftpad;

function leftpad (str, len, ch) {
  str = String(str);

  var i = -1;

  if (!ch && ch !== 0) ch = ' ';

  len = len - str.length;

  while (++i < len) {
    str = ch + str;
  }

  return str;
}

Your task is to write a proper version of leftpad; make sure yours operates in linear time instead of the quadratic time caused by the string concatenation in Azer’s code. 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’m back home after visiting my daughter in Houston. The beginning-programming forums that I track, and the email that I receive (I can’t imagine what goes through the head of someone who sends me an email and tells me I must do their programming homework for them) suggests that we are in the part of the semester where beginning programmers have to write their first program. So, today we have three programs of the type that beginners need to write for their homework:

1. Write a program that computes the sum of the integers in an array.
2. Write a program that reverses the elements of an array.
3. Write a program that sorts an array of integers, using insertion sort.

Your task is to assist our readers in completing their homework by writing the three programs 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

In the previous exercise we looked at a simple programming problem: determining the number of canoes needed for a group of boy scouts of varying weights, where each canoe could hold two boys. Today we extend that problem to the case of three boys or, more generally, n boys.

Your task is to modify your previous solution to handle the case of three boys; if you are ambitious, handle the case of n boys. There is no suggested solution, as I am on vacation visiting my daughter in Houston and don’t have time to write one. Feel free to post your solutions or discuss the exercise in the comments below.

We have today an interview question from Google:

A group of Boy Scouts is taking a trip by canoe and needs to determine how many canoes to rent. A canoe can hold one or two boys and a total of 150 pounds. Given a list of boys’ weights, how many canoes are needed?

Your task is to write a program that determines how may canoes are needed. 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

Two strings have a common prefix that consists of the longest prefix of the strings that is the same. For instance, the strings “I love cats” and “I love dogs” have the common prefix “I love ” (including a trailing space at the end of love, which doesn’t appear properly in some browsers).

Your task is to write a program that finds the common prefix of a list of strings (possibly more than two strings). 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 list of integers is sorted in “wave” order if alternate items are greater than their immediate neighbors (thus the other alternate items are less than their immediate neighbors). Thus, the list [4 1 7 5 6 2 3] is in wave order because 4 > 1, then 1 < 7, then 7 > 5, then 5 < 6, then 6 > 2, and finally 2 < 3. Note that the two alternate streams [4 7 6 3] and [1 5 2] need not themselves be sorted. It doesn’t matter if the first item is the high wave or the low trough between waves, though starting with a wave is traditional.

Your task is to write a program that takes a list of unique integers and sorts it into wave order. 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 powers of 3 are 3⁰ = 1, 3¹ = 3, 3² = 9, 3³ = 27, and so on.

Your task is to write a program that determines if a number is a power of 3; you must give more than one solution. 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