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.

Coding Interview: Pseudocode

"Interview is an artificial reality designed by companies to keep people out" - Manager Tools

Many companies won't offer helpful feedback on your interview performance. I think that feedback is a fair game, and the process should be transparent.

Pseudocode

This is a follow-up on the older post, Interview Insider: Coding fluency. A reader asked my opinion on using pseudocode to document his thoughts while working on the solution. Specifically during a phone screening, when diagramming may not be a possibility.

I want to start by quoting Steven Skiena's TADM^[1]:

Productivity Tips: Git merge

If some rather mindless activity takes 20 minutes out of your day on most days, it’s a big deal. That's two weeks in a given year you would rather spend in Hawaii. For a medium-size team, improving the productivity to save these 20 minutes is like hiring one more developer.

Efficient Git merge

I am still new to Git, and I am really liking it. The workflow I learnt from tutorials was to create a local master branch and another local branch for a pull request. To get new changes or resolve conflicts, you switch to the local maser branch, pull it, switch to the other branch, and merge from the local master branch.

The problem here is that Visual Studio reloads the solution when you switch branches. For the solution with ~100 projects, it took up to 3 minutes, times two as you need to switch back to the other branch.

I felt there must be a better way, but for several months I stuck to what I knew. To my surprise, many of my teammates (seasoned folks) were doing the same. This tip allowed merging without switching the branch, which made our day more productive and enjoyable.

Coding Interview: Coding fluency

"Interview is an artificial reality designed by companies to keep people out" - Manager Tools

Many companies won't offer helpful feedback on your interview performance. I think that feedback is a fair game, and the process should be transparent.

Coding fluency

Coding fluency is how quickly you translate your solution into code. Though I measure the time (with a stopwatch), coding fluency is not as important to me as other criteria ^[1]. Most good companies, however, have their bar set very high on coding fluency.

I saw weak candidates rapidly producing a lot of code, and very strong candidates who needed help getting going. In the end, a person who quickly wrote the initial implementation may spend a lot of time getting it right, and a candidate who took extra 10 minutes to think it through may come up with an elegant solution.

People are nervous during the interview. Many experience a blank page syndrome, or a writer's block when staring at that whiteboard. Candidates who deal with more than one language or discipline may feel rusty due to the context switching. I just recently experienced a block, panicked and then wrote messy code. I attribute it (or I hope so) to 6 months of doing web front-end development.