2 Interview Practice: Who's Missing! (20 pt.) Trinitee is just wrapping up her software engineering internship at Foogle 1. She recently developed an algorithm, genereateIDs, that gives unique IDs, starting from 0 and in increasing order, to each Google account in a particular region. This is how she defined her algorithm, in a .h' file. #include
2 3 7 // Returns a list of unique IDs for the specified region'. // 5 // `region' is a string that specifies a county, place, or location. 6 // This algorithm looks up every Foogle account in the location, // and assigns a unique ID. IDs are generated sequentially 8 // (starting at with 0) and up to n-1', where 'n' is the number 9 // of people in the given region. // // For example: // If a region has 3 accounts, return {2, 0, 1}. // If a region has 5 accounts, return {1, 0, 3, 2, 4}; 10 11 12 13 14 // 15 // Note that the returned IDs are not necessarily sorted. std::vector generateIDs(const std::string& region); 16 However, she's running into a few issues with her code. It seems that the returned vector is always too small - precisely, it seems to always be exactly one element too small. For example, Trinitee knows that in the country of Algolandia ?, there are exactly 220 = 1,048,576 accounts. However, when she runs the following lines of code: For example, Trinitee knows that in the country of Algolandia ?, there are exactly 220 1,048,576 accounts. However, when she runs the following lines of code: 1 const auto ids genereateIDs ("Algolandia"); std::cout called 'elements is sorted in 2 // descending order. That is: 3 // {1, 2, 3, 4} returns false, because it's sorted but increasing. // {4, 3, 2, 1} returns true, because it's sorted and decreasing. bool isSortedDescending (const std::vector??>& elements) { for (int i = 0; i s2 = what the sum should be if no numbers were missing. See answer to 2.2.3. return s2 - s1 Now, Trinitee and Asha look at you, and say: "Can you code it up for us?" We are expecting: You should implement the above pseudo-code in answers.cpp, which is part of the starter code you retrieved in Exercise 1]. 5If you're having trouble, check-out this video 5 3 Interview Practice: The Best Basketball Player (20 pt.) Hassan has been following closely the latest happening with the Denver Nuggest 6. He's a bit disappointed with their performance this season, so he reaches out to his friend Caleb. Caleb is a data scientist working for the U.S. Census. He tells Hassan that a big issue with the Denver Nuggest this season is that they're players are too short! What they really need is a tall player - wait, not a tall player, the tallest player in America. Thankfully, Caleb has just the data for the job! He shows Hassan that the census collects every person's height as an integer in inches? (they're too lazy, so they always round to the nearest inch). 3.1 Finding the Tallest American (10 pt.) Hassan and Caleb feel like they've done a good job so far, so they reach out to you. They know you're an expert in C++, do they ask you to write a function - findTallestPerson - which takes in a vector of integers correspondong to each person's height from the census data Caleb has, and returns the index of the largest height. If there are multiple largest heights, it returns the smaller index. They give you the following examples: findTallest Person({1, 3, 4, 5, 2}); // should return 3, the index of 5 findTallest Person({-1, -3, -4, -5, -2}); // should return 0, the index of -1 findTallest Person({}); // should throw std::invalid argument You look at them a bit funny, and wonder to yourself: "Who in the world has negative height? And why would the list ever be empty?" Still, you want to do a good job, so you do what they ask. [We are expecting: You should implement findTallest Person in answers.cpp, which is part of the starter code you retrieved in Exercise 1]. 3.2 Is it Correct? (5 pt.) After implementing the above algorithm, you want to show all your friends how good you've gotten at correcness and runtime analysis. You write down the pseudocode: algorithm findTallestPerson Input: A vector of integers representing height in inches Output: The index of the tallest person. If you're like me and do now know who they are, suffice it to say that they're a basketball team 7This is not true. It would be a violation of privacy if it was... 6 if input is empty: throw error tallestIndex = 0 for index in {1, input.size() - 1}: if input[index] > input (tallestIndex] : tallestIndex = index (1 pt.) Vincent thinks for a bit, and says - I think T()-0(?)! Is he right? If yes. what are the sand values that convince you he's right? if no, briefly explain why such values cannot exist [We are expecting: And answer to each of the above. The first should be of the form OL...), where you've filled in the .... The second should be two numbers, the c and is that convince you. The last should be either two numbere (the cand in that convince you), or a short sentence explaning why they don't exist.] 4 4 Interview Practice: Game Development (20 pt.) Nkumbu is a world-renewed game developer working for Big Corp Studies. His game works by randomly generating pets, cach which costs a randon amount of coins (only integer values). The payer s herilled to purchase precisely two pes. Being an awesome developer. Nkumbu wants to make sure that no matter how many coins the player has, there are always is pets that we can purchase at the cost of all this cons 4.1 Finding the Most Expensive Pets (10 pt.) Having been stumped with this problem for quite a bit. he reaches cut to Isaiah. wnose an avd game and recently took COMP 285. Analysis of Algorithms for help. He asks Isaiah to write a C+-function findTvoPete, which takes as input a vector of integers (corresponding to the cost of cach pet) as well as a target value (corresponding to how many coins the player currently has), and returns a pair that represents to distinct indices of pet costs that sum up to the tamct valus For some reason, Nkumbu also wants the smaller index to be first. To be super dear, he gives a fow cxamples to Isaiah: std::vector(int) pet_costa - (0, 2, 3, 4, 5): > , : std::pair out1 = findTroleta (pet_costa, /4coing=/6); ata:pair
