Code Monkey home page Code Monkey logo

algoriths's Introduction

The 10 must-know algorithms and data structures for an engineer

img01


10! In current competitive world, this question should be renamed to 100 must-know algorithms. Still, lets try to categorize the algorithms in 10 broad categories.

But first, learning such a small subset(only 10!) will do no good. The more you learn, the more you will stand out from the crowd.

Learning and visualizing algorithms will change the way you tackle real life situation, you will always start looking for an optimized way to do things. And that's great, that's what smart people are - LAZY, yes, they always try to do more work with minimal effort and that's optimization.

Start developing algorithmic thinking by visualizing algorithms.

This is what I will recommend IDeserve

It's a cool platform where you can visualize the algorithms and data structures within it. I feel it is largest source for algorithms which you can visualize. Its pretty cool to see algorithms being executed and animated on the fly.

img02

Coming back to categorizing algorithms into 10 broad categories...phew...now this will take time.


1: Sorting Algorithms

Sorting Algorithm - Bubble Sort

Sorting Algorithm - Selection Sort

Sorting Algorithm - Insertion Sort

Sorting Algorithm - Heap Sort

Sorting Algorithm - Merge Sort

Pancake Sorting


2: Algorithms on Linked Lists

Reverse a Linked List - Iterative

Reverse a Linked List - Recursive

Merge two sorted linked lists

Find intersection of two Linked Lists

Find intersection of two Linked Lists - O(m + n) Time Complexity and O(1) Space Complexity

Detect a loop in a linked list and find the node where the loop starts

Convert a binary tree to doubly linked list

Convert a sorted Doubly Linked List to Balanced Binary Search Tree

LRU Cache Implementation


3: Algorithms on Arrays

Count frequencies of array elements in range 1 to n

Find all permutations of a String

Binary Search in a Sorted Array

Leaders in an array

Find a Peak Element in an array

Find pivot in a sorted rotated array

Find an element in a sorted rotated array

Find element in sorted rotated array without finding pivot

Find duplicates in an integer array

Maximum average subarray

Maximum subarray sum

Next greater element in an array

Fibonacci Number

Rotate an Array

Find Majority Element in an Array

Find median of two sorted arrays

First non-repeating character in a string

Re-arrange elements in an array to put positive and negative elements in alternate order

Find the next greater number using same digits

Longest Substring with non-Repeating Characters

Given an array with all distinct elements, find the length of the longest sub-array which has elements(not in any particular order) that could form a contiguous sequence

Find minimum cost path in a matrix

Find the length of longest increasing subsequence in an array

Find the longest increasing subsequence in an array O(n logn)

Find the length of longest bitonic subsequence in an array

Find total number of ways to make change using given set of coins

Minimum number of coins to make change

Count all possible decodings of a given digit sequence

Find increasing sub-sequence of length three having maximum product

Find increasing sub-sequence of length three having maximum product | Optimized approach

Find index of 0 to replace to get longest continuous sequence of 1s

O(n) time approach to find index of 0 to replace to get longest continuous sequence of 1s

Find an integer array corresponding to the string specifying increase-decrease transitions

Given an array with all distinct elements, find the length of the longest sub-array which has elements(not in any particular order) that could form a contiguous sequence

Merge two sorted arrays without using extra space

0-1 Knapsack Problem

The Skyline Problem

Search a sorted matrix

Buy and sell stocks - 1

Buy and sell stocks - 2

Gold Mine Problem

Distribute Chocolates Problem

Trapping Rain Water between Towers

Find Minimum Length Sub Array With Sum K


5: Algorithms on Trees

Check if a binary tree is a binary search tree

Check if two nodes are cousins in a Binary tree

Remove all nodes which lie on path having sum less than k

Binary Search tree | Insertion and Search

Binary Search tree | Deletion

Binary Tree Level Order Traversal

Print bottom view of a binary tree

Print bottom view of a binary tree using level order traversal

Check if a binary tree is balanced or not

Check if a binary tree is sub-tree of another binary tree in space O(1)

Check if a binary tree is sub-tree of another binary tree in time O(n)

Check if all internal nodes of BST have only one child without building tree

Check if a given binary tree is symmetric tree or not

Check if two binary search trees are identical given their array representations

Check if two binary search trees are identical given their array representations | Set 2

Check if the given n-ary tree is symmetric tree or not

Check if two binary trees are identical

Convert a binary tree to doubly linked list

Convert a sorted Doubly Linked List to Balanced Binary Search Tree

Create a balanced Binary Search Tree from a sorted array

Check whether a binary tree is complete or not

Check whether a binary tree is a full binary tree or not

Construct binary tree from inorder and postorder traversals

Construct binary tree from inorder and preorder traversals

