Software Engineer Interview Guide - Data Structures and Algorithms

Software Engineer Interview Guide - Data Structures and Algorithms

You made an awesome resume, applied to a bunch of jobs, and landed a couple interviews. You diligently prepared for them, and the time has come for the real thing. So what should you do once you step foot into that interview room? Well, that's what we're going to do with the Taro blog, breaking down the main types of questions software engineering interviews ask: Data structures and  algorithms (i.e. DSA), behavioral questions, and system design. To start off, we are going to deep dive into data structures and algorithms interview questions, which are a linchpin of FAANG interviews in particular.

Communicate With The Interviewer

I think what a lot of people don’t realize is that the interviewer should be there to help you. It’s their job to bring out the best in you, and given the scarcity of software engineering talent, there’s extra incentive for them to do so. Because of this, you should always be working with your interviewer to show them your skills and make sure you’re going down the right path. Here’s what you should do:

  1. Clarify the problem - Sometimes the problem is purposely ambiguous to test you. Projects are often times not straightforward in the real world, so clarifying requirements is an important skill for software engineers to have. Keep asking the interviewer questions until you know exactly what you’re expected to deliver; it’s quite possible that the problem is actually easier than you thought.
  2. Come up with a plan - Don’t just jump straight into coding, because if your overall approach is wrong, you could easily waste half of the interview accomplishing nothing. Come up with a high-level strategy to the problem, and talk through it with your interviewer. This lets the interviewer know what’s coming so they can follow the code once you start writing it and also helps you really crystallize what you want to do.
  3. Talk through your code as you’re writing it - Reading other people’s code is hard enough, and it’s even harder in such a high pressure environment like an interview. Don’t make your interviewer’s job even harder by staying completely silent or mumbling while you’re coding. What I do is write out some code, turn back to the interviewer, explain it, and watch for their body language. They might give a signal as to whether or not you’re going in the right direction. A nod probably means that you’re doing well and a confused look probably means that you’re… not doing so well.

Focus On The Core Of The Problem

Every data structures and algorithms problem has a “key” to it. For 2 sum, it’s realizing that you should look for the differences relative to the current number. For k largest numbers, it’s realizing that you should use a heap. Your goal with any one of these interview problems is to find this key and then code it out. Don’t waste time getting bogged down in the details like how you convert an ArrayList into an Array in Java. If you need some trivial utility logic, just ask the interviewer if you can hand-wave it away or come back to it later. Also, don’t preemptively deal with the gnarliest edge cases that will warp your code into oblivion. Deal with them after you have something working for the core flows on the board.

Done Is Better Than Perfect

If you’re interviewing with a top tech company, there’s a good chance that you’ll face an algorithms problem that you won’t be able to find the optimal solution to. In this scenario, a lot of people get tunnel vision and spend forever digging for the optimal solution, ending up with effectively nothing when the time’s up. This is almost always considered a failure.

When you’re coming up with your initial plan like I mentioned before, come up with the simplest solution first, which is usually a brute force method. This shouldn’t take more than 1–2 minutes and from there, spend another 2–3 minutes trying to come up with a more optimal solution. If you can’t do it, just communicate to the interviewer that you’re going to quickly implement a sub-optimal solution just to get something on the board. At this point, your goal should be to minimize risk, and having something is always better than having nothing. This also doesn’t necessarily mean that you’re surrendering. The sub-optimal solution shouldn’t take up all of your interview time, so you will almost certainly have time to think about the better solution after coding out the sub-optimal one. On top of that, you might realize what the optimal solution is as you’re building out the inefficiencies of the sub-optimal solution. Lastly, iteration is a necessary and important software engineering skill. Being able to evolve from a sub-optimal to an optimal implementation might even be more impressive than jumping to the optimal solution immediately.

Factor In Space

Run-time is the center-piece of any algorithms problem solution analysis, but a lot of people forgot that space is a factor as well. Keep the space allocations you’re doing in mind as you’re building out your solution so you can give both a run-time and space analysis after you’re done. Also, a lot of interviewers will ask you if you can come up with a different solution to the problem, even when you’re absolutely sure that your run-time is optimal. There’s a good chance that there’s a solution that runs slower than yours but is more efficient on space usage as a trade off.

Test Your Code

After you’re done coding, run it through some sample test cases. Describe the input, how it flows through your business logic, and how the output of your algorithm matches the desired outcome. 1–2 happy flow cases should be enough, and from there, you can cover the edge cases. Here are some examples of what you can think about here:

  1. Empty/null input
  2. Extremely small or large numbers
  3. Logically impossible inputs
  4. Worst case scenarios that make your code work as hard as possible

Lastly, don’t just think about your code as just some abstract algorithms solution. Pretend that you’re building out a utility method in a production environment that others developers in your company are going to call. Think about what’s the most sensible behavior for it to take with extreme cases. Let’s say your method returns an int and you get a bad input. Should you return 0? -1? Or just fail fast and crash? Just by demonstrating this thinking, even if you don’t have the perfect answer, shows that you’re not just a regular rank-and-file developer.

Going Deeper

The goal of this article is to share some high-level tips around DSA interviews. If you really want to go deep, check out these related resources: