Close

## Maximum number of contiguous ones with K zeros

Given an array of size N, containing only 0’s and 1’s, and a number K, what is the maximum length of the sub-array with contiguous 1’s with at most K 0’s? For example consider the array A = [1, 1, 0, 1, 0, 0, 1], K = 2, the maximum length is 5. i.e the…

## Maximum elements of array

Given an array A of size N, We want to perform several iterations as described below. Select any index i such that 1 <= i <= N, Mark A[i] = 0, move left by filling each element one greater than it’s right Similarly move right, and fill each element which is one greater than it’s…

## Path length between two binary tree nodes

Given a full binary tree (all nodes except leaf nodes have left and right child) represented as shown below. If the root is labelled i, it’s left child is labelled 2*i and right child is labelled as 2*i+1. 1 /   \ 2     3 /  \   / \ 4  5  6   7 Given two nodes from…

## Partial sum queries

Given an array of numbers, we need to answer many queries of the form Sum(A[i]…A[j]), For example, let the array be [15, 6, 1, 12, 7, 4, 10] Sum(A[1:3]) = 15+6+1 = 22 Sum(A[4:6]) = 12+7+4 = 23 … The simplest solution is to iterate through the elements from i to j and return the…

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

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

## Finding the the number at a given position in even odd array

Given a number N, an array is created by first adding all the odd numbers, and then adding all the even numbers below N, How do we find the number at a given position K? For example consider N = 10, the array is [1, 3, 5, 7, 9, 2, 4, 6, 8, 10], the…