Binary Search

April 29, 2016

I goofed.

While writing a program (it may appear in a future exercise) I needed to search a sorted array for a target value. I should have copied an existing binary search, but instead I wrote my own, since I’m a good programmer and can certainly write a simple function like that. You won’t have any trouble guessing what happened next.

Your task is to write a binary search function; do it yourself, without looking at any library implementations or searching the internet. You might also want to write a test script to give you confidence in your function. 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 isn’t really an exercise but an astonishing integer formula for computing the nth Fibonacci number; here it is in Python:

def fib(n):
    return (4 << n*(3+n)) // ((4 << 2*n) − (2 << n) − 1) & ((2 << n) − 1)

You can see an explanation here and discussion here.

Your task is to translate the program to your favorite 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

GCD Sum

April 22, 2016

Today’s exercise is inspired by A018804: Find the sum of the greatest common divisors gcd(k, n) for 1 ≤ kn.

Your task is to write a function that finds the sum of the greatest common divisors. 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 3

Interview Timing

April 19, 2016

I came across an interesting interview question recently. I’ll tell you the question shortly. What made it interesting was that the same question was given to all candidates, and they were timed in getting a solution; candidates with shorter times were given higher scores than candidates with longer times.

Your task is to write the requested program, which you can access HERE after you are set up for timing.

Pages: 1 2 3

Today’s exercise solves somebody’s homework problem — but not too much, since he had to write his program in Java:

Find the two smallest ten-digit pandigital numbers (numbers that contain all the digits from 0 through 9) that are divisible by the numbers 1 through 9. Then find the two largest pandigital numbers that are divisible by the numbers 1 through 9.

Your task is to solve the homework problem. 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

Titlecase

April 12, 2016

A string is titlecased when the first letter of each word is capitalized and the remaining letters are lower case. For instance, the string “programming PRAXIS” becomes “Programming Praxis” when titlecased.

Your task is to write a function that takes a string and returns it in titlecase. 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 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

Follow

Get every new post delivered to your Inbox.

Join 709 other followers