Datastructures

This page has useful links for data structures and algorithms. This is a work in progress.

Top 10 interview questions in each category

Linked lists and arrays:

When to use Linked list over arrays
Optimally searching square and rectangular arrays 2d - Saddleback algo and variants O(n*log(m/n))

Trees (chapter 4):
Difference between trees and graphs
Why balanced trees what are balanced trees

Difference between balanced subtrees and unbalanced

Difference between tree traversals - examples
Why is binary search the de-factor as opposed to ternary or any other search

Heaps
Minimum spanning tree design and implemtnation - Heaps are used for MST
How to implement malloc() functionality PDF

Graphs
Breadth first tree traversal - recursive vs iterative
Depth first traversal - recursive and iterative

Recursion & Dynamic programming
How dynamic programming or memoization reduces recursion with an example
Matrix chain multiplication - find the minimum cost

Bit manipulation
Count number of 1s in a number (Definitely check out the Brian kerningham approach n &= (n-1))

Mathematical problems
Evaluate postfix notation in Java
Eratosthenes Sieve for finding primes [Regular Sieve] [Segmented Sieve]
Using montecarlo simulations to calculate the value of Pi
McCarthy91 and its significance in formal verification
Euclidean Algorithm for finding the GCD of two numbers

Puzzles
N doors and N passes, which door is open in the end? Rickety bridge one torch soln Download