LinkedIn SWE OA

There were 3 questions. Q1 is an easy string matching problem. Q2 is similar to Meeting rooms - ii or finding the max number of railway platforms. Q3 is hard....

There were 3 questions.

Q1 is an easy string matching problem. Q2 is similar to Meeting rooms - ii or finding the max number of railway platforms. Q3 is hard. My code didn\'t pass all the TC for this problem (

passed 8 out of 15)

There is an existing directory structure in form of a tree with n nodes and q queries. there are 3 types of queries:
1. mkdir x y -> make a folder y under x
2. rmdir x -> TDelete x from system including its subdirectories
3. count_subdir x -> compute total number of folder possibly immediate or non immediate under x including itsenf and return the count.

Return an array of integers representing the result of 3rd type of query in same order they are given.

Input is a list of edges.

What I observed was that, we cannot inherently assume the direction of the edges (edge[0] -> edge[1]). There were test cases where the edges were like this [3,4], [1,4], [2,5]. In the problem it is given that 1 is root but these edges do not form a hierarchical tree/directory structure.

I did a basic dfs for the count query, addition and removal of edges for the queries 1 and 2 respectively. But turns out that didn\'t work. I also tried to form a bi-directional graph first and then build a tree from node 1. That didn\'t work either.

How to solve this?

Not expecting a callback because recruiter mentioned that I have to solve all the 3 questions. I lost my hope but it\'s okay.

Happy interviewing guys!