Amazon Interview Question
Software Engineer / DevelopersTeam: RCX
Country: United States
Interview Type: In-Person
We need to have a Product-Product relationship (like a sparse matrix).
So, if the system has 'n' products, our matrix will be of the size nxn.
Each cell contains integer values.
Given a product 'i' and asked to find the other products that were bought along with 'i', we just lookup the ith row in the matrix, and return all the column indexes j such that value[i][j] is not zero.
I could use Sphinx search as a solution for this.
Create a real time sphinx index with schema:
id as sql_attr_uint, (auto increment)
main_product_id as sql_field_string,
other_product_id as sql_field_string
I would write inserts to this index for products bought 2 or more,
for example product ids 100, 200, 300 bought together then:
insert (main_product_id, other_product_id) values ((100,200), (100,300), (200, 300), (200,100), (300, 100), (300, 200));
To identify other products sorted by most bought when buying product 100 then do:
select @groupby, @count from index where match('@main_product_id 100') group by other_product_id order by @count desc;
Note: @groupby will become an alias of other_product_id and @count shows the number of times it was bought.
I could use Sphinx search as a solution for this.
Create a real time sphinx index with schema:
id as sql_attr_uint, (auto increment)
main_product_id as sql_field_string,
other_product_id as sql_field_string
I would write inserts to this index for products bought 2 or more,
for example product ids 100, 200, 300 bought together then:
insert (main_product_id, other_product_id) values ((100,200), (100,300), (200, 300), (200,100), (300, 100), (300, 200));
To identify other products sorted by most bought when buying product 100 then do:
select @groupby, @count from index where match('@main_product_id 100') group by other_product_id order by @count desc;
Note: @groupby will become an alias of other_product_id and @count shows the number of times it was bought.
Q. What if memory is not sufficient?
A. Sphinx runs in fixed memory which we can pre-define.
Q. How do DB tables look like?
A. one MySql table and one sphinx index with same schema as above. Ofcource we need to a mysql lookup table with product id and description.
Q. If you use multiple DB calls for every request, it may be very inefficient as you might be serving millions of requests. can you improve?
A. One sphinx call is enough for 'Customers who bought also bought' to be done.
Q. Can you state what all components are present in the system and how does the control flow after webserver receives the request?
????
I would make it similar to a dictionary problem.
- n1k41| January 28, 2012Make use of trie to store the product-list.
so if a customer adds Product A to the cart then display the top n children of the node A.
similar to suggesting/displaying words starting with A in T9 dictionary implementation.