Bloomberg LP Interview Question
Software Engineer / Developersclass Test{
public static void main(String args[]){
//following elements in the array
int arr[] = {2,4,5,66,77,1,-99,4,7,64,34,677,9};
int min1,min2;
min1=min2=arr[0];
for(int i=0;i<arr.length-1;i++){
if(min1>arr[i+1])
{min2=min1;
min1=arr[i+1];
}
else { if(min2>arr[i+1])
min2=arr[i+1];
}
}
System.out.println(min1 +" " + min2);
}
}
Uses of static variables:-
When an object of a class is created, for each non-static members there would be a separate memory allocated. A static variable is instantiated only once. It can be used for defining constants which are useful in the class methods and the the outside code which uses this class.
Most optimal solution in this case means minimum number of comparisions required. In this case minimum number of comparisions required are n+lgn-2.
I think you can look at two elems at a time. Also you need to use two variables to keep track of the 2 smallest elems. In each iteration, you can look at a, b,(a and b keep the two smallest elems seen so far) c, d. The total #iterations is O(n/2). Of course, each iteration will take constant time (3 comparisons). But totally run time will be O(3*n/2).
int sec_min, min;
sec_min = min = INFINITY;
for (i =0; i < n; i ++)
{
if (a[i] < min)
{
sec_min = min;
min = a[i];
}
}
Your code won't get the second min if the first value in the array is the minimum
Here is a code to get the min and second min in O(N)
#include<limits.h>
void main()
{
int sec_min, min,n=6,i;
int a[]={1,4,3,2,6,5};
sec_min = min = INT_MAX;
for (i =0; i < n; i ++)
{
if (a[i] < min)
min = a[i];
if(a[i] < sec_min && a[i] > min)
sec_min=a[i];
}
printf("%d %d",min,sec_min);
getchar();
}
#include<stdio.h>
#include<conio.h>
int main()
{
int a[6]={5,6,2,4,1,0};
int min1,min2,i;
min1=min2=a[0];
for(i=1;i<6;i++)
{
if(a[i]<min2)
{ min1=min2;
min2=a[i];
}
}
printf("%d %d",min1,min2);
getchar();
getchar();
return 0;
}
This will fail if
a[] = { 5, 1, 4, 6, 2, 0 };
i.e if the smallest number appears before the second smallest number.
I think we need to use a min heap to get the two of the smallest numbers (in general n-element min heap to find the first n smallest numbers).
1. Create a min heap using A[0] and A[1];
2. Now for each element from 2 to n-1; for(i = 2; i < n; ++i)
3. If A[i] > heap[0], then exchange A[i] and heap[0. Heapify to restore the min heap property. Since this is a 2-element min heap, time taken for heapify is constant (usually it is O(log n)). Hence, the complexity would be O(n).
4. Finally, the two numbers in the heap are the smallest two numbers.
Compare two consecutive elements.
Say 'a' and 'b'
Initialize : Min1 and Min2 with first 2 elements of the array such that min1 is smaller element
Suppose a<b
1.Compare a with Min1. if (a<min1) min1= a else go to step 3
2.Compare B with Min2. If (b<min2) min2 = b
3. Compare a with Min2. if(a<min2) min2 = a
So for every iteration we have 3 comparisons and n/2 total iterations
O(3*n/2)
#include "stdafx.h"
#include <iostream>
using namespace std;
void FindMin2(long x[],long&,long &);
int main()
{
long a[6] = {10,2,8,6,3,12};
long Min1 = 0, Min2 = 0;
FindMin2(a, Min1, Min2);
cout << "Minimum 1 = " << Min1 << endl;
cout << "Minimum 2 = " << Min2 << endl;
cin.get();
return 0;
}
void FindMin2(long x[],long &Min1,long &Min2){
Min1 = x[0],Min2 = 9999;
for(long i = 1; i < 6;++i)
{
if(Min1 > x[i]){
Min2 = Min1;
Min1 = x[i];
}else if((Min2 > Min1) && (Min2 > x[i]))
Min2 = x[i];
}
}
bool findSmallestTwo(const std::vector<int>& array, int& first, int& second)
- xiaofeng.ustc January 28, 2013{
const int kNumElements = static_cast<int>(array.size());
if (kNumElements <= 1) return false;
first = (array[0] <= array[1]) ? array[0] : array[1];
second = (array[0] <= array[1]) ? array[1] : array[0];
for (int index = 2; index < kNumElements; index++)
{
int value = array[index];
if (value >= second) continue;
else
{
if (value >= first)
{
second = value;
}
else
{
second = first;
first = value;
}
}
}
return true;
}