## McAfee Interview Question for Applications Developers

Country: United States
Interview Type: Phone Interview

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

c*(10k)^2 => 100 sec

1/2*c*n^2 => 100*1/2 sec => 50 sec
c * (sqrt(1/2)*n)^2 => 50 sec

n1 => input size => sqrt(1/2) * floor(10k)
~ 0.7 * 10 k
=> 7k
= 7000

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

options are
100
1000
2500
5000

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

Seems like 5k is an estimate. If you estimate the sqrt of 1/2 is 0.5, then 5k is the closest answer.

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

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

7K ,not in option but 7k is closest.(or we shuld say max Entries).

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

100/10000=50/x
ans 5000

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

It varies. In extreme scenarios, it could be from as low as 70 up to as high as 50.000.000!

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

So where do you get these numbers?

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

Bubble sort as we know has O(n^2) worst case performance and O(n) best case (when data are already sorted).

Consider the following extreme scenarios:

a) In the first run data were sorted so bubble sort run in O(n) time, that is, it did 10000 operations in 100 seconds or 100 ops per second. Now assume in second run data were sorted in reverse order so bubble sort run in O(n^2) time. With 100 ops per second it did 5000 ops, enough only to sort sqrt(5000) ~= 70 elements.

b) In the first run data were sorted in reverse order, so bubble sort took O(n^2) time, that means 10.000^2 = 100.000.000 ops or 1.000.000 ops per second. Assume the data are sorted in the second run, now bubble sort, in 50 sec, can process 50.000.000 elements.

Don't pay attention at the exact numbers, I'm talking about orders of magnitude, and it varies a lot.

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

I see what you're saying. We must have a different picture of what exactly constitutes a bubble sort. The way I learned to do it, way back in the day, has the best, worst, and average case at O(n^2). Insertion sort, on the other hand, can be as bad as O(n^2) or as good as O(n).

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

Its complexity is O(n^2). Means processor is doing 10000^2, i.e. 10^8 steps in 100 sec. In 50 Sec it will do 50*10^7 steps. Sqrt of it is approx 7000. Hence input size is 7k

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

100sec - 10000 entries
50sec - just add two zero's extra so 5000 entries

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

Here's a simple approach I thought of:

Bubble sort has a complexity of n^2. So the ratio of variation in time taken should be squared of the ratio of variation in data set size. Here, the time reduces by 2, hence the data set size must reduce by 4, i.e., 10000/4=2500 (option c is the correct answer).

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

As there are 10,000 entries so bubble sort will make at most (10,000 * 5,000) approx comparison .and it takes 100 sec(Given).
100sec-----------------(10,000 * 5,000) approx comparison
1 sec ------------------(10,000 *50 ) approx comparison
so for 50 sec------(2500 * 10,000)approx comparison
Now we have to find out the input size which makes (2500* 10,000) comparison or less...According to options 5000 entries corresponds to approx( 2500* 5000)comparison.
so I would go for 5k...

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.