Interview Question Software Developers
Country: United States
Comparing(>=<) Numbers is more expensive(32 times more expensive?) than XORing a single bit per number.
Since the the data is 10 million, the XOR solution could perform much better than Brute Force.
What do you think?
You know that if you have n elements and that each should be x size, the total size of the array should be: xn
Now you assume that one of the elements has changed size.
Divide by the middle element. One side will be (xn/2) and one side will not (as it contains the distorted element).
Continue to do this division until you find the element that is out of place.
i also answered the same. but the interviewer was asking for better ideas. can you suggest any good idea?
better ideas can appear only when the array is somehow preprocessed (i.e. maintained in sorted order, etc.).
Or, if we limit access to array only via special API, then we can detect distortion of data immediately after each access in O(logn) in worst case or even in O(1) w.h.p. if we implement some kind of hashing.
how about validating arrayelement[14] such that it doesn't contain junk value..if its junk then the length is less than 15.
if the array element is string we can check arrayelement[14] for null termination '\0',if not null terminated then length is less than 15
if the array element is number we can check arrayelement[14] for empty value or if value is other than 0 -9 then length is less than 15
How about validating the arrayelement(14) for junk value..if its junk then the length of array is less than 15.
If the array element is string then we can validate array element(14) for null termination or empty value
If array element is integer we can validate array element (14) for empty value,or junk value..
Technically an array itself assumes a contiguous piece of memory which consists of chunks of equal size, and that size is the size defined by the type of the elements stored in the array. So when you say "some of the data length changed somehow", what does that mean? Obviously the size of the array element cannot change after it's been allocated. So the only option I can imagine is something like this:
char *strArray[1000];
for (int i = 0; i < 1000; ++i)
{
strArray[i] = new char[15];
memset(strArray[i], 'a', 14); // filling first 14 positions with 'a'
strArray[i][14] = '\0';
}
// So the strings are all 15 characters long (including the terminating null).
// Now some of them can get shorter:
strArray[100][8] = '\0';
but this does not change the size of array elements in anyway, they are still of type 'pointer to char' and hence 4 bytes (if not a 64-bit architecture with 8 byte addressing). That's why I ask, what does the size change mean?
If the data in question is Numbers/Ints
- anilnuru January 06, 2016We can do a Partial MSD-Radix Sort at the Bit Level which will put all numbers more than 15 digits into the same Bucket.
The way radix sort works is with a Simple XOR operation on a certain Predetermined bit(based on 15 length) so it will be extremely fast and it is O(n).