Summary

The article discusses a Google coding interview problem involving maximizing points by selecting k cards from either end of a row of cards with associated points.

Abstract

The article presents a common Google interview question that challenges interviewees to devise an algorithm for selecting k cards from a row to achieve the maximum sum of points. The cards are represented by an integer array cardPoints, and the challenge is to pick cards from the ends of the array, not the middle. The author illustrates the problem with an example, demonstrating different combinations of card selections and their respective scores. The key insight is to avoid recomputing the sum of cards at each step, which would result in an inefficient O(k²) runtime. Instead, the author suggests an optimized approach that changes only the beginning and end elements of the sum, reducing the runtime to O(k) with O(1) space complexity. The article concludes with an invitation for readers to follow the author on Medium for more content and a link to a comprehensive guide on software engineering interview preparation.

Opinions

Sorting the array is deemed unhelpful as the order of cards is crucial to the problem.
The author suggests a brute-force approach of trying every combination as a starting point for solving the problem.
The article emphasizes the importance of the "Key Insight" to optimize the solution, highlighting the inefficiency of recomputing the sum at each step.
The author finds the problem engaging and encourages readers to share their thoughts and requests for future content.

Cute Google Coding Interview Problem: Maximum Points from Cards

This is a commonly asked Google interview question. Can you solve it?

There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Let’s take a look at an example. Say we’re given the array [1,2,3,4,5,6,1] and we can pick 3 cards. Remember that we have to pick our cards from the *ends* of the list — so the first card we pick can’t be a card in the middle.

What are our choices?

With the blue line, we’ll take the first three cards, which gives us a score of 6.

With the red lines, we’ll take two from the front, then one from the back, which gives us a score of 4.

With the green lines, we’ll take one from the front, then two from the back, which gives us a score of 8.

With the yellow lines, we’ll take all three from the back. This gives us a score of 12, which is the best answer.

Intuition

Would sorting help? No, because the order of the cards matter.

Is there a “smart” way to figure out which cards we should take? It’s not as simple as taking the higher card at each turn.

Well, what if we just tried every combination? Start by taking all the cards from the left, then try taking one fewer card from the left and one from the right, and so on, like we did our example above.

But wait, isn’t that super slow? We’d have to try k possibilities, each summing an array of size k, so the runtime is O(k²).

Key Insight

We don’t need to recompute the sum every time! Let’s start by selecting all k cards from the left. On our next attempt, we’ll remove the rightmost selected card, and add on the rightmost card in the entire list, and we’ll repeat that for the next iteration. Note that only the beginning and end elements of the sum are changing — and that’s a constant time operation, so our runtime is reduced to O(k).

Code

Our first loop is taking every card from the left.
On the next loop, we have to try k options — you can think of this as “How many cards will I take from the left?” We can take anywhere from 0 to k cards from the left.
We keep track of the highest value we’ve seen so far, and return that at the end of the loop.

This is an O(k) time solution and uses O(1) space.

Hopefully you thought this was a fun question and let me know if you have other questions!

For more articles like this, follow me on Medium. Not a member yet? Join the community. Want more software engineering interview guides and coding question tips? Check out all of my writing organized by topic in this article.

If you have any requests for what I should write, please let me know!