Eat Code Sleep – repeat
A message containing letters from A-Z can be encoded into numbers using the following mapping: ‘A’ -> “1” ‘B’ -> “2” … ‘Z’ -> “26” To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, “11106” can be mapped […]
Greedy approach and Dynamic programming both are used for solving optimisation problems. However often we need to use DP since optimal solution cannot be guaranteed by a greedy algorithm. Consider Knapsack problem We could solve it by brute-force, by generating all possibilities of choosing a subset of n items and selecting […]
In the last post, we learned about Knapsack problem and also found an efficient solution to the problem using Dynamic programming. A little recap Let given weights & values of n items to be put in a knapsack of capacity W ie. We’ve 2 integer arrays value[0..n-1] and weight[0…n-1]. The objective is to find out […]
Problem statement Let given weights & values of n items to be put in a knapsack of capacity W ie. We’ve 2 integer arrays value[0..n-1] and weight[0…n-1]. The objective is to find out the maximum value subset of value[] array such that sum of weight of subset is smaller or equal […]
In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that number of elements in the original set always equals to the sum of number of elements in each partition. Equivalently, a family of sets P is a partition of X if and only if […]
Welcome to the exciting class of Professor Manasa. In each lecture she used to play some game while teaching a new concept. Today’s topic is Set Theory. For today’s game, she had given a set A = {a1, a2, …aN} of N integers to her students and asked them to play the game as follows. […]
Quicksort algorithm was developed by a British computer scientist Tony Hoare in 1959. “Quick Sort” is capable of sorting a list of data elements significantly faster (twice or thrice faster) than any of the common sorting algorithms and that’s why it is the favourite topic of interviewers in programming interviews. It is one […]
You are given an m x n binary matrix grid. An island is a group of 1‘s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water. The area of an island is the number of cells with a value 1 in the island. Return the maximum area of an island in grid. If there […]
The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other. For a larger N, this problem couldn’t be solved in polynomial time. So, it is an NP-Complete problem. However, this problem could be solved by backtracking in non-polynomial time for a […]
Backtracking is a general algorithm for finding solutions to some computational problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.