What is the time complexity improvement of skip lists from linked lists in insertion and deletion?(a) O(n) to O(logn) where n is number of elements(b) O(n) to O(1) where n is number of elements(c) no change(d) O(n) to O(n^2) where n is number of elementsThis interesting question is from Skip List topic in portion Types of Lists of Data Structures & Algorithms II got this question in homework.

What is the time complexity improvement of skip lists from linked list

1.	What is the time complexity improvement of skip lists from linked lists in insertion and deletion?(a) O(n) to O(logn) where n is number of elements(b) O(n) to O(1) where n is number of elements(c) no change(d) O(n) to O(n^2) where n is number of elementsThis interesting question is from Skip List topic in portion Types of Lists of Data Structures & Algorithms II got this question in homework.
Answer» The correct CHOICE is (a) O(n) to O(logn) where n is NUMBER of elements Easy explanation - In Skip list we skip some of the elements by adding more layers. In this the skip list RESEMBLES BALANCED binary search trees. Thus we can change the TIME complexity from O (n) to O (logn)

Discussion

No Comment Found

Related InterviewSolutions

Accessing free list very frequently for wide range of addresses can lead to(a) paging(b) segmentation fault(c) memory errors(d) cache problemsMy enquiry is from Free List in portion Types of Lists of Data Structures & Algorithms II had been asked this question in an international level competition.
How are free blocks linked together mostly and in what addressing order?(a) circular linked list and increasing addressing order(b) linked list and decreasing addressing order(c) linked list and in no addressing order(d) none of the mentionedEnquiry is from Free List topic in section Types of Lists of Data Structures & Algorithms IThis question was addressed to me during an interview for a job.
What are the disadvantages in implementing buddy system algorithm for free lists?(a) internal fragmentation(b) it takes so much space(c) we no more have the hole lists in order of memory address, so it is difficult to detect if 2 holes remain adjacent in memory and shall be merged into one hole(d) both a and c are correctThis intriguing question originated from Free List in division Types of Lists of Data Structures & Algorithms IThe question was posed to me in an online quiz.
How does implicit free lists(garbage collection) works in adding memory to free list ?(a) whichever comes last will be added to free list(b) whichever comes first will be added to free list(c) certain blocks cannot be used if there are no pointers to them and hence they can be freed(d) makes a probabilistic guessI want to ask this question from Free List in division Types of Lists of Data Structures & Algorithms IThe question was posed to me in final exam.
What is buddy memory management of free lists ?(a) modified version of first fit(b) buddy allocation keeps several‭ ‬free lists,‭ ‬each one holds blocks which are of one particular size(c) modified version of best fit(d) a tree representation of free listsI'd like to ask this question from Free List topic in portion Types of Lists of Data Structures & Algorithms IThe question was asked during an interview for a job.
What are different ways of implementing free lists and which is simple among them?(a) best fit, first fit, worst fit, simple-first fit(b) best fit, first fit, worst fit, simple-best fit(c) best fit, first fit, worst fit, simple-worst fit(d) best fitsimple-best fitThis interesting question is from Free List topic in division Types of Lists of Data Structures & Algorithms II had been asked this question by my school teacher while I was bunking the class.
What datastructures can be used in implementing a free list?(a) only linked list(b) linked list or sort trees(c) arrays(d) treesI need to ask this question from Free List topic in division Types of Lists of Data Structures & Algorithms II had been asked this question in an online interview.
What are implicit and explicit implementations of freelists?(a) garbage collection and new or malloc operators respectively(b) new or malloc and garbage collection respectively(c) implicit implementation is not favored(d) explicit implementation is not favoredMy question is based upon Free List in section Types of Lists of Data Structures & Algorithms IThis question was addressed to me in exam.
Free lists are used in(a) static memory allocation(b) dynamic memory allocation(c) contagious allocations(d) are used for speeding up linked list operationsAsked question is from Free List in division Types of Lists of Data Structures & Algorithms II had been asked this question in an interview.
What does first and last nodes of a xor linked lists contain ? (let address of first and last be A and B)(a) NULL xor A and B xor NULL(b) NULL and NULL(c) A and B(d) NULL xor A and BMy doubt is from Xor Linked List topic in section Types of Lists of Data Structures & Algorithms IThis question was addressed to me at a job interview.

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment