Flipkart Interview Question for SDE-3s


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
0
of 0 vote

1.) Create Products Object containing {PID,ProductName,List<Timestamp> purchases,LastPurchased}
2.) Maintain a hash/Dictionary with key as PID and value as LinkedListNode<Product> and also maintain a double linked list (like LRU cache) and move the product to the beginning on a purhcase.
So the start of linked list contains the latest purchased product always
3.) To find Top 100 products in last X minutes/X Hours , maintain a heap. Start from the starting of linked list ,go comparing last purhcased timestamp , find number of purchases in last X minutes , create a structure {ProductID, NumberOfPurchases} and insert in max heap with key as number of purchases . Now pick top 100 from heap by calling GetMax of max heap.

void Purchase(){
	//Update Dict
       // Remove from linked list and insert in beginning
}

List<String> getTop100(Timestamp t){
	//start iterating list till last purchased timestamp>t
	//find number of purchases for this product where purchase time >t
	// insert in heap
	
	List<string> finalResult = new List<string>();
	int i=100;
	while(heap.Count>0 &&i>0){
		finalResult.Add(heap.GetMax().ProductName);
		i--;
	}
	return finalResult;
	
}

- Smarth July 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey can't we maintain one heap and one linked list.Heap always contain top 100 purchases in recent time and Linked List has Just the purchases in which recent ones are at the head always.

- Klaus July 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Klaus : If someone plans to use single linked list for purchases then, using a Heap needs some more care in order to do Increase-key operation efficiently because to perform Increase-key, one has to know the index of that node. But it can be done, I guess, efficiently by using some map-like data-structure.
Moreover, [ having many linked lists(each for a product) & not having main linked list ] or [ having a single list ] almost takes same space. So, we are not gaining much out of it.

- JoyZombie August 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

try Count-Min Sketch

- nobody October 23, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More