FastPrepFind Upstream Tasks of a Failed Task
Problems/Find Upstream Tasks of a Failed Task

Find Upstream Tasks of a Failed Task

Microsoft logoMicrosoft● EasyINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a Microsoft intern onsite coding round. The second question was set in a real job. A task failed, and the candidate had to find the upstream tasks that might be involved, using a dependency file. The interviewer kept raising cases that could break the idea. No code was written. Only the approach was described.

The post does not show the file layout, say which tasks count, or give any sizes. Here each line is a task name and then the tasks it reads from, all joined by single spaces. Every task the failed one depends on, directly or through others, is in the answer. The failed task itself never is. Names can repeat, a task can list itself or start more than one line, some names never start a line, and loops can happen. The tests check all of these. The answer is sorted. There are up to 1000 lines, 50 names per line and 5000 names in total. Each name is 1 to 20 lowercase letters, digits or underscores. The extra follow-up ideas in the editorial are not tested.

Our version is about 60% the same as the reported question.

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.
  • failedTask is 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

Interview reports that mention this question

  • Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
  • Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)

Microsoft interview experiences

  • Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
  • Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
  • Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
  • Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public String[] findUpstreamTasks(String[] lines, String failedTask) {
        // Write your code here.
    }
}
Checking account…