## Bloomberg LP Interview Question for Interns

Team: London
Country: United Kingdom
Interview Type: Phone Interview

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

``The question it self indirectly tells us they want stable sorting algorithm in which insertion order is not changed while sorting. We have insertion sort, merge sort which does the same thing.And here they asked to do descending order so after sorting we can reverse the elements.``

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

1. Create a class Node

``````class Node{
int n;
int firstSeenIndex;
int frequency;
public Node(int num, int i){
n=num;
firstSeenIndex=i;
frequency=1;
}``````

2. Create a HashMap<Integer, Node>
3. Linearly scan the array. For each num, if it doesn't exist in the array, create a Node and insert it.
4. If the num exists, then increase it's frequency.
5. After the scan is complete, return an array of Nodes from the HashMap.toArray()
6. Implement a comparator on Nodes -

``````class myComparator{
public int compare(Node x, Node y){
if(x.frequency==y.frequency)return x.firstSeenIndex-y.firstSeenIndex;
return x.frequency-y.frequency;
}``````

7. Use Collections.sort on Node array and myComparator to sort them.

Total runtime O(nlogn) where n is the number of items in the original array.

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

I have the same approach with defining an additional structure, so, my solution in Java:

``````/**
* Overall complexity ~ O(n*log(n))
* @param a
* @return
*/
static int[] sortTheArray(int[] a) {
int[] b = new int[a.length];
// Pre-fill the map
Map<Integer, Node> statistic = new HashMap<>();
// complexity is ~ O(n)
for (int i = 0; i < a.length; i++) {
if (!statistic.containsKey(a[i])) {
statistic.put(a[i], new Node(a[i], i, 1));
} else {
statistic.get(a[i]).frequency += 1;
}
}
// Sort all values
// Complexity is ~ O(n)
List<Node> values = new ArrayList<>(statistic.values());
// Complexity is ~ O(n*log(n))
Collections.sort(values);
// Complexity is ~ O(n)
int position = 0;
for (Node v : values) {
for (int j = 0; j < v.frequency; j++, position++) {
b[position] = v.value;
}
}
return b;
}

private static class Node implements Comparable<Node> {
int value;
int firstOccurrence;
int frequency;

public Node(int v, int o, int f) {
value = v;
firstOccurrence = o;
frequency = f;
}

@Override
public int compareTo(Node o) {
if (frequency == o.frequency) {
return Integer.compare(firstOccurrence, o.firstOccurrence);
}
return -Integer.compare(frequency, o.frequency);
}
}``````

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

I have done like this. I feel like it might be slower that using extra structure and built-in sorting, but anyway:

``````public class SortByFreq {

public static void main(String[] args) {
int[] arr = {4,5,2,6,3,5,3,4,1,10,3,5,8,7,6,9,2,5,5,3,3,4};

for (int i = 0; i < arr.length; i++) {
if (map.containsKey(arr[i])) {
map.put(arr[i], map.get(arr[i])+1);
} else {
map.put(arr[i], 1);
}
}

int[] result = new int[map.size()];
int index = 0;
while (!map.isEmpty()) {
int curMin = Integer.MAX_VALUE;
int curNumberWithMinOccur=-1;
for (Entry<Integer,Integer> entry : map.entrySet()) {
if (entry.getValue()<curMin) {
curMin = entry.getValue();
curNumberWithMinOccur = entry.getKey();
}
}
result[index] = curNumberWithMinOccur;
index++;
map.remove(curNumberWithMinOccur);

}
for (int i = 0; i < result.length; i++) {
System.out.print(result[i] + " ");
}
}

}``````

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

I have implemented a function (freqCount2) where I maintain a priority queue. And implemented a comparator function which keeps track of the most frequent element first seen in the array.

``````#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <functional>
using namespace std;

/*
* Sort elements by frequency, print the elements of an array in the
* decreasing frequency if 2 numbers have same frequency
* then print the one which came first.
* */

vector<pair<int,int>> freqCount2(vector<int>& nums){

struct Node {
int n;
int firstSeenIndex;
int frequency;
};

struct CompareNums
{
public:
bool operator()(Node n1,Node n2) {
//Keep number at top if seen first
if (n1.frequency == n2.frequency){
return (n1.firstSeenIndex > n2.firstSeenIndex);
}
return (n1.frequency < n2.frequency);
}
};

unordered_map<int,Node> map;
for(size_t i = 0; i < nums.size();i++){
if(map.find(nums[i]) == map.end()){
map[nums[i]].n = nums[i];
map[nums[i]].frequency++;
map[nums[i]].firstSeenIndex = i;
}
else{
map[nums[i]].frequency++;
}
}
vector<pair<int,int>> res;
// pair<first, second>: first is frequency,  second is number
priority_queue<Node,vector<Node>,CompareNums> pq;
for(auto it = map.begin(); it != map.end(); it++){
pq.push(it->second);
}
res.push_back(make_pair(pq.top().n,pq.top().frequency));
return res;
}

int main(){
vector<int> v = {3,3,4,4,8,8,1,1};
cout<< "Top frequent element which was seen first: " <<" ";
vector<pair<int,int>> res2 = freqCount2(v);
for(auto i : res2)
cout << i.first << ',' << i.second;
return 0;
}``````

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

Inout[] = {1,8,8,9,9,9,3,3,3,2,2}
Output[] = {9,9,9,8,8,3,3,3,2,2,1}

Trying to understand the question. Is this correct input and output.

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

``````std::vector<int> byFrequency( const std::vector<int> & values )
{
using namespace std;

map<int, int> tally;
for ( auto value : values )
{
auto insertion = tally.insert( make_pair( value, 1 ) );
if ( ! insertion.second )
{
++ insertion.first -> second;
}
}
vector<pair<int, int>> v( tally.begin( ), tally.end( ) );
sort( v.begin( ), v.end( ), []( const pair<int, int> & lhs, const pair<int, int> & rhs ) -> bool
{
return lhs.second > rhs.second;
}
);
vector<int> result( v.size( ) );
transform( v.begin( ), v.end( ), result.begin( ), []( const pair<int, int> & p ) -> int { return p.first; } );
return result;
}``````

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

Solution in Python 2.x

``````cdict = {}
def cmp_cnt_ix(k1,k2):
# custom comparator that orders per requirement
if cdict[k1]['cnt'] == cdict[k2]['cnt']:
# smaller index should be first
return cdict[k1]['ix'] - cdict[k2]['ix']
else:
return cdict[k1]['cnt'] - cdict[k2]['cnt']

def sortByFreq(arr):
global cdict
for i in arr:
if i in cdict:
cdict[i]['cnt'] += 1
else: # first seen -> set cnt and index
cdict[i] = {'cnt':1, 'ix':i}

# freq in descending order
sarr = sorted(cdict.keys(), cmp_cnt_ix, reverse=True)
print sarr

a = [11, 12, 11, 13, 9, 9, 9, 13, 13, 1, 2]

sortByFreq(a)``````

output for example in code:
[13, 9, 11, 12, 2, 1]

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

``````Map<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();
for(int i=0;i<input.length;i++){
if(null != map.get(input[i])){
int k = map.get(input[i])+1;
map.put(input[i], k);
}else{
map.put(input[i], 1);
}
}

System.out.println(map);``````

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

C++ solution:

``````template<typename T>
struct ElementFreq {
T val;
int freq;
bool operator < (const ElementFreq& other) const {
return freq > other.freq;
}
void print() const {
cout << val << ":" << freq << endl;
}
};

template<typename T>
void sortByFrequency(const vector<T>& v) {
set<T> elements;
multiset<ElementFreq<T>> freq;
for (auto it = v.begin(); it != v.end(); ++it) {
if (elements.find(*it) == elements.end()) {
elements.insert(*it);
int count = count_if(it, v.end(), [&freq, &it](const T& el) {
return *it == el;
});
freq.insert({*it, count});
}
}

for_each(freq.begin(), freq.end(), [](const ElementFreq<T>& el) {
el.print();
});
}``````

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

``````#include <iostream>
#include <unordered_map>
#include <algorithm>

struct freqVal
{
int freq;
int value;
};

int main()
{
std::vector<int> tc{ 0, 1, 2, 3, 2 }; // 1, 2, 3
std::unordered_map<int, int> elemFound;
std::vector<freqVal> fvalVec; // 1, 2, 3
int freq = 0;
for (auto &i : tc)
{
if (elemFound.count(i) == 0)
{
elemFound[i] = 1;
freq = std::count(tc.begin(), tc.end(), i);
freqVal fval;
fval.freq = freq;
fval.value = i;
fvalVec.push_back(fval);
}
}

std::stable_sort(fvalVec.begin(), fvalVec.end(), [](freqVal lhs, freqVal rhs){ return lhs.freq < rhs.freq; });

for (auto &i : fvalVec)
{
std::cout << i.value << std::endl;
}
}``````

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

package bloomberg;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

public class SortElementsByFrequency {

public static void sort(int[] arr) {
HashMap<Integer, Integer[]> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
if(map.get(arr[i])!=null){
Integer[] freq = map.get(arr[i]);
freq[0]++;
map.put(arr[i], freq);
}else{
map.put(arr[i], new Integer[]{1, i});
}
}

Comparator<Entry<Integer, Integer[]>> comp = new Comparator<Map.Entry<Integer,Integer[]>>() {

@Override
public int compare(Entry<Integer, Integer[]> o1, Entry<Integer, Integer[]> o2) {
Integer count1 = o1.getValue()[0];
Integer count2 = o2.getValue()[0];
Integer index1 = o1.getValue()[1];
Integer index2 = o2.getValue()[1];
return -count1.compareTo(count2) == 0 ? index1.compareTo(index2) : -count1.compareTo(count2);
}
};

List<Entry<Integer, Integer[]>> list = new ArrayList<>(map.entrySet());
Collections.sort(list, comp);

int i =0 ;
for(Entry<Integer, Integer[]> entry: list){
for(int j=0;j<entry.getValue()[0];j++){
arr[i] = entry.getKey();
i++;
}
}
System.out.println(arr);
}

public static void main(String[] args) {
// TODO Auto-generated method stub
sort(new int[]{2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8});
}

}

Time complexity: O(nlog(n) + n) ==> O(nlog(n))

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

``````import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

public class SortElementsByFrequency {

public static void sort(int[] arr) {
HashMap<Integer, Integer[]> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
if(map.get(arr[i])!=null){
Integer[] freq = map.get(arr[i]);
freq[0]++;
map.put(arr[i], freq);
}else{
map.put(arr[i], new Integer[]{1, i});
}
}

Comparator<Entry<Integer, Integer[]>> comp = new Comparator<Map.Entry<Integer,Integer[]>>() {

@Override
public int compare(Entry<Integer, Integer[]> o1, Entry<Integer, Integer[]> o2) {
Integer count1 = o1.getValue()[0];
Integer count2 = o2.getValue()[0];
Integer index1 = o1.getValue()[1];
Integer index2 = o2.getValue()[1];
return -count1.compareTo(count2) == 0 ? index1.compareTo(index2) : -count1.compareTo(count2);
}
};

List<Entry<Integer, Integer[]>> list = new ArrayList<>(map.entrySet());
Collections.sort(list, comp);

int i =0 ;
for(Entry<Integer, Integer[]> entry: list){
for(int j=0;j<entry.getValue()[0];j++){
arr[i] = entry.getKey();
i++;
}
}
System.out.println(arr);
}

public static void main(String[] args) {
// TODO Auto-generated method stub
sort(new int[]{2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8});
}

}``````

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

