Amazon Interview Round 2

The second round was also telephonic. It went for almost 1.5 hours though scheduled for one hour. The main reason for that i think is that i was solving questions and each time i was asked to re-look at the solution I used to improve it further.

Question 1: Shuffle pack of cards
Solution 1: It is one of the most common questions that are being asked in Amazon (Though I came to know this only after the interview:-D). I started with using Sets again but the complexity turned out to be very bad. I assumed that there is a random function with time complexity O(1) and I call this random function to get values from 1...52. Once i get that random function i will add that value in a SET. So in end I will have all the numbers from 1...52 in a random fashion. The catch in my solution was that if the random function returns number x, m times than for each number we will call this function m times and for 52 numbers it will be (m power 52). This is huge. I tried giving another solution but was no better. In the end he moved to next question. Check out here for solution.

Question 2: Count number of lines, characters and words in a file (Given that we don’t have much access to flashy java methods like readline, String methods like indexOf etc.)
Solution 2: The constraint given above simply means that one has to read character by character. I started with a basic program of reading character by character and passing that character to switch statement and doing some logic when ever i got ' ' , '\t', '\n','\r' . But the problem with this solution was that whenever i used to get some odd input like empty file, a file with just '\n' or a file with just a space then i used to patch my earlier solution. Then as i was giving solutions to problems i was asked if I could store some "state". I tokk that lead and provided another solution: -

Store a "state" variable. i.e. when ever a NON- special character (i.e. character apart from ‘ ‘ , ‘\n’ , ‘\r’, ‘\t’ , EOF comes then make the state 0. Whenever a special character comes make state 1. So whenever we go from state 0 to 1. Increase word count. Whenever we get \n or EOF we increase line count. And each time we increase character count.
After this solution no clarification was asked for.

Question 3: Write USE case for Auction model where you have a seller, an item and a buyer.
Solution: This was more generic design question and was just asked to write use-case. Not seq diagram etc.

Learning points 1: Have a nice grip on time complexity. They will make you calculate for each of the solutions you give.
Learning points 2: Concentrate real hard for that 1.5 hours and if you are not clear of the problem then don't hesitate in asking it again.
Learning points 3: You will be asked to write proper code.(even you will be asked to communicate the same through phone)
Learning points 4: The questions will be very generic and never specific to some language.
Learning point 5: Used a variety of test cases to check one's solution before presenting the same to interviewer.