## Amazon Interview Question for Software Engineer / Developers

• 1
of 1 vote

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

Do we need to take care of endianness ?

eg no=16704 can be represented as

01000001 01000001 MSB LSB
01000001 01000001 LSB MSB

depending upon endianess

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

typo in above post

eg no=16704 can be represented as

01000001 01000000 -- MSB LSB
01000000 01000001 -- LSB MSB

plz consider this !

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

I got a method:
1)Define a signature for each int. For example, an integer like 1111,0011,1111,0000 will have a signature in string as "14021604". The even char in the signature is either 0 or 1, while the odd char is the # of consecutive 0 or 1, which is represented in hex (since the consecutive # of 0 or 1 may be larger than 10, but we only want represent the # as one char).
2)therefore, we can convert the whole array into a string.
3)Go through the whole string, it is easy to get the longest consecutive sequence of 1 and its bit position.
For example, we have an array like: 3, 4, 5, 7, if we represent each int as 4 bits, we will have 0011, 0100, 0101, 0111. Then we have the signature: "0212","011102","01110111","0113".
Then we go through the string, we can get the longest consecutive sequence is 3.

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

1. Start scanning the array from base address.
2. Have a counter=0,max-counter=0,pointer initialized.
3. start incrementing the counter until a zero occurs and compare counter with max-counter and counter is greater than max-counter then store the base address as well.
4.Start incrementing the address until a 1 occurs;
5. Repeat step 2

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

@chenming: ur method seems to be gr8... but the actual time complexity according to u will lie in assigning the "signatures" for each integer... which is O(lgk) for each int ... where 'k' is the integer ....
if there are 'n' integers... then the overall complexity will be O(nlgk)
and of course for the final scanning of the string will take another O(n)
so overall complexity is O(nlgk) .
nice idea :)

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

int *largestseqone(int * p,int len)
{
int *temp=p;
int count=0,maxcount=0;
int i=0,n=0;
for(i=0;i<len;i++)
{
n=*(temp+i);
printf("\n %d \n",n);
while(n!=0)
{
if(n%2==1)
{
count++;
printf("count increment: for %d is %d ",n,count);
if(count>maxcount)
{
maxcount=count;
p=temp+i;
}
}
else
{
if(count>maxcount)
{
maxcount=count;
p=temp+i;
}
count=0;
}
n=n/2;
}
count=0;
}
return p;
}

int main()
{
int arr[5]={1,13,12,8,7};
int *q=largestseqone(arr,5);
getch();

return 0;
}

gives the answer as :7 which is correct

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

can u explain ur code??

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

Everybody has written something,but can somebody explain how can one return a pointer to a bit in C ??????????????
I think there should be a correction in the question

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

Something take this simple example:
Array = {15,7,2,1,0,23}
1111,0111,0010,0001,0000,10111
^
Result: Pointer should point to 1st bit of number 15.

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

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

Longest sequence of 1 implies the highest number in the collection. If we know the highest number in the collection, then we can return the pointer to it.

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

No, its not that way. you have to find longest sequence .
for example. if your array has following in bit representation:
1111,0111,0011,1110,0000,10111
then your longest sequence has 5 ones but the longest number has only 4 ones.

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

Thought about a method..Let me know if sounds Ok..
1.)keep incrementing the given integer pointer to access the elements of the array.
2.)for each integer element use the left shift operator to determine the longest sequence of 1's i.e.both "start" and "end" point..
2 a.)if the "end" point of previous element and starting bit of next element are continuous and greater increase the global count of "Continous 1's" and their starting position.
3.)For each element maintain the the number of continous 1 bits from the 16th bit.
3 a.)if the "end" point of previous element and starting bit of next element are continuous and greater increase the global count of "Continous 1's" and their starting position.
4.)finally we will have the global variable with maximum 1's with their start and endpoints.Probably return a type casted character pointer to the starting point..

I know I have written it in a confused manner. But I hope u get the Idea..

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

could u please explain with an example

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

I don't think we need to consider endian problem, as long as we compare bit by bit.

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

