April 10, 2015
Today’s exercise won’t ask you to write code. Let me tell you why.
I bought a new printer to replace my old printer that had failed. Both the salesman at Micro Center and the printer manufacturer’s sales rep, who was in the store that day, assured me that the printer would work with my Debian Linux system, and the manufacturer’s sales rep even gave me the web page where I could download the driver. I bought the printer, took it home, and installed the driver.
It didn’t work. My computer would no longer boot. I took computer and printer to the Knowledge Bar at Micro Center, but they don’t have sufficient Linux experience to figure out what’s wrong. After a few days, I resigned myself to re-installing the operating system.
That’s when I found out what had happened. At the point where the Linux installer asks you to specify the partition table, it told me that I had an invalid partition table and asked me to fix it, manually, before proceeding with the installation. Somehow, installing a printer driver corrupted the partition table. I won’t tell you the name of the printer manufacturer that was stupid enough to manage that trick, but it’s a big name that you would certainly recognize. Needless to say, I will be returning the printer and buying a different printer from a different manufacturer.
But before I do that, I have to fix my partition table, re-install my operating system, and restore my data from backups. As I write this on Thursday afternoon, I’m partway through that process, but I have already verified that I have a list of all installed software and that my file backup is readable.
Your task is to make sure that your backup and restore procedures are effective; if they aren’t, fix them. You should at least perform a single-file restore to demonstrate that your backup and restore procedure has at least a minimal chance of working when you need it. It looks like I will end up okay, but not without a lot of worry and a few choice words directed at a printer manufacturer that ought to know better.
April 7, 2015
Mixed-radix number systems have a base, or radix, that varies at each position. For instance, the old-style British pounds, shillings and pence form a mixed-radix system where there are twelve pence in a shilling and twenty shillings in a pound, and calendars form a mixed-radix system where there are sixty seconds in a minute, sixty minutes in an hour, twenty-four hours in a day, and seven days in a week.
Your task is to write a program that accepts a definition of a mixed-radix system — for instance, (7 24 60 60) for the calendar mentioned above — and performs addition and subtraction of numbers written in that system. 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.
April 3, 2015
Wednesday was April Fools’ Day, and I was feeling frisky, so I implemented the reluctant search algorithm from Pessimal Algorithms and Simplexity Analysis by Andrei Broder and Jorge Stolfi. Their algorithm takes time O(2n), which is worse than the naive brute force O(n), to find the index of a target x in a sorted array. We looked at a different algorithm that paper in a previous exercise. I’ll leave it to you to fetch the paper and enjoy the sincerity of the authors’ pessimality.
Your task is to implement the reluctant search algorithm. 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.
March 31, 2015
Today’s task sounds simple but leads to a little bit of complexity.
Given an array, determine if it is a palindrome. Given a linked list, determine if it is a palindrome. Make both tests as efficient, in both time and space, as possible.
Your task is to write two programs to identify palindromes. 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.
March 27, 2015
Today’s exercise is a fun little interview question:
You are given a string O that specifies the desired ordering of letters in a target string T. For example, given string O = “eloh” the target string T = “hello” would be re-ordered “elloh” and the target string T = “help” would be re-ordered “pelh” (letters not in the order string are moved to the beginning of the output in some unspecified order).
Your task is to write a program that produces the requested string re-ordering. 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.
March 24, 2015
Today’s exercise channels our inner Project Euler:
An excellent number n has an even number of digits and, if you split the number into the front half a and the back half b, then b 2 − a 2 = n. For example, 3468 = 682 − 342 = 4624 − 1156 = 3468, so 3468 is an excellent number. The only two-digit excellent number is 48 and the only four-digit excellent number is 3468. There are eight six-digit excellent numbers, 140400, 190476, 216513, 300625, 334668, 416768, 484848, and 530901, and their sum is 2615199. What is the sum of the 10-digit excellent numbers?
Your task is to compute the sum of the 10-digit excellent numbers; in the spirit of Project Euler, your solution should take no more than one minute of computation time. 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.
March 20, 2015
Transposing a matrix turns rows into columns and columns into rows; for instance the transpose of the matrix below left is the matrix below right:
11 12 13 14 11 21 31
21 22 23 24 12 22 32
31 32 33 34 13 23 33
14 24 34
That’s easy enough to do when everything fits in memory, but when the matrix is stored in a file and is too big to fit in memory, things get rather harder.
Your task is to write a program that transposes a matrix to large to fit in memory. 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.
March 17, 2015
We have another interview question today. There are several different ways to approach this task, so it makes for an interesting exercise:
Given three arrays of integers in non-decreasing order, find all integers common to all three arrays. For instance, given arrays [1,5,10,20,40,80], [6,7,10,20,80,100] and [3,4,15,20,30,70,80,120] the two common integers are 20 and 80. If an integer appears multiple times in each of the arrays, it should appear multiple times in the output, so with input arrays [1,5,5,5], [3,4,5,5,10] and [5,5,10,20] the correct output is [5,5].
Your task is to write a program to solve the 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.
March 13, 2015
In today’s exercise we write a function that determines if a number n can be written as pk with p prime and k > 0 an integer. We looked at this function in a previous exercise where we tested each prime exponent up to the base-2 logarithm of n.
Henri Cohen describes a better way to make that determination in Algorithm 1.7.5 of his book A Course in Computational Algebraic Number Theory. He exploits Fermat’s Little Theorem and the witness to the compositeness of n that is found by the Miller-Rabin primality tester. Cohen proves that if a is a witness to the compositeness of n, in the sense of the Miller-Rabin test, then gcd(an − a, n) is a non-trivial divisor of n (that is, it is between 1 and n).
Your task is to write a program that determines if a number can be written as a prime power and, if so, returns both the prime and the exponent. 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.
March 10, 2015
Count All Matches
Today’s exercise is an interview question from Google, as reported at Career Cup:
Given two strings, find the number of times the first string occurs in the second, whether continuous or discontinuous. For instance, the string CAT appears in the string CATAPULT three times, as CATapult, CAtapulT, and CatApulT.