Software and Programming
This domain tests program design and implementation: data structures, algorithm complexity, programming paradigms, testing, development process, and basic database and concurrency concepts. Questions may ask for output tracing or complexity comparison.
Core rules
- Arrays offer O(1) indexed access but O(n) insertion in the middle. Linked lists offer O(1) insertion given a node but O(n) search. Hash tables average O(1) lookup with good hashing and collision handling.
- Stacks are LIFO; queues are FIFO. Trees support ordered operations; balanced search trees keep height O(log n).
- Complexity: binary search is O(log n) but requires sorted data; merge sort is O(n log n); quicksort averages O(n log n) and worst-case O(n²); nested loops over n usually give O(n²).
- Object-oriented design uses encapsulation, inheritance, and polymorphism; composition is often preferred to deep inheritance.
- Testing includes unit, integration, system, and acceptance levels. Boundary-value and equivalence-partition tests target likely defects.
- Concurrency hazards include race conditions, deadlock, and starvation; locks, atomic operations, and message passing address them.
Worked example
How many comparisons does binary search need in the worst case for 1,000,000 sorted records? Each comparison halves the remaining range. Solve 2^k ≥ 1,000,000. Since 2^20 = 1,048,576, k = 20 comparisons suffice. Linear search would need up to 1,000,000. The logarithmic result depends on random access and sorted data; on a linked list, finding the midpoint costs O(n), so the advantage disappears.
Traps
- Ignoring the sorted-data precondition for binary search.
- Treating Big-O as a measurement of exact running time; constants and cache behaviour matter.
- Confusing stack (LIFO, call frames) with heap (dynamic allocation).
- Assuming quicksort is always O(n log n).
- Thinking unit tests replace integration testing.