Question

Microsoft | OA Coding Questions and Solutions | Set - 38 | 2022

Answer 1

I got this questions in Microsoft OA I wonder what the right answers would be :

 

Given a list of 1000 elements which of the following number is the largest?
A. The number of all possible subses of a given list
B. The number of all possible pairs of elemenst from a given list
C. The number of all possible permutations of a given list
D. 10,000,000,000,000,000

 

You are given an array with 10^8 elements and you must compute the sum A[J] + A[K] for every possible pair of elements in the array. How long will this computation take on a single mainstream computer?

 

A: milliseconds
B: seconds
C: minutes
D: hours
E: more than a few hours

Answer 2

For Question2, I think answer should be B. (seconds)

 

Reason:
Let's take with example of 4 elements {1, 5, 3, 6}
all possible pairs if reps are allowed will be: {1,1}, {1,5}, {1,3}, {1,6}, {5,1},{5,5},{5,3},{5,6}, {3,1}, {3,5}, {3,3}, {3,6}, {6,1}, {6,5}, {6,3}, {6,6}
so, each element will be summed 2N times.
Hence, the sum of all possible pairs can be calculated in a single for loop i.e for(i=0 to N-1) sum+=2N*A[i];

 

And even if reps are not allowed then also, sum can be done in O(N) time. not O(N^2)
{1,5}, {1,3}, {1,6}, {5,3},{5,6}, {3,6}. here calculation will be sum+=(N-1)*A[i]

Answer 3

Question 1

 

Let's say there are n elements and let's convert the alternatives into easier mathematical expressions:
A. 2^n
B. (n choose 2) or (n^2-n)/2, or theta of n^2
C. n!
D. 10^16 < (2^4)^16 = 2^64

 

For our n = 1000, clearly 2^1000 > 2^64, so A > D. Moreover, 1000^2 << 2^1000 since 2^1000 = (2^4)^250 > (10)^250 >> (1000)^50 >> 1000^2. Finally, we know that n! > 2^n asymptotically, but when? I actually looked it up and it's before n=4, so it's answer C.

 

Question 2

 

The complexity of the sum is theta(n^2), see B. for the first question. A modern processor has ~3 GHz or 310^9 cycles per second. We need to compute some c10^16 additions and so it would take us some theta(10^7) seconds to run. Since there are 3600 seconds in an hour, and 10^7/3600 = many hours, the answer is E.

 

I could be incorrect somewhere though, would love if someone could confirm my solution to question 2.