Uncouple

June 15, 2018

Today’s exercise is from a programming textbook:

A couple is two adjacent identical items in a sequence. You are to remove all couples, then process the list recursively to remove any additional couples formed by the removal of the original couples. For instance, given the list {red blue green green blue red yellow}, first remove the green couple, leaving {red blue blue red yellow}, then remove the blue couple, leaving {red red yellow}, and finally remove the red couple, leaving {yellow}.

Your task is to write a program to uncouple a list. 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.

Advertisements

Pages: 1 2

Multiples Of 5

June 12, 2018

We have today an interview question from Amazon:

Write a program to determine if an integer is a multiple of 5 in O(log n) time complexity. You cannot use the division or modulus operators.

Your task is to solve the Amazon 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

Overlap

June 8, 2018

We have today a simple exercise to spice up your Friday lunch hour:

A range of integers is specified by its endpoints; for instance, the range [19, 25] includes the values 19, 20, 21, 22, 23, 24, and 25. The overlap of two ranges is those values that appear in both; for instance, given the ranges [19, 25] and [22, 30], the overlap is the range [22, 25]. The ranges [19, 25] and [12, 17] have no overlap.

Your task is to write a program that takes the endpoints of two ranges and returns their overlap, or reports that they have no overlap. 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

Estimating Pi

June 5, 2018

There’s a nice piece of math (it was either on NumberPhile or 3brown1blue, but I can’t find it again, and in any event it is a well-known equality) that says if you pick two positive integers at random, the odds of them having no common divisors are 6 ÷ π² ≈ 0.61. Let’s test that.

Your task is to estimate π using the formula shown 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

Exercise 7

June 1, 2018

This must be somebody’s homework:

You are given an input file containing lines with three pipe-separated fields; the first field is a student number (a positive integer), the second field is a class name (a string), and the third field is the grade the student received for the class (a non-negative integer, no greater than 100):

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

You are to output a list of class names along with the grade earned by the lowest-numbers student in each class. For instance, given the above data, the output for Data Structures is 45 corresponding to student 22 (with student number lower than 23 or 26, who also took Data Structures) and the output for English is 81 corresponding to student 21 (with student number lower than 22 or 23, who also took English).

Your task is to write a program to produce the requested output. 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

Blockchain

May 29, 2018

In the previous exercise we studied a simple cryptographic hash. Today we will use that hash to write an equally-simple blockchain, which is the algorithm underneath Bitcoin and other cryptocurrencies.

A blockchain is a publicly-readable database in which data items are stored in blocks in an immutable, verifiable chain. The database admits two operations: adjoin, to add a new data item to the database, and validate, to verify that the database is complete and incorrupt. There is no delete operation; once a datum is added to the database, it can never be removed. There is no update operation; once a datum is added to the database, it can never be modified. And there is no sort operation; once a datum is added to the database, it can never be moved within the chain.

In our implementation, each block in the chain contains four fields: an index number, which starts from zero and is incremented each time a new datum is added; a datum, which can be anything (for simplicity, we restrict the data to strings); the previous hash number, and the current hash number, which we will discuss below.

The adjoin operation takes a blockchain and a datum and returns a new blockchain, which is a linked list of blocks; the first block in a blockchain has index 0, datum “Genesis Block”, and previous hash number 0. The current hash number is a Pearson hash of the concatenated block number, the datum, and the previous hash number. To adjoin a new block, compute the current hash number, allocate a block, attach it to the head of the blockchain, and return the new blockchain.

The validate operation recalculates the current hash number at each block in the chain. If any is incorrect, it halts and reports the blockchain is corrupt. Otherwise, if it reaches the genesis block without finding an error, it reports the blockchain is valid.

Your task is to write a program that implements the simple blockchain 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

Pearson Hashing

May 25, 2018

Cryptographic hashes, also called message digests, are ubiquitous in modern cryptography — Brce Schneier calls them “the workhorses of modern cryptography” — used among other things in digital signatures, message authentication codes, as fingerprints to detect duplicate data, and as checksums to detect data corruption. Today we look at a simple example of a hash function, not suitable for cryptography, but useful for non-cryptographic purposes.

Peter Pearson describes a hash function based on a permutation table Tof the numbers 0 inclusive to 256 exclusive. Starting from an initial hash of 0, each byte of the message is accessed in order, added to the current hash mod 256, then the hash is replaced by the value in the permutation table corresponding to that sum. In some implementations, including Pearson’s original, the two bytes are XOR’ed rather than added mod 256.

If eight bits isn’t enough, Pearson gives a simple algorithm for extending the algorithm to sixteen bits. First, compute the normal 8-bit hash. Then, add 1 (mod 256) to the first character of the string, and compute the normal 8-bit hash of the modified string; since a modification to a single bit provides a large change in the hash value, the two hashes will be independent of each other. Finally, concatenate the two hashes. Pearson doesn’t mention it, but this scheme can be extended to any multiple of eight bits.

Your task is to write a program that computes the 8-bit and 16-bit Pearson hashes of an input string, given a suitable permutation table. 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

Floyd’s Triangle

May 22, 2018

I noticed the other day this list of the Top 75 Programming Interview Questions. I’m not sure of the origin of the list, and it does have a Java feel to it, but I was happy to see that we’ve covered almost all the questions on the list. One of the questions we missed is Number 57:

Write a program to print Floyd’s Triangle.

I wasn’t familiar with Floyd’s Triangle, so I had to peek at the solution. Floyd’s Triangle lists the numbers in order, in lines of increasing length, so a Floyd’s Triangle of size 5 looks like this:

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15

Your task is to write two programs that print Floyd’s Triangle; you must write two different programs that use two fundamentally different methods. 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

Billing Period

May 18, 2018

I’m not sure of the origin of today’s exercise, but given the contrived nature of the calculation, I suspect it’s a programming exercise for beginning programming students:

Our merchants receive “weekly” invoices, following these rules:

  • Each Saturday marks the beginning of a new billing period.
  • Each 1st of a month marks the begining of a new billing period.
  • Within a year, billing periods are numbered consecutively, starting with billing period 1 on January 1st.

Thus, a billing period can be referenced by a year and period number.

Your task is to write a program that calculates the billing period for a given date. 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 Embedded Numbers

May 15, 2018

It’s mid-May, so at most universities the semester has ended and it is safe for me to solve some of the exercises that students sent to me over the last few months. Here’s a fun little one:

Given a string containing embedded numbers, find the sum of the embedded numbers. For instance, given the string “11aa22bb33cc44”, the desired sum is 11 + 22 + 33 + 44 = 110. You may not use regular expressions.

Although the problem statement doesn’t say so, you may assume that the numbers of interest are non-negative integers. Thus, the purpose of the exercise is for students to iterate through a string, identify the digits in the string, and manipulate them numerically.

Your task is to write a program that sums the numbers embedded in a string. 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