Given an array, count the number of pairs with a given sum.

Objective: Given an array of integers, write a program to count all the pairs with the given sum. Example: Given array: [1, 5, 7, 1, -1], Sum= 6 Total Pairs: 3 Note: pairs are (1, 5), (5, 1) and (7, -1) Given array: [4, 5, 1, 2, 9, -2, -4], Sum= 5 Total Pairs: 2 … Read more Given an array, count the number of pairs with a given sum.

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 Two Sum Problem

Given an array, find all unique subsets with a given sum with allowed repeated digits.

Objective: Given an array of integers and number N, Write an algorithm to find and print all the unique subsets of array for which sum is equal to N where array elements can be repeated any number of times.  Example: int [] arrA={2,4,3} sum =6 Output: [2, 2, 2] [2, 4] [3, 3] int [] … Read more Given an array, find all unique subsets with a given sum with allowed repeated digits.

Print all steps to convert one string to another string

Objective: Given two strings, source string and target string, which are permutation or anagram of each other. You are allowed two swap only consecutive characters. Write an algorithm to print all the steps ( all the swaps) which will lead the conversion of the source string to the target string. NOTE: There could be multiple … Read more Print all steps to convert one string to another string

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 Lexicographically next permutation With One swap

Find all subsets of size K from a given number N (1 to N)

Objective: Given two integers N and K, Write an algorithm to find subsets of size K from the numbers 1 to N.  Example: N = 5 K = 3 Output: [1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 3, 4] [1, 3, 5] [1, 4, 5] [2, 3, 4] [2, 3, 5] [2, … Read more Find all subsets of size K from a given number N (1 to N)

Find all possible combinations with sum K from a given number N(1 to N) with the repetition of numbers is allowed

Objective: Given two integers N and K, Write an algorithm to find possible combinations that add to K, from the numbers 1 to N.  Condition: An integer from 1 to N can be repeated any number of times in combination. Example: N = 5 K = 3 Output: [1, 1, 1] [1, 2] [3] N … Read more Find all possible combinations with sum K from a given number N(1 to N) with the repetition of numbers is allowed

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 Stable Marriage Problem – Gale–Shapley Algorithm – Java

Construct the largest number from the given array.

Objective: Given an array of integers, write an algorithm to construct the largest number possible by appending the array elements.  Example: Given Input: [7, 78] Largest Number Possible: 787 Explanation: two possibilities are 778 and 787. 787 is larger than 778. Given Input: [25, 42, 39] Largest Number Possible: 423925 Approach:  Normal sorting in descending … Read more Construct the largest number from the given array.

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 Given an array, find three-element sum closest to Zero

Given an array, print all unique subsets with a given sum.

Objective: Given an array of integers and number N, Write an algorithm to find and print all the subsets of the array for which sum is equal to N. Example: input [] = {6,2,7,8,2,4,1,3,7,5} Sum = 8 Output: [1, 2, 2, 3] [1, 2, 5] [1, 3, 4] [1, 7] [2, 2, 4] [2, 6] … Read more Given an array, print all unique subsets with a given sum.

Sum of length of subsets which contains given value K and all elements in subsets are less than equal to K.

Objective: Given an array of numbers and integer K. Your task is to find lengths of all the subsets which contain value K and all elements in the subset are less than equal to K. Example: Given Input: [1, 5, 2, 3, 8, 6, 2, 4, 9, 5, 2], and K = 5 Length of … Read more Sum of length of subsets which contains given value K and all elements in subsets are less than equal to K.

Find all unique combinations of numbers (from 1 to 9 ) with sum to N

Objective: Given an integer N, Write an algorithm to select numbers from 1 to 9 and make combinations such that its sum to N.  Example: N= 5 Output:  [1, 4] [2, 3] [5] N =12 [1, 2, 3, 6] [1, 2, 4, 5] [1, 2, 9] [1, 3, 8] [1, 4, 7] [1, 5, 6] … Read more Find all unique combinations of numbers (from 1 to 9 ) with sum to N

Number of Intervals in which given value lies

Objective: Given a list of intervals with start and end for each interval. You have given a value V, write an algorithm to find the number of intervals in which the value V lies.  Example: Given Interval: [[1,7], [3,10], [12,15]] Value : 6 lies in Intervals: 2 Given Interval: [[1,7], [3,10], [12,15]] Value : 11 … Read more Number of Intervals in which given value lies

Unique Integers in array that sum up to zero.

Objective: Given an integer N, write a function to return an array containing N unique integers that sum up to zero. There are many possible arrays that sum up to 0 for any N, you need to return any one of such arrays. Example: N = 4 Output: [-1, 1, -2, 2] or [-1, -2, … Read more Unique Integers in array that sum up to zero.