PPractick

The problem

A small library app keeps its book IDs in the order they were added, not sorted, and a librarian types an ID to check whether the book exists and where it sits in the list. Without sorted data or an index there's only one option: look at each element in turn until you find it or run out. Linear search is the baseline every other search is measured against, and knowing exactly when it's the right tool (unsorted data, a single query, tiny arrays) is as important as knowing the faster alternatives.

Example: [10, 20, 30, 40], target 30 → index 2.

Function signature

int linearSearch(const vector<int>& a, int target);  // index of the first occurrence, or -1

Test cases

Input (a, target)	Output	Explanation
([10, 20, 30, 40], 30)	2
([5, 3, 5], 5)	0	First occurrence
([1, 2, 3], 4)	-1	Not present
([7], 7)	0
([], 1)	-1	Empty array
([4, -2, 9, -2], -2)	1	Negative values

(Confirm: return the index of the first occurrence, or -1 if the target is absent; the array is not sorted.)

How interviewers phrase it

• "Search for an element in an array and return its index."
• Theory: "When would you use linear search instead of binary search?"
• GeeksforGeeks "Who will win?": compare linear and binary search costs for a given input.

Clarifying questions to ask

1. Is the array sorted? (If so, binary search is far better.)
2. First occurrence, last occurrence, or any?
3. How many queries? (Many queries might justify sorting or building a hash set first.)

Follow-ups to expect

1. "What's the complexity?"
2. "When is linear search the right choice?"
3. "How would you handle many queries on the same data?"
4. "What's a sentinel search?"
5. "Library function?"

Related questions

• Largest Element Easy
• Second Largest Element Easy
• Reverse an array Easy
• Basic Hashing Easy
• Counting Frequencies of Array Elements Easy
• Highest Occurring Element in an Array Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in