Amazon Interview Report
- 0of 0 votes
AnswersGiven a time what is the difference between the hour hand and minute hand.
- Viswanatha Reddy June 06, 2009| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Brain Teasers - 0of 0 votes
AnswersSay you have to design a Online role playing game. People can buy demons and weapns online. There are N demons and M weapons. Each weapon of class W inflicts some damage X on a Demon of class D (ie. decrease health of Demon by X). The question was to design a OOP system to accomodate this - make the program data-driven if possible - i.e to add a new demon/weapon, the user has to make as minimum number of compilations as possible. Used a Singleton for storing the Damage of Demon-Weapon combo. Coded in C++. About loading, said we use DB. He suggested config files - I protested that cannot be done because the file can be tampered - no single source of truth.
- Viswanatha Reddy June 06, 2009| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersFirstUnique() character in a ascii string. Thought about tree, then something else. Then bling!!! Decided to use an Array of 128 chars. O(N). Coded it. Errors in while(str) instead of while(*str). Array declared as char freq[128] instead of int freq[128]. Finally anyways, came out well.
- Viswanatha Reddy June 06, 2009| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
Answers1. Wanted to find LCA for two nodes in a BST - Confusion on BST vs ST (recovered) - On recursion vs iteration. When do you use what and why? Readability - tail recursion. I gave example of Fibonacci - Screwed me on that. Unlimited Heap space vs limited stack space. O(N^3) vs O(N).
- Viswanatha Reddy June 06, 2009| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersFinding common integers from sets of two integer arrays. Used sorting & traversing O(M+N+NLogN+MLogM). Made it a order N by using hash.
- Viswanatha Reddy June 06, 2009| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersDesigned the parking lot. Asked a number of questions. Design thoughts on Aggregation, Composition, etc. Designed Classes. Had a lot of disussion on the flow. How to validate or invalidate Slot, ParkingLot and Vehicles. Wanted to make Park() method a O(1) instead of O(N). I suggested that we use a Stack to store the empty slots. O(1) was for UnPark(). I was not completely satisfied with the design - we were passing the variables in/out of the methods... The interviewer was happy anyways.
- Viswanatha Reddy June 06, 2009| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersYou are given a big log file with integers (integers might be repeated, size can be in gig's). I want you to print K largest numbers.
- Viswanatha Reddy June 06, 2009
My answer was:
Break the file into small buckets of integers and from each bucket k large numbers and finally find k large numbers from those individual k large number lists.
He asked me how do u find k large numbers in the individual buckets?
I said i will have to take an array to hold the k large numbers. The first number in the array is my largest number and if i find any other number larger than this then the latest is my largest and the earlier is my second largest number and so on....| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersAmazon has many visitors to its site. And it tracks what pages the customers visited, etc and other stuff. Lets say you store the data of customer id and the page id as a record in a log-file. Now assuming that you have created one log file for each day with that above data-format. Give me the way to find all the customers who made a visit on day1 and day2 and visited atleast two different pages. Say a customer visited two different pages on day1 and then comes back on day2 and visited some other page on day2 he should be listed.
- Viswanatha Reddy June 06, 2009
Lets say the logfile1 has contents like:
c1 p1
c2 p2
c1 p3
c3 p4
c5 p6
And logfile2 has contents:
c10 c7
c4 p4
c3 p4
c5 p1
c1 p2
c2 p1
Then the customers you print out are c1, c2, c5.| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer Algorithm - 0of 0 votes
Answers1.How to do floodfill algo without using recursion. Started saying we need to find the initial position when the interviewer clarified that a seed is given. Said use Queue with the seed given. The basic floodfill algo is about replacing all similar and connected gray values to be selected and replaced with another gray value. Two pixels are said to be connected if one lies to the north-south-east-west pixel of the another.
- Viswanatha Reddy June 06, 2009
2. Design problem of train reservation system. No questions asked. Nothing about SRS. He stopped me saying that when such a huge requirement is given how do you go about designing the system. I suggested SRS, functional specs. He finally said he was looking for 'use-case'. ER design... didn't know the conventions (bad bad me). He wanted to know more about the MVC architecture etc. Said about Reservation, Seats. reservation Model object that has seats as child (Rails convention). How the pages, controller and models work.| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
Answers2. Question about how to design a feature in a Amazon page - Mail me when this item is back in inventory. Said cant use triggers. Discussed structures, suggested we do polling. Then polling the main item table. Instead said we could that when an item is added but that would also have unnecessary calls. Told that the answer was right but I am also looking at another approach. More about how to do efficient triggers/trackers... He said the answers are not wrong but he was looking at something like Message passing. Told him I had no frigging idea about that.
- Viswanatha Reddy June 06, 2009| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersThen he wanted to find the shortest path to convert one string to another using the minimum edits with each transformation string being a valid dictionary word (for->fork->ford->word->sword). Started on recursion. Suggested go with Graph (he was happy with that). In case of two paths leading to the same word replace with the shortest - eliminate the shortest. He wanted to know how we can terminate. Traversal: Breadthwise vs depthwise. Suggested we go breadth wise as that would be the shortest path as yet.
- Viswanatha Reddy June 06, 2009| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersThen he wanted to implement Pow(A,N). Blunder with returning N instead of A. Before that he asked me to have a look at the func... Then he wanted the order. And the number of multiplications happening. And why call it logN. what does it mean...
- Viswanatha Reddy June 06, 2009| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
Answers4. Then he wanted a bytewise reversal of a int. Wrote a function with bitwise or, etc. No feedback. Went overtime. And definitely wrong.
- Viswanatha Reddy June 06, 2009| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm