## Interview Question for Software Engineer / Developers

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
8
of 10 vote

``````/* Its difficult to see that the below code works in O(n) time..
Algorithm
for each ith element in array{
try to place the element in its correct position that is a[i]th -- a[a[i]].
remove the element at that position and do the same with it. till
the element at the position where it has to be is equal to it.
In this case place the element at a[i];
}
Initially when many elements are out of place the inner while loop will go potentially till n.
But then once all the elements are in place the inner
while loop is O(1).
Total number of times the array is scanned is only 2.
Hence total algorithm is O(n).

void c15303665(int a[], int N) {
int removed,temp;
for (int i = 0; i < N; i++) {
removed = a[i];
assert(a[i] < N);
while (a[removed] != removed) {
temp = a[removed];
a[removed] = removed;
removed = temp;
}
a[i] = removed;
}
int pairCount=1;
for (int i = 0; i < N; i++) {
if (a[i] + a[N - a[i]] == N)
printf("\n %d Pair  -- %d ... %d", pairCount++, a[i], a[N - a[i]]);
}
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

this is a good one. we can also use bit vector to replace the hashmap to check whether some integer is missing.

Comment hidden because of low score. Click to expand.
0

Sorry, my mistake.
+1

Comment hidden because of low score. Click to expand.
0

+1. By the way, what's with the function name?

@zyfo2: there is no hash map.

Comment hidden because of low score. Click to expand.
0

isandesh7 :I think there would be max 4 pair.
4,1
4,1
1,4
1,4

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

@Bill: why is it out of bounds?

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
0

@bill: I think the solution is for integers in the range [1, N]. You'd use one extra variable (O(1) space) to sit in place of arr[N] if you wanted to support integers in the range [0, N]. Would have some special cases, but you could still use this same idea.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

``````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]);
}
}``````

Comment hidden because of low score. Click to expand.
0

``````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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

If the largest element in the array is less than n/2, then no pairs found.
If all elements are greater than n/2, then no pairs sum to n.

Keep 3 counters: # of elements < n/2, # of elements = n/2, # of elements > n/2 [O (n) time]
..and so on..

Comment hidden because of low score. Click to expand.
0
of 0 vote

just for the clarification, for the input {1,3,3,1} and sum 4, what will be the out put?
is it just 1,3 or
1,3 and 3,1 ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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 :)

Comment hidden because of low score. Click to expand.
0

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?

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@eugene.yarovoi, you are right. thanks for the clarification.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

since the range is N. you can change original array to be negative to simulate hashmap

Comment hidden because of low score. Click to expand.
0
of 2 vote

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.

Comment hidden because of low score. Click to expand.
0

The bitmap would have N bits, so it would still consume O(N) space.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

possible modifications:
1) if you need keep duplicates in the array, then simply do not mark them, but exclude from pair search using condition a[i]!=i (because they will randomly fill empty spots)

2) do not mark duplicates to include pairs containing duplicate values.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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];
}
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Will not hashmap do?

Comment hidden because of low score. Click to expand.
0

@ 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).

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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......

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

This comment has been deleted.

Comment hidden because of low score. Click to expand.
0

@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.

Comment hidden because of low score. Click to expand.
0

Since the array is sorted you can use binary search on it and time compility will be o(log n)

Comment hidden because of low score. Click to expand.
0

Oops, sorry I misread the question!

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.