Nathan Wailes - Blog - GitHub - LinkedIn - Patreon - Reddit - Stack Overflow - Twitter - YouTube

# Algorithms, Data Structures, and Interview Questions

#### Contents

#### Child pages

#### Related pages

# Data structures

## Questions

- What is the threshold at which point it's a good idea to create a class for a data structure?

# Non-algorithm-specific interview advice

# Algorithms-Specific Informational Websites (not programming challenge websites)

Nick Parlante - Pointers, Binary Trees, etc.

Very good explanations

- GeeksForGeeks
- OK explanations

- Jason Park - Algorithm Visualizer
- Khan Academy - Algorithms
- Treehouse

# Books

- Look good:
- The Algorithm Design Manual by Skiena
- Rec'd by Adam D'Angelo in a Quora post.

- Algorithms in a Nutshell, 2nd ed.
- Essential Algorithms - 5 stars on O'Reilly
- Working with Algorithms in Python - O'Reilly video series - 4.3 stars - Same guy who wrote 'Algorithms in a Nutshell'

- The Algorithm Design Manual by Skiena
- Maybe good:
- Meh:

# Articles

- http://haseebq.com/how-to-break-into-tech-job-hunting-and-interviews/
First, a high-level roadmap.

__Watch the Princeton Coursera course on algorithms (by Robert Sedgewick)__, mostly up until Dijkstra’s algorithm and not much more than that. Try to follow along and code as you go. You don’t need to implement things in Java unless you already know Java.__Read The Algorithm Design Manual__for general algorithms and data structures background. Go through most of it. (You can skip the giant appendix about specific algorithmic topics).__Buy Cracking the Coding Interview__. We’ll be using this as a repository of coding problems and solutions.(...)

If you’re working on an algorithms problem (such as out of CTCI) and can’t figure it out,__spend no more than 20-30 minutes without making progress. Just go look up the answer. Contrary to popular belief, most struggling past 30 minutes is pointless.__Some people will disagree with this. [NW: Like Tom and Chris Uga.]

Screw those people.

That said, if you find up having to look up the answer to more than 2/3rds of problems, your problem set is too hard and you need to downgrade.

But

__banging your head against a wall or staring blankly at code is a waste of time__. For code/algorithms problems, you very much want to maximize the density of learning per hour.Any time you look up the answer to a coding problem, try to understand the solution. Walk through it with a debugger if it’s particularly mysterious. Read multiple explanations of why it works.

Then—and this is

**extremely**important—__if you didn’t solve the problem completely on your own, treat the problem as though you never solved it at all__. Put it back into your rotation of problems. Mark it as something you need to try again from scratch.__Wait at least a day, and try to solve it fresh.__If you fail, rinse and repeat ad infinitum.And finally, structure the hell out of your learning. Make a schedule. Know exactly when you’re going to be working on this stuff, when you’re going to take breaks, when you’re going to go to lunch, etc. Build flexibility into your schedule, but have clear goals for how many hours a day you’ll spend studying.

# Interview Challenge sites

- Starfighter
- Stockfighter
- this is by Kalzumeus

# Front-end interview challenge / prep sites

# Interview Prep sites

- CareerCup
- rec'd by Choketsu

- rec'd by Choketsu
- Codility
- Lessons
- Challenges
- Rec'd by Toptal

- Cracking the Coding Interview - Video Interviews
- HackerRank
- rec'd by Choketsu

- InterviewBit
- via Tom A.

- Interview Cake
- Tech Interview Handbook (GitHub project)

# Non-Interview-Prep Challenge sites

- beat.my.code()
- Rec'd by Toptal

- CoderByte
- Codility
- CodingBat
- Kaggle
- Someone who works with machine learning explaining how Kaggle is a simplification of real ML work:

- LeetCode
- Polish Olympiad in Informatics (POI)
- Project Euler
- Random Observations - Solving Project Euler Problems
- Jason B Hill's Project Euler solutions
- Rec'd by Toptal, Chris Uga

- Sphere Online Judge (SPOJ)
- Top Coder

