Gaming CS Interviews

Intro

General Tips

Interview Topics

Algorithmic Complexity

• add / remove / get / find from an array

• add / remove / find from a linked list

• add / remove / peek from a stack

• add / remove / peek from a queue

• add / remove / get from a hashmap

• add / remove / get from a balanced binary tree

• add / remove / get from a heap (though heaps are less common…)

Graphs and Trees

Terminology

• A graph is a set of nodes and edges between some of those nodes. Nodes and edges often have payloads like a label or weight associated with them.

• The most common graph distinction is between undirected vs directed graphs. E.g., when you have an edge between two nodes, is it a directed, one-way street, or is an undirected, two-way street where you can go in both directions when going from node to node.

• A tree is a very common type of graph with some interesting constraints, so anything you learn about graphs in general also applies to trees like binary search trees and the DOM.

• Traversing a graph is the process of visiting nodes in a graph, usually starting from a root node and expanding out from there recursively based on each node’s neighbors.

• The two main algorithms to understand w.r.t. graphs that 95% of graph questions boil down to, are breadth-first-search (BFS), and depth-first-search (DFS), visualized briefly below.

Advice

class Node {
  string value
  Array<Node> neighbors
}

class Graph { 
  Array<int> nodes;
  Array<[ int, int ]> edges
}

Given a graph where nodes represent major US cities and edges represent flights between those cities, write a function that takes in two cities and returns a valid flight path between those two cities or null if no such flight path exists.

• The most direct solution to this problem uses DFS.

• A harder variant of this type of question would be to find the shortest path if each edge (flight) had a number associated with it that represented distance, which is where Djikstra’s algorithm would come into play.

Sorting

/**
 * Sorts an array by ignoring it and then printing out a new, 
 * sorted array with its own "Alternative Values."
 */

let input = [ 6, 8, 3, 9, 5, 4, 1, 7, 0, 2 ]

function conwaySort () {
  return [ 15, 16, 17, 18, 19, 20 ]
}

Common Sorting Algorithms

• Mergesort; in particular, its recursive “divide & conquer” approach comes up often. O(n log(n))

• Quicksort; generally considered the most robust, general-purpose sorting algorithm. generally amortized O(n log(n))

• Radixsort; only works on numbers using bit hacks but is significantly more efficient. O(n)

Given an array of integers, write a function that will remove all duplicates. (be sure to add the obligatory followup, what is its runtime?)

• The “aha” moment here comes if you realize that by sorting the input, you can just walk along the array with all duplicates being next to each other, resulting in an efficient solution.

Strings

Notes

• Strings are just arrays of characters, so any algorithms you learn for arrays also applies to strings.

• A very common type of string problem involves finding all possible substrings of a given input string.

Given a password string of length n as input and a mapping from all 26 lowercase characters to possible alternates (like “e” maps to [ “e”, “E”, “3” ]), implement a function that returns all possible password combinations you could generate of length n.

• For example, “haxor” could be “Haxor”, “hax0r”, “HAX0r”, etc.

Recursion

Implement a function that will return the nth number in the fibonacci sequence (1, 1, 2, 3, 5, 8, 13, …).

• A common follow-up is that the straight-forward solution is typically pretty inefficient, so how could you optimize the recursion?

Given a binary tree, implement a “visitor” pattern function that takes in a node and visits all children. Implement prefix, infix, and postfix traversals.

• The difference in the traversal order is just moving the order you visit the “current” node around, either before the children, after the left child, or after the right child.

Given a simplified DOM node defined as: class Node { string className; Array<Node> children; }, write a function that takes in a Node along with a target css class and returns a list of all subnodes which match that CSS class.

• Aside from the traversal, which you’ll likely do recursively, the logic to visit each node needs to take into account the fact that DOM nodes can have multiple classnames, so it’s not enough just to do a direct comparison between the target CSS class and a Node’s className.

• This is exactly what the built-in function getElementsByClassName does.

Brainteasers (Abstract Shit)

Advice

• Realize that the goal isn’t to come up with the best possible solution, but rather a reasonable, viable solution that is backed by reasoning.

• Ask clarifying questions; “Where are we moving Mt. Fuji to?”, “What resources do we have to accomplish the task?”, etc.

• One common subset of brainteasers is to ask “How many X exist?” such as “How many gas stations are there in the US?”

• The goal here is to be able to guesstimate some numbers that give an idea of the order of magnitude of the response, so if we estimate that there are 10 gas stations per town and 2000 towns per state and 50 states, … which should be more than enough to get the ball rolling.

Less Common Topics

• Concurrency

• Databases

• More generic data structures

• Dynamic programming

• Architecture

• And sooooo many more…

Where To Go From Here?

• Interactive Coding Challenges — Lists a large number of interactive practice questions, many of which come with solutions and explanations.

• Google Interview Questions — Great list of interview questions previously used by Google provided by Interview Cake.

• Coding Interview University — Their section on coding exercises / challenges is a great meta-list of additional resources to find practice questions.