Why Do Qualified Engineers Often Fail This Type of Interview Question?

Comment

Why Do Qualified Engineers Often Fail This Type of Interview Question?

algorithim-house-robber.png

The House Robber Problem is a popular question in software engineering interviews, but not because of it’s practical applications.

We’ve seen a lot of competent engineers struggle with this problem, because, perhaps unsurprisingly, the optimal approach uses dynamic programming.

It’s a shame because a lot of otherwise qualified engineers are getting rejected from roles because they can’t solve what’s actually a relatively straightforward problem.

This article will help clarify the intuition behind the optimal approach to this problem and shed some light on the deeper problem-solving pattern at play here.

Let’s start by considering the problem setup: inputs, outputs, constraints, etc. With any problem, it’s always good to clarify what all of these are and what they mean.

Your input will be an array of integers, representing the amount of gold in each house.

Your output will be a single integer, representing the maximum amount of gold you can steal from the neighborhood.

So for example:

1_ARVbX5Gm6Vcrq2-u9bSDVg.png

When it comes to problem-solving, it’s always good to start with an example that is simple enough that we can eyeball the answer, but complex enough so as to not be trivial. This will be a sanity check against our approaches and will provide valuable data (observations) about the problem.

Right off the bat, we can notice that we’ve skipped over two numbers between the 3 and the 5. This means the optimal solution may not always consist of robbing the closest packing of houses we can find. We may want to skip over MORE than one house.

We can also start to make some predictions about time/space complexity. Often interviewers won’t give you a set constraint since that can be a big hint. They’ll just say something like “do the best you can.”

Given that it’s an array of numbers, and we’re doing some kind of aggregating of information by maximizing the sum of some subset of those numbers, a reasonable prediction might be that we can solve this in optimally in linear time. That by no means is a guarantee but given that we’ll likely have to scan every house to come up with our plan, it’s difficult to imagine a way of doing this MORE optimally than linear time.

But let’s focus first on the brute force approach, and let’s do this at a conceptual level. I’ll pose this as a question:

Given that we have to steal from a subset of houses to find the optimal amount of gold to steal, what subsets do we need to test?

The answer:

So what constitutes a valid combination of houses? Any combination that leaves at least one house between any two that get robbed.

Now that we’ve established we need to test different valid combinations of houses, this problem starts to look very similar to another problem that uses recursion. Can you guess which one?

Answer 1.png

It might seem surprising at first, but SO many recursive problems boil down to this pattern because what we’re essentially doing is trying all possible combinations of solutions.

Here’s what that looks like for our previous example:

Answer 2.png

Once we’ve created all the valid subsets of houses we can steal from, all we have to do is sum up all the values in each subset, and pick the one that produces the largest sum.

If you’re wondering “how the heck do I set up the recursion to solve this?”, you can use this high-level pseudocode. It’s basically the explanation in English:

Answer 3.png

Translating that into low-level pseudocode (mix of English and code):

Answer 4.png
Answer 5.png

Here’s what the code looks like in JavaScript, using helper method recursion:

Screen Shot 2019-04-04 at 8.10.40 PM.png

Now let’s analyze the time complexity of this approach. Thinking about this naively, testing out all possible combinations of houses should probably seem like a lot of work, especially when the neighborhood is large (many elements in the array).

If you’re at all familiar with the notion of what a power set is (set of all subsets), then you’ll probably deduce that it’s some kind of exponential runtime.

The way to work through this on your own is by manually comparing how much additional work you have to do BY ADDING 1 ADDITIONAL HOUSE TO THE NEIGHBORHOOD. For this example, that means figuring out how many additional combinations are created and need to be tested when you add 1 more house to the neighborhood.

Here’s how to do it on a simple example:

Answer 7.png

You can see that the larger input still tests all the combinations given in the smaller input, plus all the new ones that are created by adding the additional number. Just with this one example, we can see adding 1 additional house means 5 additional combinations that need testing.

Doing this exercise by hand is time-consuming, but it’s crucial to gain a deeper understanding of analyzing time/space complexities. My advice for if you’re doing this without any time constraints and just trying to learn is to try a few more inputs and see how things change.

You can even write code to see how many times the base case is hit for different input sizes:

Screen Shot 2019-04-04 at 8.13.38 PM.png

Try running this code. See what it prints.

Spoiler alert:

Answer 9.png

But in some ways, it shouldn’t come as a surprise if you really looked at both sets of code side-by-side.

1_selOPWHuUJFJVZKpW-7NYQ.png

If you actually plotted the numbers in the results table you’d get something like this on a log scale:

Answer 10.png

When considering the total space complexity we need to examine both how many calls are on the call stack at any point in time, as well as any auxiliary space we use outside of the recursion:

Answer 12.png

Great! We have a working solution to the House Robber Problem.

