Skip to main content

Solving Coding Problems, Part 1: Getting Started

Don't get intimidated by coding problems. Despite how daunting they appear, there is rhyme and reason to them. With experience solving and presenting them, you'll get much more comfortable. First, get comfortable with the format of the whiteboard coding interview. I went over this part in a previous post on format of the coding interview. Second, get familiar with the different types of problems which frequently occur in interviews. Coding interview problems are, despite all the bluster, coming from a finite pool. Interviewers may occasionally put their own twist on things, but usually the problems are variations on tried and true problem types. So it is important for you to recognize the popular types of problems and learn the main techniques for solving them cold.

Consider the following problem: write a function that takes an integer as input, reverses the bits in that integer, and returns resultant integer.

First thing, observe what are the data types involved as input and output. This problem is concerned with integers and more particularly, the bits that are the underlying representation of the integers. Once you've identified explicitly mentioned and potentially applicable data structures and data types, you should have an idea what the common operations we have at our disposal for those data types. For integers, we can do arithmetic on them. For bits in an integer, we can do bit arithmetic such as logical AND, OR, XOR, and NOT. If the data types were a linked list, we could traversal the list and modify the pointers in the linked list nodes.

Second, take a deep breath and see if the problem matches another you have previously seen. Recall in linked list problems, we have the pattern of using a single loop to advance two pointers through the list at different rates. This happens to be a common technique that plays a role in a number of linked list problems. A certain class of problems is concerned with going through an array to find a missing number of a duplicate number. There are at least a three techniques that may be applicable here. One might aggregate the array by summing and subtract the resulting sum from another summing of an array with known properties (or alternatively use a closed form mathematical formula). One might use a hash table to keep counts of how many times a given number occurs. One might use bit properties to get at duplicate or missing numbers. Once you've seen enough problems, you should be able to brainstorm a few approaches including a brute force solution. If an efficient solution doesn't come to mind immediately, don't fret about starting out with a brute force solution.

Once you have a couple of approaches in mind, now it is time to think about complexity. How fast would an optimal solution have to be? Sometimes the input or output size pretty much dictate a reasonable lower bound on how good a solution can get. Consider the problem of copying a modified linked list with cycles. If n is the number of nodes, then we can be pretty sure we can't do better than O(n) because it takes that much time just to write down a copy. Running time also helps guide our solution. If we think there is an O(n) solution, then our approach had better not be combinatorial in nature (and thus O(2^n)).

Have a few "templates" in mind for solutions. A good hint is the input. Often, you want to traverse the input efficiently. Different inputs lend themselves to different ways to traverse them. For example, it is natural to iterate through an array or a linked list by a for and a while loop respectively. For binary trees, recursion is natural, though you should learn how to use while loop iteration to traverse binary trees also. Try decompose the problem into smaller, solvable parts. For example, in the earlier example we worked through, zipping a linked list efficiently can be decomposed into finding the middle of the list, reversing the second half of the list, and linking up nodes for the two resultant lists in sequence. If you know how to find the middle of a list and how to reverse a list, you would be well on your way.

Practice: To start out, everyone needs to learn how to work through fizzbuzz cold. Google it. Learn it. Practice it. It should be clear.

Practice: Given a sequence of numbers as input, write a function that returns an array of all the unique occurrences of those numbers in the input in descending order according to frequency. This is actually somewhat would multilayered problem. You should ask clarifying questions. There is a simple case, a moderately challenging case, and a harder case. Yeah, if you could use all the libraries in Python, you can solve the easy case in one line, but that isn't the challenge here. Even for the easy case, don't use the libraries.

Comments

Post a Comment

Popular posts from this blog

Top 5 Books for Language-Specific Interview Questions

Shrunk and White of Programming When you put down that you know a certain programming language or languages on your resume, you are setting certain expectations for the interviewer. I would strongly caution against putting down "expert" in a language unless you invented or are one of the language's maintainers. You are giving your interviewer the license to quiz you on programming language lore. There are a handful of concepts that are considered "standard" knowledge for each language which go broadly beyond syntax and general semantics. These concepts commonly involve major pitfalls in a given language and the idiomatic technique for negotiating these pitfalls and writing efficient and maintainable code. Note, although the concepts are considered idiomatic, you can seldom infer them from knowledge of syntax and semantics alone. The tricky part here is that most courses that teach a particular programming language do not cover these idiomatic techniques and eve…

Interview Gotchas

It's a challenge to outperform all the other candidates in a competitive tech job only, but there is hope. You can improve your performance with practice and watching out for these gotchas: Make absolutely sure you are solving the right problem: I ran into this the other day. It is entirely a communication issue. When doing an initial screen over the phone, this problem is compounded. For example, maybe an interviewee is hacking out a function that returns the k highest priced products when the interviewer is expecting the kth highest priced product. One can squander a lot of time due to these misunderstandings. A good interviewer will try to guide you back to the right path, but you can't expect this. Be sure to ask questions. Confirm that the input and output are exactly what you expect. Use examples.Don't ever give an interviewer the impression that you are avoiding writing real code. This is an impression thing. This is a coding interview so you should be expecting to…

Complexity Analysis for Interviews, Part 1

This is part 1 of a two part series. Skip over to part 2 you'd like . For coding interviews, we are interested in gauging the asymptotic efficiency of algorithms both in terms of running time and space. The formal study of analysis of algorithms is called complexity theory, a rich field with fascinating and complicated math. For interviews, we only need a few basic concepts. Asymptotic efficiency is concerned with how the running time or memory requirements of an algorithm grows with the input size, so it is intimately concerned with how well algorithms scale to larger inputs. This is important in Computer Science and in practice because whereas some algorithms work well enough for small inputs of say < 10 inputs, the running time and space grows far faster than the input size and thus large inputs of say 10s to millions of inputs becomes impractical (usually meaning taking hours or even years of execution time). Consider sorting. Say for the sake of argument that sorting alg…