Trailing Comments

February 23, 2021

Today’s exercise is based on a blog entry that Reddit pointed me to. Sean is trying to write a program that finds lines of code in his Python programs that have trailing comments at the ends of lines, which he considers bad style. His naive program improperly flagged a line as containing a trailing comment when the comment marker is embedded in a quoted string:

x = "# This is fine"
"This \# is fine too"
x = "" # This is not

Sean gets a little bit sidetracked in his blog entry, and never quite solves the problem; I’m not convinced the code he writes is correct (though he seems to think it is), and I’m also not convinced that trailing comments are a bad thing. Nevertheless, the task makes an interesting exercise, especially when we also handle quoted escape sequences.

Your task is to write a program that identifies lines of code with trailing comments. 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

Local Maxima

February 16, 2021

A local maximum of a list of integers is an element of the list at which the adjacent list elements are either less than or equal to the current element; for instance, in the input list (1 2 1 2 3 4 3 2 3 2 1) there are three local maxima, one at the first 2, one at the 4, and one and the last 3. The elements at either end of a list should be considered as greater than the boundary. Only one maximum should be reported for a plateau (consecutive equal maxima).

Your task is to write a program that finds the local maxima of a list of 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.

Pages: 1 2

Run Length Encoding

February 9, 2021

Alexey Grigorev says:

Most candidates cannot solve this interview problem:

Input: “aaaabbbcca”

Output: [(“a”,4), (“b”,3), (“c”,2), (“a”,1)]

Write a function that converts the input to the output. I ask it in the screening inverview and give it 25 minutes. How would you solve it?

Your task is to write the requested 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

Tax Brackets

January 26, 2021

My W-2 form came in the mail a few days ago, so a task about taxes is appropriate. Given the following tax brackets:

income cap    tax rate
  $ 10,000        0%
  $ 30,000       10%
  $100,000       25%
    more         40%

Calculate the amount of tax given an amount of income. The tax brackets work like this: If your income is less than $10,000, your tax is $0. If your income is between $10,000 and $30,000, your tax is 10% of your income in excess of $10,000. If your income is between $30,000 and $100,000, your tax is 10% of the $20,000 of income between $10,000 and $30,000 (or $2,000) plus 25% of your income over $30,000. If your income is over $100,000, your tax is 10% of the $20,000 of income between $10,000 and $30,000 (or $2,000), plus 25% of your income between $30,000 and $100,000 (or $17,500), plus 40% of your income over $100,000 (ouch!).

For example, if your income is $123,456, your tax is $2,000 plus $17,500 plus 40% of $23,456 (or $9,382.40), a total tax of $28,882.40, or 23.4% of your income.

Your task is to write a program that calculates the amount of tax due for a given amount of income. 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

Stalin Sort

January 19, 2021

Stalin Sort is a single-pass sort that operates in O(1) space and O(n) time. Iterate down the list of elements checking if they are in order. Any element which is out of order is sent to the gulag (eliminated from the list). At the end you have a sorted list, though it may not be a permutation of the original list. As an example, the list (1 2 5 3 5 7) is Stalin-sorted as (1 2 5 5 7); the 3 is dropped because it is less than the 5 that it follows.

Your task is to write a program that implements Stalin sort. 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

Animal.txt

January 12, 2021

Today’s task is from a beginning programmer, who starts with an input file called animal.txt:

There once was a Dog

Wednesday he ate Apples 
Thursday he ate Apples
Friday he ate Apples
Saturday he ate carrots

There once was a Bear

Tuesday he ate carrots
Wednesday he ate carrots
Thursday he ate chicken

He wants to create this output:

Food: Apples Animals who ate it: 1
=======
Dog

Food: Carrots Animals who ate it: 2
========
Bear
Dog

Food: Chicken Animals who ate it: 1
========
Bear

He gave a complicated awk solution that didn’t work; it produced duplicate lines of output in those cases
where the same animal ate the same food on multiple days.

Your task is to write a program to produces the desired transformation form input to 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

Two Simple Tasks

January 5, 2021

Happy New Year! May 2021 be a better year than 2020.

We have two simple tasks today:

First: Write a program that prints the sequence 1, 5, 10, 50, 100, … up to a given limit.

Second: Write a program that finds all three-digit numbers n such that n/11 equals the sum of the squares of the three digits.

Your task is to write programs that solve the two tasks given 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

Rhyming Sort

December 8, 2020

I recently found on the internet a delightful paper by Kenneth Ward Church called Unix™ for Poets that provides an introduction to the Unix command line utilities for text processing. The paper must be ancient, because it gives the author’s email address at research.att.com, but I’ve never seen it before. One of the examples in the paper is rhyming sort, in which words are sorted from the right rather than the left; the left column below is in normal alphabetical order, the right column is in rhyming order:

    falsely         freely
    fly             sorely
    freely          surely
    sorely          falsely
    surely          fly

Church says:

“freely” comes before “sorely” because “yleerf” (“freely” spelled backwards) comes before “yleros” (“sorely” spelled backwards) in lexicographic order. Rhyming dictionaries are often used to help poets (and linguists who are interested in morphology).

Church solved the problem with a rev | sort | rev pipeline.

Your task is to sort a file containing one word per line into rhyming 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

Sales Commission

November 17, 2020

Today’s exercise is simple drill for beginning programmers; it was inspired by a student asking on a beginning programmer’s platform for someone to do his homework for him. The requested answer was in C++, and it was a few weeks ago, so I don’t feel too bad posting a Scheme solution:

Write a program that inputs each employee’s sales, then computes and prints the employee’s commission according to the formula $200 plus 10% of sales. Stop the input using a sentinel value. At the end of the input, display a one-dimensional array containing all the commission amounts, and the total amount of commission paid. You may not use a switch statement or multiple if statements.

Your task is to write a solution to the student’s homework; don’t use C++. 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

Memfrob

November 10, 2020

Memfrob is a light encryption algorithm that works by xor-ing 4210 = 001010102 with each input byte to create encrypted output; decryption is symmetric with encryption. Memfrob is roughly equivalent to ROT13 in cryptographic security.

Your task is to implement memfrob. 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