Clicker Questions - 26-Review-4
Question 1: Show me the result of partitioning
{251, 983, 036, 783, 734, 186, 494, 469, 619}
using the “median of three” pivot selection. Give you answer as numbers each separated by a single space.
Answer
The vector starts as 251, 983, 036, 783,734, 186, 494, 469, 619The median of 251, 734 and 619 is 619. Swap it with 251:
619, 983, 036, 783, 734, 186, 494, 469, 251Now do the parition:
619, 983, 036, 783, 734, 186, 494, 469, 251
^^^ ^^^
619, 251, 036, 783, 734, 186, 494, 469, 983
^^^ ^^^
619, 251, 036, 469, 734, 186, 494, 783, 983
^^^ ^^^
619, 251, 036, 469, 494, 186, 734, 783, 983
^^^
Swap element zero and the 186 and you get your answer:
186, 251, 036, 469, 494, 619, 734, 783, 983
Question 2: Below is a dynamic program ge(), which takes a string of integer digits, like “12345”, and a boolean, zero. It returns a long long. It is correct, but it only implements “Step 1” of dynamic programming. Your job is to do “Step 2” – memoize the program.
In the text box of the answer, simply list what changes you’d make, such as:
Before line 9, add "int j".
List one change per line. I want to stress that you don’t need to figure out what this code is doing. You do need to understand dynamic programming to the point where you can memoize this code correctly, even if you don’t really know what it does.
Answer
First you need to add a cache. I would add an unordered_map whose keys are sirings and whose vals are long longs. So the first part of my answer would be:After ine 3, add 'unordered_nap <string, long long> cache'Next, Tneed to make a memoization key from s and zero. Since s is only composed of digits, you can simply turn zero into a character and append it to s. This would be my code for that:
After line 10, add 'string key' After line 12, add 'key = s + ((zero) ? "A" : "B")'Now, you need to check the cache. This can be before line 12, after line 12, or after line 20. I would probably do it after line 20, so all the base cases run before I mess with the cache (Td also set the key after line 20, rather than after line 12 as above. Either is ok):
After line 20, add "if (cache.find(key) != cache.end()) return cache[key]"There are two places that you return, and in both places, you need to se the cache, so:
In the body of the if statement in line 33, before the return, add "cache[key] = rv"; On line 47, set rv = rv ^ gc(news, zero), and then do cache[key] = rv; return rv;