Amazon Interview Question SDE1s
Country: India
Interview Type: In-Person
static int[] AlternatingArray(int[] input)
{
int[] output = new int[input.Length];
int ones = 0, zeros = 0;
for(int i = 0; i < input.Length; ++i)
{
if (input[i] == 0)
zeros++;
else if (input[i] == 1)
ones++;
else
throw new Exception("Only accepting 1s and 0s");
}
if(zeros == 0 || ones == 0)
{
Array.Copy(input, output, input.Length);
return output;
}
int k = 0;
int n = 2;
int num = 0;
output[k++] = 0;
zeros--;
bool IsZeroGroup = false;
while(true)
{
if ((ones + zeros) == 0)
return output;
num = get_f(n++);
if(IsZeroGroup)
{
if(num <= zeros)
{
zeros -= num;
for(int j = 0; j < num; j++)
{
output[k] = 0;
k++;
}
IsZeroGroup = false;
}
else
{
for(int j = 0; j < ones; j++)
{
output[k] = 1;
k++;
}
return output;
}
}
else
{
if(num <= ones)
{
ones -= num;
for(int j = 0; j < num; j++)
{
output[k] = 1;
k++;
}
IsZeroGroup = true;
}
else
{
for(int j = 0; j < zeros; j++)
{
output[k] = 0;
k++;
}
return output;
}
}
}
}
static int get_f(int n)
{
if (n <= 1)
return 1;
else if (n == 2)
return 2;
else
return (get_f(n - 1) * get_f(n-1)) - (get_f(n - 2) * get_f(n - 2));
}
Yeah, it's definitely inefficient.
Easy one.
Sort the input array on the lines of 'Dutch National Flag' sorting scheme so all 0s come to the left and 1s come to the right. Take 2 pointers/indexes - P1 pointing to the start of the subarray with 0s and P2 pointing to the start of the subarray with 1s.
For ex:
0,0,0,0,0,1,1,1,1,1,1,1
^ ^
| !
P1 P2
In iteration k, exchange f(k) 1s from the P2's beginning with 0s from P1 and move ahead the pointers P1 and P2 accordingly. Stop when no such exchange is possible.
public static void reArrange(int[] arr){
int countZero = 0, countOne = 0;
//count 0s and 1s..O(n)
for (int i=0; i<=arr.length-1;i++){
if (arr[i]==0)
countZero++;
else
countOne++;
}
int currentDigit = arr[0];
int groupCount = 1;
int functionValue, previous1FunctionValue = 0, previous2FunctionValue = 0;
outerwhile: while (true)
{
if (groupCount == 1)
functionValue = 1;
else if (groupCount == 2)
functionValue = 2;
else
functionValue = (int) Math.pow(previous1FunctionValue, 2) - (int) Math.pow(previous2FunctionValue, 2);
for (int i = 0; i < functionValue; ++i)
{
System.out.print(currentDigit);
if (currentDigit == 0)
countZero--;
else
countOne--;
// totalPrintCount++;
if (countZero <= 0 ){
for (int j = 0; j< countOne; j++)
System.out.print(1);
break outerwhile;
}
else if (countOne <=0){
for (int j = 0; j< countZero; j++)
System.out.print(0);
break outerwhile;
}
}
currentDigit ^=1;
previous2FunctionValue = previous1FunctionValue;
previous1FunctionValue = functionValue;
groupCount++;
}
}
public static void rearrangeArray(int[] A)
{
int zeros = 0;
int ones = 0;
int aLen = A.length;
for(int i = 0; i < aLen; i++)
{
if (A[i] == 0) zeros++;
if (A[i] == 1) ones++;
}
int f1 = 1;
int f2 = 2;
int fn = 1;
int curIdx = 0;
boolean isZeros = true;
while(fn < aLen)
{
if (fn == 1 && isZeros)
{
if (zeros > 0)
{
A[curIdx++] = 0;
zeros--;
}
isZeros = false;
f1 = fn;
fn = 2;
}
else if ( fn == 2 && !isZeros)
{
while(curIdx <= fn && ones > 0)
{
A[curIdx++] = 1;
ones--;
}
isZeros = true;
f2 = fn;
fn = f2*f2 - f1*f1;
f1 = f2;
f2 = fn;
}
else
{
if (isZeros)
{
int cnt = 0;
while(cnt < fn && zeros > 0)
{
A[curIdx++] = 0;
zeros--;
cnt++;
}
isZeros = false;
}
else
{
int cnt = 0;
while(cnt < fn && ones > 0)
{
A[curIdx++] = 1;
ones--;
cnt++;
}
isZeros = true;
}
fn = f2*f2 - f1*f1;
f1 = f2;
f2 = fn;
}
}
while(zeros > 0)
{
A[curIdx++] = 0;
zeros--;
}
while(ones > 0)
{
A[curIdx++] = 1;
ones--;
}
for(int i = 0; i < aLen; i++)
System.out.print(A[i] + " ");
}
Plz point out if there exist any issue in the implementation.
[Step 1] Given an unsorted array of 0's and 1's, count the number of 0's and 1's (takes O(N)).
[Step 2] Rearrange the array by (i) computing the group length as given in the problem and (ii) putting that number of 0's (or 1's), checking whether we have sufficient number of 0's (or 1's) (O(N)). Stop when we run out of 0's (or 1's).
[Step 3] Append to the array whatever is left
void rearrange(vector<int> &ary)
{
/* count number of 0's and 1's */
int nzeros=0, nones=0;
for(int i=0; i<ary.size(); i++)
if( ary[i]==0 ) nzeros++; else nones++;
/* group lengths */
vector<int> glen;
glen.push_back(1);
glen.push_back(2);
/* put groups of 0's (or 1's) */
int i=0, k=0, len;
bool put_zero = true;
while( nzeros>0 && nones>0 )
{
// compute the group length
if( k>1 ) glen.push_back(pow(glen[k-1],2)-pow(glen[k-2],2));
len = glen[k];
if( put_zero ) {
while( nzeros>0 && len>0 ) {
ary[i++] = 0;
len--; nzeros--;
}
}
else {
while( nones>0 && len>0 ) {
ary[i++] = 1;
len--; nones--;
}
}
k++;
put_zero = !put_zero;
}
/* put whatever is left */
while(nzeros>0) { ary[i++] = 1; nzeros--; }
while(nones>0) { ary[i++] = 1; nones--; }
}
It is easy to see that S(n) = f(0) + f(1) + f(2) + ... + f(n) = sqr(f(n-1)) + 2
(This is a typical example of telescopic series where expressions cancels out cross wise)
Hence F(n) = S(n) - S(n-1).
I use this in getF() function to get F(n) & S(n).
#include <iostream>
using namespace std;
int getF(int val,int &sum) {//Takes in F(n) & S(n), returns F(n+1) & S(n+1)
switch(val) {
case 0:
sum = 1;
return 1;
case 1:
sum = 3;
return 2;
default:
int newsum = val*val + 2; //using f(0) + f(1) + f(2) + ... + f(n) = sqr(f(n-1)) + 2
int val = newsum - sum;
sum = newsum;
return val;
}
}
void rearrangeArray(int n,int *arr) {
int cnt[2];
cnt[0] = cnt[1] = 0; //This array hold # 0's and 1's
for(int i=0;i<n;i++) {
cnt[arr[i]]++;
}
int d=0; //d will be 0 or 1
int pos = 0; //current Array index
int sum = 0,fval = 0;
if (cnt[0] == 0) d=1; //No zeros in arr
while(1) {
fval = getF(fval,sum);
if (cnt[d] < fval) { //Not enough digit d
for(int i=0;i<cnt[d];i++) {//use all remaining digit d
arr[pos++] = d;;
}
for(int i=0;i<cnt[1-d];i++) {//use all remaining digit 1-d
arr[pos++] = 1-d;
}
break;
} else {//write fval d's inarr starting from pos.
for(;pos<sum;pos++) {
arr[pos] = d;
}
cnt[d] -= fval;
d=1-d; //swap 0 <---> 1
}
}
}
int main() {
int n;
cin >> n;
int *arr = new int[n];
for(int i=0;i<n;i++) {
cin>>arr[i];
}
rearrangeArray(n,arr);
for(int i=0;i<n;i++) {
cout<<arr[i];
}
cout<<endl;
}
public static void doTheThing(int arr[])
{
int currentDigit = arr[0];
int groupCount = 1;
int functionValue, previous1FunctionValue = 0, previous2FunctionValue = 0;
int totalPrintCount = 0;
outerwhile: while (true)
{
if (groupCount == 1)
functionValue = 1;
else if (groupCount == 2)
functionValue = 2;
else
functionValue = (int) Math.pow(previous1FunctionValue, 2) - (int) Math.pow(previous2FunctionValue, 2);
for (int i = 0; i < functionValue; ++i)
{
System.out.print(currentDigit);
totalPrintCount++;
if (totalPrintCount >= arr.length)
break outerwhile;
}
currentDigit ^=1;
previous2FunctionValue = previous1FunctionValue;
previous1FunctionValue = functionValue;
groupCount++;
}
}
- Westlake February 11, 2014int main(int argc, char** argv) { int d; int zeros = 0; int ones = 0; while (cin >> d) { if (d == 0) zeros++; else if (d == 1) ones++; else { cout << "bad number"; return -1; } } int fprev = 1; int f = 2; for (int i = 0; zeros && i < fprev; i++, zeros--) { cout << "0 "; } int flag = 1; while (zeros || ones) { if (flag == 1) { flag = 0; for (int i = 0; ones && i < f; i++, ones--) cout << "1 "; } else { flag = 1; for (int i = 0; zeros && i < f; i++, zeros--) cout << "0 "; } int t = f * f - fprev * fprev; fprev = f; f = t; } }