Google Interview Question
Backend DevelopersCountry: United States
DFS, starting from each company that was not acquired.
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;
class Node {
public:
Node(string id)
{
id_ = id;
parent_ = NULL;
}
vector<Node *> children_;
string id_;
Node *parent_;
};
vector<Node *> LongestPath(Node *root)
{
class StackEntry {
public:
StackEntry(Node *n, int depth)
{
n_ = n;
depth_ = depth;
}
Node *n_;
int depth_;
};
int path_size = 0;
Node *path_leaf = NULL;
stack<StackEntry> st;
st.push(StackEntry(root, 1));
while (!st.empty()) {
StackEntry &e = st.top();
st.pop();
if (e.depth_ > path_size) {
path_size = e.depth_;
path_leaf = e.n_;
}
for (Node *child : e.n_->children_) {
st.push(StackEntry(child, e.depth_ + 1));
}
}
vector<Node *> path;
for (Node *n = path_leaf; n != NULL; n = n->parent_) {
path.push_back(n);
}
reverse(path.begin(), path.end());
return path;
}
vector<string> LongestChain(vector<pair<string, string>> const &mergers)
{
unordered_map<string, Node *> id_to_node;
for (auto &m : mergers) {
Node *big = id_to_node[m.first];
if (!big) {
id_to_node[m.first] = big = new Node(m.first);
}
Node *small = id_to_node[m.second];
if (!small) {
id_to_node[m.second] = small = new Node(m.second);
}
small->parent_ = big;
big->children_.push_back(small);
}
vector<string> longest_chain;
for (auto &el : id_to_node) {
Node *n = el.second;
if (n->parent_ == NULL) {
auto chain = LongestPath(n);
if (chain.size() > longest_chain.size()) {
longest_chain.clear();
for (Node *n : chain) {
longest_chain.push_back(n->id_);
}
}
}
}
for (auto &el : id_to_node) {
delete el.second;
}
return longest_chain;
}
int main()
{
auto out = LongestChain({
{"baidu", "ofo"},
{"mobike", "alibaba"},
{"company1", "company2"},
{"baidu", "company1"},
});
for (auto &c : out) {
cout << c << "->";
}
cout << "\n";
}
This problem is too simple or I am missing something:
private int longestChain(List<String[]> list) {
HashMap<String, String> map = new HashMap<>();
for (String[] array : list) {
map.put(array[0], array[1]);
}
int max = 0;
int count = 0;
Set<String> keys = map.keySet();
for (String k : keys) {
count = 1;
String val = map.get(k);
while(map.containsKey(val)) {
count++;
val = map.get(val);
}
max = Math.max(count, max);
}
return max;
}
The worst case runtime behaviour is O(n * m) while n is the number of key-entries in the relationship and m the number of relationships between the companies.
- Scavi November 16, 2017I used an additional cache to store already calculated distance of relationships. It reduces the recursive calls if we have a company multiple times (e.g. in test1 mobike->alibaba->somethingElse (2) and cookies->mobike reuses the calculated value of 2).
Due to the cache the best case is O(n) if you have something like in test2.