Interviewing for new grad position, was super excited, but just been told they're not moving my application forward.
Given a list of requirements
Z requires X,Y
X requires A,B
print out
A
B
X
Y
Z
I remember having seen something like this (graph version) and the solution is to use topological sort, but I couldn't quite immediately get the connection. To be specific, the class contains two functions
void addReq(string name, list requirements)
void print()
My approach is to
-
use a hashtable to store requirements for a certain element
unordered_map<string,vector> requirements;
which will be populated when we use addReq() function
-
setup a container for all unique elements
unordered_set elements;
which will be populated also when we use addReq() function
-
when trying for printout, I introduce a copy of the elements container to keep track of prerequisites
unordered_set unsatisfied = elements;
which I will attempt to printout each element if requirements[element] is empty and remove them from the unsatisfied set. Otherwise I loop through the elements, if they didn't exist in the set unsatisfied (it meant they had been printed out) I delete them from requirements and go through all the unsatisfied elements again. That was my mistake actually because I didn't ask if that the print function can be called multiple times (probably meant to) and in that case I will need to make a copy of the requirements (not permanently deleting them). Quite understandly, my approach is not ideal because I will make unnecessary passes by looping through things that definitely have prerequisites first and doing so much container copying is probably too inefficient.
The interviewing experience is pretty bad (for me, don't think it was the interviewer as he is pretty quiet the whole time), I basically had a lot of Omnicron symptoms so my mind is pretty blank and I could barely lift my neck due to muscle pain. Maybe these are just excuses as it was my first job interview ever, and I just have to be better prepared next time.