Due to an auto-grading error, Wobbly has graduated CS101 top of the class, his details have been passed on to BitBank.com and he arrives for his first day at work. His first assignment is to review the method by which PINs and card numbers are checked when they arrive 'down the wire' as PIN, card# pairs. The return value is either 'Incorrect PIN' or 'PIN accepted'. The current system is a list of lists, length 9999. In each sub-list are the 16 digit card numbers that match that PIN. Example, in element 3245 (Wobbly's PIN) is his card number 0890 1281 9090 2177 (plus lots of others also associated with PIN 3245). There are about 10 million card numbers. When a pair arrives, the current program goes to the PINth element of the main list and does something like,
Any new card number are placed in their PINth element. Wobbly has no idea whether or not this is an efficient method and is left sucking his pencil at his desk. Can you help?
asked 25 Mar '12, 10:42
It's not efficient, you would use a database.
Also grouping by PIN would be a very poor idea. Think of all the people that would use 1234 (same as my luggage :O ) or repeating numbers like 2222 or 5555.
answered 25 Mar '12, 11:21
It is not efficient, you would use a set.
All you care about is whether a certain credit card has a certain pin or not. You don't care about the order, and you don't keep any extra information; you just want fast membership tests.
Alternatively, you can use a dictionary and have the credit card number be the key, and the pin number the value. This means you can (quickly) check whether some card exists, and not only whether it matches a given pin.
Which is better? Profile. This choice also largely depends on what you want to do with the data (except for what you've already stated).
That's in-memory; out of memory you'd probably use a database as SMB says.
answered 25 Mar '12, 11:37
Anton Golov ♦
jesyspa: what is a set?
Nonetheless, I took wobbly's question as a little extra homework (thanks) and measured the time between list and dictionary (with 10 million cardnumbers as suggested).
Don't know if I should post the whole code here. Nevermind.
answered 25 Mar '12, 12:26