Infinium Interview Question for Software Engineer / Developers






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

Skip list Definition: A randomized variant of an ordered linked list with additional, parallel lists. Parallel lists at higher levels skip geometrically more items. Searching begins at the highest level, to quickly get to the right part of the list, then uses progressively lower level lists. A new item is added by randomly selecting a level, then inserting it in order in the lists for that and all lower levels. With enough levels, searching is O(log n).

- Anonymous May 10, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we have an example to illustrate its implication better?

- Cookie May 10, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this will help to clear any doubts u have regd skip lists.

http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed12.htm

- algooz June 24, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the main difference between a skip list and hash table would be that skip list provides an time complexity of search of the order of log n through duplicate storage of same keys. Hash on the other hand, uses a hash function to lookup a key.

- Dinesh Bhirud July 29, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

one difference between skip list and hash table (both randomized lists) is : skip list can be used to find kth index number and output sorted data more faster than hash table.

- mrn July 12, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think mrn ur wrong using hash table we can retrive an element in o(1) complexcity but skip list uses the (logn) coplexcity. also using BST we can implement the skip list

- subhedarnikhil September 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

til i did nt get the difference between hashing and skip list plz give me a breif discription on them

- rocky August 14, 2012 | 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