Telephone directory application with insert and search mechanism, data in app memory.
First name(FN), last name(LN) and telephone number(TN) will be inserted.
Can be searched by either first name, last name combo, or last name.
Constraint on data is FN, LN combination will be unique.

Example:-
F1 L1 T1
F2 L1 T2
F1 L2 T3
F2 L2 T4

Ask what whould be best DS to build it, and assume that it has Ms of data.

Happy job hunting!