Lab · Data Structures and Algorithms (DSA) for interviews
Lab: a mall's footfall dashboard in JavaScript
The brief
A mall in Pune counts visitors at its gates every hour. Answer the operations team's questions fast: visitors between any two hours (prefix sums), staff needed each hour from overlapping shifts (a difference array) and the best stretch of days against last year (Kadane).
Why it matters
Retail analytics, metro ridership dashboards and bank statement tools answer "total between X and Y" thousands of times a second. Prefix sums and difference arrays turn each answer into O(1), and Kadane's algorithm is a favourite array question in service and product company interviews.
Skills you practise
- arrays in JavaScript
- prefix sums
- difference arrays
- Kadane's algorithm
- off-by-one care
What you will have at the end
footfall.js: range totals, an hourly staff plan and a best-stretch finder for a mall's footfall, each in O(n) or better and tested on 100,000 values.
How it is marked (rubric, 100 points)
| Correct resultsEvery check passes, including empty input, the last hour and an all-negative list. | 45 |
|---|---|
| Right complexityPrefix array built once, difference array for shifts, one-pass Kadane: no loop inside a loop. | 30 |
| Careful indexesprefix[to + 1] and diff[end + 1] are used correctly, with no off-by-one errors. | 10 |
| Can explain itYou can say why each query is O(1) after the prefix array is built. | 15 |
0/4 steps done
Step 1 of 4
Build the prefix array
buildPrefix(counts) returns an array one longer than counts, where position i holds the total of the first i hours.
A prefix array stores running totals. prefix[0] is 0 (no hours yet), prefix[1] is the first hour, prefix[2] the first two hours, and so on.
The extra 0 at the front means you never need a special case for "from the first hour". Building it is one pass: O(n) time and O(n) space.
Run shows what your code prints. Check runs the step's tests. Ctrl+Enter checks too.