## Whiteboard

#### Introduction

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.

## Google Coaching Call

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:

**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**

- think of multiple solutions and their time and space complexity. That way, if you have a solution of O
**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 time/space complexity^{4}:

- merge sort
- quick sort
- bubble sort (but don't use it)
- hash tables
- trees
- graphs
- Dijkstra

But mostly just find a good set of coding interview questions and just tackle them on a whiteboard.^{5} 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^{6}, so be honest when you don't know something as long as it isn't something you should know. Here are a few questions that Google provided on the call for us to work through:

#### 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**solution_{(n)} - sort and add:
**O**_{(log n)}solution - mystery solution:
**O**solution_{n}

Tip: Use space to optimize time^{7}: "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^{8} 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.^{9}

Tip use multiple data structures

## Simple Questions:

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

- difference between
`==`

&`===`

`.apply`

vs`.bind`

vs`.call`

- pass-by-value vs pass-by-reference
- what is duck typing?
- what is IIFE? Why do it?
*angularjs*: what is a directive*angularjs*: what is scope hierarchy and how does it work

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

## 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**space

_{(1)}^{10}

# References

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

A popular recommendation is

*Introduction to Algorithms*by Thomas Cormen et al. ↩You can find plenty of great implementations of data structures here ↩

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 "O

_{n}+ 8". This cheatsheet is useful ↩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 ↩A lot of this advice comes directly from Google employees. I also recommend this blog post ↩

from the time-memory tradeoff wikipedia article ↩

From the above link on data structures ↩

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. ↩It's explained pretty clearly in this stack overflow question ↩

Written By: Cameron Drake