Objective: Given an array of integers (in particular order or permutation of a set of numbers), write an algorithm to find the lexicographically next permutation of the given permutation with only one swap. This problem can also be asked as “Given a permutation of numbers you need to find the next larger permutation OR smallest … Read more Lexicographically next permutation With One swap
Stable Marriage Given N men and N women and the marriage preference order for each man and woman. Their marriage will be stable when these men and women marry in such a manner so that everyone gets the most desired partner as per the availability( partners in a marriage cannot find anyone else better than … Read more Stable Marriage Problem – Gale–Shapley Algorithm – Java
Objective: Given a graph, write an algorithm to find all the articulation points or cut vertices. Articulation Points: In a graph, a vertex is called an articulation point if removal of that vertex (along with all the edges associated with that vertex) increases the number of connected components or in other words, removal of that … Read more Articulation Points OR Cut Vertices in a Graph
Objective: Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of distinct or unique islands. Island: 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 … Read more Find the number of distinct Islands OR connected components.
Objective: Given a graph and a source vertex write an algorithm to find the shortest path from the source vertex to all the vertices and print the paths all well. Example: We strongly recommend reading the following before continuing to read Graph Representation – Adjacency List Dijkstra’s shortest path algorithm – Priority Queue method We will … Read more Print All Paths in Dijkstra’s Shortest Path Algorithm
Objective: Given a graph represented by the adjacency List, write a Depth-First Search(DFS) algorithm to check whether the graph is bipartite or not. Earlier we have solved the same problem using Adjacency Matrix (Check if Graph is Bipartite – Adjacency Matrix) with Time complexity: O(V2) where V – No of vertices in the graph. In … Read more Check if Graph is Bipartite – Adjacency List using Depth-First Search(DFS)
Earlier we had discussed how to evaluate prefix expression where operands are of single-digit. In this article, we will discuss how to evaluate prefix expression for any number ( not necessarily single digit.) Prefix notation is a notation for writing arithmetic expressions in which the operands appear after their operators. Let’s assume the below Operands … Read more Evaluation of Prefix Expressions (Polish Notation) | Set 2
Prefix notation is a notation for writing arithmetic expressions in which the operands appear after their operators. There are no precedence rules to learn. Let’s assume the below Operands are real numbers in real digits. (Later we will Enhance the solution for any number) Permitted operators: +,-, *, /, ^(exponentiation) Blanks are NOT permitted in … Read more Evaluation of Prefix Expressions (Polish Notation) | Set 1
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 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
Problem Statement: There is an application that has several processes running in parallel and each process prints the logs in a single log file. Log message contains the process name, timestamp, message type (WARN, ERROR, etc) and actual message. You have given start timestamp and end timestamp. Write an algorithm to process the log file … Read more Print Processes and its messages from a given log file
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 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