Not Just A Tester !: DATA STRUCTURES & ALGORITHMS

Overview
Why DSA?
Complexity

Time
Space

Asymptotic Notations

Big-O Notation (Ο)
Omega Notation (Ω)
Theta Notation (θ)

Data Structures

Linear

Array
Linked list
Stack
Queue

Non-Linear

Tree
Graph

String
Matrix
Heap
Hash Map
Hash Table

Algorithms

Searching

Linear Search
Binary Search
Ternary Search
Jump Search

Sorting

Bubble Sort
Insertion Sort
Selection Sort
Quick Sort
Merge Sort
Heap Sort
Counting Sort

Brute Force
Recursion
Divide and Conquer
Greedy
Hashing
Backtracking
Dynamic Programming
Pattern Searching / String Searching
Mathematical
Geometric
Bitwise
Two Pointers Technique
Sliding Window Technique

Practice Problems - Elemental

Print Prime Numbers
Print Factorial
Print Fibonacci Series
Reverse A Number
Identify a number as Palindrome
Swap two numbers without using a temporary variable
Get a distinct word list from the given file
Get a line with max word count from the given file
Find two lines with max characters in descending order
Find Divisors Of Given Number
Find Sum of Digits of a Number using Recursion
Check Armstrong number
Convert Binary to Decimal Format
Check Whether Given Number Is Binary Or Not
Convert Decimal to Binary Format
Fizz Buzz
Find Perfect Number
Square root of an integer
Count Perfect Squares less than N
Print Star Pattern

Practice Problems - Matrix

Spiral traversal on a Matrix
Search an element in a Matrix
Find median in a row wise sorted matrix
Find row with maximum no. of 1's
Print elements in sorted order using row-column wise sorted matrix
Maximum size rectangle
Find a specific pair in matrix
Rotate matrix by 90 degrees
Kth smallest element in a row-cpumn wise sorted matrix
Common elements in all rows of a given matrix

Practice Problems - Graph

Create a Graph, print it
Implement BFS algorithm
Implement DFS Algo
Detect Cycle in Directed Graph using BFS/DFS Algo
Detect Cycle in UnDirected Graph using BFS/DFS Algo
Search in a Maze
Minimum Step by Knight
flood fill algo
Clone a graph
Making wired Connections
word Ladder
Dijkstra algo
Implement Topological Sort
Minimum time taken by each job to be completed given by a Directed Acyclic Graph
Find whether it is possible to finish all tasks or not from given dependencies
Find the no. of Isalnds
Given a sorted Dictionary of an Alien Language, find order of characters
Implement Kruksal’sAlgorithm
Implement Prim’s Algorithm
Total no. of Spanning tree in a graph
Implement Bellman Ford Algorithm
Implement Floyd warshallAlgorithm
Travelling Salesman Problem
Graph ColouringProblem
Snake and Ladders Problem
Find bridge in a graph
Count Strongly connected Components(Kosaraju Algo)
Check whether a graph is Bipartite or Not
Detect Negative cycle in a graph
Longest path in a Directed Acyclic Graph
Journey to the Moon
Cheapest Flights Within K Stops
Oliver and the Game
Water Jug problem using BFS
Water Jug problem using BFS
Find if there is a path of more thank length from a source
M-ColouringProblem
Minimum edges to reverse o make path from source to destination
Paths to travel each nodes using each edge(Seven Bridges)
Vertex Cover Problem
Chinese Postman or Route Inspection
Number of Triangles in a Directed and Undirected Graph
Minimise the cashflow among a given set of friends who have borrowed money from each other
Two Clique Problem

Practice Problems - Heap

Implement a Maxheap/MinHeap using arrays and recursion.
Sort an Array using heap. (HeapSort)
“k” largest element in an array
Kth smallest and largest element in an unsorted array
Merge “K” sorted arrays
Merge 2 Binary Max Heaps
Leetcode- reorganize strings
Merge “K” Sorted Linked Lists
Smallest range in “K” Lists
Median in a stream of Integers
Check if a Binary Tree is Heap
Connect “n” ropes with minimum cost
Convert BST to Min Heap
Convert min heap to max heap
Rearrange characters in a string such that no two adjacent are same.
Minimum sum of two numbers formed from digits of an array

Practice Problems - Trie

Construct a trie from scratch
Find shortest unique prefix for every word in a given list
Given a sequence of words, print all anagrams together
Implement a Phone Directory
Print unique rows in a given boolean matrix

Practice Problems - Greedy Algorithm

Find Minimum number of Coins
Activity Selection Problem
Job SequencingProblem
Huffman Coding
Water Connection Problem
Fractional Knapsack Problem
Greedy Algorithm to find Minimum number of Coins
Maximum trains for which stoppage can be provided
Minimum Platforms Problem
Buy Maximum Stocks if i stocks can be bought on i-th day
Find the minimum and maximum amount to buy all N candies
Minimize Cash Flow among a given set of friends who have borrowed money from each other
Minimum Cost to cut a board into squares
Check if it is possible to survive on Island
Find maximum meetings in one room
Maximum product subset of an array
Maximize array sum after K negations
Maximize the sum of arr[i]*i
Maximum sum of absolute difference of an array
Maximize sum of consecutive differences in a circular array
Minimum sum of absolute difference of pairs of two arrays
Program for Shortest Job First (or SJF) CPU Scheduling
Program for Least Recently Used (LRU) Page Replacement algorithm
Smallest subset with sum greater than all other elements
Chocolate Distribution Problem
DEFKIN -Defense of a Kingdom
DIEHARD -DIE HARD
GERGOVIA -Wine trading in Gergovia
Picking Up Chicks
CHOCOLA –Chocolate
ARRANGE -Arranging Amplifiers
K Centers Problem
Minimum Cost of ropes
Job Scheduling
Find smallest number with given number of digits and sum of digits
Rearrange characters in a string such that no two adjacent are same
Find maximum sum possible equal sum of three stacks