- USACO Training
- rec'd by Choketsu
- How to get started training at the USACO Gateway:
- What is it like to attend the USACO training camp?
- http://www.quora.com/USA-Computing-Olym ... ining-camp
- It's only a week
- New people just get 3 hours of lab/lecture in the morning
- The top guys do a contest every day. Sometimes the contest goes until after lunch, otherwise they just review after lunch. (Seems like 5 hrs/day)
- Then everyone has fun for the rest of the day

- If one is stuck on a particular section, is it worthwhile to keep on trying to solve the given problem, or should one move on to other sources in preparation for programming contests?
- Richard Peng, one of the most successful Canadian IOI competitors of all time, on the USACO training pages:
*"USACO training was put together before the major IOI escalation (Finland/Korea/Wisconsin). A lot of the techniques described on it are no longer useful on *OI and a lot of the 'hot' topics over the past few years are not covered. Also, a lot of the bottle necks on training are quite meaningless, and they typically cause a lot of frustration and time waste on the scale of months."*

# Topics

#### Linked Lists

#### Databases

**Dynamic Programming (DP)**

- http://en.wikipedia.org/wiki/Dynamic_programming
- Jesse Farmer - Intro to Dynamic Programming (blog post)
- https://activities.tjhsst.edu/sct/lectures/0405/dp1.pdf
*"Dynamic programming, often abbreviated "DP", is a technique to efficiently solve recursion problems -- problems whose solutions depend on solutions of smaller problems -- by storing partial results. Many times, it is obvious that a given problem is a recursion problem. However, it may not be so obvious that using DP will tremendously speed up the solution. We start by looking at an example."*

#### Heaps

#### Recursion

#### Trees

##### Binary Trees

#### The interview process

# Flashcards

- Here is an explanation of how to programmatically create Anki deck packages: http://decks.wikia.com/wiki/Anki_APKG_format_documentation
- Here's an example of people collaborating on an Anki deck: http://decks.wikia.com/wiki/Main_Page
- Javascript problem manager: https://github.com/imaginate/algorithmIV-question-manager
- https://www.oxbridgenotes.com/articles/janki_method_refined

- The stages of understanding: (think about it as high-level vs. low-level understanding, or broad vs. deep understanding)
- Broad / High-level: Recognition of terms / basic understanding of definitions
- High / Mid-level Knowing when to use a particular tool
- Mid/Low-level: Knowing how to do something
- Deep / Low-level: Knowing about tricky things / edge cases / less-common problems

- Algorithms
- Testing recognition / basic understanding
- What does "BFS" stand for?
- Acronym used in IK

- What does "BFS" stand for?
- Give an example of an O(X) algorithm. ← See 'The Pragmatic Programmer' for examples.
- Give an example of an O(1) algorithm.
- Give an example of an O(lg(n)) algorithm.
- "Binary search of a sorted list, traversing a binary tree, and finding the first set bit in a machine word(?)."

- Give an example of an O(n) algorithm.
- Exhaustive searches, finding the maximum value in an array, and generating checksums.

- Give an example of an O(m * n) algorithm.
- "This commonly occurs in simple sorting algorithms, such as bubble sort, where the outer loop scans each element in the array in turn, and the inner loop works out where to place that element in the sorted result."

- Give an example of an O(n*lg(n)) algorithm.
- Quicksort

- Give an example of an O(n^2) algorithm.
- Give an example of an O(n^3) algorithm.
- Give an example of an O(2^n) algorithm.
- Give an example of an O(n!) algorithm.
- "Whenever algorithms start looking at the permutations of things, their running times may get out of hand. (...) Examples include algorithms for many of the acknowledged 'hard' problems–the traveling salesman problem, optimally packing things into a container, partitioning a set of numbers so that each set has the same total, and so on. Often, heuristics are used to reduce the running times of these types of algorithms in particular problem domains."

- Testing recognition / basic understanding
- Arrays and other Ad-hoc problems
- Concurrency
- Dynamic Programming
- Graphs and other Data Structures
- Group coding mocks
- Group mocks on Concurrency
- Group mocks on Object Modeling
- Group mocks on Scalable Systems
- Linked Lists, Stacks, and Queues
- Object Modeling
- Orientation + Behavioral
- Recursion
- Scalable Systems
- Sorting
- Strings
- Trees
- Done - K-ary tree
- Used in IK

- BST
- Used in IK

- Done - K-ary tree