Category Archives: Algorithm

Given a triangle, find the minimum path sum from top to bottom

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = Read More →

Robot in an MXN grid

Problem: A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid . How many possible unique paths are there? Approach 1(Recursion): Let NumberOfPaths(m, n) be 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 →

Check Whether a Given Point Lies inside a Triangle or not

Given three corner points of a triangle, and one more point P. Write a function to check whether P lies within the triangle or not. The program needs to read the values of three coordinates A(x1,y1) B(x2,y2) C(x3,y3) as well as another coordinate P(x,y) and determine whether this point is inside a triangle formed from 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 →

What is the Probability that a Knight Stays on Chessboard

knight_moves

Given the size of the chess board and initial position of the knight, what is the probability that after k moves the knight will be inside the chess board. Note:- 1) The knight makes its all 8 possible moves with equal probability. 2) Once the knight is outside the chess board it cannot come back Read More →

Trie Data Structure – C Implementation

Trie Tree: A trie (from retrieval), is a multi-way tree structure useful for storing strings over an alphabet. It has been used to store large dictionaries of English (say) words in spelling-checking programs and in natural-language “understanding” programs. A trie tree uses the property that if two strings have a common prefix of length n Read More →

Implement Stack and Queue using Linked List in Java

The implementation of a linked list is pretty simple in Java. Each node has a value and a link to next node. Two popular applications of linked list are stack and queue. Stack: What is stack? Stack is a linear data structure which implements data on last in first out criteria. Here is a java 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 →

Sort a Linked List of 0s, 1s and 2s

Given a Singly linked list with each node containing either 0, 1 or 2. Write code to sort the list. Input : 1 -> 1 -> 2 -> 0 -> 2 -> 0 -> 1 -> 0 Output : 0 -> 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2 Solution: 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 →