Matrix-chain multiplication
We are given a sequence (chain) (M1, M2, M3…Mn) of n matrices to be multiplied and we need to find the most efficient way to multiply these matrices together.
Category: Algorithms
Longest Common Subsequence Solution
The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to given two sequences.
Longest Increasing Subsequence Solution (LIS) – LeetCode Solution [Medium]
Given an integer array arr, return the length of the longest strictly increasing subsequence. Strictly increasing sequence is a sequence such that all elements of the sequence are sorted in increasing order.
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.
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]
Logan 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. Logan 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]
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.
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.