Lab · Data Structures and Algorithms (DSA) for interviews
Lab: searching a kirana price list
The brief
Look up items in a kirana shop's price list two ways, count how many checks each way makes, and see Big-O with your own numbers. Then catch double-scanned items in O(n) with a set.
Why it matters
Billing apps, stock systems and payment servers look things up millions of times a day. Knowing that a sorted list can be searched in about 20 checks instead of a million is the first Big-O question in most coding interviews, and the reason indexes exist in every database.
Skills you practise
- linear search
- binary search
- counting operations
- O(n) vs O(log n)
- sets for O(1) lookups
What you will have at the end
search.py: linear and binary search with check counters, a worst-case formula, and an O(n) double-scan finder, all tested on a real-looking price list.
How it is marked (rubric, 100 points)
| Correct resultsEvery check passes, including the empty list and the missing code. | 45 |
|---|---|
| Right complexityBinary search halves the range (O(log n)); the repeat finder uses a set (O(n)), not nested loops. | 30 |
| Clear codeGood names (low, high, mid, seen); no repeated logic. | 10 |
| Can explain itYou can say why 16 items need at most 5 checks and a million need 20. | 15 |
0/4 steps done
Step 1 of 4
Linear search, with a counter
linear_search(codes, target) returns (index, checks): where the code is (or -1) and how many codes were looked at.
A linear search looks at each code from the left until it finds the target. Add 1 to a counter every time you compare a code, so you can see the work it does.
The best case is 1 check (the first item). The worst case is n checks (the last item, or a code that is not there). That makes it O(n) time and O(1) extra space.
Run shows what your code prints. Check runs the step's tests. Ctrl+Enter checks too.