Find Upstream Tasks of a Failed Task
Updated
Problem statement
A job file lists tasks and where each task reads its input from. You get the file as lines, one entry per line. Each line is a list of task names separated by single spaces. The first name is a task, and every other name on the line is a task it depends on, called an upstream task.
The file is not always clean:
- The same task can start more than one line. All of its lines count.
- A name can repeat, a task can list itself, and the dependencies can form loops.
- Some names never start a line. They are still tasks; they just depend on nothing.
When failedTask fails, every task it depends on, directly or through other tasks, might be involved. Return all of these upstream tasks, each once, sorted in plain character order (so "_" comes before letters and "a10" comes before "a2"). Do not include failedTask itself, even if a loop leads back to it. If it depends on nothing, return an empty list.
Function
findUpstreamTasks(lines: String[], failedTask: String) → String[]Examples
Example 1
lines = ["report clean_orders load_users","clean_orders load_orders","load_orders","email report"]failedTask = "report"return = ["clean_orders","load_orders","load_users"]report reads from clean_orders and load_users, and clean_orders reads from load_orders. So these three tasks are upstream of report. email reads from report, so it is downstream and is not included.
Example 2
lines = ["b a","c b b","a c","d c","c"]failedTask = "a"return = ["b","c"]a depends on c, and c depends on b (listed twice). b depends on a again, which is a loop, so the search must stop there. The line "c" adds nothing for c. The answer is b and c, each once. a itself is not included even though the loop leads back to it, and d is downstream.
Example 3
lines = ["extract","load extract"]failedTask = "extract"return = []extract depends on nothing, so the answer is empty.
Constraints
1 <= lines.length <= 1000- Each line has 1 to 50 names separated by single spaces, with no space at the start or end (so a line has at most 1049 characters).
- Each name, including
failedTask, has 1 to 20 characters. Each character is a lowercase English letter, a digit or_. - All lines together hold at most 5000 names.
failedTaskis the first name on at least one line.
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Linked Merchants Within Two HopsStripe · PHONE SCREENStripe interview questions
- Finite Same-Origin Web CrawlerOpendoor · PHONE SCREENOpendoor interview questions
- Currency Conversion RateAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Hierarchical Permission CheckeBay · ONSITE INTERVIEWeBay interview questions
- Minimum Bus Routes to a DestinationPinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- Jump Game IVZomato / Eternal · ONSITE INTERVIEWZomato / Eternal interview questions
- Largest Island After One FlipOracle · ONSITE INTERVIEWOracle interview questions
- Word LadderGoogle · ONSITE INTERVIEWGoogle interview questions
- Finite Web CrawlerMongoDB · PHONE SCREEN · ONSITE INTERVIEWMongoDB interview questions
- Currency Conversion RateBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions