# Cracking Int To String

One of our oldest interview questions is int to string, where we ask candidates to, well, convert an int to the corresponding string. Back when I wrote a series on technical interviews, I wanted to follow up with a post where I actually walked through a sample interview question. Now that we’ve deprecated int2string, I’ve finally gotten to get around to it.

In this post, I’ll do my best to explain not only the problem and solution, but also the thought processes and pitfalls that I’m looking 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 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, passing in the integer `32` would return the string `"32"`. Likewise, passing in `257` would return `"257"`.

You can’t use anything that would make this problem trivial, such as Java’s “toString” method (or equivalent in your chosen language).

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

For this particular problem, there are two main misinterpretations.

## String Representation

The expected output is the same output that I’d get from Java’s `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:

``````public static void int2string(int n) {
return Integer.toString(n);
}
``````
``````public static void int2string(int n) {
return "" + n;
}
``````

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 candidates 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. That way I can gauge how much progress you’ve made on the problem. If you’re on the right track, I’ll either let you keep thinking or ask you to expand on your train of thought. If you’re off course, I’ll direct you to another idea to think about.

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, you should have some idea of how to approach the problem. It doesn’t have to be fully fleshed out; I just want to know that you’re going along the right train of thought.

For this problem, this is the general approach I’m looking for:

1. Break down the input integer into digits.
2. Convert each digit to a string (or character).
3. Concatenate the strings.

Once we’ve confirmed a good approach, I’ll give you the go-ahead to start coding. You might run into 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. For this problem, we can use the tried-and-true strategy of solving an easier problem. In this case, we could restrict our inputs to single digits such as 1, 2, 3, etc. Worst case scenario, you could convert them with a long if/else 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.

I do take hints given into account when deciding how well you did on the interview. In particular, I care about the number and the magnitude of hints given. A few nudges aren’t a big deal, but it will be hard for me to say yes if I have to give you the complete approach.

## Alternate Approaches

Sometimes you might come up with an approach that I disagree with. Most of the time, I don’t want to use an approach because it’s wrong. A small fraction of the time it’s because the approach seems more complicated than necessary. Very rarely, it’s an approach I haven’t seen before. (We have training materials that list out all the approaches we’ve seen.)

When you want to use an approach I’m not happy with, I’ll let you know. If you really want to pursue an approach then I won’t stop you, but realize that you might be wasting some of your time.

# Coding

As mentioned, our solution has three parts:

1. Break down the input integer into digits.
2. Convert each digit to a string (or character).
3. Concatenate the strings.

As it turns out, each of these steps has a potential pitfall. If you run into one, I expect you to address it as you code.

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:

``````public static String int2string(int n) {
int power = 0;
int nCopy = n;
while (nCopy > 0) {
power++;
nCopy = nCopy / 10;
}

// 10^power is one order higher than what we want.
power--;

while (n > 0) {
int digit = n / Math.pow(10, power);
n = n % Math.pow(10, power);

// To be implemented...
}
}
``````

or this:

``````public static String int2string(int n) {
int power = Math.log10(n);

while (n > 0) {
int digit = n / Math.pow(10, power);
n = n % Math.pow(10, power);

// To be implemented...
}
}
``````

There are two main issues with this code:

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

2. `10^power` will integer overflow for a large enough power, even if `n` is a sensible input.

If you take this approach, it will feel overly complex as you implement your solution and fix errors. Having to deal with issues like double/int conversion, computing correct powers, etc. are signs that an approach is too complicated. You should take a step back and see if you can use a different angle.

When we go right to left, we don’t care about how many digits there are or what power we need. The code becomes much simpler:

``````public static String int2string(int n) {
while (n > 0) {
int digit = n % 10;
n = n / 10;

// To be implemented...
}
}
``````

## 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:

``````public static String int2string(int n) {
List<String> digits = new ArrayList<>();

while (n > 0) {
int digit = n % 10;
n = n / 10;

// To be implemented...
}
}

public static String digit2string(int digit) {
// To be implemented...
}
``````

There are several ways to convert a digit. Some of them are nicer than others, but I will accept any of the approaches below. They’re all constant time (which is the main thing I care about) because there’s only 10 possible inputs to this method.

``````// Approach 1: if/else chain. (This could also be a switch.)
public static String digit2string(int digit) {
if (digit == 0) {
return "0";
} else if (digit == 1) {
return "1";
} else if (digit == 2) {
return "2";
} else if (digit == 3) {
return "3";
} else if (digit == 4) {
return "4";
} else if (digit == 5) {
return "5";
} else if (digit == 6) {
return "6";
} else if (digit == 7) {
return "7";
} else if (digit == 8) {
return "8";
} else if (digit == 9) {
return "9";
}
// I don't really care about how this edge case is handled.
throw new RuntimeException("Invalid digit!");
}
``````
``````// Approach 2: index into an array.
public static String digit2string(int digit) {
String[] digitStrings =
{"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};
return digitStrings[digit];
}
``````
``````// Approach 3: map.
public static String digit2string(int digit) {
Map<Int, String> stringsByDigit = new HashMap<>();
stringsByDigit.put(0, "0");
stringsByDigit.put(1, "1");
stringsByDigit.put(2, "2");
stringsByDigit.put(3, "3");
stringsByDigit.put(4, "4");
stringsByDigit.put(5, "5");
stringsByDigit.put(6, "6");
stringsByDigit.put(7, "7");
stringsByDigit.put(8, "8");
stringsByDigit.put(9, "9");

return stringsByDigit.get(digit);
}
``````
``````// Approach 4: ASCII codes.
// This was the original intended approach. It relies on realizing that
// the ASCII values of "0", "1", "2", etc. all differ by 1.
// This approach returns a char, so you'd need to adjust the other code or
// convert it to a String before returning.
public static char digit2string(int digit) {
return (char)((int)'0' + digit);
}
``````

## 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.

``````public static String int2string(int n) {
List<String> digits = new ArrayList<>();

while (n > 0) {
int digit = n % 10;
n = n / 10;
}

String result = "";
for (int i = digits.size() - 1; i >= 0; i--) {
result += digits.get(i);
}

return result;
}
``````

# Are You Happy?

If you got this far on your own (or with minimal hints), you’re doing a solid job. This is also where you get everyone’s favorite question: are you happy with your code?

In this case, your answer is hopefully 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, it’s not a big deal. 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.

Edge case issues are fairly common in interviews. All of the examples and everything discussed so far have actually avoided mentioning zero or negative numbers by design. (If you are unsure whether or not to handle these cases, you can always ask.)

# Edge Cases

## Zero

Currently, passing in zero returns an empty string. We can just handle zero as a special case:

``````public static String int2string(int n) {
if (n == 0) {
return "0";
}

List<String> digits = new ArrayList<>();

while (n > 0) {
int digit = n % 10;
n = n / 10;
}

String result = "";
for (int i = digits.size() - 1; i >= 0; i--) {
result += digits.get(i);
}

return result;
}
``````

I’ve had many candidates struggle with handling the zero case. That’s because they tried to modify their algorithm in a way that it would handle zero without treating it as a special case. That’s not necessary at all!

## Negative Numbers

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

With the bad approach, you change the while loop condition to be `n == 0` and assume the loop handles negative numbers 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.

``````public static String int2string(int n) {
if (n == 0) {
return "0";
}

List<String> digits = new ArrayList<>();
boolean isNegative = n < 0;
if (isNegative) {
n = n * -1;
}

while (n > 0) {
int digit = n % 10;
n = n / 10;
}

String result = "";
for (int i = digits.size() - 1; i >= 0; i--) {
result += digits.get(i);
}
if (isNegative) {
result = "-" + result;
}

return result;
}
``````

## 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 this number 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 zero is special cased).

# Final Notes

In order to pass a phone interview, I’m looking to see that you were able to:

1. Come up with a viable approach.
3. Debug and handle edge cases.

For some problems, we’ll talk about the time or space complexity for your solution. It’s not so important for this problem, since it’s hard to come up with a reasonable solution that isn’t `O(n)`.

Timing-wise, I expect most candidates to solve this problem in 20-25 minutes. The strongest candidates I’ve interviewed would finish 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 this problem is pretty straightforward, there’s a surprising amount of depth to it.

Good luck interviewing! #### Vincent Le

Hi! I've been at Yext for nearly 7 years and I currently work on our fulfillment systems. When I'm not thinking about code, I enjoy playing games or having a nice cocktail.