Uber Interview Questions - Maximum Sum of Non-adjacent Elements

Uber Interview Questions - Maximum Sum of Non-adjacent Elements As you may know, one of our blogs current focuses is on Uber interview questions. Their questions are usually representative and you can expect exactly the same kind of questions from other top companies like Google, Facebook, Airbnb, etc.. In addition, we only cover questions that were asked recently. This week, the question is maximum sum of non-adjacent elements. Its of medium difficulty, you may expect to have it as the second question in an on-site interview. We are going to cover topics including array, recursion/dynamic programming, algorithm efficiency and so on so forth. Maximum Sum of Non-adjacent Elements Given an array of integers, find a maximum sum of non-adjacent elements. For example, inputs [1, 0, 3, 9, 2] should return 10 (1 + 9). The question has been asked by Uber recently (as the time of writing). Ive also seen many similar questions like finding the maximum sum of subarrays. Analysis Again, if you havent seen this questions before, solve it by yourself first. Otherwise, theres no point to reading this post. Its not obvious to solve this problem naively. Unlike many other interview questions, you can hardly use brute force or some greedy algorithms here, because theres no way for you to list all non-adjacent elements combination. But just because of this, it provides a great hint dynamic programming. Let me explain more here. Dynamic programming You may check Step by Step Guide to Dynamic Programming if you are unfamiliar with this concept and its completely necessary to know it for coding interviews. When I was trying to solve this problem, there are two obvious things that make me think about dynamic programming. First, when the question is about finding particular subarrays or subsets, dynamic programming is usually a great approach. This is because the problem is easy to break down into sub-problems. Second, when you find it impossible to brute force all possibilities, it also indicates that recursion or dynamic programming is worth to try. For example, finding subarray with given sum can easily be solved by brute force (of course its not optimal), but you can do the same thing to find the subset with given sum. (Check this post for more info) Solution With that in mind, we should think about how to break down the big problem into sub-problems. Suppose we know the max sum for all subarrays, how can it help us to solve the overall problem? Lets use max_sum[i] denote the maximum sum for subarray arr[0i]. If the last number arr[i] is included in the sum, max_sum[i] should equal to arr[i] + max_sum[i-2] (because arr[i-1] cannot be included). Similarly, if arr[i] isnt included, then max_sum[i] should equal to arr[i-1]. Therefore, we have the following formula: max_sum[i] = MAX(arr[i] + max_sum[i-2], max_sum[i-1]) So the code is like: Memorization One of the advantages of dynamic programming is memorization. In the above code, many steps are unnecessarily re-calculated. To make it faster, we should store all results in memory. Thus, we have the following code: As you can see, we use array mem to store all results weve processed so that we wont repeat the unnecessary calculation. The time complexity is O(N) because from i = 0 to N, every single one is calculated at most once due to memorization. As we use an extra array, the space complexity is O(N) as well. Optimization Can you further optimize the solution? First of all, theres no way to improve the time complexity because we should check every single number at least once. Thus O(N) is the lower bound. Thus, we should think about reducing memory usage. If you take a look at the previous formula again, you might notice one interesting fact. Every step only relies on the previous two steps results. In other words, if we care about max_sum(i), theres no need to store anything before i-2. The code might be quite different from previous versions, that is because we are doing a bottom-up approach for dynamic programming. We use prevOne and prevTwo to store results of previous two steps. From i = 0 to N, we store the results of each subarray arr[0i] to prevOne and arr[0i-1] to prevTwo, thus the next iteration can use them to calculate for the new subarray. In essence, they are exactly the same as previous solutions. Summary I hope you found the question maximum sum of non-adjacent elements helpful. Instead of giving you the final solution, I think its very necessary to provide the whole analysis process and provide the coding solution at each step. Otherwise, many people wont be able to know where the final solution come from. Dynamic programming is a hard topic in coding interviews. Most of the time a top-down approach is enough, but for this one, a bottom-up approach is more efficient. By the way, if you want to have more guidance from experienced interviewers, you can check Gainlo that allows you to have mock interview with engineers from Google, Facebook ,etc..