Data Structures Homework
August 24, 2018
Today’s exercise is from a programming student taking a Data Structures course, using Java.
Given a text file, print a list of the ten most common words in the file, along with their frequency of occurrence. You may not use a HashMap or ArrayList, but you may use regular expressions.
Your task is to write a program to find the ten most common words in an input file. 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.
Mars Rover
August 21, 2018
Today’s exercise is a Microsoft interview question:
Write code using the commands below for two rovers to meet. Two rovers are dropped on Mars. Imagine Mars to be a straight infinite plane. When the rovers are dropped on Mars they are dropped with a parachute, so their initial position on Mars is on the parachute:
The only commands available are:
- Go left.
- Go right.
- No operation.
- If on parachute go to label.
A label points to a piece of code with a name where it is possible to transfer execution.
Using ONLY the commands above, write code to enable the rovers to meet.
Your task is to write a program to help the Mars rovers meet. 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 Search
August 17, 2018
Today’s exercise is a simple task in matrix manipulation. Given a matrix in which the rows are ordered but the columns or not, efficiently search for a specific item in the matrix. For instance, given the matrix
2 5 8 1 4 7 3 6 9
a search for 6 finds it in row 2 column 1, a search for 8 finds it in row 0 column 2, and a search for 0 fails.
Your task is to write a program that searches a matrix. 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.
A Simple Interview Question
August 14, 2018
Today’s interview question comes from Apple:
Write a program to add two integers. You may not use the
+(addition) operator, but may use the++(increment by 1) or--(decrement by 1) operators. Be sure your solution works for both positive and negative inputs.
Your task is to write a program to add two 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.
Penniless Pilgrim
August 10, 2018
Today’s exercise comes to us courtesy of long-time reader and contributor Ben Simon; you might like to look at his version of the task:
You must travel from the top-left corner of a five-by-five grid of points to the bottom-right corner, stepping from one point to another without retracing any edge. The first two steps must be eastward through the grid. Each step has a cost. An eastward step adds 2 to the current accumulated cost (so you start with an accumulated cost of 4), a westward step subtracts 2 from the current accumulated cost, a northward step halves the current accumulated cost, and a southward step doubles the current accumulated cost. It is possible to reach the bottom-right corner with an accumulated cost of zero.
Ben’s version of the task has a pretty map of Duonia, and a story about a penniless pilgrim who longs to visit the temple.
Your task is to write a program to find the zero-cost path through the grid. 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.
Odometer
August 3, 2018
Today’s exercise is an Amazon interview question:
An odometer variously uses letters and digits in its reading; for instance, an odometer might have a reading of G7TS39. Incrementing the odometer means adding 1 to a digit or increasing to the next letter to the next letter, with a carry to the next column when appropriate. Thus, G7TS39 increments to G7TS40 and G7TZ99 increments to G7UA00. As a special case, the odometer never increases in size, but rolls over, so the next odometer reading after Z9ZZ99 is A0AA00. An odometer position that initially contains a digit always contains a digit, and an odometer position that initially contains a letter always contains a letter, so 1Z9 increments to 2A0.
Your task is to write a program to increment an odometer. 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.
Double Dabble
July 31, 2018
Over at ComputerPhile, Professor Brailsford gives a beautiful explanation of the double-dabble algorithm for converting a number from binary to binary-coded decimal. If you don’t want to watch the video — you should — there is also an explanation at Wikipedia, or you can read the original description by C. B. Falconer.
Your task is to implement the double-dabble algorithm as shown by Professor Brailsford. 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.
Triple Or Add Five
July 27, 2018
By starting from the number 1 and repeatedly either adding 5 or multiplying by 3, an infinite set of numbers can be generated. For instance, starting from 1, you can triple to get 3, then add five to get 8, and finally triple to get 24, so 24 is reachable. On the other hand, 15 is not reachable, as a little thought will show.
Your task is to write a program that determines if a number n is reachable by tripling or adding five, and if the number is reachable to give the sequence of operations by which it can be reached. 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.
Fenwick Trees
July 20, 2018
There are some algorithms in coding theory where cumulative frequency tables must be maintained. This requires two tasks to be performed on an array of integers:
1) Calculate the cumulative sum of the first n elements of the array.
2) Modify the value of an element of the array.
One approach is to maintain an array of the elements, so that an element can be modified in O(1) time but calculating the cumulative sum requires O(n)time. Another approach is maintain an array of the cumulative sumes, so that a cumulative sum can be calculated in O(1) time but modifying a single element of the array takes O(n) time.
A Fenwick tree performs both operations in O(log n) time. The tree is normally embedded in a 1-based array, with the children of node i at nodes 2i and 2i + 1. Each element with index i a power of 2 contains the sum of the first i elements. Each element with index i a sum of two powers of 2 contains the sum of the elements since the preceding power of 2. In general, each element contains the sum of the values since its parent in the tree, found by clearing the least-significant bit in the index. Wikipedia has a good description of Fenwick trees.
For example, to find the sum of the first 1110 = 10112 items in the array, note that 11 has three bits set, so add elements 10002, 10102, and 10112. To modify the 11th element, modify 10112, 11002, 100002, and all higher powers of 2 up to the size of the array.
Your task is to implement Fenwick trees. 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.
Top Heavy Perfect Powers
July 17, 2018
Over at his blog, Ken is investigating top-heavy perfect powers to investigate increasing the breadth of the Cunningham project. He makes a list of 2413 perfect powers bn with b ≤ n in increasing order, up to a googol, omitting bases that are themselves perfect powers (for instance, 4n, 8n or 9n).
Your task is to make a list of the 2413 top-heavy perfect powers less than a googol. 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.
Programming Praxis 