Quick Overview

This question evaluates proficiency in data structures and algorithms, focusing on array processing, aggregation for computing per-user balances, and handling mutable range-sum queries.

Compute balances and array queries

Company: Current

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Question Given a list of transactions where each transaction has a userId and an amount (positive for credit, negative for debit), compute the final balance for every userId. LeetCode 209. Minimum Size Subarray Sum – Given an array of positive integers nums and an integer target, return the minimal length of a contiguous subarray whose sum is at least target; return 0 if none exists. LeetCode 307. Range Sum Query – Mutable – Design a data structure that supports point updates and range-sum queries on an integer array. https://leetcode.com/problems/minimum-size-subarray-sum/description/ https://leetcode.com/problems/range-sum-query-mutable/description/

Quick Answer: This question evaluates proficiency in data structures and algorithms, focusing on array processing, aggregation for computing per-user balances, and handling mutable range-sum queries.

Compute Final Balances per User

Given a list of transactions where each transaction is a pair `[userId, amount]` (amount positive for a credit, negative for a debit), compute the final balance for every userId. Return a map from each userId to its net balance. Users may appear multiple times across transactions; sum all of a user's amounts. A user's net balance may be zero or negative. Example: `[['a',100],['b',50],['a',-30],['b',20],['c',75]]` -> `{'a':70,'b':70,'c':75}`.

Constraints

  • 0 <= number of transactions <= 10^5
  • Each amount fits in a 32-bit signed integer
  • userId is a non-empty string
  • A user's net balance may be zero or negative

Examples

Input: ([['a', 100], ['b', 50], ['a', -30], ['b', 20], ['c', 75]],)

Expected Output: {'a': 70, 'b': 70, 'c': 75}

Explanation: a: 100-30=70, b: 50+20=70, c: 75.

Input: ([],)

Expected Output: {}

Explanation: No transactions yields an empty balance map.

Hints

  1. A single hash map keyed by userId is enough.
  2. Accumulate each amount into the running total for its userId; you only need one pass.
  3. Use get(userId, 0) (or equivalent) so the first transaction for a new user starts from 0.

Minimum Size Subarray Sum (LeetCode 209)

Given an array of positive integers `nums` and an integer `target`, return the minimal length of a contiguous subarray of which the sum is greater than or equal to `target`. If there is no such subarray, return 0. The signature is `solution(target, nums)`. Example: `target=7, nums=[2,3,1,2,4,3]` -> `2` (the subarray `[4,3]`).

Constraints

  • 1 <= target <= 10^9
  • 0 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^4 (all elements are positive)

Examples

Input: (7, [2, 3, 1, 2, 4, 3])

Expected Output: 2

Explanation: [4,3] sums to 7 with length 2; no length-1 subarray reaches 7.

Input: (4, [1, 4, 4])

Expected Output: 1

Explanation: A single element 4 already meets the target, length 1.

Hints

  1. All elements are positive, so a sliding window's sum grows when you extend the right end and shrinks when you advance the left end.
  2. Expand the window to the right; whenever the running sum is >= target, record the length and contract from the left.
  3. Track the minimum window length seen; return 0 if the total sum never reaches target.

Range Sum Query - Mutable (LeetCode 307)

Design a data structure that supports point updates and range-sum queries on an integer array, then replay a sequence of operations against an initial array. The driver signature is `solution(nums, operations)` where `nums` is the initial array and `operations` is a list of operations applied in order: - `['update', i, val]` sets `nums[i] = val`. - `['sumRange', l, r]` returns the inclusive sum of `nums[l..r]`. Return the list of results, one entry per `sumRange` operation, in order. Example: `nums=[1,3,5], operations=[['sumRange',0,2],['update',1,2],['sumRange',0,2]]` -> `[9, 8]`.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • -100 <= nums[i], val <= 100
  • 0 <= i, l, r < nums.length and l <= r
  • 0 <= number of operations <= 3 * 10^4

Examples

Input: ([1, 3, 5], [['sumRange', 0, 2], ['update', 1, 2], ['sumRange', 0, 2]])

Expected Output: [9, 8]

Explanation: 1+3+5=9; after nums[1]=2 the array is [1,2,5] summing to 8.

Input: ([0], [['sumRange', 0, 0], ['update', 0, 5], ['sumRange', 0, 0]])

Expected Output: [0, 5]

Explanation: Single-element array: query 0, then set it to 5, then query 5.

Hints

  1. A Fenwick tree (Binary Indexed Tree) or a segment tree supports both point updates and range-sum queries in O(log n).
  2. For an update, apply the delta (newVal - currentVal) to the structure and remember the new current value so the next update on that index uses the correct delta.
  3. Compute a range sum [l, r] as prefix(r) - prefix(l - 1); be careful with 0- vs 1-based indexing inside the BIT.

Loading coding console...