Skip to content

CTCI Technical Questions

What You Need to Know

Core Data Structures:

  • Linked Lists
  • Trees, Tries, Graphs
  • Stacks & Queues
  • Heaps
  • Vectors/Arraylists
  • Hash Tables

Algorithms:

  • Breadth-First Search
  • Depth-First Search
  • Binary Search
  • Merge Sort
  • Quick Sort

Concepts:

  • Bit Manipulation
  • Memory (Stack vs. Heap)
  • Recursion
  • Dynamic Programming
  • Big O Time & Space

Walking Through a Problem

  • 1) Listen
  • 2) Example
  • 3) Brute Force
  • 4) Optimize
  • 5) Walk Through
  • 6) Implement
  • 7) Test

Example

Create an example that is specific (eg. use real numbers, strings for a tree), sufficiently large, and not a special case.

Brute Force

Come up with a brute force solution, and state that it's a brute force solution, even if obvious (don't assume that the interviewer would know that you can come up with a simple solution; always express your thoughts clearly)

Optimize

  • Look for unused info
  • Use a fresh example
  • Solve it incorrectly; this can sometimes help come up with a better solution
  • Make time v. space tradeoff. Storing extra state about a problem can sometimes help in optimisation
  • Precompute info (eg. sorting beforehand)
  • Remove bottenecks
  • Remove unnecessary computation
  • Remove duplicated work

Removing Bottlenecks

Optimise the step that takes the longest time. Consider the following problem:

Find all pairs of elements in an unsorted array that have a difference of k.

A brute force way to find a solution would be to iterate over all pairs of elements, and see it the condition holds (a runtime of O(N^2)). We could sort the array first, and then perform a binary search for x+k and x-k for each x in the array. Both steps would be O(N log N). Optimising one step will not be enough as both have the same runtime.

Finally, we could create a hash table from the elements of the array, and then just search for x+k and x-k, resulting in the overall runtime of O(N).