Microsoft Interview Question Software Engineer in Tests
n + LOGN - 2 is a hint itself.
think about: how many number does the MAX have to "kill" to win its laurel ? Think something else than n-1, something "log"
Just n: scan all n elements, and keep update two variables: first smallest and second smallest.
if you will compare each element to both smallest, and second smallest, you will get 2*n.
Which is why you store 2 pointers, if x < smallest, then secondSmallest = smallest and smallest = x. This is an operation of n.
you missed one situation where the new item is between the values you stored:
say you have
1st_smallest = 1, 2st_smallest = 100
and what if the new item is 50?
I'm confused. If you initiate the smallest and secondSmallest to some value in the array, say A[1], then you would never have the issue where i was pointing at a number in between the values for smallest and secondSmallest. Maybe I am wrong but I feel like it would still work for all cases.
right track but regular heapify costs more than n+logn in terms of number of comparisions
first round divide into n/2 group; then divide n/2 winner into n/4 group, go on until only 1 winner left. The whole process has logn rounds, total comparsion is 2^(logn)-1; the final winner beat logn numbers, so the 2nd smallest is these logn guys, which need logn-1 comparisons to find. So the total comparison is n+logn-2.
use the heap sort.
1. create min-heap O(n), get the smallest element
2. adjust the heap, use O(logn), pick the 2nd smallest element
How about using Fibonacci heaps whose inserts are O(1) and delete min is O(log(n)).
My idea:
1. Loop over n elements and maintain the smallest element. Insert all the elements except for the smallest one in fibonacci heap. O(n)
2. Extract min from the heap. O(log(n-1))
= n + log(n-1)
I cannot get n + log(n-2), any ideas ?
I think the complete operation for finding first smallest and second smallest can be done in O(n) time, here is the code:
smallest = arr[0];
t_smallest = arr[1];
for(int ii = 1; ii < arr.size(); ii++) {
if(arr[ii] < smallest) {
t_smallest = smallest;
smallest = arr[ii];
}
else if(t_smallest > arr[ii])
t_smallest = arr[ii];
}
Comment if this can fly?
Thanks!
I don't know about the -2, but n + log(n) is the time for making the heap, and one sift down with the last element...Then the second element would be at the top. Sift down heap creation takes O(n), but the proof is tricky. Some people here have said that its O(n log n), but that's if you just insert each element in turn (sift up). Actually, it seems like after heap creation, the second element would have to be at the top of one or the other subheap, so it seems like it should be n + 1 comparison (of the sub-heap heads).
Use tournament method to find the second largest element in the list.
Compare the adjacent elements from the array and advance the winner to the next round.
As you compare the adjacent elements keep track of maximum Seen So far and the element that lost to the Maximum. Store that value in a separate array.
That will give you the list of all elements that lost to the Maximum element.
finding the max among this list will give you the sec largest.
I do not get the question. This is what I have understood so far. We are given a heap and we have to find the second smallest element.
This is what I think the answer should be. Since this is a min heap.We can find the smallest element in O(1). Remove the smallest element and heapify. O(log n). Now remove the second smallest element O(1). So the total cost should be O(log )
What am I missing here ?
@ harish write method...in first pass we ll find minimum that requires n-1 comparisons and we also store all those elements which won over their adjacent in comparison so that leaves us with log(n) numbers which again require log(n)-1 comparisons so total of n+logn(n)-2
What about the case that maximum is the first one?
All comparison is just confirm the current element is the largest. The array kept is just a meaning less n-1 element without any order info.
The smallest of n numbers can be found with n − 1 comparisons by conducting a
tournament as follows: Compare all the numbers in pairs. Only the smaller of each
pair could possibly be the smallest of all n, so the problem has been reduced to that
of Þnding the smallest of n/2 numbers. Compare those numbers in pairs, and so
on, until theres just one number left, which is the answer.
To see that this algorithm does exactly n −1 comparisons, notice that each number
except the smallest loses exactly once. To show this more formally, draw a binary
tree of the comparisons the algorithm does. The n numbers are the leaves, and each
number that came out smaller in a comparison is the parent of the two numbers that
were compared. Each non-leaf node of the tree represents a comparison, and there
are n − 1 internal nodes in an n-leaf full binary tree (see Exercise (B.5-3)), so
exactly n − 1 comparisons are made.
In the search for the smallest number, the second smallest number must have come
out smallest in every comparison made with it until it was eventually compared
with the smallest. So the second smallest is among the elements that were compared
with the smallest during the tournament. To Þnd it, conduct another tournament
(as above) to Þnd the smallest of these numbers. At most lg n (the height
of the tree of comparisons) elements were compared with the smallest, so Þnding
the smallest of these takes lg n − 1 comparisons in the worst case.
The total number of comparisons made in the two tournaments was
n − 1 + lg n − 1 = n + lg n − 2
in the worst case.
Source: CLRS :)
## My solution using divide and conquer ##
Divide step : keep dividing input array into two equal sub arrays until it's length is 1.
Conquer step :
For the base of length 1 : no comparision required to find smallest and second smallest elements
For the base case of length 2 : 1 comparision is required to find smallest and second smallest elements
For the all other cases of length > 2 : 2 comparisions are required to find smallest and second smallest elements
## Code :) ##
/**
*
* @author gajera
*/
public class SecondSmallest {
int comparisionCount;
public int findSecondSmallest(int input[]) {
int mins[] = this.smallestTwoElements(input, 0, input.length-1);
return mins[1];
}
// Returns array of length two where [0] is smallest element and [1] is second smallest element found
// in input[] array from "start" index to "end" index inclusive.
public int[] smallestTwoElements(int input[], int start, int end) {
// Base case of length 1 [No comparision]
if(start == end) {
int mins[] = {input[start], input[start]};
return mins;
}
// Base case of length 2 [1 comparision]
if(end-start == 1) {
int mins[] = new int[2];
if(input[start] <= input[end]) {
mins[0] = input[start];
mins[1] = input[end];
} else {
mins[0] = input[end];
mins[1] = input[start];
}
return mins;
}
int middleIndex = start + (end-start)/2;
int rightMins[] = this.smallestTwoElements(input, start, middleIndex);
int leftMins[] = this.smallestTwoElements(input, middleIndex+1, end);
// Actual saving of comparision happens in following step. It reduces 3 comparisions to 2 comparisions.
// From pair of two smallest elements, it determines <min1,min2>
int mins[] = new int[2];
if(rightMins[0] <= leftMins[0]) {
mins[0] = rightMins[0];
mins[1] = (rightMins[1] <= leftMins[0]) ? rightMins[1] : leftMins[0];
} else {
mins[0] = leftMins[0];
mins[1] = (leftMins[1] <= rightMins[0]) ? leftMins[1] : rightMins[0];
}
return mins;
}
}
## Analysis ##
There are total n/2 nodes at last level (base case of length 1) = n/2 * 0 comparisions
There are total n/2 nodes at all other levels (base case of length 2 and > 2) = n/2 * 2 comparisions
Total comparisions = 0 + n - 2 [-2 because we don't need 2 comparisions at root node]
Please comment :)
--Tushar
A working, tested, simple and recursive solution in Python:
def two_min(L, i,j):
if j==i+1:
return [L[i]]
k= (i+j)/2
return sorted(two_min(L, i,k)+two_min(L, k,j))[:2]
Actually, only two comparisons are needed in the last line.
'sorted' (of at most 4 elements) will use a bit more, but nicely simplifies the code.
This algorithm works in worst case logn+n-2 comaprisons
public static void MinAndSecondMin(int[] arr, ref int min, ref int min2)
{
if (arr.Length <= 2)
{
return;
}
if (arr[0] < arr[1])
{
min = arr[0];
min2 = arr[1];
}
else
{
min = arr[1];
min2 = arr[0];
}
for (int i = 2; i < arr.Length; ++i)
{
if (arr[i] < min)
{
min2 = min;
min = arr[i];
}
else if (arr[i] < min2)
{
min2 = arr[i];
}
}
}
considering all cases
static void Main(string[] args)
{
int[] arr = { -1,-1,-1, -1, -1, -1, -1, -1,-1,
-2,-22,34,56,1111,34,567};
int secondMin = 0;
if (SecondMin(arr, ref secondMin, arr.Length))
{
Console.WriteLine(secondMin);
}
else Console.WriteLine(" no secondMinimum");
Console.Read();
}
public static Boolean SecondMin(int[] arr,ref int secondMin, int n)
{
int min = 0;
try
{
if (n >= 2)
{
if (arr[0] < arr[1])
{
min = arr[0];
secondMin = arr[1];
}
else if (arr[0] > arr[1])
{
min = arr[1];
secondMin = arr[0];
}
else
{
min = arr[1];
secondMin = arr[0];
if (arr[0] == arr[1] && n == 2)
return false;
}
}
if (n > 2)
{
int i = 2;
while (i < n)
{
if (arr[i] < min)
{
secondMin = min;
min = arr[i];
}
else if (arr[i] < secondMin || arr[i] > secondMin&&min==secondMin)
{
if (arr[i] != min)
secondMin = arr[i];
}
i++;
}
}
}
catch (Exception ex)
{
Console.WriteLine(ex.ToString());
}
if(min!=secondMin)
return true;
else return false;
}
}
public int secondSmallestElement(int[] arr) {
int[] tempArr = Arrays.copyOf(arr, arr.length);
List<Map<Integer, Integer>> winnerList = new ArrayList<>();
while (tempArr.length > 1) {
int[] nextLevel = new int[tempArr.length % 2==0 ? tempArr.length/2:tempArr.length/2+1];
int index = 0;
int min = tempArr.length % 2 == 0 ? (arr[0] < arr[1] ? arr[0]
: arr[1]) : arr[0];
Map<Integer, Integer> pairs = new HashMap<>();
int i = tempArr.length % 2 == 0 ? 1 : 2;
if (tempArr.length % 2 != 0) {
nextLevel[index++] = tempArr[0];
}
for (; i < tempArr.length; i += 2) {
if (tempArr[i - 1] < tempArr[i]) {
pairs.put(tempArr[i - 1], tempArr[i + 1]);
nextLevel[index++] = tempArr[i - 1];
} else {
pairs.put(tempArr[i], tempArr[i - 1]);
nextLevel[index++] = tempArr[i];
}
}
tempArr = nextLevel;
winnerList.add(pairs);
}
int min = tempArr[0];
int[] losersToMin = new int[winnerList.size()];
int index = 0;
for (Map<Integer, Integer> num : winnerList) {
losersToMin[index++] = num.get(min);
}
int secMin = losersToMin[0];
for (int i = 1; i < losersToMin.length; i++) {
if (secMin > arr[i]) {
secMin = arr[i];
}
}
return secMin;
}
This question makes me wonder if either
A) OP forgot to say something about the question
or
B) the employer was checking your sanity
For the price of making a heap, you might as well store the second smallest element pointer/value which makes this an n operation. I mean, if you want that runtime you can just do a worthless spin at the end for log(n)-2.
use the quick sort idea!!!
find the position of the pivot element....
using the partition alorithm...
if the position is higher than the 2nd position...then apply partition to the left partition of the array...else the right one
- Josh March 23, 2011I just spent awhile on this, so I figured I'd post what worked for me. 1 2 3 4 5 6 7 8 \/ \/ \/ \/ 1 3 5 7 \ / \ / 1 5 \ / 1 1 is the smallest, it took n-1 = 7 comparisons. Now compare all the numbers which 1 was compared to (compare 2,3,5). 2 3 5 \/ / 2 / \/ 2 2 is the second smallest. It took lg(n)-1 = 2 comparisons. To understand where the ceiling comes from, try this with n odd.