``````package bloomberg;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

public class SortElementsByFrequency {

public static void sort(int[] arr) {
HashMap<Integer, Integer[]> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
if(map.get(arr[i])!=null){
Integer[] freq = map.get(arr[i]);
freq[0]++;
map.put(arr[i], freq);
}else{
map.put(arr[i], new Integer[]{1, i});
}
}

Comparator<Entry<Integer, Integer[]>> comp = new Comparator<Map.Entry<Integer,Integer[]>>() {

@Override
public int compare(Entry<Integer, Integer[]> o1, Entry<Integer, Integer[]> o2) {
Integer count1 = o1.getValue()[0];
Integer count2 = o2.getValue()[0];
Integer index1 = o1.getValue()[1];
Integer index2 = o2.getValue()[1];
return -count1.compareTo(count2) == 0 ? index1.compareTo(index2) : -count1.compareTo(count2);
}
};

List<Entry<Integer, Integer[]>> list = new ArrayList<>(map.entrySet());
Collections.sort(list, comp);

int i =0 ;
for(Entry<Integer, Integer[]> entry: list){
for(int j=0;j<entry.getValue()[0];j++){
arr[i] = entry.getKey();
i++;
}
}
System.out.println(arr);
}

public static void main(String[] args) {
// TODO Auto-generated method stub
sort(new int[]{2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8});
}

}``````

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

