Close

## Facebook Hackercup 2016- Boomerang constellations problem solution

This problem is from the recently concluded Facebook Hackercup 2016 Qualification round. You can take a look at the problem statement in this link. I am giving the abridged problem statement here. Given a set of coordinates in a 2D-plane, We have to find out the total number of pairs of lines with equal length…

## Counting pairs in array

Given an array A of distinct numbers, how to count the number of pairs (i,j) such that A[i] < A[j] For example, let us consider A = [2, 1, 3] the pairs are (1,2), (1,3), (2,3). So there are 3 pairs. Similarly for A = [10, 6, 9, 2], there are 6 pairs This problem…

## Number of ways to make coin change

Given some amount N, and a set of denominations, how do you find the number of ways to make change for N? Let us assume that there is infinite supply of coins for each denomination. For example, if we have to make change for 4, and the given denominations are {1, 2, 3}, the possibilities…

## Maximum increasing sub array

Given an array of numbers, how to find the maximum length of increasing (non-decreasing) continuous sub-sequence? For example consider the array [7, 9, 1, 3, 5, 8, 2], the maximum length is 4. Similarly for [23, 10, 18, 18, 6], it is 3. This is a straight forward implementation problem (appeared on Codeforces). Following is…

## Check if an array has a sub-array with given sum

Given an array of numbers and a sum, how to check if there is any sub-array with the given sum. For example consider an array A = [7, 2, 9, 1, 5], and the sum is 12, then we can find a sub-array [2, 9, 1] which sums up to 12. So the answer is…

## Decreasing string

Given a number K, Find the shortest and smallest string  which has K positions in it, such that the character at that position is alphabetically greater than the character immediately after it. Only the lower case alphabets [a-z] are allowed. For example consider K = 1 “ba” is the shortest and smallest string possible. There…

## Minimum difference between two elements in array

Given an array, how do we find the minimum difference between any two elements in that array? For example consider the array [56, 18, 89, 24, 10], the minimum difference is 6 (between 18, and 24). A straight forward method to find the minimum difference between any two pairs is to iterate through each possible…

## Up down array

Given an array of numbers A[N], how do we arrange them in the following order. A[0] <= A[1] >= A[2] <= A[3]…A[N-1] For example consider the array A =[6, 9, 36, 24, 42] The answer can be [6, 36, 9, 42, 24]. There can be multiple answers also like [6, 42, 9, 36, 24]. We…

## Linear search

Given an array of numbers, how do we search for a given number? For example, given an array [6, 50, 24, 36, 42], the number 36 is present at the index 3 starting with 0. The number 17 is not present any where. The simplest algorithm to solve this problem is to check each element…

## How to check if sequence is a sub sequence of another

Given two arrays of numbers, how to check if the first sequence is a sub sequence of second sequence.For example [3, 7, 11] is a sub-sequence of [9, 3, 1, 7, 5, 11]where as [4, 8, 9] is not a sub-sequence of [6, 4, 9, 2, 8]The algorithm here is simple.  Let us assume two…