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
这道题把地图离散成网格，每个格子有一个数值，需要同时支持：
1）单个格子的数值更新 updateValue；
2）任意矩形区域内所有格子的平均值查询 getAverage。
如果只用静态前缀和，更新会很慢，所以更合适的结构是二维 Fenwick Tree 或二维线段树：维护区域总和与格子数量，使得每次更新和查询都能在大约 O(log²N) 时间内完成，从而实时支撑交互式地图的上色与缩放需求。
正文完
