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:
- mkdir x y -> make a folder y under x
- rmdir x -> TDelete x from system including its subdirectories
- 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!