And this is exactly where the interviewer will ask you to come up with optimizations. So let’s go back to the drawing board and make some observations:

Answer 13.png
Answer 14.png

Intuitively, there are a lot of junk combinations we are testing out. The reason for this is that we’re testing a lot of smaller combinations that are contained within larger ones. This means there are combinations that are strictly betterthan others. This means we can start thinking about how we can get rid of those smaller combinations.

The other things to look for at this point are any key insights that might unlock the problem. This is just an observation or conclusion that is true about this problem. We arrive at it deductively after gathering data about the problem. If you think of the problem-solving process as an hourglass, this would be the narrowest point:

Answer 15.png

So what is the key insight for this problem?

Answer 16.png

It’s a simple conclusion but it has powerful implications. We derive it from our earlier observations that we are testing a lot of junk combinations. The proof for it being true rests in the fact that if we ever left a larger gap, there’d be some house with a positive amount of gold we’re overlooking.

Remember, that’s an important detail of the problem. It’s something that you’ll want to ask the interviewer about.

Answer 17.png

As far as how we use the insight, we’ll have to go back to working with some examples and change up our approach. Before, we were trying all possible combinations. What if instead, we broke an example down and treated it as a sequence of different inputs? Then we can track how the output for that sequence changed.

Answer 18.png
Answer 19.png

Even with this one example, we can draw an important conclusion:

Answer 20.png

It’s always a good idea to test out more examples, just as a sanity check. Does it make sense that the output should always be growing as we grow our input?

Let’s see:

Answer 21.png
Answer 22.png

Looks like the pattern holds. And notice the kinds of examples we tried. They are ones with obvious solutions we can check.

So what’s the next step?

Let’s rewrite all those outputs as a table. You’ll notice, each output corresponds to the addition of a house to the neighborhood. Here’s what that means:

Answer 23.png

At this point, it should be pretty clear what these tables mean, and you should have some intuition about why this approach works. The main question you should have is “how do we create those tables?”

Because if you can answer that question, you’ve effectively solved the problem. At that point, it’s just a matter of coding it out and debugging any minor syntax or off-by-one errors.

But just having this table as a goal is HUGE progress. Now you know concretely what it is you’re trying to build out. Initially, the problem started off sort of vague and broad, and now we have a very clear goal in mind. Notice this pattern in the future when you’re solving new problems. You want to make your tasks as concrete as possible.

So let’s build out one of these tables manually first and see if we can spot any patterns. Remember what each element in the table represents! It’s the maximum amount of gold you can have when you’ve reached that point in the neighborhood. This is important to remind yourself of during ANY dynamic programming problem.

For the first element, obviously, we’ll want to steal from that house. Let’s add that to our table.

Answer 24.png

For the second element, we’ll either keep the first element as our max if it’s greater. Otherwise, we’ll choose to steal from the second element. So far, so good.

Answer 25.png

Things get a little trickier at the third element. What are our options?

Well, we can either add to what we stole from the first house OR we can skip this house and keep what we stole from the second house. It depends on which of those two values is greater.

Answer 26.png
Answer 27.png

It’s always a good idea to list out all the options available to you in a particular scenario. And the best way to figure out the different possibilities is just by trying different examples as I did above.

Now let’s add a fourth house. What should we add to our table?

Intuitively we know the answer is 8, but how do we arrive at that number? We’re adding one of the fives, but which one?

Answer 28.png

To answer this, let’s look at adding another number.

Answer 29.png

If we add a 4, we can easily see that the output should be 9. It’s easy to eyeball the input and come to that conclusion. But we want to come up with a process for reliably finding that 9.

If we look at our table, we can see that we’re adding the value of the new house, to the max gold 2 indices back. Why? Because that’s the maximum amount of gold we’ve aggregated from an input two units smaller (aka, with two fewer houses).

Essentially what we’re asking here is “should we add this new house and skip the previous one or should we skip this new house and steal from the previous one?” And we’re doing this every time we add a new house.

One important detail to notice from this process is that we’re just finding the maximum amount of gold we can steal given the full set of houses, we’re not tracking which houses we stole from. We’d have to modify our solution if we wanted that information, but luckily we don’t care about where the gold came from. Always remember to answer the question you were asked.

With that said, let’s translate this into pseudocode:

“For every house in the list, either add its gold to the max gold 2 indices back or keep the max gold 1 index back.”

If we look at two more examples, we can see the pattern holds:

Answer 30.png
Answer 31.png

In the first example, we add the 5 and 8 together because that sum is greater than 9.

In the second example, we keep the 13, because that is greater than adding 1 and 9.

What we return at the end is hopefully pretty obvious: it’s just the last element in the max_gold array.

And that’s how you solve the House Robber Problem. Hopefully, coming up with the code solution to this is relatively straightforward at this point. I encourage you to try your hand at it before taking a look at the solution below.

