Interview Question


Country: India




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

Lets assume each element in node is represented as -

struct node {
    int data;
    struct node *next;
};

Given a list you can clone it with the above structure -

void cloneList(struct node *src, struct node **dest)
{
    struct node *start = src;
	
    struct node *element = NULL;
	if (src == NULL) {
		// empty list
		*dest = NULL;
		return;
	}
	element = createNode(src->data);
	*dest = element;
	src = src->next;
	while (src) {
		printf("Element created %d\n", src->data);
		element->next = createNode(src->data);
		if (element == NULL) {
			// alloc failure, free list and return empty clone list
			destroyList(*dest);
			*dest = NULL;
			break;
		}
		src = src->next;
		if (src == start) {
			// circular list
			element->next->next = *dest;
			break;
		}		
		element = element->next;
	}
	return;
}

Test cases would be -

1. validListClone(list)
Expected output should produce a copy. Validate using the number of elements in source and destination should match

2. emptyListClone(NULL);
Expected output should produce a empty list

3. circularListClone(list);
Expected output should to produce a circular list with last node of the cloned list pointing to the first element of the cloned list and not the original list.

- RS August 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if the list doesn't loop back to the beginning, but rather in the middle?

- helloru August 09, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

You have a valid point. The test case of cloning a malformed list is required.

The correctness in expected output is ambiguous -

a) clone fails as soon as it detects a loop and returns NULL
b) clone completes by detecting the loop and returns a malformed list
c) clone completes by detecting and removing the loop in the cloned copy (source is read only).

What is required to be done is supplement the function to detect malformed list.

- RS August 10, 2016 | 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