Predict output when iterating ordered keys
Company: Intersystems
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Assume you have a data structure `global_var[a][time]` that behaves like an **ordered map**:
- Keys (`time`) are kept in **sorted ascending** order.
- `order(map, key, dir)` returns the **next key** after `key`.
- If `dir = 1`, it returns the next higher key.
- If `dir = -1`, it returns the next lower key.
- If `key = ""`, then `order(map, "", 1)` returns the **smallest** key and `order(map, "", -1)` returns the **largest** key.
- If there is no next key, it returns `""`.
Given:
```
global_var["A"] = {
2: 5,
4: 6,
9: 1,
15: 3
}
```
And this pseudocode:
```text
time = ""
sum = 0
visited = []
while true:
time = order(global_var["A"], time, -1)
if time == "":
break
visited.append(time)
sum = sum + global_var["A"][time]
print(visited)
print(sum)
```
**Task:** What does the program print (the `visited` list and `sum`)?
Quick Answer: This question evaluates understanding of ordered maps, iteration semantics, reverse traversal and accumulation of values in code. It is commonly asked in Coding & Algorithms interviews to test the ability to reason about iteration order, sentinel return values and summation behavior, and it examines practical application of data-structure semantics rather than purely abstract theory.
Given an ordered-map-like dictionary from time to value, simulate repeatedly asking for the next lower key starting from the empty cursor. Return [visited_keys, sum_of_values].
Constraints
- Keys are comparable time values
- Reverse order means largest key to smallest key
Examples
Input: ({2: 5, 4: 6, 9: 1, 15: 3},)
Expected Output: [[15, 9, 4, 2], 15]
Input: ({1: 10},)
Expected Output: [[1], 10]
Input: ({},)
Expected Output: [[], 0]
Hints
- Starting with an empty cursor and dir=-1 visits the largest key first.