Int2String Interview Walkthrough

dt051124

A few years ago, I wrote a series of articles on technical interviews. There was supposed to be a follow-up post where I actually walked you through a sample problem. Thing is, I never got around to it. Until now.

We’re going to be looking at a question that was a staple interview question at Yext for several years. The question is int2string, since it involves converting an integer to a string. Throughout this article, I’m going to be doing my best to explain not only the problem and solution, but also the various thought processes and pitfalls that I look for as an interviewer.

Let’s get started!

Interview Setup

First, let’s go through a few quick things to remind you of a pretty standard phone interview setup.

After a quick hello and introduction, I’m going to get you into some sort of collaborative coding environment. We used to use collabedit, which is just an online text editor with syntax highlighting. Today we use coderpad, which lets you also actually run code.

I’ll also ask you to choose a language to code in. I highly recommend you pick the language you’re most familiar with.

Problem Statement

Please write a method that takes in an integer and returns the string representation of that integer.

For example:
32 -> “32”
257 -> “257”

You can’t use anything that would make this problem trivial, namely the “toString” method (or equivalent in your language).

When explaining the problem, I’d say something nearly verbatim to the statement above. The first thing you should do when getting a problem is making sure that you understand the problem!

As an interviewer, I’m also looking to clarify anything that might be confusing. You should definitely ask questions if the statement isn’t clear.

For this particular problem, there are two main misinterpretations.

String Representation

The expected output is the same output that I’d get from Integer.toString, as shown in the two examples. I am not expecting an integer to be converted into English, i.e. 32 should not be converted into “thirty-two”.

toString

Seeing as this is an interview question, I’m not looking for something that would make the problem trivial. Very often, candidates would immediately answer with a solution that looks something like one of these:

Neither of these are what I’m looking for. They both trivialize the problem by using toString (implicitly for the second example).

Once the problem statement is cleared up, we get into actually solving it.

Finding a Solution

At this point the candidate will think through some possible ways to solve the problem. If you’re looking for practice, you might want to take a few minutes and brainstorm right now.

I personally don’t care if candidates think out loud. If it’s been a while and you haven’t said anything, I’ll ask you what you’re thinking so I can gauge how much progress you’ve made on the problem.

With that said, it can make it easier for interviewers to follow your train of thought if you talk out loud. Sometimes candidates mention a good idea but discard it. Having heard them mention it already makes it much easier for me to direct them back to that line of thought.

A Good Approach

After a few minutes, I’ll expect you to have some idea of how to approach the problem. I don’t expect it to be fully fleshed out, just that you’re going along the right train of thought.

For this problem, the approach I want to hear is that you’ll get the digits of the input, convert them to strings, and then concatenate them. Once you’ve gotten that far, I’ll give you the go-ahead to start coding. There are some pitfalls, but they can be worked out as you run into them.

Breaking Down Problems

If you are having trouble finding a workable approach, I’ll start guiding you with hints. I’ll probably be making mental notes as to how much guidance you need. It’s not a dealbreaker if I have to completely give you the basic approach, but you’ll need to do pretty well on the rest of the interview.

The int2string approach can be found with the tried-and-true strategy of solving an easier problem. In this case, inputs such as 1, 2, 3, etc. are as easy as it gets. (You could literally do an if statement.)

From there you can realize that if you can convert a single digit, you can break down the entire integer into digits and convert them one at a time.

Coding

As mentioned, our solution has three parts:

  1. Break down the input integer into digits.
  2. Convert each digit.
  3. Concatenate the results.

As it turns out, each one of these steps has (potentially) some additional work you need to figure out. I generally expect you find and address them as you code.

As a general tip, coding is typically not very complicated for interview questions. If you find yourself getting into a complicated mess, that’s probably a symptom that something can be improved with your approach. As an interviewer, I’m hoping to see that you can recognize this and adjust.

Digit Break Down

