# Sort a K-Messed Array — coding interview question

Aced (formerly Exponent) publishes a public search API over its indexed pages; the guide is at https://www.aced.io/agents/agent-access.

Source: https://www.aced.io/questions/3061/sort-k-messed-array
Source observed: 2026-11-05T00:29:28.700Z
Last checked: 2026-11-05T00:29:28.7+00:00
Indexed: 2026-11-06T05:25:51.496+00:00

---

# Sort a K-Messed Array

**Difficulty:** Medium  
**Roles:** [Software Engineer](https://www.aced.io/questions?role=swe)  
**Companies:** [Google](https://www.aced.io/questions?company=google), [Meta](https://www.aced.io/questions?company=meta-facebook)  
**Categories:** [Data Structures & Algorithms](https://www.aced.io/questions?type=algorithms), [Coding](https://www.aced.io/questions?type=coding)

## Problem

Given an integer array `arr` in which every element is at most `k` positions away from its sorted position, implement an efficient function `sortKMessedArray` that sorts `arr`.

For an input array of size `10` with `k = 2`, an element that belongs at index `6` in the sorted array can appear at index `4`, `5`, `6`, `7`, or `8` in the input array.

Analyze the time and space complexity of your solution.

## Example

```text
input:  arr = [1, 4, 5, 2, 3, 7, 8, 6, 10, 9], k = 2
output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
```

No community answers have been contributed yet. Detailed company statistics are available through [Upgrade](https://www.aced.io/upgrade?src=questions).

## Interview experiences

One interview experience is shared:

- **Company:** Google
- **Reported:** 2 years ago
- **Role:** Software Engineer · Senior / L5
- **Experience:** “It was nice but very robotic. The question was same as reported be others before. I started with the verbal solution first and then code in google doc.”

[Read the Google interview experience](https://www.aced.io/experiences/google-senior-software-engineer-interview-a84ae7)

![Google company logo](https://exponent-static.s3.amazonaws.com/company_logos/google.png)

## Related questions

- [Sort a nearly sorted (or K sorted) array.](https://www.aced.io/questions/5392/k-sorted-array)
- [Squares of sorted array](https://www.aced.io/questions/3824/square-of-sorted-array)

## Related courses

### [Software Engineering Interview Prep](https://www.aced.io/courses/software-engineering)

![Software Engineering Interview Prep](https://images.ctfassets.net/x78yjrjc11pq/4VkuYewBHUFIVUS5oJDW5h/02e833439b1289f25f38f13f81cbdca3/adobe_stock_optimized.jpeg?w=800&h=800&fm=webp&q=75)

We help candidates prepare for software engineering roles at Google, Amazon, Microsoft, Meta, Apple, and other top companies. The course covers mock interviews, frameworks, advice from senior candidates, data structures, algorithms, system design, people management, behavioral interviews, and more.

### [System Design Interviews](https://www.aced.io/courses/system-design-interviews)

![System Design Interviews](https://images.ctfassets.net/x78yjrjc11pq/78x7miFZFjBCrM5GqftrMJ/2f6d26e632c4e7265c49f6a180227edb/system_design_track_compressed_26ac98a46e__281_29_5be2280f31.jpeg?w=800&h=800&fm=webp&q=75)

We teach candidates how to answer current system-design questions across product, infrastructure, and AI domains through in-depth video examples, written breakdowns, reference patterns, and mock-interview videos featuring senior engineers and managers.

You can return to [All Questions](https://www.aced.io/questions) or [sign up to run code](https://www.aced.io/signup?src=lesson).

---

[Read this page’s summary](https://www.aced.io/agents/api/public/v1/page-tldr?url=https%3A%2F%2Fwww.aced.io%2Fquestions%2F3061%2Fsort-k-messed-array&trace=t_679ff9ab98f3)

## Ask a follow-up about this page

Need a more specific answer? Ask the exact question you have. It returns a fresh, cited answer from Aced (formerly Exponent)’s knowledge base. No account or API key required.

Open this URL with your own question, URL-encoded. Include your question in q. All research inputs are optional; no account or setup.

`GET https://www.aced.io/agents/agent/faq?q={question}&trace=t_679ff9ab98f3`

[Tool guide and examples](https://www.aced.io/agents/agent-access) · [OpenAPI](https://www.aced.io/agents/api/public/v1/openapi.json) · [Page TLDR form](https://www.aced.io/agents/agent-tools/page-tldr?url=https%3A%2F%2Fwww.aced.io%2Fquestions%2F3061%2Fsort-k-messed-array). Opening a form does not execute a tool.