Coding Interview: The Game Plan

I am doing interviews few times a year, and it's probably not enough[1]. Opportunities aside, I learn a valuable lesson every time.

Interview pressure uncovers weaknesses. Mine are overcomplication, impatience and panic:

• I somehow expect the problem to be hard. So, I dismiss valuable cues and intuitions if they look too obvious.
• If I feel a hunch, I dive in without full understanding. I keep stepping on this rake... and solving a wrong problem!
• I the problem sounds intimidating, I panic and freeze, not knowing where to start.

Brute-force

To compensate for these weaknesses, I now start with a simplest solution that comes to mind. I work on a naïve solution first, clarifying my understanding, and then brainstorm ideas to improve it.

Structuring your work this way reduces the cognitive load when you start working on an improved solution.

This is an intuitive and well-recommended technique. However, I feel that candidates are afraid to look inexperienced and skip this step. As an interviewer, you may want to offer your candidate to start easy.

The Game Plan

It helps to mentally structure the interview into phases. The opening is important as it sets the tone, and brute-force can help you get through. Early phases are head-up: collaborate, learn and explore. Late phases are head-down: focus and deliver.

The game plan also helps manage your time and deliver a solution before the interview is over.

Interview Pearls: K Consecutive Bit Flips

This is a cool problem that sounds very hard by becomes easy with two intuition sparks (and a little twinkle).

Description

In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of K-bit flips required so that there is no 0 in the array. If it is not possible, return -1.

Example

Input: A = [0,0,0,1,0,1,1,0], K = 3
Output: 3

Interview Pearls: Sliding Window

If the problem talks about continuous subarrays or substrings, the sliding window technique may help solve it in a linear time. Such problems are tricky, though the solution is simple once you get it. No wonder I am seeing such problems in almost every interview!

Here, we will take a look at Subarrays with K Different Integers (LeetCode Hard), which appeared on LeetCode weekly contest #123. You can also master the sliding windows technique with these additional problems:

• Longest Substring Without Repeating Characters
• Longest Substring with At Most Two Distinct Characters
• Longest Substring with At Most K Distinct Characters

Problem Description

Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K. For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.

Return the number of good subarrays of A.

Example

Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

Dynamic Programming: Minimum Travel Cost

The higher is the bar, the more you're expected to use dynamic programming (DP) during an interview. This technique requires a lot of practice to grasp; if you've mastered the recursion, DP is the next level.

This problem appeared on LeetCode weekly contest #121, and it's a good problem to practice the DP thinking.

Problem Description

In a country popular for train travel, you have planned some train travelling one year in advance. The days of the year that you will travel is given as an array days. Each day is an integer from 1 to 365.

Train tickets are sold in 3 different ways:

• 1-day pass is sold for costs[0] dollars;
• 7-day pass is sold for costs[1] dollars;
• 30-day pass is sold for costs[2] dollars.

The passes allow that many days of consecutive travel. For example, if we get a 7-day pass on day 2, then we can travel for 7 days: day 2, 3, 4, 5, 6, 7, and 8.

Return the minimum number of dollars you need to travel every day in the given list of days.