Amazon Interview Question
Software Engineer / DevelopersI 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.
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
@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 :)
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);
printf("\n the answer is %d",*q);
getch();
return 0;
}
gives the answer as :7 which is correct
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.
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..
I agree, we can iterate over bitarray using bitwise operators.
But how can we return address of bit in int?
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.
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++)
{
mask = 0x8000;
for (j = 0; j < 16; j++)
{
if (arr[j] & mask)
{
if (!count)
{
iCandidate = i;
jCandidate = j;
}
count++;
}
else
{
if (count > max)
{
max = count;
ii = iCandidate;
jj = jCandidate;
}
count = 0;
}
max >>= 1;
}
}
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);
printf("\n the answer is %p",p);
getchar();
return 0;
}
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;
unsigned int index=0;
unsigned int max_bits=0;
unsigned int temp_bits=0,no_bits=0;
unsigned int mask=0;;
for(i=0;i < ARRAYSIZE;i++)
{
mask = 1;
no_bits = 0;
for(j=0;j<INTSIZE;j++)
{
if(a[i] & mask)
temp_bits++;
else
{
if(temp_bits > no_bits)
no_bits=temp_bits;
temp_bits=0;
}
mask = mask << 1;
}
if(no_bits > max_bits)
index=i;
}
return i;
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 mask=0;
unsigned int temp_bit_index=0;
for(i=0;i < ARRAYSIZE;i++)
{
mask = 1;
no_bits = 0;
for(j=0;j<INTSIZE;j++)
{
if(array[i] & mask)
temp_bits++;
else
{
if(temp_bits > no_bits)
{
no_bits=temp_bits;
temp_bit_index =j - temp_bits;
temp_bits=0;
}
mask = mask << 1;
}
if(no_bits > max_bits)
{
array_index=i;
bit_index = temp_bit_index;
}
}
return;
}
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 mask=0;
unsigned int temp_bit_index=0;
int i=0,j=0;
for(i=0;i < ARRAYSIZE ;i++)
{
mask = 1;
no_bits = 0;
temp_bits=0;
for(j=0;j<INTSIZE;j++)
{
if(array[i] & mask)
temp_bits++;
else
{
if(temp_bits > no_bits)
{
no_bits=temp_bits;
temp_bit_index = j - no_bits;
temp_bits=0;
}
}
mask = mask << 1;
}
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;
}
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;
}
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;
}
Do we need to take care of endianness ?
- Anonymous June 18, 2010eg no=16704 can be represented as
01000001 01000001 MSB LSB
01000001 01000001 LSB MSB
depending upon endianess