Syllabus.md

Syllabus

Analysis of Algorithms

• Asymptotic Analysis
• Worst, Average and Best Cases
• Asymptotic Notations
• Little o and little omega notations
• Lower and Upper Bound Theory
• Analysis of Loops
• Solving Recurrences
• Amortized Analysis
• What does ‘Space Complexity’ mean?
• Pseudo-polynomial Algorithms
• NP-Completeness Introduction
• Polynomial Time Approximation Scheme
• Time Complexity of building a heap
• Time Complexity where loop variable is incremented by 1, 2, 3, 4 ..
• Time Complexity of Loop with Powers
• Performance of loops (A caching question)

Searching

• Linear Search
• Binary Search
• Jump Search
• Interpolation Search
• Exponential Search
• Ternary Search
• Interpolation search vs Binary search

Sorting

• Selection Sort
• Bubble Sort
• Insertion Sort
• Merge Sort
• Heap Sort
• QuickSort
• Radix Sort
• Counting Sort
• Bucket Sort
• ShellSort
• Comb Sort
• Pigeonhole Sort
• Cycle Sort
• Stability in sorting algorithms
• When does the worst case of Quicksort occur?
• Lower bound for comparison based sorting algorithms
• Which sorting algorithm makes minimum number of memory writes?

Codes on Searching and Sorting

• Find the Minimum length Unsorted Subarray, sorting which makes the complete array sorted
• Merge Sort for Linked Lists
• Sort a nearly sorted (or K sorted) array
• Iterative Quick Sort
• QuickSort on Singly Linked List
• QuickSort on Doubly Linked List
• Find k closest elements to a given value
• Sort n numbers in range from 0 to n^2 – 1 in linear time
• A Problem in Many Binary Search Implementations
• Search in an almost sorted array
• Sort an array in wave form
• Why is Binary Search preferred over Ternary Search?
• K’th Smallest/Largest Element in Unsorted Array
• Find the closest pair from two sorted arrays
• Find common elements in three sorted arrays
• Given a sorted array and a number x, find the pair in array whose sum is closest to x
• Count 1’s in a sorted binary array
• Binary Insertion Sort
• Insertion Sort for Singly Linked List
• Why Quick Sort preferred for Arrays and Merge Sort for Linked Lists?
• Merge Sort for Doubly Linked List
• Minimum adjacent swaps to move maximum and minimum to corners

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
  • Prim’s MST for Adjacency List Representation
• Dijkstra’s Shortest Path Algorithm
  • Dijkstra’s Algorithm for Adjacency List Representation
• Job Sequencing Problem
• Greedy Algorithm to find Minimum number of Coins
• K Centers Problem
• Minimum Number of Platforms Required for a Railway/Bus Station

Dynamic Programming

• Overlapping Subproblems Property
• Optimal Substructure Property
• Longest Increasing Subsequence
• Longest Common Subsequence
• Edit Distance
• Min Cost Path
• Coin Change
• Matrix Chain Multiplication
• Binomial Coefficient
• 0-1 Knapsack Problem
• Egg Dropping Puzzle
• Longest Palindromic Subsequence
• Cutting a Rod
• Maximum Sum Increasing Subsequence
• Longest Bitonic Subsequence
• Floyd Warshall Algorithm
• Palindrome Partitioning
• Partition problem
• Word Wrap Problem
• Maximum Length Chain of Pairs
• Variations of LIS
• Box Stacking Problem
• Program for Fibonacci numbers
• Minimum number of jumps to reach end
• Maximum size square sub-matrix with all 1s
• Ugly Numbers
• Largest Sum Contiguous Subarray
• Longest Palindromic Substring
• Bellman–Ford Algorithm for Shortest Paths
• Optimal Binary Search Tree
• Largest Independent Set Problem
• Subset Sum Problem
• Maximum sum rectangle in a 2D matrix
• Count number of binary strings without consecutive 1?s
• Boolean Parenthesization Problem
• Count ways to reach the n’th stair
• Minimum Cost Polygon Triangulation
• Mobile Numeric Keypad Problem
• Count of n digit numbers whose sum of digits equals to given sum
• Minimum Initial Points to Reach Destination
• Total number of non-decreasing numbers with n digits
• Find length of the longest consecutive path from a given starting character
• Tiling Problem
• Minimum number of squares whose sum equals to given number n
• Find minimum number of coins that make a given value
• Collect maximum points in a grid using two traversals
• Shortest Common Supersequence
• Compute sum of digits in all numbers from 1 to n
• Count possible ways to construct buildings
• Maximum profit by buying and selling a share at most twice
• How to print maximum number of A’s using given four keys
• Find the minimum cost to reach destination using a train
• Vertex Cover Problem | Set 2 (Dynamic Programming Solution for Tree)
• Count number of ways to reach a given score in a game
• Weighted Job Scheduling
• Longest Even Length Substring such that Sum of First and Second Half is same

Pattern Searching

