Frontend School

Flatten Nested List with Alternating Sign

DSA
medium

Flatten Nested List with Alternating Sign

Medium
Recursion
Depth-First Search
Arrays

Overview

Inmobi's ad serving platform often processes complex configuration data or user segment definitions, which can involve deeply nested structures. To optimize processing or apply specific business rules, these structures sometimes need to be flattened into a simpler linear format. This problem challenges you to flatten a nested list of integers, applying a unique transformation based on the nesting depth, mirroring real-world scenarios where data transformation needs to account for structural context.

What you need to do / Task

Implement a function flattenNestedListWithAlternatingSign that takes a list of NestedInteger objects and flattens it into a single number[] array. The flattening process must adhere to the following rule:

  • For any integer found at an odd nesting depth (1, 3, 5, ...), its value must be multiplied by -1.
  • For any integer found at an even nesting depth (2, 4, 6, ...), its value must remain unchanged.

The outermost list provided to the function is considered to be at depth 1. If a NestedInteger contains a list, its elements are considered to be at the next depth level.

Input & output

Input

  • nestedList: NestedInteger[]: A list where each element is either a single integer or another list of NestedInteger objects. The NestedInteger interface provides methods to inspect its content.

Output

  • number[]: A flattened list of integers, where each integer has been transformed according to the alternating sign rule based on its original nesting depth.

Clarifications

  • NestedInteger Interface: You are provided with an interface NestedInteger that has the following methods:
    • isInteger(): boolean: Returns true if this NestedInteger holds a single integer, false if it holds a nested list.
    • getInteger(): number | null: Returns the single integer that this NestedInteger holds. Returns null if it holds a nested list.
    • getList(): NestedInteger[]: Returns the nested list that this NestedInteger holds. Returns an empty array if it holds a single integer.
  • Depth Definition: The initial nestedList passed to your function is at depth 1. Any list contained within an element at depth d will have its contents at depth d+1.
  • Empty Lists: Empty lists (e.g., [] as a NestedInteger holding a list, or [[[]]]) should be traversed but do not contribute any numbers to the flattened output.

Examples

1

Example 1

Input:

nestedList = [[1,1],2,[1,1]]

Output:

[1,1,-2,1,1]

Note:

Initial list [[1,1],2,[1,1]] is at depth 1.

  • First NestedInteger holds [1,1] (a list) at depth 1. Its elements (1,1) are at depth 2 (even), so they remain 1, 1.
  • The NestedInteger holding 2 (an integer) is at depth 1 (odd), so it becomes -2.
  • Second NestedInteger holds [1,1] (a list) at depth 1. Its elements (1,1) are at depth 2 (even), so they remain 1, 1. Result: [1,1,-2,1,1].
2

Example 2

Input:

nestedList = [1,[4,[6]]]

Output:

[-1,4,-6]

Note:

Initial list [1,[4,[6]]] is at depth 1.

  • The NestedInteger holding 1 (an integer) is at depth 1 (odd), so it becomes -1.
  • The NestedInteger holding [4,[6]] (a list) is at depth 1. Its elements are at depth 2.
    • The NestedInteger holding 4 (an integer) is at depth 2 (even), so it remains 4.
    • The NestedInteger holding [6] (a list) is at depth 2. Its element is at depth 3.
      • The NestedInteger holding 6 (an integer) is at depth 3 (odd), so it becomes -6. Result: [-1,4,-6].
3

Example 3

Input:

nestedList = [[]]

Output:

[]

Note:

An empty nested list [[]] contains an empty list at depth 1. No integers are found, so the output is an empty array.

Constraints

Constraints & assumptions

  • The total number of integers across all nested lists will not exceed 1000.
  • The maximum nesting depth will not exceed 50.
  • Integer values will be within the range [-100, 100].
  • The input nestedList will not contain any circular references.

What interviewers evaluate

  • Recursive Logic: Correctly implementing a recursive solution to traverse the nested structure.
  • Depth Tracking: Accurately tracking and utilizing the current nesting depth.
  • Alternating Sign Rule: Correctly applying the sign transformation based on odd/even depths.
  • Edge Case Handling: Gracefully handling empty lists and single-integer inputs.
  • Code Quality: Readability, modularity, and adherence to best practices.

Loading editor...