Informatica Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
the LRU element will be removed. so we should delete from the front of the linked list.
LRU stands for "least recently used". That means that if elements are being placed in the front as they're used, deletion should happen from the back, because that's where the least recently used elements are.
Hi, you mentioned "transfer it to the front of the linked list". Is this means that when adding a already-exist element, we put it in the front of the LL, and right shift all other element by 1 position, which takes O(n) to "transfer"?
@Prepare4Job: No. This is a linked list, not an array. You don't have to shift anything when you're using linked lists. In a linked list, deletion takes O(1) once you have the node you want to delete.
Of course, there's still the matter of how we find the node to move to the front. Searching in a Linked List _could_ take O(n) time. However, the question didn't mention anything about having to search for elements efficiently, only about having to delete elements efficiently, which we can do because we know they're in the back. If we did have to make elements searchable efficiently, though, we could do O(1) searching by making a HashMap that maps elements to the nodes having those elements.
Thanks, Anonymous on September 06, 2012 :). I was thinking about LL actually, but I used it as an array...
Not sure how we can achieve O(1) deletion for LRU scheme if we just move the most recently used node to the front. We will need to remove the node at the end. Unless we maintain a pointer there, we will need to get to the tail and that is O(N) .
"Eugene, If you maintain a pointer at the end, how are you going to update it after deletion? It has to be done in O(1) time."
I will ensure the list is a doubly-linked list so I can do that. If it's a doubly linked list, you have a pointer to the previous node.
Eugene,
If we are dealing with doubly linked list, your idea is perfect. I was wondering if there is a solution for singly linked list. Perhaps if we have singly linked list, one can actually move the recently used element at the end. In that way, the node pointed to head will be the one to be removed, which can be done in O(1) time. We will still have to maintain a tail pointer.
Eugene,
If you maintain a pointer at the end, how are you going to update it after deletion? It has to be done in O(1) time.
So, I guess we can just maintain a singly linked list with an additional tail pointer. Every time an element is used we move it to the end of the list (use the tail pointer to do it in O(1) time) and every time we have to delete we remove the first element (using the head pointer, make the head pointer point to the next)
struct Node
{
int data;
struct Node* next;
};
struct LinkedList
{
struct Node* head;
struct Node* tail;
int size;
};
void insert(struct LinkedList* list, int elem)
{
if(list->size >= MAXSIZE)
deleteFront(list);
list->tail->next = (struct Node*)malloc(sizeof (struct Node));
list->tail->next->data = elem;
list->tail->next->next = NULL;
list->tail = list->tail->next;
list->size = list->size + 1;
}
void deleteFront(struct LinkedList* list)
{
struct Node* old = list->head;
list->head = list->head->next;
free(old);
list->size = list->size - 1;
}
int accessElement(struct LinkedList* list, int elem)
{
if(list->size == 1) //No need to change the list
{
if(list->head->data == elem)
return elem;
else
return INT_MIN;
}
//Else the size of the list is more than 1 and we may need to transform the list
else
{
struct Node* current = list->head;
//If head contains the element and list size is atleast 2
if(current->head->data == elem)
{
list->tail->next = list->head;
list->head = list->head->next;
list->tail = list->tail->next;
list->tail->next = NULL;
return list->tail->data;
}
else if(list->tail->data == elem)
{
return list->tail->data;
}
else if //Element may reside inside somewhere in the list
{
while(current != NULL)
{
if(current->next->data == elem)
break;
current = current->next;
}
if(current != NULL) //We got the element after current
{
list->tail->next = current->next;
current->next = current->next->next;
list->tail = list->tail->next;
list->tail->next = NULL;
return list->tail->data;
}
}
}
return INT_MIN;
}
Every time you use an element, transfer it to the front of the linked list. When you need to delete elements, delete them from the back. It's that simple, if I understand the question correctly.
- eugene.yarovoi September 06, 2012