Microsoft Interview Question Member Technical Staffs
Team: Azure
Country: India
Interview Type: Phone Interview
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).
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.
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.
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.
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).
Transform given set of IP addresses into 32 bit unsigned int
- lepeisi November 28, 2015Apply 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.