Microsoft Interview Question
Software Engineer / DevelopersHi Gaurav,
Your solution gives the obvious answer... But have you given a thought of how you can improve it?
With some realistic assumptions that the list of customers is ordered... we could use Bit vector ...maybe?? just a thought.
Use a Hash table and fill the list of all the customers who paid money. Next scan through the list of all the customers and see if he is there in the hash table. If yes that means he is the one who paid, if not, then he is the one who didn't pay and hence print the name of the customer. Repeat it for the entire list of customers. This is linear in both time and space complexity.
- gauravk.18 February 23, 2008