Quick Overview

For every right cyclic shift of one integer array, compute its total absolute difference from a second array and return all scores sorted with multiplicity. Handle negative values, repeated scores, one-element inputs, and sums requiring a wide integer type.

Sort Absolute-Difference Scores Across Cyclic Shifts

Company: ByteDance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

## Problem Two integer arrays `nums1` and `nums2` have the same length. For every right cyclic shift of `nums1` by `t` positions, compute the sum of absolute differences against `nums2`. Return all `n` scores sorted in nondecreasing order. ### Function Contract Implement `cyclic_shift_scores(nums1, nums2) -> list[int]`. ### Constraints - `1 <= n = len(nums1) = len(nums2) <= 500`. - Each value is in `[-10^9, 10^9]`. - The score for shift zero uses the original order. - Return scores with multiplicity; equal scores are not deduplicated. ### Examples - `nums1 = [1,4,2,11]` and `nums2 = [10,1,8,4]` return `[7,13,25,25]`. - Two one-element arrays return a one-element score list. ```hint Index a right shift At output position `i`, a right shift by `t` uses `nums1[(i - t) mod n]`. ``` ### Edge Cases - Negative values are allowed. - Several shifts can have the same score. - Large differences require a wide integer type.

Overview: For every right cyclic shift of one integer array, compute its total absolute difference from a second array and return all scores sorted with multiplicity. Handle negative values, repeated scores, one-element inputs, and sums requiring a wide integer type.

Read the full ByteDance Software Engineer interview experience this question came from

Two integer arrays nums1 and nums2 have the same nonzero length n. For every right cyclic shift of nums1 by t positions, compute the sum of absolute differences against nums2 at aligned positions. Shift zero uses nums1's original order. Return all n scores sorted in nondecreasing order, preserving multiplicity when several shifts have equal scores.

Constraints

  • 1 <= n = len(nums1) = len(nums2) <= 500.
  • Every array value lies in [-1000000000, 1000000000].
  • Shift zero uses the original nums1 order.
  • Return one score per shift with multiplicity, sorted nondecreasingly.
  • Use a wide integer type for accumulated absolute differences.

Examples

Input: ([1, 4, 2, 11], [10, 1, 8, 4])

Expected Output: [7, 13, 25, 25]

Explanation: This is the source example and retains both equal scores.

Input: ([5], [-3])

Expected Output: [8]

Explanation: A one-element array has only shift zero.

Hints

  1. For right shift t, position i reads nums1[(i - t) mod n].
  2. Compute all n exact scores first, then sort them without deduplicating.

Loading coding console...