Q142: Block allocation for files using linked list.

This is in continuation with Question 141

Question 142: Which of the following is true when the files will be allocated as per the linked list?

1. Dynamic allocation of the blocks is easy.
2. Moving to any offset in the file is easy.
3. Difficult to grow the size of the file.
4. None of the above

Solution: The correct answer is option 1 as any block can be allocated anywhere in the disk and can be joined via linked list.

Q107: Linked list with a cycle

Question #107: Following linked list is an example of linked list with a cycle.

Which of the following is a method to detect if there is a loop in a linked list of unknown size?

Options:

• Take two pointers, start traversing using the first pointer and start the second pointer after first pointer has reached second element of the linked list. If the pointers meet, there is a cycle/loop.
• Take two pointers, increment first pointer by one step and second pointer by two steps. If the pointers meet, there is a cycle/loop.
• Starting from the first element in the list, assume that it’s the part of the loop. Start traversal from that element till the element repeats. Repeat for all of the elements.
• Both 1 and 2.

Solution: The correct answer is option 2. Option 1 will detect cycle of size 2 only. Option 3 will loop forever if the first element of the linked list is not part of the cycle.

Q88: Memory requirement for finding kth element from back

Question 87 might be of interest to you before this one!

Question 88: Match the following methods to “find k^th element from the end” to the “memory space” that they take.

Set 1

a) Going till the end of the linked list to find the size n, and then traverse again from the start ‘n-k’ steps.

b) Traverse two pointers, second pointer starting at the time when first pointer has reached k-1^th

c) Take a queue of size ‘k’, and start enqueueing elements from the start of the linked list. When it gets full, dequeue one element and enqueue from the linked list. After all the elements of the linked list are enqueued, the next element to be dequeued will be the n-k^th element from the end.

Set 2

x) O(1)

y) O(k)

z) O(1)

Options:

• a-x, b-y, c-z
• a-x, b-z, c-y
• a-y, b-x, c-z
• None of the above, all of them take O(1)

Solution: The correct answer is option 2. We need extra memory space in the algorithm where queue is involved which is of the size k. Also, see below:

In other two methods, we are just using pointers, which is O(1) memory.

 

Q87: Kth element from last in a linked list

Question #87: Which of the following is not correct algorithm to find k^th element from the end of a linked list whose size is unknown?

For example, 2^nd element from the end in the above example is “d”.

Options:

• Going till the end of the linked list to find the size n, and then traverse again from the start ‘n-k’ steps.
• Traverse two pointers, second pointer starting at the time when first pointer has reached k-1^th
• Take a queue of size ‘k’, and start enqueueing elements from the start of the linked list. When it gets full, dequeue one element and enqueue from the linked list. After all the elements of the linked list are enqueued, the next element to be dequeued will be the n-k^th element from the end.
• Only A and B are the methods

Solution: The correct answer is option 4. All of the three algorithms correctly find k^th element from the end.