how about taking two character pointers pointing to beginning of array and move till its size. moving a pointer one by one as soon as u find 1 and simultaneously tracking the sequence count and initial pointer of sequence.

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

I would suggest to have a 16 bit long bitmask with first bit set as 1 and rest set to zero. Do AND of that with a given integer. Check if output is 1 else do left shift of 1 bit on bitmask and check for 1 again. Once you got 1, store it and check for longest sequence in a similar way.

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

this is problem on bit array(search wiki) ,implement iterator over bitarray .

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

I agree, we can iterate over bitarray using bitwise operators.
But how can we return address of bit in int?

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

wtf!!
y are u giving yr phone number here.. lame

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

Definately, It is not for the people who think like you.
sometimes students call me for doubts.

Please be as professional, and not like 3rd class people on road.

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

This makes you lamer.

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

People are posting their phone numbers here lol. I wish u were a girl then :D

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

Get a life dude. :)

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

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

@eName, @lamer, @Mahesh, @Anonemous... All of you put your heads under .......

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

I don't think that it is important point to return pointer to bit. What is important that the algorithm implementation.

``````mask = 0x8000;
count = 0;
max = 0;
ii = 0;	// index of element in the array where longest sequence of "1"s start.
jj = 0;	// index of first "1" bit in above element
iCandidate = 0, jCandidate = 0;
for (i = 0; i < arrLen; i++)
{
for (j = 0; j < 16; j++)
{
{
if (!count)
{
iCandidate = i;
jCandidate = j;
}
count++;
}
else
{
if (count > max)
{
max = count;
ii = iCandidate;
jj = jCandidate;
}
count = 0;
}

max >>= 1;
}
}``````

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

Tested this in VC++, but can't figure out how to return ptr to bit.

void printArrayBits (int *ptr, int arraySize)
{
unsigned int i = 0, j = 0;
unsigned char *p = 0;

p = (unsigned char *) ptr;
for (i = 0; i < arraySize * sizeof(int); i++) {
printf ("%08X: ", i+p);
for (j = 0; j < 8; j++) {
if (*(p+i) & (0x80 >> j))
printf ("1");
else
printf ("0");
}
printf ("\n");
}
}

unsigned char *findLongestContinuousOneBitsInArray (int *ptr, int arraySize)
{
unsigned int i = 0, j = 0;
unsigned char *retPtr = 0;
unsigned char *p = 0;
unsigned char *q = 0;
int numOfOnes = 0;
int maxNumOfOnes = 0;

p = (unsigned char *) ptr;
for (i = 0; i < arraySize * sizeof(int); i++) {
for (j = 0; j < 8; j++) {
if (*(p+i) & (0x80 >> j)) {
if (numOfOnes == 0) {
// remember where we started
q = (p+i);
}
numOfOnes++;
} else {
if (numOfOnes > maxNumOfOnes) {
maxNumOfOnes = numOfOnes;
retPtr = q;
}
numOfOnes = 0;
}
}
}

// In case the array is all 1's
if (numOfOnes > 0 && q == 0) {
retPtr = q;
}

return retPtr;
}

int main(int argc, char* argv[])
{
int arr[5]={1,13,12,8,7};

printArrayBits (arr, 5);
unsigned char *p = findLongestContinuousOneBitsInArray (arr, 5);

getchar();

return 0;
}

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

unsigned int index=0;
unsigned int max_bits=0;
unsigned int temp_bits=0;
unsigned int flag=1;

for(i=0;i< ARRAYSIZE;i++)
{
flag = 01U;
for(j=0;j<INTSIZE;j++)
{
if(a[i]& flag)
temp_bits++
flag = flag << 1;
}
if(temp_bits > max_bits)
index=i;
}
return i;

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

unsigned int index=0;
unsigned int max_bits=0;
unsigned int temp_bits=0;
unsigned int flag=1;

for(i=0;i< ARRAYSIZE;i++)
{
flag = 01U;
for(j=0;j<INTSIZE;j++)
{
if(a[i]& flag)
temp_bits++;
flag = flag << 1;
}
if(temp_bits > max_bits)
index=i;
}
return i;

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

