## Ordered Cartesian Coordinates

### April 21, 2015

Today’s exercise is a simple little interview question:

Generate the pairs of cartesian coordinates within a square bounded by (1,1) and (

n,n) ordered by their product in ascending order. For instance, whennis 3, the coordinates are (1,1), (1,2), (2,1), (1,3), (3,1), (2,2), (2,3), (3,2) and (3,3). Can you find a solution with time complexity better than O(n^{2})?

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.

## Euler’s Sum Of Powers Conjecture

### April 17, 2015

Fermat’s Last Theorem, which dates to the seventeenth century states that there are no solutions in integers to the equation *x ^{n}* +

*y*=

^{n}*z*for

^{n}*n*> 2; the Theorem was finally proved a few years ago by Andres Wiles. In the eighteenth century, Euler conjectured that for any

*n*> 2, it would take at least

*n*terms of the form

*x*to sum to an

_{i}^{n}*n*th power. That conjecture held until the age of computers, in 1967, when Lander and Parkin found the counter-example 27

^{5}+ 84

^{5}+ 110

^{5}+ 133

^{5}= 144

^{5}.

Your task is to write a program that finds counter-examples to Euler’s Conjecture. 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.

## Balanced Ternary Arithmetic

### April 14, 2015

We studied mixed-radix arithmetic in a previous exercise. In today’s exercise we look at a different kind of non-standard positional notation: balanced ternary, which is a base-3 number system that uses -1, 0 and 1 as its “trits” rather than 0, 1 and 2. For instance, the number -47 is written as (-1 1 1 -1 1) in balanced ternary, which is equivalent to -3^{4} + 3^{3} + 3^{2} – 3^{1} + 3^{0}. No separate sign is needed when using balanced notation; the sign of the leading trit is the sign of the whole number.

Arithmetic on balanced ternary numbers is done using the grade-school algorithms. Addition is done right-to-left with a carry; it is easy and fun to work out the plus-table. Subtraction is done by adding the negative, which can be computed by changing the sign of every trit. Multiplication works trit-by-trit through the multiplier, shifting at each trit.

Your task is to write functions that perform arithmetic on balanced ternary integers. 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.

## Pounds, Shillings, Pence

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

## Reluctant Search

### 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(2*n*), 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.

## Identifying Palindromes

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

## String Re-ordering

### March 27, 2015

Today’s exercise is a fun little interview question:

You are given a string

Othat specifies the desired ordering of letters in a target stringT. For example, given stringO= “eloh” the target stringT= “hello” would be re-ordered “elloh” and the target stringT= “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.

## Excellent Numbers

### March 24, 2015

Today’s exercise channels our inner Project Euler:

An

excellentnumbernhas an even number of digits and, if you split the number into the front halfaand the back halfb, thenb^{2}−a^{2}=n. For example, 3468 = 68^{2}− 34^{2}= 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.

## Matrix Transpose

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

## Common Elements Of Three Arrays

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