Construct the binary tree from its parent array representation

AVL tree | Basics

AVL tree | Insertion

AVL tree | Deletion

Convert binary tree to binary search tree

Find depth of deepest odd level leaf node

Diagonal Sum of a Binary Tree

Find height of the binary tree from its parent array representation

Find sum of all left leaves of a binary tree

Find floor and ceiling of an element from given dataset using binary search tree

Recover a Binary Search Tree if positions of two nodes are swapped

In-order Successor of a Node in a Binary Tree

In-order Traversal of a Binary Tree

Print left view of a binary tree

Lowest Common Ancestor of 2 nodes in a Binary Tree

Minimum Depth of a Binary Tree

Convert a binary tree to its mirror tree

Convert the given n-ary tree to its mirror image

Trie Data Structure | Insert and search

Trie Data Structure | Delete

Pattern matching using Trie

Longest Prefix Matching using Trie

Post-order Traversal of a Binary Tree

Pre-order Traversal of a Binary Tree

Print all Root to Leaf paths of a Binary Tree

Print binary tree in vertical order

Print all nodes of a binary tree that do not have sibling

Remove all the half nodes from a given binary tree

Remove the nodes of binary search tree which are outside the given range

Print right view of a binary tree

Serialize and Deserialize a binary search tree using post order traversal

Serialize and Deserialize a binary search tree

Find the size of largest BST in a binary tree

Print top view of a binary tree using level order traversal

Print top view of a binary tree

Total number of possible Binary Search Trees with n keys

Given a sequence of words, group together all anagrams and print them


7: Algorithms on Strings

Word Break Problem

Reverse words in a string

Find all permutations of a String

Find minimum edit distance between given two strings

To print maximum number of As using given four keys

Check balanced parentheses in a string

Distinct binary strings of length n with no consecutive 1s

Finding 10 letter repeated DNA sequences

First non-repeating character in a string

Group all anagrams together from a given array of strings | Set 1

Longest Common Subsequence

Longest Common Substring

Longest Palindromic Subsequence

Longest Palindromic Substring

Longest Substring with non-Repeating Characters

Palindrome Min Cut

Shortest Palindrome

The longest prefix suffix array computation in KMP pattern matching algorithm

The Knuth Morris Pratt algorithm for pattern matching


8: Algorithms on Graphs

Bellman-Ford Algorithm

Dijkstra's Shortest Path algorithm

Friend Circles Problem - Graph Theory

Topological Sorting of a Directed Acyclic Graph


10: Dynamic Programming Algorithms

Word Break Problem

Find minimum cost path in a matrix

Maximum subarray sum

Find total number of ways to make change using given set of coins

Minimum number of coins to make change

Find the length of longest increasing subsequence in an array

Find the length of longest bitonic subsequence in an array

Count all possible decodings of a given digit sequence

To print maximum number of As using given four keys

Find minimum edit distance between given two strings

Total number of possible Binary Search Trees with n keys

0-1 Knapsack Problem

Longest Common Subsequence

Longest Common Substring

Longest Increasing Subsequence O(n logn)

Longest Palindromic Subsequence

Longest Palindromic Substring

Fibonacci Number

Palindrome Min Cut

Shortest Palindrome

Subset Sum Problem

Gold Mine Problem


Did anybody notice something amiss? Turned out 7 categories will do for now

(Considering we started with only 10 algorithms!)


Sorting Algorithms Time & Space Complexity

img03

Algorithms Time Complexity Space Complexity
Best Average Worst Worst
QuickSort Ω(n log(n)) Θ(nlog(n)) O(n^2) O(log(n)
Merge Sort Ω(n log(n)) Θ(nlog(n)) O(nlog(n)) O(n)
TimSort Ω(n) Θ(nlog(n)) O(nlog(n)) O(n)
Heap Sort Ω(n log(n)) Θ(nlog(n)) O(nlog(n)) O(1)
Bubble Sort Ω(n) Θ(n^2) O(n^2) O(1)
Insertion Sort Ω(n) Θ(n^2) O(n^2) O(1)
Selection Sort Ω(n^2) Θ(n^2) O(n^2) O(1)
Tree Sort Ω(n log(n)) Θ(nlog(n)) O(n^2) O(n)
Shell Sort Ω(n log(n)) Θ(nlog(n))^2 O(nlog(n))^2 O(1)
Bucket Sort Ω(n+k) Θ(n+k) O(n^2) O(n)
Radix Sort Ω(nk) Θ(nk) O(nk) O(n+k)
Counting Sort Ω(n+k) Θ(n+k) O(n+k) O(k)
CubeSort Ω(n) Θ(nlog(n)) O(log(n) O(n)

algoriths's People

Contributors

zioguillo avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.