Imagine a linked list with not just a next node, but a down node as well.
We want to write a function that would "flatten" that linked list by taking all
the downward segments and merging them up between their parent and their parent's next.
Example (conceptual structure):
Top level:
[1] -> [2] -> [3] -> [8] -> [10]
|
v
[4] -> [5] -> [6]
|
v
[7]
Another downward segment from [8]:
[8]
|
v
[9]
Flattened result should be:
[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> [8] -> [9] -> [10]
You have a multi-level linked list where each node has next and optional down pointers. The goal is to“flatten”it into a single-level list by splicing every down chain between the parent node and the parent’s original next, preserving relative order within each chain. Recursion or an explicit stack both work: when you see a down, flatten that sublist and attach it before continuing with the saved next.
Bloomberg Interview Question: Dynamic Grid Averages for an Interactive Map
An interactive map displays some live metric (e.g. GDP, infection rates, population
density) by splitting the map into grid squares and coloring each square based on
its value compared to the grid average. Squares with no data are grayed out.
When someone zooms in to a part of the grid, or when a value occasionally changes,
the squares need to be recolored based on the average value of the visible squares.
Write a program to calculate the average value of the whole or a part of the grid
at any time. You should support the following methods:
updateValue - takes in a grid square and a new value
getAverage - takes in coordinates for a rectangle of grid squares and returns
their average value
This design question models a 2D grid where each cell stores a numeric value. You must support frequent point updates (updateValue) and fast queries for the average over any axis-aligned rectangular region (getAverage). A straightforward prefix-sum solution is too slow for many updates; instead, you typically use a 2D Binary Indexed Tree (Fenwick tree) or 2D segment tree to maintain cumulative sums and counts, so both operations run in about O(log²N).
