Bloomberg LP Interview Question
Developer Program EngineersCountry: United States
Interview Type: Phone Interview
Server-side:
Create 2 hash tables: {Ticker->Subscribers} and {Ticker->price update counter}. An alternative would be to hash out a unique integer id that would be used as an index into subscribers and counter arrays.
Notify the the subscribers and update the counter using the hash tables.
Client-side:
Not sure if plotters show the global top 10, or if they're based on the tickers the client is interested in. Assuming the latter...Plotter keeps an array of tickers it's subscribed to. When notified, it will perform QuickSelect on its array using the "price update counter" table. It will require some tie-breaker heuristic for stable results (unique id will help here). The plotter's resulting Top 10 will not be sorted, but if needed, any sorting algorithm should work quickly on 10 elements.
Server-side:
Create 2 hash tables: {Ticker->Subscribers} and {Ticker->price update counter}. An alternative would be to hash out a unique integer id that would be used as an index into subscribers and counter arrays.
Notify the the subscribers and update the counter using the hash tables.
Client-side:
Not sure if plotters show the global top 10, or if they're based on the tickers the client is interested in. Assuming the latter...Plotter keeps an array of tickers it's subscribed to. When notified, it will perform QuickSelect on its array using the "price update counter" table. It will require some tie-breaker heuristic for stable results (unique id will help here). The plotter's resulting Top 10 will not be sorted, but if needed, any sorting algorithm should work quickly on 10 elements.
I am using Publisher-Subscriber pattern. For this specific problem, since we only need to care the frequency of each ticker, I didn't involve price here. The tricky part is client side class, where I need to actually track the frequency of each subscribed ticker (hashmap) as well as top 10 most frequent tickers (sorted set of max size 10).
class Server {
private:
unordered_set<Client*> _clients;
public:
void registerClient(Client* client) {
_clients.insert(client);
}
void unregisterClient(Client* client) {
if (_clients.count(client)) _clients.erase(client);
}
void update(string ticker) {
for (auto c:_clients) c->update(ticker);
}
};
struct Comp {
bool operator()(const pair<string,int>& a, const pair<string,int>& b) {
return a.second > b.second;
}
};
class Client {
private:
string _id;
unordered_map<string, int> _freq;
set<pair<string,int>, Comp> _top10freq;
Server* _server;
public:
Client(string id, Server* server)
:_id(id), _server(server) {
if (_server) _server->registerClient(this);
}
void registerTicker(string ticker) {
if (!_freq.count(ticker)) _freq[ticker] = 0;
}
void update(string ticker) {
if (!_freq.count(ticker)) return;
_freq[ticker]++;
for (auto& x:_top10freq) {
if (x.first == ticker) {
_top10freq.erase(x); break;
}
}
if (_top10freq.size() < 10) _top10freq.emplace(ticker, _freq[ticker]);
else if (_top10freq.rbegin()->second < _freq[ticker]) {
_top10freq.erase(*_top10freq.rbegin());
_top10freq.emplace(ticker, _freq[ticker]);
}
}
vector<string> getTop10freq() {
vector<string> top10;
for (auto& x:_top10freq) top10.push_back(x.first);
return top10;
}
};
I am using Publisher-Subscriber pattern. For this specific problem, since we only need to care the frequency of each ticker, I didn't involve price here. The tricky part is client side class, where I need to actually track the frequency of each subscribed ticker (hashmap) as well as top 10 most frequent tickers (sorted set of max size 10).
class Server {
private:
unordered_set<Client*> _clients;
public:
void registerClient(Client* client) {
_clients.insert(client);
}
void unregisterClient(Client* client) {
if (_clients.count(client)) _clients.erase(client);
}
void update(string ticker) {
for (auto c:_clients) c->update(ticker);
}
};
struct Comp {
bool operator()(const pair<string,int>& a, const pair<string,int>& b) {
return a.second > b.second;
}
};
class Client {
private:
string _id;
unordered_map<string, int> _freq;
set<pair<string,int>, Comp> _top10freq;
Server* _server;
public:
Client(string id, Server* server)
:_id(id), _server(server) {
if (_server) _server->registerClient(this);
}
void registerTicker(string ticker) {
if (!_freq.count(ticker)) _freq[ticker] = 0;
}
void update(string ticker) {
if (!_freq.count(ticker)) return;
_freq[ticker]++;
for (auto& x:_top10freq) {
if (x.first == ticker) {
_top10freq.erase(x); break;
}
}
if (_top10freq.size() < 10) _top10freq.emplace(ticker, _freq[ticker]);
else if (_top10freq.rbegin()->second < _freq[ticker]) {
_top10freq.erase(*_top10freq.rbegin());
_top10freq.emplace(ticker, _freq[ticker]);
}
}
vector<string> getTop10freq() {
vector<string> top10;
for (auto& x:_top10freq) top10.push_back(x.first);
return top10;
}
};
I am using Publisher-Subscriber pattern. For this specific problem, since we only need to care the frequency of each ticker, I didn't involve price here. The tricky part is client side class, where I need to actually track the frequency of each subscribed ticker (hashmap) as well as top 10 most frequent tickers (sorted set of max size 10).
class Server {
private:
unordered_set<Client*> _clients;
public:
void registerClient(Client* client) {
_clients.insert(client);
}
void unregisterClient(Client* client) {
if (_clients.count(client)) _clients.erase(client);
}
void update(string ticker) {
for (auto c:_clients) c->update(ticker);
}
};
struct Comp {
bool operator()(const pair<string,int>& a, const pair<string,int>& b) {
return a.second > b.second;
}
};
class Client {
private:
string _id;
unordered_map<string, int> _freq;
set<pair<string,int>, Comp> _top10freq;
Server* _server;
public:
Client(string id, Server* server)
:_id(id), _server(server) {
if (_server) _server->registerClient(this);
}
void registerTicker(string ticker) {
if (!_freq.count(ticker)) _freq[ticker] = 0;
}
void update(string ticker) {
if (!_freq.count(ticker)) return;
_freq[ticker]++;
for (auto& x:_top10freq) {
if (x.first == ticker) {
_top10freq.erase(x); break;
}
}
if (_top10freq.size() < 10) _top10freq.emplace(ticker, _freq[ticker]);
else if (_top10freq.rbegin()->second < _freq[ticker]) {
_top10freq.erase(*_top10freq.rbegin());
_top10freq.emplace(ticker, _freq[ticker]);
}
}
vector<string> getTop10freq() {
vector<string> top10;
for (auto& x:_top10freq) top10.push_back(x.first);
return top10;
}
};
typical Pub-sub.
- Prem August 17, 2016will use HashMap to have the subscription, tick as key and list of clients as value