array problems

Find Pair of Numbers in Array with a Given Sum

Problem Definition This problem has appeared in many interviews as well as the qualifying round of Google Code Jam in the past. There are various versions of the problem. To list a few: Find Pair of Numbers in Array with a Given Sum - The array is unsorted and contains a given range of numbers bounded by min and max. Find Pair of Numbers in Array with a Given Sum - The array is sorted and contains a given range of numbers bounded by min and max. Find Pair of Numbers in Array with a Given Sum - The array contains unique numbers only. In all the above versions, we have to return the ...
Read More

Arrays are permutation of each other

Problem Definition – Arrays are permutation of each other The problem definition goes as follows: Given two arrays of equal length, find out if the elements of one array is the permutation of the elements of another array. Of course the constraint is to solve it in constant space and linear time. Which means that the running time should be O(N) and auxiliary space required should be O(1). Approach There may be several thoughts which seem to work but eventually they will fail at one or the other ways. Here are few interesting ways which may not work for all the conditions: XORing the ...
Read More

Shift Zeroes To Right

Problem Definition - Shift Zeroes To Right We are trying to solve a problem at hand in which we are given an array of zeroes and positive integers. We need to Shift Zeroes To Right and positive integers to the left without disturbing the relative order of the positive integers. Approach I try to solve the problem in a simple way, you may find a similar problem on the web, here is a approach which solves this problem in O(N) time using constant auxiliary space (may be one or two extra variables). The first thing which comes in mind can be traversing the array and swapping zeroes with the ...
Read More