Find the Maximum Subarray and its Sum [Kadane’s Algorithm]
Find the maximum subarray and its sum is a problem of finding contiguous subarray with largest sum in an array of integers.
Category: Algorithms
Strassen’s Algorithm for Matrix multiplication
Strassen’s Algorithm for Matrix multiplication is a recursive algorithm for multiplying n x n matrices. Strassen’s algorithm is based on a familiar design technique – Divide & Conquer.
Find the minimum distance to travel through a road having hills [Interview Question]
Alansh has to travel through a road having hills of different heights. Also each hill has a cave to pass through it, to avoid travelling extra distance of a hill. Alansh wants to travel through this road by taking at most K caves.
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.
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]
he efficiency of an algorithm can be measured by two parameters: Time Complexity also known as running time of an algorithm is the number of primitive operations executed on a particular input.
Space Complexity is the total (extra) memory space required by the program for its execution.
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.