/reminder

coding interview preparation

reminder

coding interview preparation

Dynamic Programming

  • Longest Common Subsequence
  • Longest Increasing Subsequence
  • Edit Distance
  • Minimum Partition
  • Ways to Cover a Distance
  • Longest Path In Matrix
  • Subset Sum Problem
  • Optimal Strategy for a Game
  • 0-1 Knapsack Problem
  • Assembly Line Scheduling
  • Optimal Binary Search Tree
  • All DP Algorithms

BackTracking

  • Rat in a Maze
  • N Queen Problem
  • Subset Sum
  • m Coloring Problem
  • Hamiltonian Cycle

Greedy Algorithms

  • Activity Selection Problem
  • Kruskal’s Minimum Spanning Tree Algorithm
  • Huffman Coding
  • Efficient Huffman Coding for Sorted Input
  • Prim’s Minimum Spanning Tree Algorithm

Graph Algorithms : One of the most important topic which you can not ignore if preparing for ACM – ICPC.

  • Breadth First Search (BFS)
  • Depth First Search (DFS)
  • Shortest Path from source to all vertices Dijkstra
  • Shortest Path from every vertex to every other vertex Floyd Warshall
  • Minimum Spanning tree Prim
  • Minimum Spanning tree Kruskal
  • Topological Sort
  • Johnson’s algorithm
  • Articulation Points (or Cut Vertices) in a Graph
  • Bridges in a graph
  • All Graph Algorithms

Basic Mathematics

Arithmetic :

Programmers must know how integers and real numbers are represented internally and should be able to code high-precision numbers. Bit manipulation tricks and knowing library functions for number basic arithmetic would be very helpful.

Number theory : Knowing some of these concepts would save a lot of time and efforts while programming in the contests.

  • Modular Exponentiation
  • Modular multiplicative inverse
  • Primality Test | Set 2 (Fermat Method)
  • Euler’s Totient Function
  • Sieve of Eratosthenes
  • Convex Hull
  • Basic and Extended Euclidean algorithms
  • Segmented Sieve
  • Chinese remainder theorem
  • Lucas Theorem

Combinatorics :

Although directly might not seam to be important, Combinatorics is important to estimate asymptotic complexity of algorithms.

Analysis of Algorithms

  • Combinatorial Game Theory | Set 1 (Introduction)

Geometrical Algorithms

  • Convex Hull

  • Graham Scan

  • Line Intersection

  • Matrix Exponentiation and this

  • Online construction of 3-D convex hull

  • Bentley Ottmann algorithm to list all intersection points of n line segments

  • Rotating Calipers Technique

  • Area/Perimeter of Union of Rectangles

  • Closest pair of points

  • Area of Union of Circles

  • Delaunay Triangulation of n points

  • Voronoi Diagrams of n points using Fortune’s algorithm

  • Point in a polygon problem

  • Network Flow Algorithms

  • Maxflow Ford Furkerson Algo and Edmond Karp Implementation

  • Min cut

  • Stable Marriage Problem

  • Maximum flow using Dinic’s Algorithm

  • Minimum Cost Flow Problem

  • Successive Shortest path Algorithm

  • Cycle Cancelling algorithm

  • Maximum weighted Bipartite Matching (Kuhn Munkres algorithm/Hungarian Method)

  • Hungarian Algorithm Wiki

  • Hungarian Algorithm for Assignment Problem

  • Maximum Bipartite Matching

  • Stoer Wagner min-cut algorithm

  • Maximum matching in general graph (Blossom Shrinking)

  • Gomory-Hu Trees

  • Chinese Postman problem(Please see this too)

  • Hopcroft–Karp Algorithm for Maximum Matching

More Advanced Stuff

  • Bit Algorithms
  • Randomized Algorithms
  • Branch and Bound
  • Mathematical Algorithms
  • Heavy Light Decomposition
  • A* Search