FastPrepClone an Undirected Graph State

Clone an Undirected Graph State

Apple logoApple● MediumNEW GRADOA
Learn

Problem statement

Create an independent deep copy of a connected undirected graph, then apply the listed edits only to the copy. Return both final snapshots so an edit to the copy cannot change the original.

Nodes are numbered from 1 through n. Node i has data values[i-1] and the sorted neighbor list neighbors[i-1]. The initial graph is simple: no self-loop or parallel edge, and every edge appears in both endpoint lists.

For this exercise, the following finite edit protocol makes copy independence observable:

  • [0,u,x] replaces only cloned node u's data with x.
  • [1,u,v] toggles the undirected edge between distinct nodes u and v in the clone: add it if absent or remove it if present.

Return [originalRows,clonedRows]. In each snapshot, row i-1 is [nodeData,neighbor1,neighbor2,...], with neighbors in increasing order. Edits may disconnect the clone; perform no extra graph analysis. Original rows must remain unchanged.

Function

cloneGraphState(values: int[], neighbors: int[][], edits: int[][]) → int[][][]

Examples

Example 1

values = [7,8]neighbors = [[2],[1]]edits = [[0,1,9],[1,1,2]]return = [[[7,2],[8,1]],[[9],[8]]]

The clone's first value changes and its edge is removed. The original retains both values and its reciprocal edge.

Example 2

values = [4]neighbors = [[]]edits = []return = [[[4]],[[4]]]

A one-node graph is copied even when no edits are requested.

Constraints

  • 1 <= values.length = neighbors.length <= 2000.
  • -10^9 <= values[i], replacementData <= 10^9.
  • Every initial neighbor list is strictly increasing, reciprocal, and contains only valid node IDs.
  • 0 <= edits.length <= 2000; every edit has the stated valid form.

More Apple problems

See Apple hiring insights
public int[][][] cloneGraphState(int[] values, int[][] neighbors, int[][] edits) {
    // Write your solution here.
}
values[7,8]
neighbors[[2],[1]]
edits[[0,1,9],[1,1,2]]
expected[[[7,2],[8,1]],[[9],[8]]]
Checking account…