Flipkart Interview Question for SDE1s


Country: India
Interview Type: In-Person




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

Use LinkedList and HashMap, map is needed to keep the track of node in linkedlist.

1. Create -> add node to both linkedlist and map O(1)
2. Retrieve -> get the reference of the node in list using map and return the node. O(1)
3. Update -> get the reference of the node in list using map and update it in the list O(1)
4. Delete -> get the reference of the node in list using map and delete it from the both linkedlist and map O(1)

- Naveen August 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

What's the point of a linked list here? Why not just use a HashSet and be done with it:

1. Create/Insert -> O(1)
2. Retrieve -> O(1)
3. Update -> O(1)
4. Delete -> O(1)

- jbaum517 August 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Naveen: There may be a possibility of collision when you use hashMap so your retrieval and deletion will not be in O(1) in worst case.

And @jbaum517: Can you please elaborate how HashSet will give the result of all CRUD operations in O(1) ?

- Aman Mittal August 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@Aman_Mittal: Operations on a HashMap are considered to be amortized O(1). Much like adding an element to an ArrayList is amortized O(1)

- zortlord August 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@Aman Mittal: A HashSet is essentially a HashMap without values that are mapped from the key set. HashSet has all of those same access functions and their worst case behavior since it's based on a constant time hash of the object.

Since we're talking about HashSet though which is part of java's util package, I should also note that HashSet is NOT synchronized. So we would need some sort of external locking mechanism in place if this data structure were to be used by multiple processes simultaneously.

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

@Naveen When you have the reference to a node in the linkedlist, the only way to delete it is to copy the value from next node to that node and delete next.

- shabgard August 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Naveen - if you are caring of collision, then you should ask that what data you are going to store, how you are going to make the key ? If you have right hash function, there is less chances of collision. Still if you want you can have multilevel of hash implementation where on collision, you can recalculate the key (obviously that object has some difference in some properties) and value would be hash table on basis of recalculated key. A variation of this is also known as cuckoo hashing.

- Phoenix September 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Naveen How will u delete the last node in linkedlist?

- Anonymous October 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use of LinkedList is beneficial only for retrieving values in sequence .. may be for printing ..

- Jay December 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use a boolean array

- ANKIT YADAV June 06, 2017 | 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