Coding interviews
using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
uint state=17; int checks=0;
for(int trial=0;trial<200;trial++) {
int length=trial%13; int[] data=new int[length];
for(int i=0;i<length;i++) { state=unchecked(state*1664525+1013904223); data[i]=(int)(state%5)-2; }
if(Fast(data)!=Oracle(data)) throw new Exception("differential mismatch"); checks++;
}
Console.WriteLine("differential checks:"+checks);
static int? Fast(int[] data) { var count=new Dictionary<int,int>(); foreach(int x in data) count[x]=count.GetValueOrDefault(x)+1; foreach(int x in data) if(count[x]==1) return x; return null; }
static int? Oracle(int[] data) { foreach(int x in data) { int count=0; foreach(int y in data) if(x==y) count++; if(count==1) return x; } return null; }
Reveal answer and reasoning
The output lines, in order, are “differential checks:200”. Two hundred trials use lengths zero through twelve cyclically and values from minus two through two. Fast counts occurrences and then preserves input order when selecting the first unique value. Oracle recounts each candidate by scanning the entire array. Every trial must agree before the program prints differential checks:200. The generator is a specified unchecked unsigned recurrence, followed by modulo five and a shift into the small signed domain.
Its purpose is varied reproducible fixtures, not statistical randomness or security. The final count reports completed comparisons, while any mismatch throws before printing a misleading success count.
Fast uses expected O(n) time and O(u) stored counts. Oracle can take O(n squared) time but requires constant auxiliary state. The slow method is intentionally retained only for small verification inputs, where simplicity and independence can be more valuable than speed. Two implementations sharing the same mistaken selection rule can agree while both are wrong. Generated tests therefore complement explicit examples such as empty input, all duplicates and a unique negative value.
Passing two hundred cases is bounded evidence, not an exhaustive proof or a benchmark.
What a strong answer covers
- Exact output: differential checks:200
- Two hundred trials use lengths zero through twelve cyclically and values from minus two through two.
- Two implementations sharing the same mistaken selection rule can agree while both are wrong.
Common pitfall
Two implementations sharing the same mistaken selection rule can agree while both are wrong. Generated tests therefore complement explicit examples such as empty input, all duplicates and a unique negative value. Passing two hundred cases is bounded evidence, not an exhaustive proof or a benchmark.
Follow-up questions
- Deliberately change Fast to return the smallest unique value and add a fixture whose first unique value is larger. Hint: the oracle must preserve the stated first-occurrence contract, not just membership in the set of unique values.
- What additional mechanism would turn this deterministic generator into a test system with shrinking?
Self-review
Choose what to revisit. These marks are your own assessment and are separate from lesson completion.