Amazon Interview Question Software Engineer / Developers
@vinod: nice solution :)
Here is a simple example that I worked on to grasp your idea. Plz correct if I assumed something wrong:
given array [1...11] = {2,5,12,13,15,20,6,9,10,18,25}, k = 6
when i = 3, j = 7, a[3] > a[7]
result after rotation= {2,5,6,9,10,18,25,12,13,15,20}
next i=6, j=8, a[6] > a[8]
result after rotation= {2,5,6,9,10,12,13,15,20,18,25}
next i=9, j=10, a[9] > a[10]
result after rotation= {2,5,6,9,10,12,13,15,18,25,20}
next i=10, j=11, a[0] > a[11]
result after rotation= {2,5,6,9,10,12,13,15,18,20,25}
I've doubt if it's really O(n)? Because whenever you rotate, it takes O(n-i+1) operations to shift the elements from [i,n]. Assume the worst case like below:
a[1...10] = {2,4,6,8,10,1,3,5,7,9}
for this input if i do the above process it is indeed O(n^2).
Could you give amortized analysis of your approach which ensures O(n) operations for any input? Thanks.
Yes, you are right. I checked my solution again and thought about the worst case, where all elements of the first array are larger than every element of the second array.
Here, the case (3) would be executed at every instance, as everytime the value of a[j] is greater than a[i]. And the cost of the array rotation function would actually be O(n). Hence I guess the total time would be k or n-k times O(n), which would become non-linear.....
I dont think this is possible in O(n) time and O(1) space... think about it.. if this was possible then why would the merge step in mergesort need additional space? Please do correct me if I am wrong.
It doesn't; it's just that in practice, all in-place merges suck out loud and thus do not get covered in undergraduate algorithms courses.
But do those inplace merges happen in linear time? Rotating the array may work but it clearly is non-linear right?
What if you start the last indexes of both arrays like a[k-1] and a[n], then I feel you don't need the repeat step. correct me if I am wrong.
#include<iostream>
using namespace std;
class Sorter
{
private:
int *arrPtr1, *arrPtr2, *head;
int n1,n2, flag;
void swap()
{
int temp = *arrPtr1;
*arrPtr1 = * arrPtr2;
*arrPtr2 = temp;
}
public:
Sorter(int *p, int n)
{
head= arrPtr1 = p;
flag=1;
arrPtr2 = NULL;
// finding k
int i;
for ( i =0; i<n; i++, p++)
{
if( (*p) < (*(p+1)))
continue;
else
{
flag=0;
n1 = i+1;
arrPtr2 = (p+1);
n2 = n - n1;
break;
}
}
}
void Sorty()
{
if ( !flag)
{
for( int i =0; i<n2; i++)
{
for(int j=0; j<n1; j++, arrPtr1++)
{
if( *arrPtr1 > *arrPtr2)
swap();
}
n1++;
arrPtr2++;
arrPtr1 = head;
}
}
}
};
void main()
{
int arr1[] = { 1,2,6,8,9,10,3,4,5,7,13};
int arr2[] = {13,14,15,19,21,26,28,11,13,17,18,20,25};
Sorter s1(arr1, 11);
Sorter s2(&arr2[0], 13);
for( int i=0;i<11; i++)
cout<<arr1[i]<<' ';
s1.Sorty();
cout<<endl;
for( int i=0;i<11; i++)
cout<<arr1[i]<<' ';
cout<<endl<<endl<<endl;
for( int i=0;i<13; i++)
cout<<arr2[i]<<' ';
s2.Sorty();
cout<<endl;
for( int i=0;i<13; i++)
cout<<arr2[i]<<' ';
cout<<endl;
getchar();
}
void CyclicShift(int a[], int N, int K)
{
if (K > N) K %= N;
if (!K) return;
int processed_elements = 0,
loop_start_index = 0;
while (processed_elements < N) {
int current_index = loop_start_index;
int memory = a[current_index];
do {
int mapped_index = (current_index + K) % N;
a[mapped_index] ^= memory ^=
a[mapped_index] ^= memory;
++processed_elements;
current_index = mapped_index;
} while (current_index != loop_start_index
&& processed_elements < N);
++loop_start_index;
}
}
void Merge(int a[], int N, int offset)
{
int i = 0, j = offset;
while (i < j && j < N)
if (a[i] > a[j]) {
int k = j;
while (a[k] < a[i] && k < N) ++k;
CyclicShift(a + i, k - i, k - j);
i += k - j;
j = k;
} else ++i;
}
I don't understand why the HELL people post their code? Who needs code here? Can't we code this program if we can grasp the idea?
Guys, you should explain the idea clearly. It'd help you to flourish your capability to explain an idea which must help you in real interview as well. It's not an easy task to comprehend your idea in a convincing manner, specially when you are in a job interview. It's a lot easier for others to detect flaws in idea, rather in code. A job seeker should be able to code this type of programs using basic syntax of a language (otherwise, how the f*** s/he desires to be hired).
Please no offense. I wanted to encourage you guys to help in constructive way for the other candidates. Thanks.
I believe that just the idea is not enough to code it entirely. Code is like the complete solution. I do agree that being able to succinctly present your idea is very essential. But being able to code on it is more so. I screwed a few interviews even when I had a complete idea, because I hadn't coded in a while.
I have a solution, it's actually pretty simple to implement. It's O(n) in time and O(1) in space. I haven't run it but I think the logic is sound. Any bugs here?
void sortarrays(int[] A, int k, int n)
{
int i=0;
while (i<=k)
{
if (a[i] < a[k+1]) // nothing to do, already in sorted order
i++;
else
{
int j=k+1;
// swap a run from within a[i..i+N-1] with a[k..k+N-1], N is # iterations
// the loop exits when a[i+N] < a[k+N] however we also know that
// a[i+N] > a[i..i+N-1] (before swaps) since A[0..k] is sorted
// so by transitivity
// a[i+N] < a[k+N] < a[k+N+1..n]
// a[i..i+N-1] (before swap) < a[k+N] < a[k+N+1..n]
// a[k+1..k+N-1] (after swap) < a[k+N] < a[k+N+1..n]
// so in fact a[k+1..n] is still sorted, this is the original problem again
// so iterate until i>k and exit. Since a[k-1] < a[k] the resulting list is
// fully sorted.
while (a[i] > a[j] && i <= k && j <= n)
{
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
j++;
i++;
}
}
}
}
Dude, there's no O(N) time solution but there's O(NlogN) time solution with O(1) space complexity. I am sure about this because I have come across this question during amazon interview :P. My first reply was O(N^2) complexity solution which he then told me to improve it. He also gave me hint to solve this problem , with which i concluded it's O(NlogN) .
so all you guyz can start trying for O(NlogN) and O(1) space complexity.
If you only need an O(nlogn) solution, just use any inplace sorting algorithm (e.g. heapsort).
Correct me if I am wrong...but does your solution use O(1) memory ?? I donot think so..
Solution is very simple
problem clearly says we have two arrays
One is a[1…k] and other is a[k+1...n] which themselves are sorted
Next we have to apply the merge sort in a single array
It takes less than O(n) time
I would clear that
In best case it will take O(k) or O(1) or O(n-k) if k+1=n which is less than O(n)
try the following code
sort(int a[],int k,int n)
{
int j=k+1;
for(int i=0;i<k && j<n;i++)
{
// condition is true then they are in order just move to next element in the first array
if(a[i]<a[j])
continue;
else
{// swapping needed
a[i]=a[i]+a[j];
a[j]=a[i]-a[j];
a[i]=a[i]-a[j];
j++;
}
}
}
it take either O(n-k) or O(k) time
O(1) space
you may ask a question that what about i is it not take sapce
generally on finding the space complexity we ignore the looping vars
why because they will store in registers
Hinax, man, if k=0 it's the best case as everithing is sorted. King is the King. Exept for a minor fixable issue it works.
0(n) time with o(1) space complexity solution
void Sort(VEC_INT_ARRAY& a, int k)
{
int i = 0;
int j = k + 1;
int s = k;
while (i <= k)
{
bool bFirstSwap = false;
while(i <= k && j < a.size())
{
if(a[i] < a[j])
{
i++;
}
else
{
swap(a[i], a[j]);
if(!bFirstSwap)
{
bFirstSwap = true;
s=i;
}
i++;
j++;
}
}
i = s + 1;
j = k+1;
}
}
Recursive approach. Some will contend that recursion isn't really O(1) space, but sometimes I doubt whether the interviewer just says O(1) space to prevent you from creating additional array or using auxiliary data structure.
Idea is as follows. We have 2 sorted subarrays, so let's have i & j refer to the first element of both subarrays. In each recursive call, we pick the smaller element that we will eventually write to arr[p], while performing a recursive call that advances either i or j depending on which element is smaller or which subarray we have exhausted etc.
static void mergeAt(int[] arr, int k) {
int i = 0;
int j = k+1;
int p = 0;
placeAt(arr, p, i, j, k);
}
// place min(arr[i], arr[j]) into arr[p]
static void placeAt(int[] arr, int p, int i, int j, int k) {
if(i>k && j>=arr.length)
return;
int min = 0;
if(i>k || (j<arr.length && arr[i] > arr[j])) {
min = arr[j];
placeAt(arr, p+1, i, j+1, k);
} else {
min = arr[i];
placeAt(arr, p+1, i+1, j, k);
}
arr[p] = min;
}
Nice question.
- vinod July 18, 2010Ok, heres my algorithm:
1. Have to indexes i and j pointing to the first elements of a[0]...a[k] and the other array respectively.
2. Now, compare a[i] and a[j]. If, a[i] is the smaller value, the good, you dont have to do anything as it is already in the right position. Just increment the value of i.
3. If a[j] is the smaller value, then comes the problem, as it should go to the position of i.
3.a Now, let x point to j and increment x till the value of a[i] is smaller than a[x]
or till x goes beyond the array.
3.b Now as per logic, the entire array a[j...x-1] should come before a[i....k]. For this just call another function, which simply rotates the array a[i...x-1] by k-i+1 left using O(1) space. That is pretty simple, and already this part was posted as a q by someone.
3.c After that, update your k to k+(x-j) (as x-j elements added to the initial array) and your i to i+(x-j+1) and your j to x-1.
3.d If either j or i has not reached end of array, ie. n and k respectively, then go to (2). Else END.