FastPrepSort a K-Displaced Array
Problems/Sort a K-Displaced Array

Sort a K-Displaced Array

Akuna Capital logoAkuna Capital● MediumINTERNNEW GRADPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in Akuna Capital intern and new grad phone screens. One report says "almost sorted" means each item is at most k places from its sorted spot, and asks for a sorting solution. That candidate mostly talked about the approach and the cost, because time was short. A second report, from a quant researcher phone screen, only mentions an almost-sorted list. Using this exact k rule for that report is our own choice. We also decided how duplicates are placed, set the input limits, return a new array, and defined the empty case. Our version is about 85% the same as the reported questions.

You are given an integer array nums and an integer k. The array is k-almost-sorted: every value is at most k positions away from where it ends up after sorting.

To handle repeated values, sort the occurrences by value and break ties by original index. If an occurrence starts at index i and has final index r in that order, the input promises |i-r| <= k. All supplied inputs satisfy this promise.

Return all input values in nondecreasing order. Keep every duplicate. Return a new array and leave nums unchanged. An empty input has k=0 and returns an empty array.

Explain how knowing this bound can save work compared with a plain sort.

Function

sortAlmostSorted(nums: int[], k: int) → int[]

Examples

Example 1

nums = [3,1,2,5,4]k = 2return = [1,2,3,4,5]

Sorting gives [1,2,3,4,5]. The value 3 moves from index 0 to index 2, and every other value moves by one position. So the input fits k=2.

Example 2

nums = [2,1,1,3]k = 2return = [1,1,2,3]

Keep both occurrences of 1, giving [1,1,2,3]. With equal values tied by original index, the two ones move left by one position each, while 2 moves right by two positions.

Example 3

nums = []k = 0return = []

There are no input occurrences, so the sorted result is an empty array.

Constraints

  • 0 <= nums.length <= 100.
  • Every element is an integer between -1000000 and 1000000, inclusive.
  • k is an integer with 0 <= k <= nums.length.
  • Every occurrence stays within k positions of its sorted place, as the statement describes.

More Akuna Capital Phone Screen questions

  • Match Orders by Price and Arrival TimeOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Biased Coin: Probability of Exactly h HeadsPHONE SCREEN · Seen Nov 2026
  • Positive Nth Root with Gradient DescentPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Two SumOA · PHONE SCREEN · Seen Sep 2026
  • Maximum Value in a Binary TreePHONE SCREEN · Seen Sep 2026
  • Tiered Expiring Item StorePHONE SCREEN · Seen Aug 2026
  • Statistics for the Latest K ValuesPHONE SCREEN · Seen Nov 2025
  • Remove Duplicates While Preserving OrderPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2025
  • Sliding Window MaximumPHONE SCREEN · Seen Oct 2025
  • Evaluate a PolynomialPHONE SCREEN · Seen Oct 2025

Similar questions at other companies

  • Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
  • Maximum Number of Events That Can Be AttendedByteDance · PHONE SCREENByteDance interview questions
  • Meeting Rooms IIeBay · PHONE SCREENeBay interview questions
  • Top K Frequent ElementsAmazon · OA · PHONE SCREEN
  • Select the Top User MatchesDuolingo · PHONE SCREENDuolingo interview questions
  • Meeting Rooms IIQuince · PHONE SCREENQuince interview questions
  • Kth Largest Element in an ArrayLinkedIn · PHONE SCREENLinkedIn interview questions
  • Meeting Rooms IISecuronix · PHONE SCREEN
  • Merge Multiple Sorted StreamsNVIDIA · PHONE SCREENNVIDIA interview questions
  • Maximum Number of Events That Can Be AttendedSnowflake · PHONE SCREENSnowflake interview questions

Interview reports that mention this question

  • Akuna Capital QR-ML Interviews: 11 Experiences (Part 4 of 6)

Akuna Capital interview experiences

  • Akuna Capital Quant Trader and QR Interviews: 5 Experiences
  • Akuna Capital JQR CodePair Rounds: 8 Experiences (Part 6 of 6)
  • Akuna Capital QR Probability Phones: 14 Experiences (Part 5 of 6)
  • Akuna Capital QR Regression Rounds: 11 Experiences (Part 3 of 6)
  • Akuna Capital QR Coding Interviews: 17 Experiences (Part 2 of 6)
All Akuna Capital interview questionsSee Akuna Capital hiring insights
Saved
class Solution {
    public int[] sortAlmostSorted(int[] nums, int k) {
        // write your code here
    }
}
Checking account…