• Naive Pattern Searching
• KMP Algorithm
• Rabin-Karp Algorithm
• A Naive Pattern Searching Question
• Finite Automata
• Efficient Construction of Finite Automata
• Boyer Moore Algorithm – Bad Character Heuristic
• Suffix Array
• Anagram Substring Search (Or Search for all permutations)
• Pattern Searching using a Trie of all Suffixes
• Aho-Corasick Algorithm for Pattern Searching
• kasai’s Algorithm for Construction of LCP array from Suffix Array
• Z algorithm (Linear time pattern searching Algorithm)
• Program to wish Women’s Day

Other String Algorithms

• Manacher’s Algorithm – Linear Time Longest Palindromic Substring
• Longest Even Length Substring such that Sum of First and Second Half is same
• Print all possible strings that can be made by placing spaces

Backtracking

• Print all permutations of a given string
• The Knight’s tour problem
• Rat in a Maze
• N Queen Problem
• Subset Sum
• m Coloring Problem
• Hamiltonian Cycle
• Sudoku
• Tug of War
• Solving Cryptarithmetic Puzzles

Divide and Conquer

• Introduction
• Write your own pow(x, n) to calculate x*n
• Median of two sorted arrays
• Count Inversions
• Closest Pair of Points
• Strassen’s Matrix Multiplication
• Quick Sort vs Merge Sort

Geometric Algorithms

• Closest Pair of Points
• How to check if two given line segments intersect?
• How to check if a given point lies inside or outside a polygon?
• Convex Hull
  • Jarvis’s Algorithm or Wrapping
  • Graham Scan
• Given n line segments, find if any two segments intersect
• Check whether a given point lies inside a triangle or not
• How to check if given four points form a square

Mathematical Algorithms

• Write an Efficient Method to Check if a Number is Multiple of 3
• Efficient way to multiply with 7
• Write a C program to print all permutations of a given string
• Lucky Numbers
• Write a program to add two numbers in base 14
• Babylonian method for square root
• Multiply two integers without using multiplication, division and bitwise operators, and no loops
• Print all combinations of points that can compose a given number
• Write you own Power without using multiplication(*) and division(/) operators
• Program for Fibonacci numbers
• Average of a stream of numbers
• Count numbers that don’t contain 3
• MagicSquare
• Sieve of Eratosthenes
• Number which has the maximum number of distinct prime factors in the range M to N
• Find day of the week for a given date
• DFA based division
• Generate integer from 1 to 7 with equal probability
• Given a number, find the next smallest palindrome
• Make a fair coin from a biased coin
• Check divisibility by 7
• Find the largest multiple of 3
• Lexicographic rank of a string
• Print all permutations in sorted (lexicographic) order
• Shuffle a given array
• Space and time efficient Binomial Coefficient
• Reservoir Sampling
• Pascal’s Triangle
• Select a random number from stream, with O(1) space
• Find the largest multiple of 2, 3 and 5
• Efficient program to calculate e^x
• Measure one litre using two vessels and infinite water supply
• Efficient program to print all prime factors of a given number
• Print all possible combinations of r elements in a given array of size n
• Random number generator in arbitrary probability distribution fashion
• How to check if a given number is Fibonacci number?
• Russian Peasant Multiplication
• Count all possible groups of size 2 or 3 that have sum as multiple of 3
• Tower of Hanoi
• Horner’s Method for Polynomial Evaluation
• Count trailing zeroes in factorial of a number
• Program for nth Catalan Number
• Generate one of 3 numbers according to given probabilities
• Find Excel column name from a given column number
• Find next greater number with same set of digits
• Count Possible Decodings of a given Digit Sequence
• Calculate the angle between hour hand and minute hand
• Count number of binary strings without consecutive 1?s
• Find the smallest number whose digits multiply to a given number n
• Draw a circle without floating point arithmetic
• How to check if an instance of 8 puzzle is solvable?
• Birthday Paradox
• Multiply two polynomials
• Count Distinct Non-Negative Integer Pairs (x, y) that Satisfy the Inequality xx + yy < n
• Count ways to reach the n’th stair
• Replace all ‘0’ with ‘5’ in an input Integer
• Program to add two polynomials
• Print first k digits of 1/n where n is a positive integer
• Given a number as a string, find the number of contiguous subsequences which recursively add up to 9
• Program for Bisection Method
• Program for Method Of False Position
• Program for Newton Raphson Method

Bit Algorithms

• Find the element that appears once
• Detect opposite signs
• Set bits in all numbers from 1 to n
• Swap bits
• Add two numbers
• Smallest of three
• A Boolean Array Puzzle
• Set bits in an (big) array
• Next higher number with same number of set bits
• Optimization Technique (Modulus)
• Add 1 to a number
• Multiply with 3.5
• Turn off the rightmost set bit
• Check for Power of 4
• Absolute value (abs) without branching
• Modulus division by a power-of-2-number
• Minimum or Maximum of two integers
• Rotate bits
• Find the two non-repeating elements in an array
• Number Occurring Odd Number of Times
• Check for Integer Overflow
• Little and Big Endian
• Reverse Bits of a Number
• Count set bits in an integer
• Number of bits to be flipped to convert A to B
• Next Power of 2
• Check if a Number is Multiple of 3
• Find parity
• Multiply with 7
• Find whether a no is power of two
• Position of rightmost set bit
• Binary representation of a given number
• Swap all odd and even bits
• Find position of the only set bit
• Karatsuba algorithm for fast multiplication
• How to swap two numbers without using a temporary variable?
• Check if a number is multiple of 9 using bitwise operators
• Swap two nibbles in a byte
• How to turn off a particular bit in a number?
• Check if binary representation of a number is palindrome

