Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
If you want to search on any of the categories like ItemNo or Authour or title etc you would need multiple maps.
1. You can create object which encapsulates everything.
2. Create multiple maps with Keys like(Title/Author/Product No) and value is a pointer to the Object.
You need not store the whole objects in the map.
Could you give more details. How this will work. Some psuedo code for data structures involved.
@LV: psuedo code
class Product
{
item#, prod#, category, title, author, etc...
}
void buildDS(File f, char delimiter)
{
if(null == f)
return;
List<Product> products = new List<Product>();
Dictionary<string, List<int>> index_title = new Dictionary<>(string, List<int>);
// Add one dictionary per queriable meta-data (title, category, author)
while(!f.eof)
{
string line = f.readLine();
// Handle bad line scenarios
// Create product instance and populate
string[] infos = string.tokenize(line, delimiter);
products.add(new Product(infos[0], ... infos[infos.length - 1]));
index_title.add(prod.title, products.length - 1);
// Update all the dictionaries created
}
}
HTH :)
use multidimensional indexed trees like KD-tree etc.
Or maintain bit index and make queries with bit operations.
import java.util.HashMap;
import java.util.Map;
public class Product
{
private int itemNo;
private String productNo;
private String title;
private String author;
}
public class ProductMap
{
private Map <String, Product> allProducts = new HashMap<String,Product>();
//store author and [list of product ids]
private Map authorProductMap <String, List<String>> = new HashMap<String, List<String>>();
//store title and list of product ids
private Map titleProductMap <String, List<String>> = new HashMap<String, List<String>>();
//store category and list of product ids
private Map categoryProductMap <String, List<String>> = new HashMap<String , List<String>>();
private void addProductToMaps(Product item)
{
allProducts.add(item.getProductNo() , Product);
List<String> authorsForProduct = new ArrayList<String>();
if( authorProductMap.get(item.getAuthor()) == null)
{
authorsProductMap.add(item.getProductId());
}
else
{
authorsProductMap.get(item.getAuthor()).add(item.getProductId())
}
//repeat for other maps
}
private void queryForProduct(Product item)
{
//increment the hit count by 1 for each item found during query of maps
//item product with highest hit count is the most relevant product
Map<String , Int> productHitCount = new HashMap<String,Int>();
for (each item field query the map)
Example: Query item.getAuthor() in product map if item.getAuthor != null.
Get the list of product IDs, found and add it to a hitList
Return the hitCount of each product Id, in sorted order.
}
}
I suggest - create an object to hold each record. Place every record read into a Map where the Book id is key.
For every other search index, create a new Map with key as the property value (e.g. Title) and the value field as the id of the record.
This is similar to primary and secondary indexes seen in database. Hope this helps.
import java.util.HashMap;
- Skywalker July 10, 2014import java.util.Map;
public class ProductMap {
public static void main(String []args) {
Detail l_detail1 = new Detail("A",1,"File1");
Detail l_detail2 = new Detail("B",2,"File2");
Key l_key1 = new Key(l_detail1);
Key l_key2 = new Key(l_detail2);
Map<Key,Detail> l_objMap= new HashMap<Key,Detail>();
l_objMap.put(l_key1,l_detail1);
l_objMap.put(l_key2,l_detail2);
DetailHashMap<String,Key> l_authMap= new DetailHashMap<String,Key>();
l_authMap.put(l_detail1.author,l_key1);
l_authMap.put(l_detail2.author,l_key2);
DetailHashMap<String,Key> l_bookMap= new DetailHashMap<String,Key>();
l_bookMap.put(l_detail1.book,l_key1);
l_bookMap.put(l_detail2.book,l_key2);
}
}
class DetailHashMap<A,B> {
Map <A,B> map;
DetailHashMap() {
map = new HashMap<A,B>();
}
public void put(A p_author, B p_detail) {
map.put(p_author, p_detail);
}
}
class Detail {
String author;
int sNo;
String book;
Detail(String p_author, int p_sNO,String p_book) {
author = p_author;
sNo = p_sNO;
book = p_book;
}
}
class Key {
String author;
String book;
Key(Detail p_detail) {
author = p_detail.author;
book = p_detail.book;
}
@Override
public int hashCode() {
return (author.hashCode() + book.hashCode());
}
@Override
public boolean equals(Object p_obj) {
if(this.author.equals(((Key)p_obj).author) && this.book.equals(((Key)p_obj).book)) {
return true;
}
return false;
}
}
// Detail class will be actual object(big object) and will have all required fields. Key class is for only specific fields of Detail class who involve in decision for searching. Suggestion invited.