Bloomberg LP Interview Question
Financial Software DevelopersCountry: United States
Interview Type: In-Person
static int secondLargest(int *arr, int size)
{
int secondL, largest;
largest = arr[0];
secondL = 0;
for(int i=0; i < size; i++)
{
if(arr[i+1] > largest)
{
secondL = largest;
largest = arr[i+1];
}
else if(arr[i+1] > secondL)
{
secondL = arr[i+1];
}
}
return secondL;
}
public class secondLargest {
public static void main(String args[])
{
int arr[] = {100,6,10,7,11,12,3,2,100,17,8,9,100,91,981,5};
int second = findSecond(arr);
System.out.println(" The second largest element in the array is - "+second);
}
//function which returns the second largest element..
public static int findSecond(int arr[])
{
int length =arr.length;
int large,slarge, flag=0;
large=arr[0];
slarge=arr[0];
for(int i=0;i<length;i++)
{
if(large<arr[i])
{
large=arr[i];
}
}
for(int i=0;i<length;i++)
{
if(large!=arr[i])
{
slarge=arr[i];
flag=1;
break;
}
}
//to check whether the array contains only one value or not
if(flag!=1)
{
slarge=large;
return slarge;
}
for(int i=0;i<length; i++)
{
if((slarge<arr[i]) && (arr[i]<large))
{
slarge=arr[i];
}
}
return slarge;
}
}
We can solve this way: First create a Max-Heap with all the values (Build-Heap takes O(n) time). Then We extract max O(logn) time, and then Maximum (O(1)) is the second largest value. For one value, after extract max heap will be empty and next Maximum call will return null.
int find2ndmax(const vector<int>& ar)
{
int max = numeric_limits<int>::min();
int max2 = numeric_limits<int>::min();
for (vector<int>::const_iterator ii = ar.begin(); ii != ar.end(); ii++) {
if (*ii > max) {
max2 = max;
max = *ii;
}
}
if (max2 == numeric_limits<int>::min()) {
throw 1; // or return max, depends on what this function is used for
}
return max2;
}
public class SecondMax {
/**
* @param args
*/
public static void main(String[] args) {
SecondMax secondMax = new SecondMax();
int [] array = {10,4,6,4,7};
int secondMaxValue = secondMax.getSecondMax(array);
System.out.println("The second max number in the array " + secondMaxValue);
}
private int getSecondMax(int[] array){
int max = Integer.MIN_VALUE;
for(int i =0; i<array.length;i++){
if(array[i] > max)
max = array[i];
}
int difference = 0;
int secondMax =0;
int value = Integer.MAX_VALUE;
for(int i =0; i<array.length;i++){
difference = max - array[i];
if(difference < value && difference !=0){
value = difference;
secondMax = array[i];
}
}
return secondMax;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int arr[] = {100,6,10,7,11,12,3,2,100,17,8,9,100,91,981,5};
int max;
int nextMax;
Arrays.sort(arr);
System.out.println("First max is: "+arr[arr.length - 1]);
for(int i = arr.length - 2; i>=0 ;i--){
nextMax = arr[i];
if(nextMax != arr[arr.length - 1]){
System.out.println("Next max is: "+nextMax);
break;
}
}
}
- If the length of array is 1 then throw exception
- If the length of array is 2 then return the array itself
- If the length of array is greater than two then sort the array in desending order using some algorithm and then return the 1st two elements
if array has only one element than we can throw a exception or print a message saying that array has only one element
}
- ajaypathak June 20, 2012