How do you check if an array is sorted in linear time?
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 the next, the array is not sorted, and I return false immediately. If the loop completes without finding such a pair, the array is sorted. This approach runs in O(n) time and uses O(1) extra space, making it optimal for large datasets.
Common Mistakes to Avoid
- Using nested loops resulting in O(n^2)
- Ignoring empty or single-element arrays
- Not handling duplicate values correctly
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.
Related Interview Questions
How do you implement binary search on a sorted array?
Easy
MicrosoftWhat is the difference between value type and reference type?
Easy
TCSHow do you add two numbers represented by linked lists?
Medium
AmazonWrite Selenium and Java code to automate an Amazon search
Medium
InfosysWhat is the best way to find the middle of three numbers?
Easy
InfosysWhat skills do you have for this job?
Easy
Infosys