``````class Letter:
def __init__(self, ch, fs, freq=1):
self.char = ch
self.freq = freq
self.firstOccurence = fs

def __lt__(self, other):
if self.freq != other.freq:
return self.freq < other.freq
else:
return self.firstOccurence > other.firstOccurence

def __gt__(self, other):
if self.freq != other.freq:
return self.freq > other.freq
else:
return self.firstOccurence < other.firstOccurence

def __repr__(self):
return self.char

# A test input string.
test_arr = list(test)

letters_dict = dict()

# Construct the hashmap.
for idx, ch in enumerate(test_arr):
if letters_dict.get(ch, None) is None:
letters_dict[ch] = Letter(ch,idx)
else:
letters_dict[ch].freq += 1

# Get the list of letter objects and sort it in reverse order.
letters_list = list(letters_dict.values())
letters_list.sort(reverse=1)

print(letters_list)``````

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

``````class Letter:
def __init__(self, ch, fs, freq=1):
self.char = ch
self.freq = freq
self.firstOccurence = fs

def __lt__(self, other):
if self.freq != other.freq:
return self.freq < other.freq
else:
return self.firstOccurence > other.firstOccurence

def __gt__(self, other):
if self.freq != other.freq:
return self.freq > other.freq
else:
return self.firstOccurence < other.firstOccurence

