How do you check if an array is sorted in linear time?
Direct Answer
This question asks candidates to verify the sorted order of an array efficiently. It tests understanding of basic iteration and comparison logic.
Why Interviewers Ask This
Interviewers ask this to assess a candidate's ability to write clean, efficient code for fundamental data manipulation tasks. They want to see if the candidate understands the definition of a sorted array and can implement a solution with O(n) time complexity. This simple problem also reveals attention to edge cases, such as empty arrays or single-element inputs, which are often overlooked by junior developers.
How to Answer This Question
Start by clarifying the input constraints, such as whether the array contains duplicates or negative numbers. Propose a single-pass algorithm that compares adjacent elements. Explain why nested loops are unnecessary and how to handle boundary conditions gracefully. Conclude by discussing the time and space complexity to demonstrate analytical skills.
Key Points to Cover
- Iterate once through the array
- Compare adjacent elements
- Return false on violation
- Handle edge cases like empty arrays
Sample Answer
To check if an array is sorted, I would iterate through the array from the first element to the second-to-last element. In each iteration, I compare the current element with the next one. If any element is greater than t…
Common Mistakes to Avoid
- Using nested loops resulting in O(n^2)
- Ignoring empty or single-element arrays
- Not handling duplicate values correctly
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.