Whiteboard

Coding interviews are stressful. I have been on both sides of many interviews and have seen the process go many different ways. Being self taught I had just as much to learn for the interview process as I did for actually doing my job.

tweet

Preparation

Google has a notoriously difficult hiring process. So if you are looking for a golden standard to prepare for its not a bad place to look (not that Facebook, Apple and a lot of other companies aren't just as hard. In my opinion, Google has the most advanced process, which even includes a coaching call. I don't know if this applies to everyone or those like myself who may be self taught or non-traditional developers, but participating was very helpful. My coach was an awesome guy who has written about his experience getting hired at Google[1]. The call started with him explaining his basic tips to success:

  1. Repeat the Question Aloud (in your own words)
  • State and clarify your assumptions
    • scalability? you should ask.
    • clarify the function signature (input, output)
    • disambiguate the results
  • Use an Example
    • visualize your data structure on the whiteboard
    • gives you something visual to work with
    • if they provide one, use it
  • Brainstorm
    • think of multiple solutions and their time and space complexity. That way, if you have a solution of O(n) vs O(log n), you know you should go for the latter. Getting to this point in the process should take ~5 mins
  • Write Code
    • no pseudocode, it looks like weakness
    • write small, and leave space
  • Test Code
    • seriously, always do it. If the interviewer has to point it out they will be disappointed
    • go line by line, on the whiteboard and act as compiler
  • Practice a Lot

The last point is obviously the most important. You'll want to study algorithms[2] as much as you can, and dynamic programming. Brush up on your discrete math. Be familiar with as many data structures as possible.[3] It may be helpful to memorize a few algorithms and data structures and their space/time complexity[4]:

Sorting Algorithms in Javascript

Data Structures in Javascript

Sorting Algorithms

Other Algorithms

Data Structures

But mostly just find a good set of coding interview questions and just tackle them on a whiteboard.[6] A lot of the problems that you are given are underspecified. Part of the process is to ask the correct questions to fully understand the question. Show your work, it is as important as the "correct answer", arguably more so for the purposes of an interview. Keep in mind that generally, no one expects you to know every API exactly[7], so be honest when you don't know something as long as it isn't something you should know.

Simple Questions:

Every interview will start with some basic conversational questions that can generally be answered simply, like:

  • What is the DOM?
  • How does the browser work?
  • What is a closure?
  • How does this work?
  • Describe a few ways to communicate between a server and a client. Describe how a few network protocols work at a high level (IP, TCP, HTTP/S/2, UDP, RTC, DNS, etc.)
  • What is the node.js event loop
  • difference between == & ===
  • .apply vs .bind vs .call
  • pass-by-value vs pass-by-reference
  • what is duck typing?
  • what is IIFE? Why do it?

Javascript Scope:
If we execute this Javascript, what will the browser's console show?

  var text = 'outside';
function logIt(){
    console.log(text);
    var text = 'inside';
};
logIt();

Answer: The console will log undefined. To understand this, we need to explain a few things about Javascript.

  • Function-level scope. Functions create new scopes in Javascript
  • Declaration vs. assignment. A variable declaration simply tells the interpreter that a variable exists. By default it initializes the variable to undefined.
  • Hoisting. In Javascript, variable declarations are "hoisted" to the top of the current scope. Variable assignments, however, are not.

There's not much of a way to prepare for this part besides just knowing your shit TBH.[8]

Whiteboard Questions

I've decided to include here a running log of interesting challenges that I stumble on in the hiring process and my responses to them at the time. I won't bore you with every dumb fizz buzz question I see.

Palindrome

Given two strings, write a function that will determine whether or not the strings are palindromes.

Jack & Jill

Given an array of names, write a program that will sort the array such that Jack always comes first and Jill always comes second. Jill should come first if there are not Jacks.

Object Equality

given two inputs of any type, determine if the inputs are equal. i.e. if they are strings or numbers they should be equal, if they are objects all of their attributes should be equal.

Simple Recursion

Given a JSON object that you know little about, how can you return data of a specific type? e.g. write a function that can return and array of all of the numbers/strings/etc in an object:

Stock Price Challenge

Suppose we could access yesterday's stock prices as a list, where:

The indices are the time in minutes past trade opening time, which was 9:30am local time. The values are the price in dollars of Apple stock at that time. So if the stock cost $500 at 10:30am, stock_prices_yesterday[60]returns 500.

Write an efficient function that takes stock_prices_yesterday and returns the best profit I could have made from 1 purchase and 1 sale of 1 Apple stock yesterday.

First I made sure that I understood the structure of the data:

var stock_prices_yesterday = [24, 2, 11, 4, 6, 3];

I asked some clarifying questions to get a better understanding of the problem and implemented a really terrible solution because I did not properly understand the problem. Once I fully understood the problem I described a brute force approach which I was encouraged to implement:

function maximumProfit(prices) {
  var lowest = prices[0];
  var maximumProfit = 0;

  for (var i = 0; i < prices.length; i++) {      
    for (var j = i; j < prices.length; j++) {
      var profit = prices[j] - prices[i];
      if (profit > maximumProfit) {
        maximumProfit = profit;
      }
    }
  }
  console.log(maximumProfit);
}
maximumProfit(stock_prices_yesterday);  // Correctly returns 9

This solution works but I quickly pointed out that it was an O(n2) and we could surely do better. So I thought for a few minutes for a a better solution. Eventually, the interviewer just asked me to simply think about what I would have to do at each step to determine the maximum. Soon I came up with a much better solution:

What I came up here was a dynamic programming solution that I developed simply by thinking about what had to occur at each step in order to return the correct answer. What I came up satisfied my goal of a solution that could run in O(n) time O(1) space[9]

Some Arithmetic

Given an array of integers, determine whether or not there exist two elements in the array (at different positions) whose sum is equal to some target value. Examples: [5, 4, 2, 4], 8 --> true [5, 1, 2, 4], 8 --> false

Make sure you know what you need to return, it can save you a lot of work. Boolean returns are the best because once true you can bail. With this problem you should be able to brainstorm to a few solutions:

  • two loops: O(n) solution
  • sort and add: O(log n) solution
  • mystery solution: On solution

Tip: Use space to optimize time[10]:
"Biological usage of time–memory tradeoffs can be seen in the earlier stages of animal behavior. Using stored knowledge or encoding stimuli reactions as "instincts" in the DNA avoids the need for "calculation" in time-critical situations. More specific to computers, look-up tables have been implemented since the very earliest operating systems."

My Answer:

Set Data Structure/Random Number Generator

Implement a set data structure[11] that supports Insert, Remove, and GetRandomElement efficiently. Example: If you insert the elements 1, 3, 6, 8 and remove 6, the structure should contain [1, 3, 8]. Now, GetRandom should return one of 1, 3 or 8 with equal probability.

Who needs a getRandom on a data structure? That should tell you what this question is about.

  • Get: O(1)
  • Set: O(1)
  • Random O(1)

They can all be done in constant time, which is about the best you can do.[12]

Tip use multiple data structures

Reading Library

What follows is a list of books that I have/am/plan reading. These books typically came recommended to me and I think they represent a good subset of the large amount of literature out there.

Software Engineering

  • Code - Charles Petzold | amazon
  • The Pragmatic Programmer - Andrew Hunt and David Thomas | amazon
  • The Art of Comuter Programming - Donald Knuth | wiki | amazon
  • Introduction to Algorithms 3rd Edition by Thomas H. Cormen | amazon
  • The Algorithm Design Manual - Steven S. Skiena | amazon
  • Algorithms - Jeff Erickson
  • Software Architecture Patterns - Mark Richards
  • Cracking the Coding Interview - Gayle Laakmann McDowell | amazon
  • Programming Pearls - Jon Bentley | amazon

Web Development

  • High Performance Websites - Steve Souders | amazon
  • Javascript: The Good Parts - Douglas Crockford | amazon
  • Secrets of the Javascript Ninja - John Resig | amazon
  • CSS The Definitive Guide | amazon
  • CSS Pocket Reference | amazon
  • CSS Cookbook 3rd Edition | amazon
  • CSS3 for Web Developers

Linux

Math & Stats

  • Notes on Discrete Mathematics - Miguel A. Lerma
  • An Introduction to Statistical Learning with Applications in R
  • Think Bayes - Allen B. Downey

Footnotes


  1. Google Would Never Hire a Person Like Me by Anthony Mays ↩︎

  2. A popular recommendation is Introduction to Algorithms by Thomas Cormen et al. ↩︎

  3. You can find plenty of great implementations of data structures here ↩︎

  4. Big O Notation can be tricky to understand at first but is actually pretty simple. When calculating space time complexity they really only care about the curve, so don't give something like "On + 8". This cheatsheet is useful ↩︎

  5. Hash Tables are used quite a bit and definitely worth learning. This stackoverflow answer is also good. ↩︎

  6. There are many great sources for interview questions. My coach recommended Cracking the Coding interview and I have found the email list of Interview Cake provides some excellent questions for practice ↩︎

  7. A lot of this advice comes directly from Google employees. I also recommend this blog post ↩︎

  8. This article is really good for basic frontend interview questions ↩︎

  9. It's explained pretty clearly in this stack overflow question ↩︎

  10. from the time-memory tradeoff wikipedia article ↩︎

  11. From the above link on data structures ↩︎

  12. We say about because you can actually do better than O(1) by using a bitmap. In general, bit manipulation is an important concept to understand for optimizing space and time of algorithms when applicable. ↩︎

Written By: Cameron Drake

Tagged: development, tech, code, javascript, js, learn, coding, programming