Informatica Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 1 vote

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the LRU element will be removed. so we should delete from the front of the linked list.

- gnahzy September 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi September 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes, you are right. i misunderstood LRU....

- gnahzy September 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 September 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- Anonymous September 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks, Anonymous on September 06, 2012 :). I was thinking about LL actually, but I used it as an array...

- Prepare4Job September 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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) .

- random_procrastinator September 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

And we will maintain a pointer to the end. Why in the world wouldn't we?

- eugene.yarovoi September 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

"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.yarovoi September 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- random_procrastinator September 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- random_procrastinator September 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It will be a doubly linked list

- s.kalyanasundaram March 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Instead, Put the used element at the end of the list.
So deleting the first element at the head will be in O(1) time
Also adding at the end will be in O(1) time.

- Ajay July 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- artemis October 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Vijay November 25, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More