Summary
I was presented with a problem requiring me to determine which build targets need to be rebuilt based on dependency information and a list of changed files.
Full Experience
Problem
Write a function that takes build dependency information and a list of files that have changed since the last build, and returns a list of targets that need to be rebuilt. The build dependencies are make-like target-dependency pairs, for example:
[ ["prog", "a.o"], ["prog1", "b.o"], ["a.o", "a.c"], ["b.o", "b.c"], ["prog2", "b.o"], ["prog2", "c.o"], ["c.o", "c.c"],]
For this example, if a.c changes, then we need to rebuild a.o and then prog1, but not prog2. But if b.c changes, we would need to rebuild b.o, which would trigger a rebuild for both prog1 and prog2.
The resulting target list should contain unique values. I.e. no duplicates
The order of the resulting list is unimportant. NOTE: The test harness will check against a specific order, and might fail, you can manually verify the results though as test cases are very small.
Interview Questions (1)
Problem
Write a function that takes build dependency information and a list of files that have changed since the last build, and returns a list of targets that need to be rebuilt. The build dependencies are make-like target-dependency pairs, for example:
[ ["prog", "a.o"], ["prog1", "b.o"], ["a.o", "a.c"], ["b.o", "b.c"], ["prog2", "b.o"], ["prog2", "c.o"], ["c.o", "c.c"],]
For this example, if a.c changes, then we need to rebuild a.o and then prog1, but not prog2. But if b.c changes, we would need to rebuild b.o, which would trigger a rebuild for both prog1 and prog2.
The resulting target list should contain unique values. I.e. no duplicates
The order of the resulting list is unimportant. NOTE: The test harness will check against a specific order, and might fail, you can manually verify the results though as test cases are very small.