Google Interview Question for Backend Developers


Country: United States




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

public int longestChain(@Nonnull Map<String, String> relationships) {
        int count = 0;
        Map<String, Integer> cache = new HashMap<>();
        for (Map.Entry<String, String> relationship : relationships.entrySet()) {
            count = Math.max(count, longestChain(relationships, cache, relationship.getKey()));
        }
        return count;
    }


    private int longestChain(@Nonnull Map<String, String> relationships, Map<String, Integer> cache, String lookup) {
        int count = 0;
        if (cache.containsKey(lookup)) {
            count = cache.get(lookup);
        }
        else if (relationships.containsKey(lookup)) {
            String newLookup = relationships.get(lookup);
            count = 1 + longestChain(relationships, cache, newLookup);
            cache.put(lookup, count);
        }
        return count;
    }



    @Test
    public void test1() {
        Map<String, String> relationships = new HashMap<>();
        relationships.put("beidu", "ofo");
        relationships.put("mobike", "alibaba");
        relationships.put("alibaba", "somethingElse");
        relationships.put("cookies", "mobike");

        int result = new CompanyMerger().longestChain(relationships);
        assertThat(result).isEqualTo(3);
    }


    @Test
    public void test2() {
        Map<String, String> relationships = new HashMap<>();
        relationships.put("foo", "bar");
        relationships.put("bar", "abc");
        relationships.put("abc", "ooo");
        relationships.put("ooo", "xyz");
        relationships.put("xyz", "cookies");

        int result = new CompanyMerger().longestChain(relationships);
        assertThat(result).isEqualTo(5);
    }

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

- Scavi November 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Run DFS

- Jerry Pepper November 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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";
}

- Alex December 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }

- Hugh May 27, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More