Tuesday, January 23, 2018

Algos: Qestions






Algorithms


Topics :
Analysis of Algorithms:
  1. Asymptotic Analysis
  2. Worst, Average and Best Cases
  3. Asymptotic Notations
  4. Little o and little omega notations
  5. Analysis of Loops
  6. Solving Recurrences
  7. Amortized Analysis
  8. What does ‘Space Complexity’ mean?
  9. Pseudo-polynomial Algorithms
  10. NP-Completeness Introduction
  11. Polynomial Time Approximation Scheme
  12. A Time Complexity Question
  13. Time Complexity of building a heap
  14. Time Complexity where loop variable is incremented by 1, 2, 3, 4 ..
  15. Time Complexity of Loop with Powers
  16. Performance of loops (A caching question)


Pattern Searching:
  1. Naive Pattern Searching
  2. KMP Algorithm
  3. Rabin-Karp Algorithm
  4. A Naive Pattern Searching Question
  5. Finite Automata
  6. Efficient Construction of Finite Automata
  7. Boyer Moore Algorithm – Bad Character Heuristic
  8. Suffix Array
  9. Anagram Substring Search (Or Search for all permutations)
  10. Pattern Searching using a Trie of all Suffixes
  11. Aho-Corasick Algorithm for Pattern Searching
  12. kasai’s Algorithm for Construction of LCP array from Suffix Array
  13. Z algorithm (Linear time pattern searching Algorithm)

Other String Algorithms:
  1. Manacher’s Algorithm – Linear Time Longest Palindromic Substring – Part 1, Part 2, Part 3, Part 4
  2. Longest Even Length Substring such that Sum of First and Second Half is same
  3. Print all possible strings that can be made by placing spaces

Backtracking:
  1. Print all permutations of a given string
  2. The Knight’s tour problem
  3. Rat in a Maze
  4. N Queen Problem
  5. Subset Sum
  6. m Coloring Problem
  7. Hamiltonian Cycle
  8. Sudoku
  9. Tug of War
  10. Solving Cryptarithmetic Puzzles

Divide and Conquer:
  1. Introduction
  2. Write your own pow(x, n) to calculate x*n
  3. Median of two sorted arrays
  4. Count Inversions
  5. Closest Pair of Points
  6. Strassen’s Matrix Multiplication

Geometric Algorithms:
  1. Closest Pair of Points | O(nlogn) Implementation
  2. How to check if two given line segments intersect?
  3. How to check if a given point lies inside or outside a polygon?
  4. Convex Hull | Set 1 (Jarvis’s Algorithm or Wrapping)
  5. Convex Hull | Set 2 (Graham Scan)
  6. Given n line segments, find if any two segments intersect
  7. Check whether a given point lies inside a triangle or not
  8. How to check if given four points form a square



Randomized Algorithms:
  1. Linearity of Expectation
  2. Expected Number of Trials until Success
  3. Randomized Algorithms | Set 0 (Mathematical Background)
  4. Randomized Algorithms | Set 1 (Introduction and Analysis)
  5. Randomized Algorithms | Set 2 (Classification and Applications)
  6. Randomized Algorithms | Set 3 (1/2 Approximate Median)
  7. Karger’s algorithm for Minimum Cut
  8. K’th Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time)
  9. Reservoir Sampling
  10. Shuffle a given array
  11. Select a Random Node from a Singly Linked List
Branch and Bound:
  1. Branch and Bound | Set 1 (Introduction with 0/1 Knapsack)
  2. Branch and Bound | Set 2 (Implementation of 0/1 Knapsack)
  3. Branch and Bound | Set 3 (8 puzzle Problem)
  4. Branch And Bound | Set 4 (Job Assignment Problem)
  5. Branch and Bound | Set 5 (N Queen Problem)
  6. Branch And Bound | Set 6 (Traveling Salesman Problem)


Quizzes on Algorithms:
  1. Analysis of Algorithms
  2. Sorting
  3. Divide and Conquer
  4. Greedy Algorithms
  5. Dynamic Programming
  6. Backtracking
  7. Misc
  8. NP Complete
  9. Searching
  10. Analysis of Algorithms (Recurrences)
  11. Recursion
  12. Bit Algorithms
  13. Graph Traversals
  14. Graph Shortest Paths
  15. Graph Minimum Spanning Tree
Misc:
  1. Commonly Asked Algorithm Interview Questions | Set 1
  2. Given a matrix of ‘O’ and ‘X’, find the largest subsquare surrounded by ‘X’
  3. Nuts & Bolts Problem (Lock & Key problem)
  4. Flood fill Algorithm – how to implement fill() in paint?
  5. Given n appointments, find all conflicting appointments
  6. Check a given sentence for a given set of simple grammer rules
  7. Find Index of 0 to be replaced with 1 to get longest continuous sequence of 1s in a binary array
  8. How to check if two given sets are disjoint?
  9. Minimum Number of Platforms Required for a Railway/Bus Station
  10. Length of the largest subarray with contiguous elements | Set 1
  11. Length of the largest subarray with contiguous elements | Set 2
  12. Print all increasing sequences of length k from first n natural numbers
  13. Given two strings, find if first string is a subsequence of second
  14. Snake and Ladder Problem
  15. Write a function that returns 2 for input 1 and returns 1 for 2
  16. Connect n ropes with minimum cost
  17. Find the number of valid parentheses expressions of given length
  18. Longest Monotonically Increasing Subsequence Size (N log N): Simple implementation
  19. Generate all binary permutations such that there are more 1’s than 0’s at every point in all permutations
  20. Lexicographically minimum string rotation
  21. Construct an array from its pair-sum array
  22. Program to evaluate simple expressions
  23. Check if characters of a given string can be rearranged to form a palindrome
  24. Print all pairs of anagrams in a given array of strings
Please see Data Structures and Advanced Data Structures for Graph, Binary Tree, BST and Linked List based algorithms.
We will be adding more categories and posts to this page soon.
You can create a new Algorithm topic and discuss it with other geeks using our portal PRACTICE. See recently added problems on Algorithms on PRACTICE.
at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)