DSA Day-17

Hello Guys!!! Hope all of you are doing well.

We have completed Linked List and now we’ll have a self evaluation of the topic according to the exact placement procedures conducted.

ROUND 1: MCQs

1. Consider an implementation of unsorted singly linked list. Suppose it has its representation with a head pointer only. Given the representation, which of the following operation can be implemented in O(1) time?

i) Insertion at the front of the linked list
ii) Insertion at the end of the linked list
iii) Deletion of the front node of the linked list
iv) Deletion of the last node of the linked list

a) I and II
b) I and III
c) I,II and III
d) I,II and IV

2. What would be the asymptotic time complexity to insert an element at the second position in the linked list?

a) O(1)
b) O(n)
c) O(n²)
d) None

3. Consider the following definition in c programming language

struct node
{
int data;
struct node * next;
}
typedef struct node NODE;
NODE *ptr;

Which of the following c code is used to create new node?

a) ptr=(NODE*)malloc(sizeof(NODE));
b) ptr=(NODE*)malloc(NODE);
c) ptr=(NODE*)malloc(sizeof(NODE*));
d) ptr=(NODE)malloc(sizeof(NODE));

4. A variation of linked list is circular linked list, in which the last node in the list points to first node of the list. One problem with this type of list is?

a) It waste memory space since the pointer head already points to the first node and thus the list node does not need to point to the first node.

b) It is not possible to add a node at the end of the list.
c) It is difficult to traverse the list as the pointer of the last node is now not NULL

d) All of above

5. Linked lists are not suitable to for the implementation of?

a) Insertion sort
b) Radix sort
c) Polynomial manipulation
d) Binary search

6. The following C function takes a singly linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code left blank.

typedef struct node
{
int value;
struct node* next;
}Node;
Node* move_to_front(Node* head)
{
Node* p, *q;
if((head==NULL) || (head->next==NULL))
return head;
q=NULL;
p=head;
while(p->next != NULL)
{
q=p;
p=p->next;
}
return head;
}

Choose the correct alternative to replace the blank line

a) q=NULL; p->next=head; head =p ;
b) q->next=NULL; head =p; p->next = head;
c) head=p; p->next=q; q->next=NULL;
d) q->next=NULL; p->next=head; head=p;

Answers:

1. (b)
2. (a)
3. (a)
4. c)
5. (d)
6. (d)

ROUND 2: Coding

1. Merge a linked list into another linked list at alternate positions.

https://www.geeksforgeeks.org/merge-a-linked-list-into-another-linked-list-at-alternate-positions/

2. Rotate a linked list.

3. Remove the loop in linked list

Remove loop in Linked List | Practice | GeeksforGeeks

ROUND 3: Technical Interviews

1. How can you insert a node in the beginning of linked list?
2. Mention some interfaces implemented by linked list in java.

3. How can we find the sum of two linked list using stacks?

Answer:

2. Some of the main interfaces implemented by Java Linked Lists are:

• Serializable
• Queue
• List
• Cloneable
• Collection
• Deque
• Iterable

Now, as I have mentioned it previously also, I will be sharing my personal notes on interview preparation for linked list.

1. Given two linked lists find if they are making a shape of 'Y' or a shape of 'V'.
- traverse both the lists 
- check if the intersecting node is the last node for both, if yes then V, otherwise Y

Time complexity: O(m+n)

2. Insert a value into a sorted linked list. 
- Create two pointers, prev and current 
- Traverse till the node with value greater than insertion value is found
- check if the prev == null .. that implies that the element has to be added before head.
- check if prev.next ==null.. that implies that the element has to be added at the end 

Time complexity: O(n) 

3. Implement a doubly linked list using stacks. 
- Use two stacks. One to store data in given order, other one to store data in reverse order 
Time complexity: O(2N)

4. Delete the repeated elements in a singly linked list in O(n) time complexity without using extra space. Linked list contains elements in unsorted order 
P.S. - Sorting is not allowed
 - Create an arraylist. 
 - Traverse throughout the linkedlist and for each element check if the element is already there, if yes, delete the element. If no, then insert it into the arraylist. 
 
 Time Complexity: O(N)
 Space complexity: O(N) : for arraylist
 
 5. reverse the doubly linked list without using extra space
 
 public static Node reverse(Node head){
	Node n = head, next;
	while(n.next() != null){
		next = n.next;
		n.next = n.prev;
		n.prev = next;
		n = next;
	}
	// n is the new head.
	return n;
}

6. Delete a node from SLL, in which the last node points to the middle node( in case of even no of nodes, it points to the first middle node) and update the SLL.

Step 1: Try to find out the middle node and also the number of the nodes in the linked list whether they are even or odd. 

How to: Start from Head (using fast and the slow pointers). 
if fast -> next == slow (Then the number of nodes would be odd). 
else if (fast->next->next == slow) then the number of nodes would be even. 
Now after this iteration we would be able to get the pointer to the middle element and also to the last element in the linked list. 

Step 2: Remove the node: 

How To: Go to the desired node. 
if the number of nodes are odd then after removal of the desired node the number of nodes would be even so the location of the middle element wont change. 

In case there are odd nodes currently then the new middle node would be the node previous to the current middle node. 

Note: Some special cases have to be taken care of. 
1. If the desired node itself is the middle element. 
2. If the desired node is the last element in the linked list.

7. Given a linked list with next and high pointers, populate high pointers to the next higher node, inplace and O(n).
- Create a treemap with node value as key and index as value. 
- Traverse the entire linked list while pointing high pointer to immediately next pair in treemap since treemap stores pairs in sorted way on basis of keys. 

Time Complexity: O(2N) 
Space complexity: O(N)

8. Implementation of circular linked list. 
- queue implementation

Hope this article proves to be helpful to all the people out there. Feel free to share your views.