It should be pretty easy to see that the time and space complexity are both linear since we need to iterate over each element once, and for each element, we are storing a corresponding maximum amount of gold possible at that point in the array.

One little piece of extra credit I encourage you to think about is how can we optimize this solution a little more? There’s one simple tweak that we can make that will save us some space, can you think of how we might do that?

Here are the optimized solutions:

Screen Shot 2019-04-04 at 9.18.57 PM.png

The main idea behind the second one: you only need to keep track of the previous two maximums. Everything else can be thrown out.

I hope you enjoyed the read, feel free to drop me a comment if you think I left anything out or if anything was unclear. This is a problem we cover at Outco to help engineers prep for their coding interviews so if you want to learn more about our 5–week program you check out our site. We have weekly visitor sessions and new cohorts starting every month.

Happy coding!

Comment

How Ryan Landed a Job at Microsoft - Outco Program Review [VIDEO INTERVIEW]

Comment

How Ryan Landed a Job at Microsoft - Outco Program Review [VIDEO INTERVIEW]

As an engineer when you walk into the interviewing room, you never know who you are going to meet or what questions they are going to ask you.

Take Ryan, he had graduated with a computer science degree and experienced a lay off along with his entire team at Erickson. Even though he had finished a CS Degree a year prior, he still felt rusty during his initial interviews.

After initially struggling to receive even one onsite company interview, he joined Outco where he was flown to Microsoft’s Headquarters during week 3 of the program.

In this 30 minute video interview with Ryan and our CEO Dan Klos, Ryan sheds light on the Microsoft technical interview process and how he was able to stand out from the crowd of 19 other candidates to land an amazing job offer.

In this unfiltered Outcoder interview you’ll hear:

  • How Outco Helped Ryan Receive the Highest Possible Interview Scores

  • Why ‘Pointless Small Talk’ Made Him Stand Out from 19 Other Candidates

  • How 60 Seconds of Outco’s Salary Negotiation Tactics Immediately Paid for Outco

How Outco Helped Ryan Receive the Highest Possible Scores on All of His Interviews

 

How “Small Talk” Made Ryan Stand Out from a Pool of 20 Engineering Candidates

 

How 60 Seconds of Outco’s Salary Negotiation Tactics Immediately Paid for Outco

If you’re curious to learn more about Outco join our virtual info session or you can even attend a live drop-in class.

Comment

 Make Sure You Do this One Thing Before Answering Any Algorithm Question

Comment

Make Sure You Do this One Thing Before Answering Any Algorithm Question

There you stand, alone staring at a whiteboard with the hiring manager standing behind you.

They ask you to solve a problem you’ve never seen before.

Have you ever had the experience of freezing after being given a particularly hard problem?

This is common for engineers (myself included) and the reason for this is something called an Amygdala Hijack, one of the many blockers we talk about during Outco. In short, this is when the fear center of the brain takes over higher functions of the brain and prevents us from being able to think clearly and effectively problem-solve.

The technical interview is one of the most grueling parts of an engineers job search.

You have to be ready to answer any question - whether you’ve seen it or not, but there’s a hidden gem you can utilize to make any question easier to answer.

What is that, you might ask? The simple act of asking a question.

How to Utilize Questions Effectively

After being given the prompt to any problem, start by asking questions about it. It doesn’t matter if you’re just working on the problem by yourself or if an interviewer is asking you.

This is all about establishing an understanding of the problem, and to constrain your thinking about it.

Start by Asking Yourself Some Questions

  • Does this look like a problem you’ve seen before?

  • What do you remember about similar problems?

  • What immediately stands out about it to you?

Begin to think through time and space constraints. Knowing this will help you rule out solutions that run too inefficiently, or it will give you a hint of how many auxiliary data structures or loops you need.

Interview Questions About Arrays

If you have an array, for example, ask if it’s sorted.

  • Does it contain only numbers?

  • Are those numbers integers?

  • Can they be negative, or just positive?

Ask if there is a max length, or range of input sizes.

Interview Questions About Strings

For strings, ask if there is a distinction between upper/lower case.

  • Are there spaces?

  • Is there punctuation?

Ask about edge cases, like empty strings, empty arrays, very large or very small inputs etc.

Asking Language Specific Questions

  • Can you use certain libraries?

  • How should you handle errors?

  • What kinds of inputs should your function handle?

Asking Questions in a Pair Programming Situation

  • Can you google syntax and docs?

  • Can you run your code with examples?

  • Will the interviewer be able to answer certain questions?

Try to figure out what other guarantees there are in the problem.

Again, it’s all about putting constraints on your thinking and finding parameters that will focus your attention towards a smaller solution space.

What if the Interviewer Doesn’t Give You An Answer?

