Bloomberg LP Interview Question for Software Engineer / Developers






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

bool findSmallestTwo(const std::vector<int>& array, int& first, int& second)
{
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;
}

- xiaofeng.ustc January 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class 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);
}
}

- vinay gupta November 13, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Ravi Chandra November 15, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think most optimal solution are in O(n + log(n))

- fat0ss November 16, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Most optimal solution in this case means minimum number of comparisions required. In this case minimum number of comparisions required are n+lgn-2.

- Shiv November 20, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how did you come to that? also O(n+log n) is O(n)

- Yash August 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

find 1st minimum O(n)
find 2nd minimum O(n)
total = O(n)
you could also do these together in one loop which is again O(2n) ==> O(n)
space = O(1)
thanks.

- chennavarri November 17, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

- AW November 23, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

each iteration requires 4 comparisons. So the total is O(2n).

- cw February 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int sec_min, min;
sec_min = min = INFINITY;
for (i =0; i < n; i ++)
{
if (a[i] < min)
{
sec_min = min;
min = a[i];
}
}

- Anonymous December 04, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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();
}

- nagarajmailing May 29, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm not sure. But I'm wondering if quick_sort is a better way to do it, i.e.,just randomly pick a pivot point and see if the pivot point is the third smallest number. I think this approach has O(n) run-time complexity, right?

- freaxer December 05, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- nacent coder January 04, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will fail if
a[] = { 5, 1, 4, 6, 2, 0 };

i.e if the smallest number appears before the second smallest number.

- hcmurthy February 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

small correction: a[] = { 5, 1, 4, 6, 2, 3 };

- hcmurthy February 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- hcmurthy February 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

instead of a min heap, use a max heap.

For each elem in the array,
compare it with the maximum in the heap
if it is smaller than the maximum, replace the maximum with it and heapify the max heap.
otherwise, do nothing

- cw March 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

nth_element(arr, arr+2, arr+arr_size, less<int>);

- Anonymous August 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Eh? What does 'static' have to do with it? Badly written question I think.

- JeffD January 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- dhaval January 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

let min1 = min2 = array[0];
for each element in the array
if a[i] <= min1 then
min2 = min1; min1=a[i]
else if a[i] > min1 && a[i] <min2
min2 = a[i]

complexity : O(n)

- Anonymous January 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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];
}
}

- srikanth srigiri March 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a simple O(n) solution

void TwoMinimum(int Arr[], int n)
{
    int min1,min2;
    min1 = min2 = INT_MAX;
    for(int i = 0; i< n ; i++)
    {
        if( Arr[i] < min1 )
        {
            min2 = min1;
            min1 = Arr[i];
        }
        else
        {
            if( (Arr[i] < min2) && (Arr[i] != min1))
            {
                min2 = Arr[i];
            }
        }
}

- Snehal Kumar January 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I saw lots of solutions over here. But I feel, you guys can do it much quicker than what you've posted.
Build a min Heap and only 2 rounds.
That will give the lowest numbers in the array.

- Akki March 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@Find two minimum from an arrray:
Create a binary tree out of that array, do an inorder traversal, first two elements are two minimum from an array.

- OutBox November 16, 2010 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More