def __repr__(self):
return self.char

# A test input string.
test_arr = list(test)

letters_dict = dict()

# Construct the hashmap.
for idx, ch in enumerate(test_arr):
if letters_dict.get(ch, None) is None:
letters_dict[ch] = Letter(ch,idx)
else:
letters_dict[ch].freq += 1

# Get the list of letter objects and sort it in reverse order.
letters_list = list(letters_dict.values())
letters_list.sort(reverse=1)

print(letters_list)``````

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

``````class Sorter : IComparer {
public int Compare(object x, object y) {
Tuple<int, int,int> t1 = x as Tuple<int, int, int>;
Tuple<int, int, int> t2 = y as Tuple<int, int, int>;

// order t1.Item1
//count t2.item2
if (t1.Item2 > t2.Item2)
return -1;
else if (t1.Item2 < t2.Item2)
return 1;
else {
return t1.Item1.CompareTo(t2.Item2);
}
}
}
private static void sortArryByFreq(int[] arr) {

// int[] ret = new int[arr.Length];
Dictionary<int, Tuple<int,int,int>> dictCount = new Dictionary<int, Tuple<int, int,int>>();
// List<int> listOfOrder = new List<int>();
int order = 0;
foreach(var a in arr) {
if (dictCount.ContainsKey(a))
dictCount[a] = Tuple.Create(dictCount[a].Item1, dictCount[a].Item2+1,a);
else {

}
}
var newArr = dictCount.Values.ToArray();
Array.Sort(newArr, new Sorter());
foreach(var a in newArr) {
Console.WriteLine(a.Item3);
}

}``````

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

``````class Sorter : IComparer {
public int Compare(object x, object y) {
Tuple<int, int,int> t1 = x as Tuple<int, int, int>;
Tuple<int, int, int> t2 = y as Tuple<int, int, int>;

// order t1.Item1
//count t2.item2
if (t1.Item2 > t2.Item2)
return -1;
else if (t1.Item2 < t2.Item2)
return 1;
else {
return t1.Item1.CompareTo(t2.Item2);
}
}
}
private static void sortArryByFreq(int[] arr) {

// int[] ret = new int[arr.Length];
Dictionary<int, Tuple<int,int,int>> dictCount = new Dictionary<int, Tuple<int, int,int>>();
// List<int> listOfOrder = new List<int>();
int order = 0;
foreach(var a in arr) {
if (dictCount.ContainsKey(a))
dictCount[a] = Tuple.Create(dictCount[a].Item1, dictCount[a].Item2+1,a);
else {

}
}
var newArr = dictCount.Values.ToArray();
Array.Sort(newArr, new Sorter());
foreach(var a in newArr) {
Console.WriteLine(a.Item3);
}

}``````

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

