Cisco Systems Interview Question for Software Engineer / Developers


Team: Switching Softwares
Country: United States
Interview Type: Phone Interview




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

try insertion sort. that is efficient than bubble + inplace + no traverse back too

- Anonymous July 01, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Bubble sort is no way the best performance sorting algorithm, as insertion sort is 5 times faster on an array, let alone on a linked list

Read the wikipedia page

- wyefei88 May 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

Bubble Sort, with O(n^2) time complexity, I think without additional memory, this is best solution, and use isSorted and pEnd to reduce complexity too.

struct Node
{
Node *next;
int value;
};

Node* BubbleSortList(Node *pHead)
{
if ( pHead == NULL || pHead->next == NULL ) // Empty or only one node case.
return pHead;

bool isSorted = false;
Node *pEnd = NULL; // point to last loop sorted item.
Node *pLastSwapNode = NULL;

while (pEnd != pHead && isSorted == false)
{
isSorted = true;
Node *pCurrent = pHead;

while (pCurrent->next != pEnd)
{
if (pCurrent->value > pCurrent->next->value )
{
swap(pCurrent->value, pCurrent->next->value); // don't swap node, just swap its value.
isSorted = false;
pLastSwapNode = pCurrent->next; // record swap last node.
}

pCurrent = pCurrent->next;
}

pEnd = pLastSwapNode;
}

return pHead;
}

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

void sortList(Node* h)
{
	Node *cur1,*prev1,*next1,*cur2,*prev2,*next2;
	
	prev1=h;
	cur1=h->next;
	
	while(cur1!=NULL)
	{
		next1=cur1->next;
		prev2=h;
		cur2=h->next;
		while(cur2!=cur1)
		{
			next2=cur2->next;
			if(cur2->data>cur1->data)
			{
				prev2->next=cur1;
				cur1->next=cur2;
				prev1->next=next1;
				cur1=next1;
				break;
			}
			prev2=prev2->next;
			cur2=cur2->next;
		}
		if(cur2==cur1)
		{
			prev1=prev1->next;
			cur1=cur1->next;
		}
	}
				
}

- sarath July 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*Sorting of linklist using bubble sort */
void sort_list ( LIST *head) {
        int count=0,tmp,i;
        LIST *node;
         node=head;
/*count the number of elements*/
        while (node!=NULL){
                count++;
                node=node->next;
        }
/*do a bubble sort */
        for ( i=1;i<count;i++){
                node = head;
                while(node->next!=NULL){
                        if(node->value > node->next->value)
                        {
                                tmp = node->value;
                                node->value = node->next->value;
                                node->next->value = tmp;
                        }
                                node = node->next;
                }
        }



}

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

Selection sort:

public static void sortList(Node head) {

	Node tail = head;
	while (tail.next != null) {
	    tail = tail.next;
	}
	Node n = head;
	Node prev = null;
	Node max = null;
	Node prevForMax = null;
	while (tail != head) {
	    max = tail;
	    n = head;
	    prevForMax = null;
	    prev = null;
	    while (n != tail) {
		if (n.d > max.d) {
		    max = n;
		    prevForMax = prev;
		}
		prev = n;
		n = n.next;
	    }
	    if (max != tail) {
		if (prevForMax != null) {
		    prevForMax.next = tail;
		}
		if (max == prev) {
		    max.next = tail.next;
		    tail.next = max;
		} else {
		    Node temp = tail.next;
		    tail.next = max.next;
		    prev.next = max;
		    max.next = temp;
		}
	    }
	    if (max == head) {
		head = tail;
	    }
	    if (max != prev) {
		tail = prev;
	    }
	}
	//Node.printList(head);
    }

- Anonymous July 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Cisco gives hike once in 2-3 years.

New-Joinees only get hike after 2-3 years, so take 100% hike at the time of joining .. . otherwise don't cry after joining. :)

- Simple April 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Its simple.. Perform merge sort for linked list.
In case of array it is not inplace but for Linked List merge sort is in place algorithm.
Solution can be found on geeksforgeeks website.

- Kartik Agarwal September 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This comment has been deleted.

- Administrator March 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This won't work in all cases.

The while loop breaks out after a single pass in some cases.


What happens if (list.first.data < list.first.nextLink.data) after the first pass. It should not break out simply.

- Shekar Gurram March 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can use simple bubble sort.... Though it has complexity of n^2, it solves the problem at least.

- lippie_ March 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

can we get better time complexity...in place and better than On^2

- sprateek1990 April 19, 2012 | Flag


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