Close

## Searching for an element in array of adjacent numbers

Given an array of numbers where the difference between any adjacent numbers is 1, how do we efficiently find a given number? For example consider the array {1, 2, 1, 2, 3, 2, 3, 4, 5, 6}, and we want to search for the number 5. The simplest solution is to check if the number…

## Check if a string is a double string

Given a string, we need to check if a string is a double string possibly by deleting a character. A double string is a repetition of two strings affixed together. For example the following strings are double strings “aa”, “meme”, “abbabb” Where as the follwing are not double strings “ab”, “abc”, “acbab” However “acbab” can…

## Printing a cross with given word

Given a string we have to print the characters of that string into a cross mark. If the string is “12345”, we need to print 1 5 2 4 3 2 4 1 5 This is printing the two diagonals of a square matrix filled the given string. Following is the simple code to print…

## Check if array can be divided into two parts with same XOR

Given an array of numbers, how do we check if it can be divided into two parts such that XOR values of both are same. For example consider an array A = [1, 2, 3], it can be divided into [1, 2], and  because 0001 ^ 0010 = 0011 Similarly, [8, 3, 12, 7],…

## 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…

## Finding the number in a shuffled array

Given an array [1, 2, 3,…N], we apply a series of reversal operations on different range of indices [L,R]. How to find out the position of a number after these operations are applied? For example consider an array of 5 numbers [1, 2, 3, 4, 5] and the number 2. Reverse elements between 1, and…

## Odd number out

Given an array of numbers which contains all even numbers except one, or all add numbers except one. How do you find the different number? For example consider the array [1, 2, 3, 5, 9], 2 is the different number. Similarly in the array [10, 6, 7, 24, 36], 7 is the different number. This…

## 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 Xor of two bit patterns

Given two numbers A, B, What is the maximum value of A’ XOR B’, where A’, B’ are obtained by permuting the binary representations of A, B respectively. For example assume A = 3, B = 1 and they are represented in 4 bits. A = 0011, B = 0001 in binary. Suppose A’ =…