Graph Algorithms

• Graph and its representations
• Breadth First Traversal for a Graph
• Depth First Traversal for a Graph
• Applications of Depth First Search
• Detect Cycle
  • Directed Graph
  • Undirected Graph
• Longest Path in a Directed Acyclic Graph
• Topological Sorting
• Check whether a given graph is Bipartite or not
• Snake and Ladder Problem
• Biconnected Components
• Check if a given graph is tree or not

Minimum Spanning Tree

• Prim’s Minimum Spanning Tree (MST))
• Applications of Minimum Spanning Tree Problem
• Prim’s MST for Adjacency List Representation
• Kruskal’s Minimum Spanning Tree Algorithm
• Boruvka’s algorithm for Minimum Spanning Tree

Shortest Paths

• Dijkstra’s shortest path algorithm
  • Dijkstra’s Algorithm for Adjacency List Representation
• Bellman–Ford Algorithm
• Floyd Warshall Algorithm
• Johnson’s algorithm for All-pairs shortest paths
• Shortest Path in Directed Acyclic Graph
• Some interesting shortest path questions
• Shortest path with exactly k edges in a directed and weighted graph

Connectivity

• Find if there is a path between two vertices in a directed graph
• Connectivity in a directed graph
• Articulation Points (or Cut Vertices) in a Graph
• Biconnected graph
• Bridges in a graph
• Eulerian path and circuit
• Fleury’s Algorithm for printing Eulerian Path or Circuit
• Strongly Connected Components
• Transitive closure of a graph
• Find the number of islands
• Count all possible walks from a source to a destination with exactly k edges
• Euler Circuit in a Directed Graph
• Biconnected Components
• Tarjan’s Algorithm to find Strongly Connected Components

Hard Problems

• Graph Coloring (Introduction and Applications)
• Greedy Algorithm for Graph Coloring
• Travelling Salesman Problem (Naive and Dynamic Programming)
• Travelling Salesman Problem (Approximate using MST)
• Hamiltonian Cycle
• Vertex Cover Problem (Introduction and Approximate Algorithm)
• K Centers Problem (Greedy Approximate Algorithm)

Maximum Flow

• Ford-Fulkerson Algorithm for Maximum Flow Problem
• Find maximum number of edge disjoint paths between two vertices
• Find minimum s-t cut in a flow network
• Maximum Bipartite Matching
• Channel Assignment Problem

Misc

• Find if the strings can be chained to form a circle
• Given a sorted dictionary of an alien language, find order of characters
• Karger’s algorithm for Minimum Cut
• Hopcroft–Karp Algorithm for Maximum Matching
• Length of shortest chain to reach a target word
• Find same contacts in a list of contacts
• Commonly Asked Algorithm Interview Questions
• Given a matrix of ‘O’ and ‘X’, find the largest subsquare surrounded by ‘X’
• Nuts & Bolts Problem (Lock & Key problem)
• Flood fill Algorithm – how to implement fill() in paint?
• Given n appointments, find all conflicting appointments
• Check a given sentence for a given set of simple grammer rules
• Find Index of 0 to be replaced with 1 to get longest continuous sequence of 1s in a binary array
• How to check if two given sets are disjoint?
• Minimum Number of Platforms Required for a Railway/Bus Station
• Length of the largest subarray with contiguous elements
• Print all increasing sequences of length k from first n natural numbers
• Given two strings, find if first string is a subsequence of second
• Snake and Ladder Problem
• Write a function that returns 2 for input 1 and returns 1 for 2
• Connect n ropes with minimum cost
• Find the number of valid parentheses expressions of given length
• Longest Monotonically Increasing Subsequence Size (N log N)
• Generate all binary permutations such that there are more 1’s than 0’s at every point in all permutations
• Lexicographically minimum string rotation
• Construct an array from its pair-sum array
• Program to evaluate simple expressions
• Check if characters of a given string can be rearranged to form a palindrome
• Print all pairs of anagrams in a given array of strings

Randomized Algorithms

• Linearity of Expectation
• Expected Number of Trials until Success
• Randomized
  • Mathematical Background
  • Introduction and Analysis
  • Classification and Applications
  • 1/2 Approximate Median
• Karger’s algorithm for Minimum Cut
• K’th Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time)
• Reservoir Sampling
• Shuffle a given array
• Select a Random Node from a Singly Linked List

Branch and Bound

• Introduction with 0/1 Knapsack
• Implementation of 0/1 Knapsack
• 8 puzzle Problem
• Job Assignment Problem
• N Queen Problem
• Traveling Salesman Problem