Problem: A message containing letters from A-Z is being encoded to numbers using the following mapping: ‘A’ – 1 ‘B’ – 2 ‘Z’ – 26 Given an encoded message containing digits, determine the total number of ways to decode it. For example, Given encoded message “12″, it could be decoded as “AB” (1 2) or … Read More →
Finding All the Subsets of a Set – Backtracking Problem
Given a set of distinct integers, S, return all possible subsets. Note: Elements in a subset must be in non-descending order. The solution set must not contain duplicate subsets. For example, If S = [1,2,3], a solution is: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] We use the backtracking method to solve … Read More →
Determine if a Sudoku is Valid
Determine if a Sudoku is valid The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’. Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated. Because the number range of sudoku is 1-9, so each number in each row, … Read More →
Matching Nuts & Bolts Problem (Lock & Key problem)
Problem: Matching nuts and bolts problem can be stated as follows: “Given a collection of n nuts of distinct sizes and n bolts such that there is a one-to-one correspondence between the nuts and the bolts, find for each nut its corresponding bolt.” We can only compare nuts to bolts i.e., we can neither compare … Read More →
Check for Balanced Parentheses in an Expression
Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[' and ']‘, determine if the input string is valid. The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not. Algorithm: 1) Declare a character stack S. 2) Now traverse the expression string exp. … Read More →
Cousin nodes in Binary Tree
Given the binary Tree and the two nodes say ‘p’ and ‘q’, determine whether the two nodes are cousins of each other or not. Solution: What are cousin nodes ? Two nodes are said to be cousins of each other if they are at same level of the Binary Tree and have different parents. For … Read More →
Repeatedly Delete N nodes after M nodes of a Linked list
Given a linked list and two integers M and N. Traverse the linked list such that you retain M nodes then delete next N nodes, continue the same until end of the linked list. Input: M = 2, N = 2 Linked List: 1->2->3->4->5->6->7->8 Output: Linked List: 1->2->5->6 The main part of the problem is … Read More →
Min Number of Platforms Required for a Railway Station
At a bus-station, you have time-table for buses arrival and departure. You need to find the minimum number of platforms so that all the buses can be placed as per their schedule. For example consider the above example. arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00} dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00} All … Read More →
Break String into Dictionary Words
Given an English dictionary (implemented as a hashmap (word -> meaning)) and a string without spaces, output all possible combinations of valid English words that when combined, reproduce the input string. e.g. input: “programmerit” output: {{pro, gram, merit}, {program, merit}, {programmer, it}} output: Solution: Recursive implementation: The idea is simple, we consider each prefix and … Read More →
Find Buy/Sell Prices in Array of Stock Values to Maximize Profit
Problem: You have given a stock prices for next 10 days. Find out: max benefit in best time complexity in buy and sell 1 share ? Condition: Share must be sold any day after buying date. For ex: Share price in thousands 5 1 4 6 7 8 4 3 7 9 Max benefit 9 – 1 … Read More →
What’s going on ?