Expert

Check if Graph is Bipartite – Adjacency Matrix using Depth-First Search(DFS)

by

Objective: Given a graph represented by the adjacency matrix, write a Depth-First Search(DFS) algorithm to check whether the graph is bipartite or not. Bipartite Graphs OR Bigraphs is a graph whose vertices can be divided into two independent groups or sets so that for every edge in the graph, each end of the edge belongs … Read more

Round Price Problem

by

Problem Statement: When customers book an Airbnb the total price, which includes base price + service fee + cleaning fee. all these prices are in decimals. Write an algorithm to round each price such that the sum of the prices equals the round of the total sum of all decimal prices and minimize the rounding. … Read more

Smallest Number after Removing K digits

by

Objective: Given a number with N digits, write a program to get the smallest number possible after removing k digits from number N. OR Implement a method that returns the lowest possible number that could be generated after removing n characters from a string of digits. Example: N = 1453287, k = 3 Output: 1287 … Read more

Reverse a Stack using recursion – In Place (Without using extra memory)

by

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

K-Means Algorithm

by

The algorithm of kMeans is an unsupervised learning algorithm for clustering a set of items into groups. Given a set of multi-dimensional items and a number of clusters, k, we are tasked of categorizing the items into groups of similarity. The centers of these groups are called means. Overview The algorithm in pseudocode: Input: Data … Read more

Max Flow Problem – Ford-Fulkerson Algorithm

by

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

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

by

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

by

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

Least Recently Used (LRU) Cache – Using HashMap and Doubly Linked List | Set 1

by

Objective: Design and Implement a data structure Least Recently Used (LRU) Cache. Least Recently Used (LRU) Cache: You have given a cache (or memory) capacity. The cache will be filled with items you will access or look for it. The most recently accessed item will be at the top of the cache whereas the least … Read more

Find the nearest building which has bike | Find nearest specific vertex from source in a graph.

by

Objective: Given a matrix (NxN) which represents the buildings in community. You are in a building and you need a bike to travel.  There are few buildings in community which has bikes which you can take for your ride. Write an algorithm to find the nearest building which has bike and distance from your building. … Read more

Max Flow Problem – Introduction

by

Max Flow Problem- Maximum flow problems find a feasible flow through a single-source, single-sink flow network that is maximum. This problem is useful for solving complex network flow problems such as the circulation problem. The maximum value of the flow (say the source is s and sink is t) is equal to the minimum capacity of an s-t … Read more

Dijkstra Algorithm Implementation – TreeSet and Pair Class

by

Earlier we have seen what Dijkstra algorithm is and how it works. In this article, we will see its implementation using adjacency list and TreeSet. 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 … Read more

Find no of reverse pairs in an array which is sorted in two parts in O(N)

by

Objective: Given an array of integers A[] which is sorted in two parts (both parts are individually sorted), find no of reverse pairs means no of (i, j) pairs where i belongs to the part one and j belongs to part 2 and A[i]>A[j]. Example: A[] = {4, 6, 8, 9, 1, 5, 10, 11} … Read more

Dijkstra’s – Shortest Path Algorithm (SPT) – Adjacency List and Priority Queue – Java Implementation

by

Earlier we have seen what Dijkstra’s algorithm is and how it works. In this article, we will see its implementation using the adjacency list and Priority Queue. 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 … Read more

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

by

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