``````class Sorter : IComparer {
public int Compare(object x, object y) {
Tuple<int, int,int> t1 = x as Tuple<int, int, int>;
Tuple<int, int, int> t2 = y as Tuple<int, int, int>;

// order t1.Item1
//count t2.item2
if (t1.Item2 > t2.Item2)
return -1;
else if (t1.Item2 < t2.Item2)
return 1;
else {
return t1.Item1.CompareTo(t2.Item2);
}
}
}
private static void sortArryByFreq(int[] arr) {

// int[] ret = new int[arr.Length];
Dictionary<int, Tuple<int,int,int>> dictCount = new Dictionary<int, Tuple<int, int,int>>();
// List<int> listOfOrder = new List<int>();
int order = 0;
foreach(var a in arr) {
if (dictCount.ContainsKey(a))
dictCount[a] = Tuple.Create(dictCount[a].Item1, dictCount[a].Item2+1,a);
else {

}
}
var newArr = dictCount.Values.ToArray();
Array.Sort(newArr, new Sorter());
foreach(var a in newArr) {
Console.WriteLine(a.Item3);
}

}``````

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

test

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

import java.util.*;
public class freqqq {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
String s=input.next();
for(int i=0;i<s.length();i++)
{
if(hm.containsKey(s.charAt(i)))
{
hm.put(s.charAt(i),hm.get(s.charAt(i))+1);
}
else
{
hm.put(s.charAt(i),1);
}
}
String arr[]=new String[hm.size()];
int c1,index=0;
char c2='a';
String s1="";
while(!hm.isEmpty())
{
s1="";
c1=Integer.MIN_VALUE;
for(Map.Entry<Character,Integer> entry:hm.entrySet())
{
if(entry.getValue()>c1)
{
c1=entry.getValue();
c2=entry.getKey();
}
}
for(int i=0;i<c1;i++)
{
s1=s1+c2;
}
arr[index++]=s1;
hm.remove(c2);
}
for(int i=0;i<arr.length;i++)
{
System.out.print(arr[i]);
}
}

}

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

import java.util.*;
public class freqqq {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
String s=input.next();
for(int i=0;i<s.length();i++)
{
if(hm.containsKey(s.charAt(i)))
{
hm.put(s.charAt(i),hm.get(s.charAt(i))+1);
}
else
{
hm.put(s.charAt(i),1);
}
}
String arr[]=new String[hm.size()];
int c1,index=0;
char c2='a';
String s1="";
while(!hm.isEmpty())
{
s1="";
c1=Integer.MIN_VALUE;
for(Map.Entry<Character,Integer> entry:hm.entrySet())
{
if(entry.getValue()>c1)
{
c1=entry.getValue();
c2=entry.getKey();
}
}
for(int i=0;i<c1;i++)
{
s1=s1+c2;
}
arr[index++]=s1;
hm.remove(c2);
}
for(int i=0;i<arr.length;i++)
{
System.out.print(arr[i]);
}
}

}

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

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class SortByFrequency {

public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {2,3,2,4,5,12,2,3,3,3,12};
sortArraybyFrequency(a);
}

public static void sortArraybyFrequency(int[] a){

Map<Integer,Integer> map = new HashMap<Integer, Integer>();
for(int number : a) {
if(map.containsKey(number)) {
Integer count = map.get(number);
map.put(number, ++count);
} else {
map.put(number,1);
}
}

class FrequencyComparator implements Comparator<Integer> {
Map<Integer,Integer> refMap;
public FrequencyComparator(Map<Integer,Integer> base) {
this.refMap = base;
}

public int compare(Integer k1, Integer k2) {
Integer val1 = refMap.get(k1);
Integer val2 = refMap.get(k2);

int num = val2.compareTo(val1) ;
// if frequencies are same then compare number itself
return num == 0 ? k1.compareTo(k2) : num;
}
}

FrequencyComparator comp = new FrequencyComparator(map);
TreeMap<Integer,Integer> sortedMap = new TreeMap<Integer,Integer>(comp);
sortedMap.putAll(map);
for(Integer i : sortedMap.keySet()) {
int frequencey = sortedMap.get(i);
for(int count = 1 ; count <= frequencey ; count++) {
System.out.print(i + " " );
}
}

}

}

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.

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