How do we get the digits from our integer? The pitfall here is whether or not you decide to go left to right or right to left.

Many candidates try to go left to right. This involves figuring out the magnitude of the input integer and dividing by that amount. Candidates with approach would normally start writing code that looked something like this:

There are already a few subtle bugs with this code.

The first is that the Math functions return doubles. So you need to convert between doubles and ints which (1) can lead to errors and (2) is an indicator that you’re doing something too complicated.

The second is that 10^power will overflow for a large enough power, even if the input is a sensible input.

Most candidates taking this approach struggle a lot with the coding. I’ve seen a lot of different places where people struggle: figuring out what the basic code structure should look like, double/int conversion, computing the correct power, etc. These are all signs that the approach is too complicated.

If they keep trying to make it work, I’ll usually step in and mention that their approach seems like it’s getting complicated. This is a hint that reads: you should simplify or change your approach.

Going right to left radically simplifies things since you don’t care how many digits there are:

Convert Each Digit

The next step in our algorithm is to convert the digits we’ve found. In other words, we need to fill out this helper method:

There are several ways to convert a digit. Some of them are nicer than others, but I actually accepted all of the approaches below. They’re all O(1) since there’s only 10 possible inputs to this method.

Concatenate Digit Strings

This step isn’t complicated. However, there is a potential pitfall–because we parsed our digits right to left, you need to reverse the digits when concatenating.

Are You Happy?

If you got this far on your own (or with minimal hints), you’re doing a solid job. Interviewers will then ask you if you’re happy with your code.

Ideally, your answer would be no. That’s because you haven’t solved the problem yet–this solution only handles positive integers. A full solution should handle 0 and negative numbers.

If you answered yes, I would just ask how you would test your code. This hint has always gotten candidates to realize they weren’t handling all possible integers.

This type of thing is fairly common in interviews. Notice that the examples and everything else discussed so far have not mentioned 0 or negative numbers. That’s by design. (If you are unsure whether or not to handle these cases, you can always ask.)

Edge Cases

Zero

The zero case isn’t handled automatically since the while loop in the solution would terminate immediately. The method then returns an empty string.

I have had many candidates struggle with handling the zero case. That’s because they would always try to modify their algorithm to somehow handle the zero case.

That’s a terrible way to handle this issue. This is a special case, and it’s completely fine to handle it as such:

Negative Numbers

It’s not hard to modify our approach to handle negative numbers. However, there’s a bad approach that people tried surprisingly often.

With this approach, you change the while loop condition to be n == 0 and assume the loop handles digits correctly. Spoiler alert: it doesn’t!

The reason it doesn’t is due to how negative mods work. For example, -57 % 10 is either -7 or 3. I say either because the answer actually depends on your programming language! Regardless, both values are wrong since you actually want 7.

The good approach is pretty straightforward. (Hopefully you’re seeing a pattern here.) If the input is negative, note that it’s negative and multiply it by -1. Then convert the number as before. At the end, if the original input was negative, slap a negative sign on the front.

One Last Edge Case

At this point, I’d accept the solution. However, if you finished the problem quickly, I’d challenge you by telling you there was still one edge case remaining. Very sharp candidates would also realize that there’s still an edge case.

That number is Integer.MIN_VALUE. (This is actually language-dependent; this edge case doesn’t exist in python.) The reason it doesn’t work is that multiplying it by -1 results in an integer overflow.

I’m not including a snippet for this, but you would handle this by special casing it (exactly the same way 0 is special cased).

Final Notes

As mentioned, int2string was a staple question for our phone screen for several years. It was actually the first of two questions; we expected candidates to solve it in 20-25 minutes. The strongest candidates I’ve seen would solve it in around 10.

Hopefully this breakdown has given you a good idea of both how to approach an interview problem and what an interviewer might expect from you. Even though the problem is relatively straightforward, there’s a surprising amount of depth to it.

Good luck interviewing!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s