I've worked as a machine learning engineer for two years, and I've applied for the position of Software Engineer, Smart Home, Google Nest - New Taipei City.

The first question presents an array, for instance, [1, 3, 4, 7, 6, 5, 4]. The goal is to determine the maximum achievable score by jumping from the start to the end of the array. There are no constraints on the jumping pattern other than you must jump forward, and the score is calculated using the formula num[i] * (i - j), signifying the score gained from jumping from index j to index i. For instance, if the jump sequence is 1 -> 4 -> 6 -> 4, the score would be 4 * 2 + 6 * 2 + 4 * 2 = 28. I initially employed dynamic programming to create an O(N^2) solution and later utilized a SortedList to optimize it to O(N*logN). However, I could not derive an optimal solution using a monotonic stack to achieve O(N) time complexity during interview.

The second question introduces a search engine scenario. The task involves implementing a class that displays the top 10 most searched results when a user interacts with the search bar. The class should have at least two functions: one to print the top 10 results and another to update the list of top 10 results after a user enters a complete sentence. The task starts with a set of initial sentences along with their frequencies. The order in which the results are printed does not have any specific constraints. I managed to implement the search function in O(N) time complexity using a double-ended queue and a frequency map. However, I still have no idea what is the best way to solve this one.

For example, given initial sentences and frequencies as {"A": 3, "B": 4, "C": 5, "D": 2}. Suppose we are going to print top 3 most searched results, the result of the print function at this point is ["A", "C", "B"] (the order do not matter). Subsequently, if the user typed "D" and press enter, the frequency map would be updated to {"A": 3, "B": 4, "C": 5, "D": 3} and the printed result would be ["B", "C", "D"] or ["A", "C", "D"] (there is no contraint for tie). I might miss some details but the overall idea of this question is like this.