Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
this code works only for array with all distinct values without duplicates. It will stuck with infinite loop if array contains at least one duplicate value.
I have tested it for duplicates It works perfectly fine.
void testCareerCup() {
int a[] = {4, 4, 1, 4, 4}, N = 5;
c15303665(a, N);
}
1 Pair -- 4 ... 1
2 Pair -- 1 ... 4
3 Pair -- 4 ... 1
4 Pair -- 4 ... 1
5 Pair -- 4 ... 1
this is a good one. we can also use bit vector to replace the hashmap to check whether some integer is missing.
Ya there would be 4 pair.. 1 more is returned cannot get rid of that. That is because when i scan array i do not check which ones i have already out put. We could change the code to get only distinct ones.
eugene -- the function name is the question id that appears in the address bar.
this will not work if the input array contains 0, may be more than one 0s
e.g. { 5, 2, 0, 7, 3, 4, 6, 0 } N=8
after sorting, the array becomes : { 0,5,2,3,4,5,6,7} (which does not seem correct)
it will go out of bound index. am I missing something?
@eugene.yarovoi for code line
for (int i = 0; i < N; i++) {
if (a[i] + a[N - a[i]] == N)
if a[i] =0 then a[N-a[i]] would be out of bound
If the data range is [1, n], instead of [0, n], O(n) time and O(1) space can be achieved through steps below.
Step 1: scan the array, for each a[i] make a[ |a[i]| - 1] negative
Step 2: scan the array, for all a[i] where a[n - |a[i]| - 1] is negative, print the pair of |a[i]| and n - |a[i]|
Step 3: scan the array, set all negative elements back to positive.
public static void main(String[] args) {
int[] arr = { 5, 5, 14, 11, 13, 3, 12, 2, 14, 15, 16, 12, 3, 18, 1, 16,
16, 19, 4, 7 };
System.out.println(Arrays.toString(arr));
int sum = arr.length;
int temp;
for (int i = 0; i < arr.length; ++i) {
temp = Math.abs(arr[i]) - 1;
arr[temp] = -Math.abs(arr[temp]);
}
for (int i = 0; i < arr.length; ++i) {
temp = sum - Math.abs(arr[i]) - 1;
if (arr[temp] < 0) {
System.out.println(String.format("%s, %s", Math.abs(arr[i]), temp + 1));
arr[temp] = Math.abs(arr[temp]);
temp = Math.abs(arr[i]) - 1;
arr[temp] = Math.abs(arr[temp]);
}
}
for (int i = 0; i < arr.length; ++i) {
arr[i] = Math.abs(arr[i]);
}
}
public static void main(String[] args) {
int[] arr = { 8, 5, 14, 11, 13, 3, 12, 2, 14, 15, 16, 12, 3, 18, 1, 16, 16, 19, 4, 7 };
System.out.println(Arrays.toString(arr));
for (int i = 0; i < arr.length; ++i) {
int temp = Math.abs(arr[i]) - 1;
arr[temp] = -Math.abs(arr[temp]);
}
for (int i = 0, j = arr.length - 2; i < j; i++, j--) {
if (arr[i] < 0 && arr[j] < 0) {
System.out.println(String.format("%s, %s", i + 1, j + 1));
}
arr[i] = Math.abs(arr[i]);
arr[j] = Math.abs(arr[j]);
}
}
Results:
[8, 5, 14, 11, 13, 3, 12, 2, 14, 15, 16, 12, 3, 18, 1, 16, 16, 19, 4, 7]
1, 19
2, 18
4, 16
5, 15
7, 13
8, 12
There is 1 way of doing this - in-place count sort - en.wikipedia.org/wiki/In-Place_Count_Sort . But, the problem here is, in-place count sort won't work with duplicates. So, we will have to find an alternate way of in-place count sort. This is as follows -
Let's say N=10, numbers are (in each pass, we are swapping A[i] and A[A[i]], if A[i] and A[A[i]] are same, then A[i] = -1)
5, 6, 10, 8, 9, 5, 7, 6, 5, 10
Pass 1 - 9, 6, 10, 8, 5, 5, 7, 6, 5, 10
Pass 2 - 9, 5, 10, 8, 5, 6, 7, 6, 5, 10
Pass 3 - 9, 5, -1, 8, 5, 6, 7, 6, 5, 10
Pass 4 - 9, 5, -1, 6, 5, 6, 7, 8, 5, 10
Pass 5 - 9, 5, -1, 8, 5, 6, 7, 8, -1, 10
after this pass the values will be the same
Now, repeat the process once more, ignoring A[i] = -1 cases.
Pass 1 - -1, 5, -1, 8, 5, 6, 7, 8, 9, 10
Pass 1 - -1, -1, -1, 8, 5, 6, 7, 8, 9, 10
Pass 1 - -1, -1, -1, -1, 5, 6, 7, 8, 9, 10 (after this pass, the values will be same)
Now, the array will be sorted, with occasional -1 between elements. Now, apply the regular O(N) algorithm to find the sum as N, with slight modifications to skip -1 elements.
Or, -1 elements can be completely removed from the array in O(N) time, and then apply O(N) algorithm to find the sum as N.
So, the time complexity is O(N) and space complexity O(1).
This is very close, but I think there's one subtle flaw. Can you prove that you only need to do that process twice? I think you may need to do it up to log(n) times for some inputs. If you have K entries out of position, at least K/2 of them are resolved in the next pass. That's because for each out-of-place entry, you either replace it with -1, or you swap it with another entry, putting at least 1 of those 2 entries into place (and possibly leaving the other still out of place). So no more than logN passes will be needed, as out-of-place entries will decrease like k, k/2, k/4, ... If there is 1 entry out of place, it is guaranteed to be resolved.
You can fix this problem by staying on the same spot when arr[i
I have thought very hard to find an example where it would require more than 2 iterations. Can you give an example? Nor I can prove that no more than 2 iterations are required :)
I think I'll be able to find one. But why didn't you mention this issue in your analysis, especially if you thought about it and couldn't prove it?
Sorry man, I am in office. I couldn't find a trivial proof. Once I return back, I will think of a proof, or find a counter-example which requires more than 2 iterations. In the meantime, please see if you can find a proof or a counter-example.
I understand if you can't find a proof or counterexample. All I'm saying is that it's important to mention conjectures on which the result depends so that people can proactively validate them, as opposed to catching them hidden within a proof.
The conjecture turns out to be false. The O(log n) upper bound is tight. Consider the following family of sequences:
S_0 = (1)
S_k = (2^k, 2^k - 1, ..., 2^(k-1) + 1) + Reverse(S_(k-1))
where + is sequence concatenation.
So the first sequences are
S_0 = (1)
S_1 = (2) + (1) = (2, 1)
S_2 = (4, 3) + S_1 = (4, 3) + Reverse(2, 1) = (4, 3, 1, 2)
S_3 = (8, 7, 6, 5) + Reverse (4, 3, 1, 2) = (8, 7, 6, 5, 2, 1, 3, 4)
Observe that each S_k is chosen so that applying one pass of your algorithm mirrors it about the center. (2^k, 2^k - 1, ..., 2^(k-1) + 1) + Reverse(S_(k-1)) becomes S_(k-1) + (2^(k-1) + 1, ... , 2^k - 1, 2^k). So the second half has all the elements in their right place, and the first half becomes S_(k-1).
S_1 takes 1 pass to sort. S_k takes 1 + passes for S_(k-1). By induction, it takes k passes to sort S_k. We can also see that S_k has twice the length of S_(k-1). S_1 has length 2^1, so S_k has length 2^k. The number of passes needed can thus be as high as logarithmic in the number of elements. Thus, if you make all the passes you need to ensure correctness, the algorithm will be O(n log n) time overall.
You can fix this just by staying on the same spot after you swap and a[i] still doesn't equal i. In that case, you can do it in one process:
5, 6, 10, 8, 9, 5, 7, 6, 5, 10
Pass 1 - 9, 6, 10, 8, 5, 5, 7, 6, 5, 10
Pass 2 - 5, 6, 10, 8, 5, 5, 7, 6, 9, 10
Pass 3 - -1, 6, 10, 8, 5, 5, 7, 6, 9, 10
Pass 4 - -1, 5, 10, 8, 5, 6, 7, 6, 9, 10
Pass 5 - -1, -1, 10, 8, 5, 6, 7, 6, 9, 10
Pass 6 - -1, -1, -1, 8, 5, 6, 7, 6, 9, 10
Pass 7 - -1, -1, -1, 6, 5, 6, 7, 8, 9, 10
Pass 8 - -1, -1, -1, -1, 5, 6, 7, 8, 9, 10
the rest are the same.
Since each pass we eliminate an out of place element, advance the current index, or both, we know that it's at most 2n steps, each of which is constant time.
Your solution with this change is actually a slightly different form of the top-voted solution. It's essentially the same thing, give or take optimizations.
It's interesting how the most subtle differences can change the complexity.
Why not keep a bitmap with bit turned on when corresponding value is in the array. This will have O(1) space and requires one pass through the array to populate the bit array.
Do another pass through the unsorted array, and for each element in the array if sum - arr[i] is ON in the bitmap , return the pair. This would be O(n) time and O(1) space complexity.
This is O(N) solution.
O(N) to sort and mark duplicates (with 0 or -1 or whenever you want) and O(N) to print pairs.
I've modified count sort a little bit to handle duplicates.
I assume that input array is size of N and values are in range [0,N-1] for simplicity.
But you can modify it if you need to honor your requirements.
I'm setting all duplicates to zero. But you can set it to some negative value and skip them from duplicates search part if you want.
this code prints both (a,b) and (b,a) pair and (a,a) pair. But again you could fix it as well if it is required.
for example:
input array {2, 7, 5, 3, 7, 2, 6, 7, 2, 9} will look like {-1, -1, 2, 3, -1, 5, 6, 7, -1, 9} after sorting.
void printPairs(int a[]) {
int N = a.length;
for (int i = 0; i < N; i++) {
while (a[i] != i) {
if (a[a[i]] == a[i]) { //duplicate found
a[i] = 0; //mark it
break;
}
swap(a, i, a[i]);
}
}
int pairCount = 1;
for (int i = 0; i < N; i++) {
if (N - a[i] < N && a[i] + a[N - a[i]] == N) {
System.out.println("Pair " + (pairCount++) + " " + a[i] + ":" + a[N - a[i]]);
}
}
}
void swap(int a[], int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
#include<iostream>
#include<conio.h>
using namespace std;
int main()
{ int a[100],i,n,nop=0,l;
cin>>n;
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
{ if(a[i]<0)
{ l=a[i]*-1;
if(a[l]>0)
{ a[l]*=-1;
}
}
else
{ if(a[a[i]]>0)
{ a[a[i]]*=-1;
}
}
}
l=n;
for(i=0;i<=n/2;i++)
{ if(a[i]<=0)
{ if(a[l]<0)
{ cout<<i<<'\t'<<l<<'\n';
nop++;
}
}
l--;
}
cout<<nop<<'\n';
getch();
return 0;
}
This works in all cases.
constraints Mentioned:
array index 0 to N : total N+1
values 0 to N
find all <i,j> for which sum of the values arr[i] + arr[j] = N
We can achieve this in O(N) time and O(1) space. Here is my algorithm
Run a initial loop to mark all the numbers found.
if a[i] = 5
then a[5] = a[5] + N+1 ;
We can detect whether a number existed in the list by performing the simple test
if ( a[number] >= N+1)
then number exist in the list, else this number is not in the list .
Following is the code snippet:
int getValue(int arr[], int index,int N);
void markIndex(int arr[], int index,int N);
bool isMarked(int arr[],int index,int N);
void findPairs(int arr[], int N)
{
// set the values
// find the pairs
int i = 0;
int iVal = 0;
for (i = 0; i <= N; i++)
{
iVal = getValue(arr,i,N);
markIndex(arr,iVal,N);
}
for (i = 0; i <= N; i++)
{
iVal = getValue(arr,i,N);
if ( isMarked(arr,N-iVal,N) )
cout << "Pairs:" << iVal << "," << N-iVal <<endl;
}
}
int getValue(int arr[], int index,int N)
{
int val = arr[index];
if ( val >= (N +1) )
val -= (N + 1);
return val;
}
void markIndex(int arr[], int index,int N)
{
if ( arr[index] < (N+1) )
{
arr[index] += N+1
}
}
bool isMarked(int arr[],int index,int N)
{
bool ret = false;
if (arr[index] >= (N+1))
ret = true;
return ret;
}
In this algorithm we are exploiting the constraint of ranged value i.e. values from 0-N. We need not sort or disturb the values from the original location.
We can also run a loop that will un-mark all the elements in Linear time.
for (i = 0 ; i <= N; ++i)
{
if (arr[i] >= (N+1))
arr[i] -= N+1;
}
Using in-place marker, it can be done in O(n) time complexity and O(1) space complexity with consideration on two special cases: the pair of 0 and N, and the pair of 1/2 N and 1/2 N when N is an even number. It is a non-destructive solution.
Scan 1: for all arr[i], set arr[ |arr[i]| ] to negative, with special handling for 0 and 1/2 N when N is even.
Scan 2. First, if the pair of 0 and N presents, print it; Second, print all pair of arr[i] and arr[arr.length - 2 - i] when they are both negative; third, if the pair of 1/2 N and 1/2 N, print it.
Scan 3. If requiring to preserve original data, set all element back to positive.
public static void printAllPairsSummedToN(int[] arr) {
System.out.println(Arrays.toString(arr));
boolean hasZero = false;
int halfSum = arr.length >> 1;
boolean sumIsEven = halfSum << 1 == arr.length;
int halfSumCount = 0;
for (int i = 0; i < arr.length; ++i) {
int temp = Math.abs(arr[i]) - 1;
// Bookkeep value 0's appearance
if (temp < 0) {
hasZero = true;
continue;
}
// Count value 1/2 N's appearance when N is even
if (sumIsEven && temp + 1 == halfSum) {
++halfSumCount;
continue;
}
// Otherwise, convert the element, whose index is
// equal to current arr[i], to negative
arr[temp] = -Math.abs(arr[temp]);
}
// special handling on the pair of 0 and N
if (hasZero && arr[arr.length - 1] < 0) {
System.out.println(String.format("%s, %s", 0, arr.length));
}
for (int i = 0, j = arr.length - 2; i < j; i++, j--) {
if (arr[i] < 0 && arr[j] < 0) {
System.out.println(String.format("%s, %s", i + 1, j + 1));
}
}
// special handling for the pair of 1/2 N and 1/2 N when N is an even number
if (halfSumCount > 1) {
System.out.println(String.format("%s, %s", halfSum, halfSum));
}
// If requiring to preserve original data, set all element back to positive
for (int i = 0, j = arr.length; i < j; ++i) {
arr[i] = Math.abs(arr[i]);
}
System.out.println(Arrays.toString(arr));
}
Test 1:
[8, 5, 10, 18, 11, 3, 12, 12, 19, 15, 2, 0, 3, 18, 1, 16, 16, 19, 4]
0, 19
1, 18
3, 16
4, 15
8, 11
[8, 5, 10, 18, 11, 3, 12, 12, 19, 15, 2, 0, 3, 18, 1, 16, 16, 19, 4]
Test 2:
[8, 5, 10, 18, 10, 3, 20, 10, 12, 19, 15, 2, 0, 10, 18, 1, 16, 16, 19, 4]
0, 20
1, 19
2, 18
4, 16
5, 15
8, 12
10, 10
[8, 5, 10, 18, 10, 3, 20, 10, 12, 19, 15, 2, 0, 10, 18, 1, 16, 16, 19, 4]
I think we can use the below mentioned code.
Space complexity O(1)
Time complexity : O(n)
Assume input is a sorted array.
int main () {
int a[] = { 0,0,1,2,2,4,5,6,9,11,11};
int n = 11;
int j = n -1; //last index
for (int i=0; i <= j; ) {
if(a[i] + a[j] == n) {
printf ("pairs %d & %d [index %d & %d] \n %d & %d [index %d & %d] \n", a[i],a[j], i,j,a[j],a[i],j,i);
j--;
} else if (a[i] + a[j] < n) {
i++;
} else if (a[i] + a[j] > n) {
j--;
}
}
return 0;
}
output will be
pairs 0 & 11 [index 0 & 10]
11 & 0 [index 10 & 0]
pairs 0 & 11 [index 0 & 9]
11 & 0 [index 9 & 0]
pairs 2 & 9 [index 3 & 8]
9 & 2 [index 8 & 3]
pairs 5 & 6 [index 6 & 7]
6 & 5 [index 7 & 6]
Correct me if I overlooked anything.
void find_pairs(int *a, int n)
{
// Assumption:
// for i::0..n-1
// 0 >= a[i] < n
// i.e. all the elements of array are non-negative.
int i;
for (i = 0; i < n; ++i) {
// if 'k' is found in array then make a[k] negative
// negative will work like a bolean flag.
// i.e. a[k] < 0 implies 'k' was present in the array.
if (a[a[i]] > 0) {
a[a[i]] = 0 - a[a[i]];
}
}
for (i = 1; i <= n/2; ++i) {
int j = n - i; // n = i + j;
if (a[i] < 0 && a[j] < 0) {
printf("%d %d\n", i, j);
}
}
// We are done now, lets clean-up negetive bits.
for (i = 0; i < n; ++i) {
if (a[i] < 0) {
a[i] = 0 - a[i];
}
}
}
@ anish[1] - space complexity should be O(1), hashmap will be similar to my first solution (using array of size N) with space complexity O(n) and time complexity O(n).
I guess interviewer want you to look into the bit wise storage..
As if N is 32 than only single storage is suffice to solve this as when you scan this array set the sum-arr[index] bit in that variable if it is already set this is the pair of require sum.. let me know if you find something wrong.
what the hell is "bit-wise storage" ????
if you're referring to a bitmap, then I guess it's well known that a bitmap is always O(1), right ????
Why not have 32 bitmaps then, it's still constant space, right ?
I guess whenver you need O(1) space just use a bitmap, as this is a magical data structure than can store infinite items on O(1) space......
Solution is simple..
Here if the array is having elements greater than N then no need of saving them.Anyhow it is mentioned 0-N is the range of elements in array. so you can say the same solution which is O(n) space complexity .But the only modification is like you have to say that the hashtable you are taking is of size N not n. Because it anyhow wont depend on 'n'.As N is already known it will become O(1) space complexity now.Thats it.
@hwasungmars - As mentioned in the Q itself, i gave a solution where i first sorted the array in O(nlogn) and then search for pairs in O(n) time. IMO we don't need to use binary search for finding pairing, as if we use binary search for finding pairs it will again need O(nlogn) time to find all pairs. Better we can keep two pointers in sorted array one at beginning and other at last and move them (++beginpointer & --lastpointer whenever condition meet) by comparing sum of value at beginpointer + lastpointer with N until beginpointer>lastpointer.
Nevertheless, just want to make a point your solution is also O(nlogn), is there something better possible wrt to time complexity.
Since the array is sorted you can use binary search on it and time compility will be o(log n)
- isandesh7 January 30, 2013