• How to Make a Huge Binary Tree Fast

This interesting interview problem was asked by Jane Street.

Generate a finite, but an arbitrarily large binary tree quickly in O(1).

That is, generate() should return a tree whose size is unbounded but finite.

...more
• A Neat Bitwise Trick For Swapping Even and Odd Bits

Here’s a problem that was asked by Cisco.

Given an unsigned 8-bit integer, swap its even and odd bits. The 1st and 2nd bit should be swapped, the 3rd and 4th bit should be swapped, and so on.

For example, 10101010 should be 01010101.

...more
• How to Solve the Anagram Indices Problem

Given a word and a string S, find all starting indices in S which are anagrams of word.

For example, given that word is “ab”, and S is “abxaba”, return 0, 3, and 4.

...more
• Lockable Binary Trees

Implement locking in a binary tree. A binary tree node can be locked or unlocked only if all of its descendants or ancestors are not locked.

...more
• How to Find the Longest Increasing Subsequence

This problem was asked by Microsoft.

Given an array of numbers, find the length of the longest increasing subsequence in the array. The subsequence does not necessarily have to be contiguous.

For example, given the array [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], the longest increasing subsequence has length 6: it is 0, 2, 6, 9, 11, 15.

...more
• Graph Coloring

Given an undirected graph represented as an adjacency matrix and an integer k, determine whether each node in the graph can be colored such that no two adjacent nodes share the same color using at most k colors.

...more
• Counting Unival Subtrees

A unival tree (which stands for “universal value”) is a tree where all nodes have the same value.

Given the root to a binary tree, count the number of unival subtrees.

...more
• How to Solve the Knight's Tour Problem

Let’s work through the problem of the knight’s tour problem.

A knight’s tour is a sequence of moves by a knight on a chessboard such that all squares are visited once.

Given N, write a function to return the number of knight’s tours on an N by N chessboard.

...more
• How to Formulaically Solve Tree Interview Questions

Tree questions are very common at top tech company interviews. I had two tree questions in my Google onsite interviews and one during my Facebook onsite interviews. An awesome thing about them is that they can be formulaically solved every single time. It doesn’t involve any genius insight. Let me show you how.

...more
• An Introduction To Backtracking

Backtracking is an effective technique for solving algorithmic problems. In backtracking, we search depth-first for solutions, backtracking to the last valid path as soon as we hit a dead end.

...more