Pump your brain with some fun puzzles!
- Question: Read input from the user one line at a time, and output the last x distinct lines in sorted order, where x>=0 is a parameter. If there are fewer than x lines, print the existing distinct lines. For example, input lines “a”, “b”, “b”, “c” and x=3 would output “a”, “b”, “c”, as would the input “a”, “b”, “c”, “b”. As another example, input lines “x”, “e”, “b”, “e”, “c”, “d” with x=3 would output “c”, “d”, “e”. As a last example, input lines “a”, “b”, “c”, “a”, “d” and x=3 would output “a”, “c”, “d”.
- Goal: Implement a method with wasted space and runtime complexity: O(x).
- Question: Read input from the user one line at a time and output a line if it is the maximum over the last x lines, where x>=0 is a parameter to the doIt method. That is, output a line if there are at least x lines total, and this line is the maximum of the x-1 lines previous to the current one and the current one. For example, input lines “y”, “a”, “b”, “p”, “p” with x=3 would output “p”, “p” since p is the maximum of {a, b, p} and p the second p is the maximum of {b, p, p}. We don’t print out y because there are not 2 other elements to compare it to when we read it in. Note that with this definition, when x=0 every line is a maximum. As another example, input lines “x”, “e”, “b”, “e”, “c”, “d” with x=3 would output “e”.
- Goal: Implement a method with wasted space and runtime complexity: O(x).
- Question: Read input from the user one line at a time and output a new line if it is a prefix of some previous line. For example, input lines “abc”, “def”, “abc”, “de”, “ef”, “efg” would output “abc”, “de” because they are prefixes of lines that come before them.
- Goal: Implement a method with wased space: O(s) - where s is the number of unique lines. And runtime complexity: O(1)
- Question: Read input from the user one line at a time and output a new line if it is a substring of some previous line. To get full points, try to use as little extra space and time as possible. For example, input lines “abc”, “def”, “abc”, “de”, “ef”, “efg” would output “abc”, “de”, “ef” because they are all substrings of lines that come before them.
- Goal: Implement a method with wasted space and runtime complexity: O(k) - where k is the number of suffixes.
- Question: Read input from the user one line at a time and for each line, output the minimum of all lines so far that start with ‘c’. If you ever read in the line ‘###’ remove the current minimum line that starts with ‘c’ before printing the (new) minimum, and continue. As with question 1, if no minimum exists, print a ‘’ on its own line. When removing the minimum line, if no such minimum exists, just continue. For example, input lines “berry”, “apple”, “cheer”, “car”, “car”, “###”, “###” “add” would result in the output “”, “*”, “cheer”, “car”, “car”, “car”, “cheer”, “cheer”.
- Goal: Implement a method with wasted space: O(n) - where n is the number of lines. And runtime complexity: O(1).
- Question: For this question, you may assume that every input line is distinct. A “step” is a line such that every line that follows it is greater than it. Read in the lines one at a time, and output all the steps. You may assume all lines are distinct. For example, input lines “f”, “d”, “a”, “c”, “b” would output “a”, “b”.
- Goal: Implement a method with wasted space: O(1). And runtime complexity: O(s) - where s is the number of "steps".
- Consider the following 2-player “road trip” game: player 1 starts with a word w1 (typically country or city); player 2 then names a new word w2 that starts with the last letter of w1. Player 1 then names a new word w3 that starts with the last letter of w2, and so on. For example, this game might play out as “dortmund”, “dominican republic, “canada”, “ajax”. Read in the input one line at a time, and output the fewest number of turns it might take for such a game that starts at line 1, ends at line n (where n is the total number of lines in the file), using only lines of the file as the possible words in between. If there is no way to play to get to the last line from the first line, output 0. For example, the input “dortmund”, “bermuda”, “canada”, “paris”, “dominican republic”, “ajax” would return 4 (“dortmund” -> “dominican republic” -> “canada” -> “ajax”), whereas the input “dortmund”, “bermuda”, “canada”, “dominican republic”, “ajax”, “paris” would return 0 since there is no way of getting from “dortmund” to “paris” on just the input lines.