unsigned int index=0;
unsigned int max_bits=0;
unsigned int temp_bits=0;
unsigned int flag=1;

for(i=0;i< ARRAYSIZE;i++)
{
flag = 01U;
for(j=0;j<INTSIZE;j++)
{
if(a[i]& flag)
temp_bits++;
flag = flag << 1;
}
if(temp_bits > max_bits)
index=i;
}
return i;

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

unsigned int index=0;
unsigned int max_bits=0;
unsigned int temp_bits=0;
unsigned int flag=1;

for(i=0;i< ARRAYSIZE;i++)
{
flag = 01U;
for(j=0;j<INTSIZE;j++)
{
if(a[i]& flag)
temp_bits++;
else
{
if(temp_bits > no_bits)
no_bits=temp_bits;
temp_bits=0;
}
flag = flag << 1;
}
if(temp_bits > max_bits)
index=i;
}
return i;

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

unsigned int index=0;
unsigned int max_bits=0;
unsigned int temp_bits=0,no_bits=0;

for(i=0;i < ARRAYSIZE;i++)
{
no_bits = 0;
for(j=0;j<INTSIZE;j++)
{
temp_bits++;
else
{
if(temp_bits > no_bits)
no_bits=temp_bits;
temp_bits=0;
}
}
if(no_bits > max_bits)
index=i;
}
return i;

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

void get_indexes(int *array_index,int * bit_index,int *array)
{

unsigned int max_bits=0;
unsigned int temp_bits=0,no_bits=0;
unsigned int temp_bit_index=0;

for(i=0;i < ARRAYSIZE;i++)
{
no_bits = 0;
for(j=0;j<INTSIZE;j++)
{
temp_bits++;
else
{
if(temp_bits > no_bits)
{
no_bits=temp_bits;
temp_bit_index =j - temp_bits;
temp_bits=0;
}
}
if(no_bits > max_bits)
{
array_index=i;
bit_index = temp_bit_index;
}
}
return;
}

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

The following function will work

#define ARRAYSIZE some value
#define INTSIZE 16

void get_indexes(int *array_index,int *bit_index,int *array)
{
unsigned int max_bits=0;
unsigned int temp_bits=0,no_bits=0,temp_bits1=0;
unsigned int temp_bit_index=0;

int i=0,j=0;

for(i=0;i < ARRAYSIZE ;i++)
{
no_bits = 0;
temp_bits=0;
for(j=0;j<INTSIZE;j++)
{
temp_bits++;
else
{
if(temp_bits > no_bits)
{
no_bits=temp_bits;
temp_bit_index = j - no_bits;
temp_bits=0;
}
}

}
if((no_bits > max_bits) || (temp_bits > max_bits) )
{
max_bits=temp_bits > no_bits ? temp_bits : no_bits;
*array_index=i;
*bit_index = temp_bits > no_bits ? (j - temp_bits) : temp_bit_index;
}

}
return;
}

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

I think this should work, any advice ? ( make a little change, return max length of '1', no start position )

``````int	LeftOne( short  num)
{
int count = 0;
while( num & (short)0x8000)
{
count++;
num <<= 1;
}
return count;
}

int	RightOne(short num )
{
int count = 0;
while( num & (short) 1 )
{
count++;
num >>= 1;
}
return count;
}

int	MaxContiguousOne( short *input, int len)
{
int max = 0;
int sum = 0;

for ( int i = 0; i < len; i++)
{
if ( input[i] == 0xEEEE )
{
sum += 16;
continue;
}
else
{
sum += LeftOne(input[i]);
if ( sum > max )
max = sum;
sum = RightOne(input[i]);
}
}
return max;
}``````

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

static int bitcount_lookup[256] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};

/* returns number of 1 bits */
static idx_t
count(bitarrayobject *self)
{
Py_ssize_t i;
idx_t res = 0;
unsigned char c;

setunused(self);
for (i = 0; i < Py_SIZE(self); i++) {
c = self->ob_item[i];
res += bitcount_lookup[c];
}
return res;
}

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.