1. What is the functionality of the following piece of code?
public int function()
{
Node temp = tail.getPrev();
tail.setPrev(temp.getPrev());
temp.getPrev().setNext(tail);
size--;
return temp.getItem();
}
a) Return the element at the tail of the list but do not remove it
b) Return the element at the tail of the list and remove it from the list
c) Return the last but one element from the list but do not remove it
d) Return the last but one element at the tail of the list and remove it from the list
Explanation: The previous and next pointers of the tail and the last but one element are manipulated, this suggests that the last node is being removed from the list.
2. What differentiates a circular linked list from a normal linked list?
a) You cannot have the ‘next’ pointer point to null in a circular linked list
b) It is faster to traverse the circular linked list
c) You may or may not have the ‘next’ pointer point to null in a circular linked list
d) Head node is known in circular linked list
Explanation: The ‘next’ pointer points to null only when the list is empty, otherwise it points to the head of the list. Every node in a circular linked list can be a starting point(head).
3. What is the time complexity of searching for an element in a circular linked list?
a) O(n)
b) O(nlogn)
c) O(1)
d) O(n2)
Explanation: In the worst case, you have to traverse through the entire list of n elements.
4. Which of the following application makes use of a circular linked list?
a) Undo operation in a text editor
b) Recursive function calls
c) Allocating CPU to resources
d) Implement Hash Tables
Explanation: Generally, round robin fashion is employed to allocate CPU time to resources which makes use of the circular linked list data structure. Recursive function calls use stack data structure. Undo Operation in text editor uses doubly linked lists. Hash tables uses singly linked lists.
5. What is the functionality of the following code?
public int function()
{
if(head == null)
return Integer.MIN_VALUE;
int var;
Node temp = head;
while(temp.getNext() != head)
temp = temp.getNext();
if(temp == head)
{
var = head.getItem();
head = null;
return var;
}
temp.setNext(head.getNext());
var = head.getItem();
head = head.getNext();
return var;
}
a) Return data from the end of the list
b) Returns the data and deletes the node at the end of the list
c) Returns the data from the beginning of the list
d) Returns the data and deletes the node from the beginning of the list
Explanation: First traverse through the list to find the end node, then manipulate the ‘next’ pointer such that it points to the current head’s next node, return the data stored in head and make this next node as the head.
6. Consider a small circular linked list. How to detect the presence of cycles in this list effectively?
a) Keep one node as head and traverse another temp node till the end to check if its ‘next points to head
b) Have fast and slow pointers with the fast pointer advancing two nodes at a time and slow pointer advancing by one node at a time
c) Cannot determine, you have to pre-define if the list contains cycles
d) Circular linked list itself represents a cycle. So no new cycles cannot be generated
Explanation: Advance the pointers in such a way that the fast pointer advances two nodes at a time and slow pointer advances one node at a time and check to see if at any given instant of time if the fast pointer points to slow pointer or if the fast pointer’s ‘next’ points to the slow pointer. This is applicable for smaller lists.
7. Which of the following real world scenarios would you associate with a stack data structure?
a) piling up of chairs one above the other
b) people standing in a line to be serviced at a counter
c) offer services based on the priority of the customer
d) tatkal Ticket Booking in IRCTC
Explanation: Stack follows Last In First Out (LIFO) policy. Piling up of chairs one above the other is based on LIFO, people standing in a line is a queue and if the service is based on priority, then it can be associated with a priority queue. Tatkal Ticket Booking Follows First in First Out Policy. People who click the book now first will enter the booking page first.
8. What does ‘stack underflow’ refer to?
a) accessing item from an undefined stack
b) adding items to a full stack
c) removing items from an empty stack
d) index out of bounds exception
Explanation: Removing items from an empty stack is termed as stack underflow.
9. What is the time complexity of pop() operation when the stack is implemented using an array?
a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)
Explanation: pop() accesses only one end of the structure, and hence constant time.
10. What happens when you pop from an empty stack while implementing using the Stack ADT in Java?
a) Undefined error
b) Compiler displays a warning
c) EmptyStackException is thrown
d) NoStackException is thrown
Explanation: The Stack ADT throws an EmptyStackException if the stack is empty and a pop() operation is tried on it.