Keep in mind time and space complexities might not always be given. They might just say ‘do the best you can.’

This shouldn’t deter you, but it also means there could be several ways to solve this problem, and some are better than others.

The point is that there are a ton of conditions and constraints that will help focus your thinking and can hint at the direction you need to go in.

At the most basic level you are gathering data.

With all this said, keep this portion of the interview short, maybe just a couple minutes of discussion or thinking.

Don’t frame it as you looking for hints. Frame it as you trying to understand the problem better.

Also remember you can ask questions later on as they come up, so don’t stress about trying to nail EVERY constraint now.

In summary, asking questions is all about gathering more information making sure you are solving the correct problem.

It would shock you how often people start solving different problems than the one I asked, all because they didn’t clarify what they were supposed to be doing.

Let’s use an example to practice.

The Tower of Hanoi Problem

tower-of-hanoi-problem.gif

By Trixx (I designed this using http://thewalnut.io/) [GFDL (http://www.gnu.org/copyleft/fdl.html) or CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia Commons

Problem: Tower of Hanoi
The Tower of Hanoi is a puzzle with three pegs, and a variable number of discs. The discs are stacked with the largest ones on the bottom and the smallest on top. Each time a disc is moved from one peg to another peg, counts as one step, regardless of if the new peg is adjacent to the old one.
The goal of the puzzle is to move the whole tower from one peg to another peg in the smallest number of steps.
Your task is to write a function that takes an integer as the input and outputs another integer that represents the minimum number of steps necessary to move a tower of that size from one peg to another.
Input: Integer (discs)Output: Integer

In this example the questions you should be asking are about the nature of the discs, and the answers will provide you with constraints you can use later on:

  • Can you move more than one at a time?

  • Can you put larger ones on smaller ones?

  • Is there a maximum number of discs for this problem to be solvable?

  • What should the time complexity of the solution be?

You should also be asking if you actually have to simulate the motion of the discs themselves.

This isn’t an immediately obvious question to ask, but it’s a very important one. A lot of students start devising data structures and disc swapping algorithms they’ll need to solve this problem, when in reality they’ve already failed the interview.

The solution only asks for the NUMBER OF MOVES, not for you to actually create the SEQUENCE OF MOVES. This is a BIG difference, one which simplifies the problem tremendously.

This is something all interviewees should be on the look out for when they are asking questions.

Often times the problem description will appear deceptively difficult, or conversely, deceptively simple. Asking more questions about it will help shed light on whether the problem is straight forward, or if there are hidden subtleties.

Document All Question Answers or Constraints

All the answers to these questions should go somewhere, whether that’s on a whiteboard, or on a shared text editor, or even a piece of paper.

You should also write down everything that comes to mind: patterns you notice, constraints you are given or things you observe. Any hunches, ideas or thoughts should all go somewhere.

This might be like identifying important features of the problem.

  • For example, is the max/min element relevant?

  • Does there seem to be some kind of pattern between input size and output size?

  • Can you rule out certain approaches based on constraints, like using built in methods or certain libraries?

These are the building blocks of your solution. Think of this as a brain dump.

You want to get everything down so you can go back to it later. You can only hold so much in your head at a time, and this will help lighten some of that cognitive load.

Additionally, the process of writing things down and thinking of how to express them in another way is what helps your brain move closer to a solution. It’s the same as how the simple act of talking out loud about a problem can help you solve it. There’s something that happens when your brain translates ideas from one format to another, that makes you gain a deeper understanding of those ideas.

Again, the goal here is to simply get everything written down somewhere.

It doesn’t need to be super organized, but it should be legible and you should be able to make sense of it. This step is meant to be a tool for you to use later one when you are solving your problem.

/*Here are the constraints:Only move one disc at a timeOnly smaller discs on larger discsNo max number of discs Number of discso won't be negativeDo the best you can on space and timeNo need to simulate moves, just output total number*/

If you have any questions or comments on this process please leave them below in the comments.

Want to see Outco’s live 5-week program in action? You can now drop-in on a free class with one of our technical mentors.

Learn how to solve a dynamic programming problem and receive multiple optimizations and solutions with a free visitor class.

Comment

The Algorithm of an Algorithm

Comment

The Algorithm of an Algorithm

Working at Outco for the better part of a year now, I’ve noticed some patterns in how engineers learn the material and what kinds of roadblocks they run into. We cover a lot during the 5-week program, from how to traverse trees and graphs, to sorting lists efficiently, to reducing the time complexity of recursive functions. Looking through some of my old college course readers, the breadth of material covered is roughly equivalent to two semesters of computer science topics because we deliver it in such a condensed way. And although engineers going through the program will learn a lot by sticking to the material we provide them, the ones that learn the most excel at another, more meta skill that is harder to teach explicitly. (… Read Full Article on Medium )

Comment