Bloomberg LP Interview Question Interns
Team: London
Country: United Kingdom
Interview Type: Phone Interview
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.
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);
}
}
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};
Map<Integer,Integer> map = new LinkedHashMap<>();
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] + " ");
}
}
}
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;
}
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;
}
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]
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();
});
}
#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;
}
}
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))
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});
}
}
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});
}
}
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 = "aacadccbed"
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)
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 = "aacadccbed"
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)
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 {
dictCount.Add(a, Tuple.Create(order++,1,a));
}
}
var newArr = dictCount.Values.ToArray();
Array.Sort(newArr, new Sorter());
foreach(var a in newArr) {
Console.WriteLine(a.Item3);
}
}
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 {
dictCount.Add(a, Tuple.Create(order++,1,a));
}
}
var newArr = dictCount.Values.ToArray();
Array.Sort(newArr, new Sorter());
foreach(var a in newArr) {
Console.WriteLine(a.Item3);
}
}
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 {
dictCount.Add(a, Tuple.Create(order++,1,a));
}
}
var newArr = dictCount.Values.ToArray();
Array.Sort(newArr, new Sorter());
foreach(var a in newArr) {
Console.WriteLine(a.Item3);
}
}
import java.util.*;
public class freqqq {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
String s=input.next();
Map<Character,Integer> hm=new LinkedHashMap<Character,Integer>();
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]);
}
}
}
import java.util.*;
public class freqqq {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
String s=input.next();
Map<Character,Integer> hm=new LinkedHashMap<Character,Integer>();
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]);
}
}
}
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 + " " );
}
}
}
}
- Arun January 25, 2017