FastPrepRemove Redundant Task Dependencies
Problems/Remove Redundant Task Dependencies

Remove Redundant Task Dependencies

Microsoft logoMicrosoft● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: This comes from the third round of a Microsoft software engineering intern interview. The interviewer described a task dependency file that keeps growing because it stores links that can already be worked out from other links. They asked how the candidate would make it smaller. Answers did not have to be purely algorithmic.

The sample in the post is written inconsistently about which side of a pair depends on the other, so here [x, y] always means x depends on y. The post also says nothing about cycles, repeated pairs, output order or size. Here there are no cycles or repeated pairs, there are up to 200 tasks and 2000 pairs, and the kept pairs come back sorted. Ideas such as a new file format are covered in the editorial but not tested.

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

A file lists some tasks and the needs between them. Each pair [x, y] in dependencies means task x depends on task y, so y must finish before x can start.

Some pairs add nothing. If you can already get from x to y by following other pairs (for example x depends on w and w depends on y), then the pair [x, y] is redundant: removing it does not change which tasks must finish before which.

Return the pairs that must stay. A pair [x, y] stays only when following the other pairs from x never reaches y. Keep each kept pair in the same [x, y] order as the input.

Sort the kept pairs by the first task, then by the second task, using plain character order (so "_" comes before letters and "a10" comes before "a2"). If no pair is kept, return an empty list.

Function

removeRedundantDependencies(tasks: String[], dependencies: String[][]) → String[][]

Examples

Example 1

tasks = ["a","b","c","d"]dependencies = [["c","a"],["d","a"],["d","c"]]return = [["c","a"],["d","c"]]

Task c needs a, and task d needs a and c. Since d needs c and c needs a, the pair ["d","a"] adds nothing new, so it is removed. Tasks a and b need nothing.

Example 2

tasks = ["build","compile","fetch","lint","test"]dependencies = [["test","fetch"],["build","compile"],["test","build"],["compile","fetch"],["lint","fetch"],["test","lint"]]return = [["build","compile"],["compile","fetch"],["lint","fetch"],["test","build"],["test","lint"]]

test needs build, which needs compile, which needs fetch. So ["test","fetch"] is already implied and is removed. Every other pair is the only way to get from its first task to its second task, so it stays. The five kept pairs are listed in sorted order.

Example 3

tasks = ["deploy"]dependencies = []return = []

There are no pairs, so nothing is kept.

Constraints

  • 1 <= tasks.length <= 200, and all task names are different.
  • Each task name has 1 to 10 characters. Each character is a lowercase English letter, a digit or _.
  • 0 <= dependencies.length <= 2000
  • dependencies[i] = [x, y] where x and y both appear in tasks and x != y.
  • No pair appears twice, and the pairs never form a cycle.

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

  • Course SchedulePlaud · ONSITE INTERVIEW
  • Course ScheduleAmazon · PHONE SCREEN · ONSITE INTERVIEW
  • Course Schedule Cycle DetectionGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
  • Audit Discounted Category AncestorsFaire · ONSITE INTERVIEW
  • Detect a Cycle in a Directed GraphMakeMyTrip.com · ONSITE INTERVIEWMakeMyTrip.com interview questions
  • Course ScheduleFlexTrade · ONSITE INTERVIEWFlexTrade interview questions
  • Course ScheduleBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
  • Can All Courses Be FinishedC3.ai · ONSITE INTERVIEWC3.ai interview questions
  • Trace Terminal Company OwnershipPalantir · ONSITE INTERVIEWPalantir interview questions
  • Deepest Common Ancestors in a Multi-Parent DAGSalesforce · ONSITE INTERVIEWSalesforce interview questions

Interview reports that mention this question

  • Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 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, Early 2025: 41 Experiences (Part 5 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[][] removeRedundantDependencies(String[] tasks, String[][] dependencies) {
        // Write your code here.
    }
}
Checking account…