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
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 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
Objective: Given an array of integer write an algorithm to find the majority element in it (if exist). Majority Element: If an element appears more than n/2 times in array where n is the size of the array. Example: int [] arrA = {1,3,5,5,5,5,4,1,5}; Output: Element appearing more than n/2 times: 5 int []arrA = {1,2,3,4}; … Read more Majority Element – Part 1
Objective: Given a linked list and integer ‘k’, write an algorithm to reverse the linked list in groups of size ‘k’. Example: Approach: Earlier we have seen how to reverse a linked list, solution for reverse the linked list in groups of size will be extension of this solution. Reverse first ‘k’ nodes of the … Read more Reverse a Linked List in groups of given size ‘K’
Objective: Given a string, find a longest palindromic subsequence in it. What is Longest Palindromic Subsequence: A longest palindromic subsequence is a sequence that appears in the same relative order, but not necessarily contiguous(not substring) and palindrome in nature( means the subsequence will read same from the front and back. Example: String A = ” … Read more Dynamic Programming — Longest Palindromic Subsequence
Objective: – Given a binary tree, Do the reverse level order traversal. In our earlier post we have seen normal Level Order Traversal. In reverse level order traversal we first need to print the last level followed by second last level up to the root, which is the first level.
Example:
Approach: Use Stack