FastPrepTransitive Greater-Than Relation Queries

Transitive Greater-Than Relation Queries

Bloomberg LP logoBloomberg LP● MediumNEW GRADONSITE INTERVIEW
Learn

Problem statement

Each [a,b] in relations means a > b. The directed relation is acyclic.

For each query [x,y], return GREATER if a transitive path proves x>y, LESS if a path proves y>x, and UNKNOWN otherwise.

Function

resolveRelations(relations: int[][], queries: int[][]) → String[]

Examples

Example 1

relations = [[1,2],[1,4],[4,7],[7,5]]queries = [[1,5],[5,1],[2,4]]return = ["GREATER","LESS","UNKNOWN"]

1 reaches 5 transitively; the reverse query is LESS; 2 and 4 are unrelated.

Constraints

  • At most 10^5 relations and queries.

More Bloomberg LP problems

See Bloomberg LP hiring insights
public String[] resolveRelations(int[][] relations, int[][] queries) {
  // Write your code here.
}
relations[[1,2],[1,4],[4,7],[7,5]]
queries[[1,5],[5,1],[2,4]]
expected["GREATER", "LESS", "UNKNOWN"]
Checking account…