Today’s exercise is an interview question from Google:

Given a list of words, find the maximum value of the product of the lengths of two words from the list, subject to the constraint that the two words cannot share any letters. For instance, given the words ABCW, BAZ, FOO, BAR, XTFN, and ABCDEF, the pair FOO BAR has a product of 9, the pair BAZ XFTN has a product of 12, and the pair ABCW XTFN has a product of 16, which is the maximum. Note that the pair ABCW ABCDEF doesn’t work because the two words share three letters.

Your task is to write a program to solve Google’s interview question. 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

Java Interview Question

April 5, 2016

We have an interview question today:

Input comes from a file containing pipe-delimited records with three fields: student id (a positive integer), course title (a string), and score (a positive integer). You may assume that any combination of student id and course is unique. Here’s an example input file:

22|Math|45
23|English|52
22|English|51
26|Math|72
23|Math|61
21|English|81

The file may have any number of records, and there is no limit on the number of unique courses. You should write a program to read the file and write a list of all courses in the file, combined with the score of the lowest-numbered student in the course. Thus, the correct output for the input shown above is:

Math 45
English 81

Your task is to write a program to solve the interview question; the original question specified a Java solution, but you are free to use any language. 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

SUM And XOR

April 1, 2016

I don’t know the origin of it, but today’s exercise must be either a homework problem or an interview question:

Assume there are two positive integers a and b that have sum s and XOR x. Given an s on the range [2, 1012] and x on the range [0, 1012], find a list of possible values of the ordered pairs (a, b). For instance, given s = 9 and x = 5, there are four possible pairs: (2, 7), (7, 2), (3, 6) and (6, 3).

Your task is to write a program that finds the pairs. 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

Multi-Way Merge

March 29, 2016

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

Leftpad

March 25, 2016

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

Three Homework Problems

March 22, 2016

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

Three Boys And A Canoe

March 15, 2016

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.

Two Boys And A Canoe

March 11, 2016

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

String Prefixes

March 8, 2016

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

Wave Sorting

March 4, 2016

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

Follow

Get every new post delivered to your Inbox.

Join 724 other followers