Interview Questions

Surviving the Coding Interview

Let’s face it, job-hunting sucks. Especially if you are in the market for a challenging and interesting coding job. To get one of these jobs you need to subject yourself to the popular hazing ritual known as The Coding Interview. You will be expected to spent a day with the company, during which you will be bombarded with numerous programming problems to solve by coding. You will have to write your code on a whiteboard most of the time. This sucks for a whole lot of reasons, mainly being that it bears no resemblance to the real world work environment where you would have a modern IDE, Google and Stack Overflow at your disposal. But, let’s not stop there. In the real world work environment, you wouldn’t have someone standing over your shoulder who has already solved this problem hundreds of times with other people. Someone who knows the various possible solutions intimately who is now waiting for _you_ to solve it with your bad handwriting on a whiteboard which is certain to be way too small. Well, maybe your handwriting is beautiful and the space isn’t too small for you, but my handwriting is atrocious and I have spatial analysis deficits which make it hard to judge how small I need to write in order to fit all the entire solution on a given whiteboard. Especially the solution to a problem I haven’t solved yet.

Chances are you haven’t written a HashMap or LinkedList implementation in years. You haven’t implemented the Merge sort or Quicksort implementation since you passed your CS Algorithms 101 class a decade ago. And why the fuck would you? There are libraries out there that do all this stuff that have been tested, debugged, and optimized ages ago by people who are better at this than you are. Nevertheless, you will have to ‘prove’ you can code by showing that you can do this, or know how to do it by solving programming problems that are generally thinly disguised versions of these types of tasks. This page on my little blog is intended to help you in this journey. I am sharing my solutions to these problems as I prepare to get my next job. If I can do this, you can too! The trick is that you need to practice a lot. Once you have solved a problem, you need to study other possible solutions to it.

My philosophy on this is that you shouldn’t have to settle for a job if you don’t have to. You’re going to be spending 8-12 hours working at a job on any given workday and probably more weekends than you would like. You will have to drag your ass out of bed to go to this job when you’re tired and and burned out, when the weather outside totally blows, when the traffic is awful or your public transportation is particularly crowded or unreliable. Your kids will be hitting milestones that you’re missing because you’re working that job. Therefore, it pays to make sure you can get the best job possible. It’s worth the grueling hours of re-learning your CS education all over again, in all of the languages you listed on your resume, because you can bet your ass that you will be asked to solve programming problems in any of the languages you have listed on it.

Strings And Arrays

If you go to a coding interview, you will definitely be asked to solve a programming problem involving strings and/or arrays. In order to be properly prepared to handle these questions, make sure you know how to do the following in the languages you have listed on your resume:

  • Find duplicates in an array or string
  • Search for and replace items in an array or a string
  • Reverse an array or string
  • Compare two arrays or strings and determine if they are a permutations of each other
  • Handle matrices represented as multi-dimensional arrays
  • Handle the entire Unicode character set for string-based problems

I snagged a copy of Cracking the Coding Interview to prepare for coding interviews. I am using the 5th edition, but the 6th edition is available and has more problems to solve. In addition to getting a copy of this book, I sighed up for LeetCode and TopCoder.

Below is a list of programming problems related to strings and arrays that I have worked through, along with my solutions.

Problem 1: Determine if a string contains duplicate characters. Do not use any additional data structures.

Source: Cracking the Coding Interview, 5th edition

See Java solution

Problem 2: Given two strings, write a method to determine if they are permutations of each other.

Source: Cracking the Coding Interview, 5th edition

See Java solution

Problem 3: Write a method to replace all spaces in a string with ‘%20’.

Source: Cracking the Coding Interview, 5th edition

See Java solution

Problem 4: Implement a method to perform basic string compression using the counts of repeated characters. For example, the string a a b c c c c c a a a would become a2blc5a3. If the “compressed” string would not become smaller than the original string, your method should return the original string.

Source: Cracking the Coding Interview, 5th edition

See Java solution

Problem 5: Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

Source: Cracking the Coding Interview, 5th edition

See Java solution

Problem 6: Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to 0

Source: Cracking the Coding Interview, 5th edition

See Java solution

Problem 7: Write methods to reverse a string iteratively as well as recursively

Source: My CS education. This is a coding 101 question and you should know how to do it.

See Java solution

Problem 8: Write a method to determine if an input string is a palindrome

Source: My CS education. This is a coding 101 question and you should know how to do it.

See Java solution

Share This:

Comments are closed.