## Interview Question for Software Developers

Country: United States

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

If the data in question is Numbers/Ints
We 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).

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

why should we use it if it is not faster than brute force?

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

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?

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

asymptotically this is the same O(n), because asymptotically 15 = 1, i.e. 15 is a constant.

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

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.

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

brute force O(n) quite works.

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

i also answered the same. but the interviewer was asking for better ideas. can you suggest any good idea?

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

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.

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

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

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

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..

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

Binary search would work better O(log n)

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

array is unsorted by default.

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

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?

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

just use filter on the array... Array.filter { Your condition } // This will only give the list of distorted elements.

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.