Practice Problems - BackTracking

Permutations of the given string
Rat in a maze Problem
Printing all solutions in N-Queen Problem
Remove Invalid Parentheses
Sudoku Solver
m Coloring Problem
Print all palindromic partitions of a string
Subset Sum Problem
The Knight’s tour problem
Tug of War
Find shortest safe route in a path with landmines
Combinational Sum
Find Maximum number possible by doing at-most K swaps
Print all permutations of a string
Find if there is a path of more than k length from a source
Longest Possible Route in a Matrix with Hurdles
Print all possible paths from top left to bottom right of a mXn matrix
Partition of a set intoK subsets with equal sum
Find the K-th Permutation Sequence of first N natural numbers

Practice Problems - Dynamic Programming

Coin ChangeProblem
Knapsack Problem
Binomial CoefficientProblem
Permutation CoefficientProblem
Program for nth Catalan Number
Matrix Chain Multiplication
Edit Distance
Subset Sum Problem
Friends Pairing Problem
Gold Mine Problem
Assembly Line SchedulingProblem
Painting the Fenceproblem
Maximize The Cut Segments
Longest Common Subsequence
Longest Repeated Subsequence
Longest Increasing Subsequence
Longest Common Substring
LCS (Longest Common Subsequence) of three strings
Space Optimized Solution of LCS
Maximum Sum Increasing Subsequence
Count all subsequences having product less than K
Longest subsequence such that difference between adjacent is one
Maximum subsequence sum such that no three are consecutive
Egg Dropping Problem
Maximum Length Chain of Pairs
Maximum size square sub-matrix with all 1s
Maximum sum of pairs with specific difference
Min Cost PathProblem
Maximum difference of zeros and ones in binary string
Minimum number of jumps to reach end
Minimum cost to fill given weight in a bag
Minimum removals from array to make max –min <= K
Count number of ways to reacha given score in a game
Count Balanced Binary Trees of Height h
Unbounded Knapsack (Repetition of items allowed)
Word Break Problem
Largest Independent Set Problem
Partition problem
Longest Palindromic Subsequence
Count All Palindromic Subsequence in a given String
Longest Palindromic Substring
Longest alternating subsequence
Weighted Job Scheduling
Coin game winner where every player has three choices
Count Derangements (Permutation such that no element appears in its original position)
Maximum profit by buying and selling a share at most twice
Optimal Strategy for a Game
Optimal Binary Search Tree
Palindrome PartitioningProblem
Word Wrap Problem
Mobile Numeric Keypad Problem
Boolean Parenthesization Problem
Largest rectangular sub-matrix whose sum is 0
Largest area rectangular sub-matrix with equal number of 1’s and 0’s
Maximum sum rectangle in a 2D matrix
Maximum profit by buying and selling a share at most k times
Find if a string is interleaved of two other strings
Maximum Length of Pair Chain

Practice Problems - Bit Manipulation

Count set bits in an integer
Find the two non-repeating elements in an array of repeating elements
Count number of bits to be flipped to convert A to B
Count total set bits in all numbers from 1 to n
Program to find whether a no is power of two
Find position of the only set bit
Copy set bits in a range
Divide two integers without using multiplication, division and mod operator
Calculate square of a number without using *, / and pow()
Power Set

Practice Problems - Searching & Sorting

First and last occurrences of an element
Find a Fixed Point (Value equal to index) in a given array
Search an element in a sorted and rotated array
Search an element in a sorted and infinite array
Optimum location of point to minimize total distance
Find the repeating and the missing numbers
Majority Elements / Boyer–Moore Majority Vote Algorithm
Searching in an array where adjacent differ by at most k
Find A Pair With A Given Difference
Find Four Elements That Sums To A Given Value
Find Maximum Sum Such That No 2 Elements Are Adjacent
Product Array Puzzle
Sort Array According To Count Of Set Bits
Minimum Number Of Swaps Required To Sort An Array
Kth Smallest Number Again
Find Pivot Element In A Sorted Array
Kth Element of Two Sorted Arrays
Missing Number in AP
Smallest number with at least n trailing zeroes in factorial
Subset Sums
Implement Merge-sort in-place
Partitioning and Sorting Arrays with Many Repeated Entries
Aggressive cows
Book Allocation Problem
Painters Partition Problem
Bishu and Soldiers
Rasta and Kheshtak
Roti Prata - SPOJ
Double Helix - SPOJ
EKO - SPOJ

Practice Problems - Pattern Searching / SubString Search

Rabin-Karp Algorithm
Knuth-Morris-Pratt (KMP) Algorithm
Boyer Moore Algorithm