## Microsoft Interview Question for Member Technical Staffs

Team: Azure
Country: India
Interview Type: Phone Interview

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

Transform given set of IP addresses into 32 bit unsigned int
Apply quick sort or merge sort.
Transform it back to the ip addresses. O(n*logn).

Or you can write a comparator with transform the ip to int on the fly O(n*logn).

The former is faster. The latter save a bit on space.

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

Fastest solution. Nice.

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

not fastest.
Where is the complexity of transformations?
Total complexity will be O(n + n*logn).
Not faster then any other solution with transformations before and after sort (mine, for example).

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

First of all, i didn't say it is the fastest.

Second, the big O notation is a set which consider asymptoticly performance.

Therefore O(n+nlogn) is exactly the same as O(nlogn).

Do not write things like this or O(4n). It is misleading and only showing people your lack of understanding of asymptotic notation.

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

TheShocker1999 said it was the fastest. So, my notice was for him.
I agree with you, with some note:
O(n+nlogn) is quite possible, but it is necessary then to proceed: O(n+nlogn) -> O(n*(1+logn)) -> O(nlogn).
Things like O(4n) are also possible during the process of evaluating. See, always where I use it, I write "O(4n), actually O(n)", meaning: " O(4n), but because 4 - is a constant, actually O(n)". This is ok, I show the process, how I evaluate the complexity.

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

Transform each IP address into a vector of 4 bytes, b1.b2.b3.b4
Step1 : Apply bucket-sort with 256 buckets using b1 as a key. All IP-s with b1 = k are placed into bucket k, for k = 0 to 255. O(n) time complexity.
Step 2: Go over all the buckets that have more than 1 element, and apply another bucket sort using b2 as a key. O(n) time complexity.
Step 3/4 : Apply bucket sort with b3/b4 as a key respectively for all sub-buckets that still have more than 1 element.
Total complexity: O(4*n) = O(n). Worst case is when all the IP addresses are the same, as they will go to the same bucket for each of the steps.

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

I like lepeisi's solution.
1. Simple and transform is one liner.
split the IP into words and convert to int.

``ip_int = nibble0 << 24 + nibble1 << 16 << nibble2 << 8 + nibble0.``

2. Less complexity = less debug, less bugs and fast.
3. use preexisting sort.

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

transform given set of IP addresses into 2D Nx4 matrix of bytes. O(4n), actually O(n),
Then apply MergeSort 4 times according to the number of columns. O(4n*log n), actually O(n*log n).
Then transform result 2D matrix into set of IPs. O(4n), actually O(n),

Overall complexity O(2n + n*logn), actually O(n + n*logn).

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

Use Radix Sort for better performance

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.