Find subarray with a sum to given number-2 | Handle negative numbers

Problem: Given an array (positive and negative) and an integer, find the subarray with sum is equal to the given integer.  Note: This problem is an extension of – find the subarray with sum to a Given Value, in which arrays with negative numbers are not handled.  Example: Given input: [25, 12, -14, 22, -19, … Read more

Sort the two dimensional (2D) array – In-place

Problem: Given a two-dimensional array where each individual row is sorted in ascending order. Your task to sort the entire 2d array in ascending order. Write an algorithm for the sorting. Example: Given Array: [[5, 12, 17, 21, 23] [1, 2, 4, 6, 8] [12, 14, 18, 19, 27] [3, 7, 9, 15, 25]] Sorted … Read more

Implement/Design the version control map system

Problem: Implement the version control map system which takes the snapshot of the versions of data. Implement the following functions: put(key, value) – puts the value again the key in the latest version of the map get(key) – get the value of the key for the latest version of the data snapshot() – take a … Read more

Two Sum Problem

Objective: Given an array of integers, and k. Write a program to find indexes of two elements in an array which sum is equal to K. Example: Given array: [5, 4, 7, 3, 9, 2], Sum = 13 Output: Found indexes are: 4 and 1 Given array: [1, 2, 3, 4, 5], Sum = 9 … Read more

Lexicographically next permutation With One swap

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

Stable Marriage Problem – Gale–Shapley Algorithm – Java

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

Given an array, find three-element sum closest to Zero

Objective: Given an array of integers, find the sum of any three elements which is closest to zero. The array may contain positive and negative elements.  Example:  Given Input: [-1, 4, -2, 5, 10, -5] Minimum Sum with three elements is: 1 Explanation:  -1, 4, -2 sums to -1  Given Input: [-1, 4, -2, 5, … Read more

Articulation Points OR Cut Vertices in a Graph

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

Print All Paths in Dijkstra’s Shortest Path Algorithm

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

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

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

Longest substring with at most K unique characters

Objective: Given a string, write an algorithm to find the longest substring with at most K characters. Example: Input: aabbaacdeeeeddded, K = 3 Output: Longest substring with 3 most unique characters is: cdeeeeddded with length 11 Input: abcddefabc, K = 4 Output: Longest substring with 4 most unique characters is: abcdd with length 5 Input: … Read more

Sort a given stack – Using Recursion

Objective: Given a stack of integers, write an algorithm to sort the stack using recursion.  Example: Original Stack: [14, 9, 67, 91, 101, 25] Sorted Stack: [9, 14, 25, 67, 91, 101] Original Stack: [4, 9, 6, 8, 10, 5] Sorted Stack is:[10, 9, 8, 6, 5, 4]  Approach: In this solution, we need two … Read more

Determine the given routing number belong to which bank

Objective: Given the banks and range of routing numbers for each bank. You have given a routing number, write a program to determine which bank it belongs to. Input: Given a list of routing ranges for each bank, with a start number, end number, and bank name. For instance, range = [1001, 1005, BOFA] has … Read more