Evaluation of Infix expressions

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

Least Recently Used (LRU) Cache – Using LinkedHashSet and Deque | Set 2

Objective: Design and Implement a data structure Least Recently Used (LRU) Cache. Earlier we had seen Least Recently Used (LRU) Cache – Using HashMap and Doubly Linked List. In this article, we will see the implementation using LinkedHashSet and Deque. Lets first brief about LRU- Given a cache (or memory) with capacity. The cache will … Read more

Merge K sorted Linked List – Using Priority Queue

Objective: Given, K sorted linked list, Write an algorithm to merge all the linked list into one linked list which will be also be sorted. Example: List 1: –>1–>5 List 2: –>4–>8 List 3: –>4–>6–>9 List 4: –>2–>7–>10 Merged Linked List: –>1–>2–>4–>4–>5–>6–>7–>8–>9–>10 Approach: Use Priority Queue Please read Priority Queue and Linked List if needed. … Read more

Valid Brackets – Part 2 | Stack Method

Objective: Given a string containing just the characters ( , ) determine if the input string is valid. Example: ()()(()(()))() valid: true )()()( valid: false ()()) valid: false Approach: Earlier we discussed the solution which keeps the count of open and closed parentheses. In this solution we will solve this problem using stack. Using Stack: Initialize a … Read more

Dijkstra’s – Shortest Path Algorithm (SPT) – Adjacency List and Min Heap – Java Implementation

Earlier we have seen the basics of Dijkstra algorithm. In this article, we will see its implementation using the adjacency list and Min Heap. brief: What is Dijkstra’s algorithm? Dijkstra algorithm is a greedy algorithm. It finds a shortest-path tree for a weighted undirected graph. This means it finds the shortest paths between nodes in a graph, … Read more

Graph – Find Cycle in Undirected Graph using Disjoint Set (Union-Find)

Objective: Given a graph, check if the graph contains a cycle using disjoint set. Note: Disjoint-set data structure, also called a union–find data structure or merge–find set. Example: Earlier in Detect Cycle in Undirected Graph using DFS we discussed about how to find cycle in graph using DFS. In this article we will discuss how to find cycle using … Read more

Graph – Detect Cycle in a Directed Graph using colors

Objective: Given a directed graph write an algorithm to find out whether graph contains cycle or not. Example: Approach: Graph contains cycle if there are any back edges. There are two types of back edges as seen in the example above (marked in red) Edge from a vertex to itself. Self loop. (4-4) Edge from … Read more

Snake and Ladder Problem

Objective – Given a snake and ladder game, write a function that returns the minimum number of jumps to take top or destination position. You can assume the dice you throw results in always favor of you means you can control the dice. Rules: Start from cell 1. Throw the dice and whatever number you … Read more

Majority Element- Boyer–Moore majority vote algorithm

Objec­tive:  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 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

Maximum Subarray OR Largest Sum Contiguous Subarray Problem – Divide and Conquer

Objec­tive:  The max­i­mum sub­ar­ray prob­lem is the task of find­ing the con­tigu­ous sub­ar­ray within a one-dimensional array of num­bers which has the largest sum. Exam­ple: int [] A = {−2, 1, −3, 4, −1, 2, 1, −5, 4}; Output: contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6. Approach: Ear­lier we have seen how to … Read more

Find two elements whose sum is closest to zero

Objective: Given an array of positive and negative integers, write a algorithm to find the two elements such their sum is closest to zero. Example: int a [] = {1, 4, -5, 3, -2, 10, -6, 20}; Output: Sum close to zero in the given array is : 1 int a [] = {-5, 5, … Read more

Find the first repeating character in a given string

Objective: Given a string, write an algorithm to find the first repeating character in it. Example: String input = “horizon tutorials” Output: ‘o’ String input = “algorithms” Output: No repeating character found. Approach: Naive approach: This problem can be easily solved using two nested loops. Take each character from the outer loop and check the … Read more

Find longest Snake sequence in a given matrix

Objective: Given two dimensional matrix, write an algorithm to find out the snake sequence which has the maximum length. There could be many snake sequence in the matrix, you need to return the one with the maximum length. Travel is allowed only in two directions, either go right OR go down. What is snake sequence: … Read more

Dynamic Programming – Count all paths in 2D Matrix with Obstructions in it

Objective: Given two dimensional matrix, write an algorithm to count all possible paths from top left corner to bottom-right corner. You are allowed to move only in two directions, move right OR move down. There are few obstructions as well, means few cells are blocked and you cannot travel that cell.

Many times this problem is being referred as “Robot Travel Problem“. Given a 2d matrix, how many ways a robot can travel from top left corner to bottom right corner and there are few cells in which robot cannot travel.

Read more