Explore topic-wise InterviewSolutions in .

Correct answer is (a) circular linked list and increasing addressing order

The best explanation: A COMMON way is circular linked list and address are ARRANGED in increasing order because merging would be easier which is ACTUALLY a problem in BUDDY memory allocation.

The correct answer is (d) both a and C are correct

The best I can EXPLAIN: Internal fragmentation is an issue to be dealt and it TAKES so much SPACE.

Right ANSWER is (c) certain blocks cannot be used if there are no pointers to them and HENCE they can be freed

The explanation is: When no pointers pointing a block that MEANS it is USELESS to be in memory.

Correct answer is (b) BUDDY allocation keeps several‭ ‬free lists,‭ ‬each ONE holds blocks which are of one PARTICULAR size

The best explanation: When an allocation request is received,‭ ‬the list that holds blocks that are just large ENOUGH to satisfy the request are considered, and an open location is returned.‭ ‬If no‭ ‬free‭ ‬blocks that are smaller than two times the size that are requested are available,‭ ‬a larger block is split in two to satisfy the requirements.

Correct option is (a) BEST fit, first fit, worst fit, simple-first fit

For EXPLANATION: The‭ ‬simplest form of MEMORY management system can be called as first-fit.‭ ‬a DEVICE or system maintains a single‭ ‬list of free memory locations.‭ ‬When request to memory is sent,‭ ‬the list is searched and the first block that is LARGE enough is returned.

Right choice is (B) LINKED LIST or sort trees

For explanation: Sort trees can ALSO be USED in impelementing free lists which remaincomplex.

The CORRECT ANSWER is (a) GARBAGE collection and new or MALLOC operators respectively

Easiest explanation - Gc and new most widely KNOWN.

The correct answer is (a) NULL XOR A and B xor NULL

Easy EXPLANATION - NULL xor A and B xor NULL.

The correct CHOICE is (a) EVERY NODE STORES the XOR of ADDRESSES of previous and next nodes

The best explanation: Every node stores the XOR of addresses.

Correct answer is (d) least frequently USED

The EXPLANATION is: Least frequently used is a BUFFER replacement policy, while other three are methods to reorder the nodes in the self-organizing LISTS based on their ACCESS probability.

Right CHOICE is (b) move to FRONT method

Easy explanation - Move-to-front method performs POORLY when the elements are accessed in sequential order, especially if that sequential order is then repeated multiple TIMES.

Correct option is (a) searched node is swapped with its predecessor

Easy explanation - In Transpose METHOD, if any node is searched, it is swapped with the node in front unless it is the HEAD of the LIST. So, in Transpose method searched node is swapped with its predecessor.

The correct ANSWER is (c) a self ORGANIZING list

Easy explanation - Self organizing list allows fast sequential search and it is SIMPLE to IMPLEMENT and requires no extra storage. Self-organizing list is USED to implement the symbol table.

The correct answer is (b) count

Easy explanation - In the count method, the NUMBER of times a node was ACCESSED is counted and is stored in a counter variable associated with each node. Then the NODES are arranged in DESCENDING order based on their ACCESS counts. And the node with highest access count is head of the list.

Correct answer is (c) self organizing list

The best explanation: Self-organizing list is EASY and simple to IMPLEMENT than search tree and it REQUIRES no additional space. So using self organizing list is PREFERRED when list size is small.

The correct answer is (C) O(n)

The best I can explain: Worst case OCCURS when the ELEMENT is located at the very end of list. So n comparisons must be made to the locate element. So the worst case running time of linear search on SELF organizing list is O(n).

The correct option is (c) may over-reward infrequently accessed nodes

For explanation: In Move-To-front Method the ELEMENT which is searched is moved to the head of the list. And if a NODE is searched even once, it is moved to the head of the list and given maximum PRIORITY even if it is not going to be accessed frequently in the future. Such a SITUATION is REFERRED to as over-rewarding.

The correct OPTION is (d) linear search

Explanation: Linear search in a linked list has TIME complexity O(n). To improve the efficiency of the linear search the self ORGANIZING list is used. A self-organizing list improves the efficiency of linear search by moving more frequently ACCESSED elements towards the HEAD of the list.

The correct answer is (a) design each level of a multi-level skip list with VARIED probabilities

Easy explanation - For EXAMPLE consider a 2 level skip list. the level-2 skip list can skip one NODE on a average and at some places may skip 2 nodes, depending on probabilities. this ensures O(logn).

Right option is (a) true

The explanation is: To ACHIEVE above OPERATIONS AUGMENT with few ADDITIONAL stuff like partial counts.

Correct answer is (a) balanced BINARY search trees

The explanation is: Skip LISTS are similar to any RANDOMLY built binary search tree. a BST is balanced because to avoid skew tree formations in case of sequential input and HENCE achieve O(logn) in all 3 CASES. now skip lists can gurantee that O(logn) complexity for any input.

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)

The correct choice is (d) balanced binary search tree

The explanation is: Skip lists have the same ASYMPTOTIC time complexity as balanced binary search tree. For a Balanced Binary Search Tree, we skip almost half of the NODES after ONE comparison with root element. The same thing done in the skip lists. Hence skip lists are similar to balanced Binary search trees.

Correct answer is (b) a linkedlist that allows faster search within an ORDERED sequence

Easy explanation - It is a DATASTRUCTURE, which can MAKE search in sorted linked list faster in the same way as BINARY search tree and sorted array (using binary search) are faster.