Edit Distance – LeetCode Solution [Hard]
Given two strings word1 and word2 (in lowercase alphabets), return the minimum number of operations required to convert word1 to word2.
Category: Algorithms
Topological Sort [Hackerearth]
A Topological sort of a Directed-Acyclic graph G is a linear ordering of all its vertices such that if G contains an edge E (u, v), then u appears before v in the ordering. And if the graph is not acyclic, then no linear ordering is possible.
Time & Space complexity [Cheat Sheet]
Time Complexity is the number of primitive operations executed on a particular input. It measures the amount of time an algorithm takes to complete as a function of the length of the input.
Why is Quicksort better than Merge Sort? [Divide & Conquer]
Quicksort is a sorting algorithm whose worst-case running time is O(n^2), for an input of size n. Quicksort, in spite of having worse time complexity than Merge Sort which is O(nlogn), it is a better practical choice for sorting. This is because it is remarkably efficiently on average cases, where its time complexity is O(nlogn).
Which sorting algorithm makes minimum number of swaps?
Sorting means arranging a set of data in an order. There’re various algorithms to sort the data (in a data structure) in increasing or decreasing order. These algorithms can be divided on basis of various factors. Inplace sorting means that all the data which is to be sorted can be accommodated at a time in memory. Examples of inplace sorting algorithms are Selection sort, Bubble sort etc.
DFS (Depth-First Search) in Binary Trees and Graphs
DFS (Depth-First Search) is an algorithm for traversing a graph. DFS starts from source vertex (graph) or root (in trees) and then visits an unvisited adjacent node v. After that it checks if node v has any adjacent node which is unvisited. If it reaches a leaf node or any node having no unvisited adjacent node. It backtracks and continue traversing other nodes.
BFS (Breadth-First Search) in Binary Trees and Graphs
BFS (Breadth-First Search) is one of the simplest algorithms for traversing a graph. Prim’s min-spanning-tree and Djikstra’s algorithm use similar ideas as BFS. BFS is also known as Level-order traversal because the algorithm discover all nodes at distance k from root before discovering any nodes at distance k+1.
Activity Selection problem
Activity selection problem is the problem of selecting the largest set of mutually exclusive activities. Each activity has its own starting time si and finish time fi. No two activities can share the resource at any time point.
Custom Sort String – LeetCode Solution [Medium]
You are given two strings order and t. All the words of order are unique and were sorted in some custom order previously.
Job sequencing problem
There are n jobs to be processed on a machine. Each job i has a deadline and a profit. Profit is earned if the job is completed by its deadline. Job is completed if it is processed on a machine for unit time.