Objective: Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Assume all four edges of the grid are all surrounded by water. Given such a grid, write an algorithm to find the … Read more Number of Islands
Objective: Given a number N, write an algorithm to convert that number to 1. Below are the allowed operations. If N is even, do N = N/2. If N is odd, either do N =N – 1 or do N = N + 1 Example: N = 16 Output: 4 16 → 8 → 4 … Read more Minimum No of operations required to convert a given number to 1 – Integer Replacement Problem.
Objective: You are working on a project where QA team has automated set of test cases for the project, but these test cases have to be executed in a specific order since test cases has dependencies on each other, for example if test case A and dependency on test case B then test case B … Read more Determine the order of Tests when tests have dependencies on each other
Objective: Given a Stack, write an algorithm to reverse the stack. Example: Original Stack: [14, 9, 67, 91, 101, 25] Reversed Stack: [25, 101, 91, 67, 9, 14] Approach: Use Recursion In this solution, we need two recursive functions. reverse() and insert_at_bottom(). reverse() – this function will be called by the driver. In this function, … Read more Reverse a Stack using recursion – In Place (Without using extra memory)
Objective: Given a Prefix expression, write an algorithm to convert it into Postfix expression. Example: Input: Prefix expression: + A B Output: Postfix expression: A B + Input: Prefix expression: *-A/BC-/AKL Output: Postfix expression: ABC/-AK/L-* Approach: Use Stacks Algorithm: Iterate the given expression from right to left, one character at a time If the character … Read more Convert Prefix to Postfix Expression
Objective: Given a stack of integers, write an algorithm to sort the stack using a temporary stack. Example: Given Stack: [14, 9, 67, 91, 101, 25] Sorted Stack: [9, 14, 25, 67, 91, 101] Approach: Use another stack, let’s call it a temporary stack. While given original is not empty Pop the element from the … Read more Sort a given stack – Using Temporary Stack
Objective: Given a Postfix expression, write an algorithm to convert it into prefix expression. Example: Input: Postfix expression: A B + Output: Prefix expression- + A B Input: Postfix expression: ABC/-AK/L-* Output: Infix expression: *-A/BC-/AKL Approach: Use Stack Algorithm: Iterate the given expression from left to right, one character at a time If the character … Read more Convert Postfix to Prefix Expression
Objective: Given an Integer, write a program to convert it to Roman number. This problem can be stated as “Convert Decimal to Roman String” OR “Convert numeral value to Roman numeral”. Roman Number – Letters used in Roman numerals and the corresponding numerical values are given in the table below. Rules: Roman numerals are … Read more Convert Integer to Roman
Objective: Given a Postfix expression, write an algorithm to convert it into Infix expression. Example: Input: Postfix expression: A B + Output: Infix expression- (A + B) Input: Postfix expression: ABC/-AK/L-* Output: Infix expression: ((A-(B/C))*((A/K)-L)) Approach: Use Stack Algorithm: Iterate the given expression from left to right, one character at a time If a character … Read more Convert Postfix to Infix Expression
Objective: Given a string, write an algorithm to find the longest substring with at most two characters. Example: Input: aabbccddc Output: ccddc, length: 5 Input: aabacbeeeebeaabb Output: beeeebe, length 7 Input: aaaaaa Output: Only one unique character is present in the input string Approach: Brute Force Identify all the substrings of the given input string … Read more Longest substring with at most two unique characters
Objective: Given a Prefix expression, write an algorithm to convert it into Infix expression. Example: Input: Prefix expression: + A B Output: Infix expression- (A + B) Input: Prefix expression: *-A/BC-/AKL Output: Infix expression: ((A-(B/C))*((A/K)-L)) Approach: Use Stacks Algorithm: Iterate the given expression from right to left (in reverse order), one character at a time … Read more Convert Prefix to Infix Expression
Objective: Given an Infix expression, write an algorithm to convert it into Prefix expression. Example: Input: Infix expression – A + B Output: Prefix expression- +AB Input: Infix expression – A+B*(C^D-E) Output: Prefix expression- +A*B-^CDE Approach: Use Stack Operator stack: This stack will be used to keep operations (+, -, *, /, ^) Order of … Read more Convert Infix to Prefix Expression
Objective: Given a directed graph that represents a flow network involving source(S) vertex and Sink (T) vertex. Each edge in the graph has an individual capacity which is the maximum flow that edge allows. Flow in the network has the following restrictions- Input flow must match to output flow for each node in the graph, … Read more Max Flow Problem – Ford-Fulkerson Algorithm
Objective: Given an Infix expression, write an algorithm to convert it into Postfix expression. Example: Input: Infix expression – A + B Output: Postfix expression- AB+ Input: Infix expression – A+B*(C^D-E) Output: Postfix expression- ABCD^E-*+ Approach: Use Stacks Operator stack: This stack will be used to keep operations (+, -, *, /, ^) Order of … Read more Convert Infix to Postfix Expression
Infix notation is commonly used in arithmetic formula or statements, the operators are written in-between their operands. Let’s assume the below Operands are real numbers. Permitted operators: +,-, *, /, ^(exponentiation) Blanks are permitted in expression. Parenthesis are permitted Example: A * ( B + C ) / D 2 * (5 + 3) / … Read more Evaluation of Infix expressions