Bloomberg LP Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
//
// Pt 1
//
bool f( int array[ ], unsigned size );
//
// Pt 2
//
std::string asReadableList( const std::vector<int> & v )
{
using namespace std;
ostringstream os;
auto begin = v.begin( ), end = v.end( );
if ( ! v.empty( ) )
os << * begin ++;
for ( ; begin != end; ++ begin )
os << "," << * begin;
return os.str( );
}
//
// Pt 3
//
int minCommonPair( std::vector<int> & v, std::vector<int> & w )
{
using namespace std;
sort( v.begin( ), v.end( ) );
sort( w.begin( ), w.end( ) );
for ( auto iv = v.begin( ), iw = w.begin( ); iv != v.end( ) && iw != w.end( ); )
{
if ( * iv == * iw )
return * iv;
if ( * iv < * iw )
++ iv;
else
++ iw;
}
// There is no common element.
return 0; // Something!
}
//
// Pt 4
//
int minCommonAny( std::vector<std::vector<int>> & v )
{
using namespace std;
// Sorted already.
vector<vector<int>::iterator> begins( v.size( ) );
vector<vector<int>::iterator> ends( v.size( ) );
transform( v.begin( ), v.end( ), begins.begin( ), []( vector<int> & v ) { return v.begin( ); } );
transform( v.begin( ), v.end( ), ends.begin( ), []( vector<int> & v ) { return v.end( ); } );
auto finished = [ & begins, & ends ] ( ) -> bool
{
for ( auto beginit = begins.begin( ), endit = ends.begin( ); beginit != begins.end( ); ++ beginit, ++ endit )
{
if ( * beginit == * endit )
return true;
}
return false;
};
while ( ! finished( ) )
{
vector<int> minimums( v.size( ) );
transform( begins.begin( ), begins.end( ), minimums.begin( ), []( vector<int>::iterator i ) { return * i; } );
cout << "{ " << asReadableList( minimums ) << " }" << endl;
int minmin = * min_element( minimums.begin( ), minimums.end( ) );
int maxmin = * max_element( minimums.begin( ), minimums.end( ) );
if ( minmin == maxmin )
return minmin;
for_each( begins.begin( ), begins.end( ), [maxmin]( vector<int>::iterator & it ) { if ( * it < maxmin ) ++ it; } );
}
// There is no common element... return something.
return 0;
}
Pt 4
bool firstCommon(vector<vector<int>>& input, int& result) {
int size = input.size();
vector<vector<int>::iterator> first;
for (int i = 0; i < size; ++i) {
first.push_back(input[i].begin());
}
while(true) {
int maxFirst = *(first[0]);
for (int i = 1; i < size; ++i ) {
if (*(first[i]) > maxFirst) {
maxFirst = *(first[i]);
}
}
bool found = true;
for (int i = 0; i < size; ++i ) {
if (*(first[i]) < maxFirst) {
if (++first[i] == input[i].end()) {
return false;
}
found = false;
}
}
if (found) {
result = maxFirst;
return true;
}
}
}
int CommonElement(vector<vector<int>> const &arrays)
{
int el = numeric_limits<int>::min();
vector<int> idxes;
idxes.resize(arrays.size(), 0);
for (int i = 0; i < arrays.size(); ++i) {
bool found = false;
bool greater = false;
while (idxes[i] < arrays[i].size()) {
int n = arrays[i][idxes[i]];
if (el == numeric_limits<int>::min() ||
n == el)
{
el = n;
found = true;
break;
}
if (n > el) {
el = n;
found = true;
greater = true;
break;
}
idxes[i]++;
}
if (!found) {
break;
}
if (greater) {
i = -1;
}
if (i == arrays.size() - 1) {
return el;
}
}
return numeric_limits<int>::min();
}
#solution works for sorted arrays
def findFirstCommonElement(arr):
for i in range(len(arr[0])): #take the first array as reference
val = arr[0][i]
found = True
for j in range(1, len(arr)): # check through all the other arrays in the list
for k in range(len(arr[j])):
if arr[j][k] == val:
found = True
break
elif arr[j][k] > val: # if element > the value being searched we can quit
found = False
break
if found == False: # if val not in 1 array no point in searching further
break #check the next val
if found == True: # if val found in all arrays
return val
return -1
Using PHP for #4:
- Bikash Rai April 10, 2017