Interview Question for Software Engineer / Developers


Country: United States




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

I am inserting the list in sorted order
heres the code
if (head == null)
{
Node additem = new Node();
additem.data = item;
head = additem;
}
else
{
Node curr = head;
Node Prev = head;
if (item < head.data)
{
Node additem = new Node();
additem.data = item;
head = additem;
additem.next = curr;
}
else
{
while (curr != null)
{
if (curr.data > item)
{
Node additem = new Node();
additem.data = item;
Prev.next = additem;
additem.next = curr;
return;
}
else
{
Prev = curr;
curr = curr.next;
}
}
Node additem1 = new Node();
additem1.data = item;
Prev.next = additem1;
}
}
Now Merging the two sorted list. changing the Ist list by appending the node of the second list if its coming in between the nodes of the Ist list...Merging in assending order..
code is...
Node prev = list1.head;
curr1 = prev.next;
curr2 = list2.head;
Node tempptr = new Node();
while (curr1!=null && curr2!=null)
{
if (prev.data == curr2.data)
{
tempptr = curr2.next;
curr2.next = curr1;
prev.next = curr2;
prev = curr2;
curr2 = tempptr;
}
if (prev.data<curr2.data && curr2.data<curr1.data)
{
tempptr = curr2.next;
curr2.next = curr1;
prev.next = curr2;
prev = curr2;
curr2 = tempptr;
}
else
{
prev = curr1;
curr1 = curr1.next;
}

}
Reply to me if its not working in any condition...

- Suvi February 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Bubble sort isn't even worth mentioning, unless the list is very small; It's an archaic algorithm and almost every other other algorithm performs better. Since the list is a linked list, you don't get the benefits of locality. If the list is close to being sorted, use Insertion sort. Otherwise, for a large list, use an "external sorting" algorithm, e.g. mergesort.

- Jack February 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

//After the while loop.. what if list2 is bigger than list1 .. append the list2 to list1
if(ptr2 != null) {
prev.next = ptr2;
}
return head1;
}

- Anonymous May 21, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void MergeUnSortedList(stIntList* pList1,stIntList* pList2,stIntList*& pSorted)
{
stIntList* pList1Temp = pList1;
stIntList* pList2Temp = pList2;

std::map<int,int> mapNoVsCount;
while(pList1Temp != NULL || pList2Temp != NULL)
{
if(pList1Temp != NULL)
{
std::map<int,int>::iterator it1 = mapNoVsCount.find(pList1Temp->data);
if(it1 != mapNoVsCount.end())
it1->second++;
else
{
std::pair<int,int> key(pList1Temp->data,1);
mapNoVsCount.insert(key);
}
pList1Temp = pList1Temp->pNList;
}

if(pList2Temp != NULL)
{
std::map<int,int>::iterator it1 = mapNoVsCount.find(pList2Temp->data);
if(it1 != mapNoVsCount.end())
it1->second++;
else
{
std::pair<int,int> key(pList2Temp->data,1);
mapNoVsCount.insert(key);
}
pList2Temp = pList2Temp->pNList;
}
}
stIntList* pMerge = NULL;
std::map<int,int>::iterator begin = mapNoVsCount.begin();
while(begin != mapNoVsCount.end())
{
for(int i = 0; i < begin->second; i++)
{
insertIntIntoList(pSorted,pMerge,begin->first);
}
begin++;
}
}

- rishikantku June 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Consider two list as list1 and list2.
list1 = Sort(list1)
list2 = Sort(list2)
return Merge(list1,list2)

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

My attempt:

public class MergeAndSort {
	public static void main(String[] args) {
		Node n11 = new Node(5);
		Node n12 = new Node(11);
		Node n13 = new Node(9);
		Node n14 = new Node(11);
		Node n15 = new Node(10);

		n11.next = n12;
		n12.next = n13;
		n13.next = n14;
		n14.next = n15;

		Node n21 = new Node(3);
		Node n22 = new Node(19);
		Node n23 = new Node(12);
		Node n24 = new Node(4);
		Node n25 = new Node(6);
		Node n26 = new Node(11);
		Node n27 = new Node(4);

		n21.next = n22;
		n22.next = n23;
		n23.next = n24;
		n24.next = n25;
		n25.next = n26;
		n26.next = n27;

		Node temp = null;
		Node current = null;
		Node head = temp = n11;
		int count = 0;
		while (temp != null) {
			current = temp;
			temp = temp.next;
			count++;
		}
		temp = current.next = n21;
		while (temp != null) {
			temp = temp.next;
			count++;
		}
		temp = head;
		while (temp != null) {
			System.out.print(temp.value + " ");
			temp = temp.next;
		}
		System.out.println();
		System.out.println("Count : " + count);

		Node finalHead = mergeSort(head);
		temp = finalHead;
		while (temp != null) {
			System.out.print(temp.value + " ");
			temp = temp.next;
		}
		temp = current = finalHead;
		while (temp != null && temp.next != null) {
			boolean considered = false;
			while (temp.value == temp.next.value) {
				temp = temp.next;
				considered = true;
			}
			if (considered) {
				current.next = temp;
			}
			current = temp;
			temp = temp.next;
		}
		System.out.println();
		temp = finalHead;
		while (temp != null) {
			System.out.print(temp.value + " ");
			temp = temp.next;
		}
	}

	public static Node mergeSort(Node headOriginal) {
		if (headOriginal == null || headOriginal.next == null)
			return headOriginal;
		Node a = headOriginal;
		Node b = headOriginal.next;
		while ((b != null) && (b.next != null)) {
			headOriginal = headOriginal.next;
			b = (b.next).next;
		}
		b = headOriginal.next;
		headOriginal.next = null;
		return merge(mergeSort(a), mergeSort(b));

	}

	public static Node merge(Node a, Node b) {
		Node temp = new Node();
		Node head = temp;
		Node c = head;
		while ((a != null) && (b != null)) {
			if (a.value <= b.value) {
				c.next = a;
				c = a;
				a = a.next;
			} else {
				c.next = b;
				c = b;
				b = b.next;
			}
		}
		c.next = (a == null) ? b : a;
		return head.next;
	}
}

public class Node {
	int value;
	Node next;

	public Node(int value) {
		this.value = value;
	}

	public Node() {
	}
}

- vijayinani August 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

1. Append list 2 to the end of list 1.
2. Now you have one in unsorted link list.
3. Use bubble sort or merge sort to sort the list.
4. Bubble sort will give you time complexity of o(n2). Merge sort has better time complexity of o(nlogn).

- Anonymous February 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Take a binary search tree implementation put all the elements from the two list in BST and trace back the BST in inorder traversal and put the element in new linked list...that elemets are automatically sorted...

- vky_garg June 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Take a binary search tree implementation put all the elements from the two list in BST and trace back the BST in inorder traversal and put the element in new linked list...that elemets are automatically sorted...

- vky_garg June 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This shouts heap sort.
1. Create a heap using an array - O(n)
2. Heap sort - O(nlogn)
3. Create a linked list from the array O(n)

Time complexity = O(nlogn), Space complexity = O(n)

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

Use merge sort to sort the two lists individually and then merge the lists similar to used for merge sort.
Time - O(nlgn) - n is number of total elements.
Space - O(1)

- Achilles February 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Space is O(1) ??? :O :O :O And how will you achieve that?

- Bevan February 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

quick sort can be done in place

- zyfo2 February 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Space is O(1) as no extra space is required to merge the two sorted lists.
Remove the elements from the original list and add them to the sorted list.
E.g. 1-3-5 and 2-4 can be merged by moving 1 to the head of new list (3-5, 2-4) remain. Then add 2 making the sorted list 1-2 (3-5,4) remain and so on.
No extra space was required and hence is O(1) in space.

- Achilles February 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's simply a merge_sort algorithm on link-list, I don't suggests to merge the list initially. It will just increase the traversing of break_list algorithm eventually you've to break the list into two.

So here it what should be done.
- 1. Perform MergeSort on List1. (mlogm) assuming size of list m.
- 2. Perform MergeSort on List2. (nlogn) assuming size of list n.
- 3. Merge two sorted List O(m+n).

MergeSort on Link-List can be performed as follows:
- 1. If size of list is one no need to sort.
- 2. break the list into two (say left, right).
- 3. recursively sort the left & right sub-lists.
- 4. merge the two sub-lists into sorted one.

Here is the sample code in C/C++

class Node {
	public:
		int value;
		Node* next;
		Node(int v, Node* n) : value(v), next(n) {}
	};



	Node* merge(Node* left, Node* right) {

		Node* head = NULL, *tail = NULL;

		while (left != NULL && right != NULL) {

			if (left->value < right->value) { 

				Node* t = left->next;
				if (head == NULL) {
					head = tail = left;
				}
				else {
					tail->next = left;
					tail = tail->next;
				}

				left = t;
			}
			else {

				Node* t = right->next;
				if (head == NULL) {
					head = tail = right;
				}
				else {
					tail->next = right;
					tail = tail->next;
				}

				right = t;
			}
		}

		if (left != NULL) {
			if (head == NULL) {
				head = tail = left;
			}
			else {
				tail->next = left;
			}
		}

		if (right != NULL) {
			if (head == NULL) {
				head = tail = right;
			}
			else {
				tail->next = right;
			}
		}

		return head;
	}

	void break_list(Node* head, Node*& left, Node*& right) {

		if (head == NULL)
			return;

		Node* slow = head, *fast = head;
		Node* tailSlow = NULL;
		while (fast) {
			tailSlow = slow;
			slow = slow->next;
			fast = (fast->next) ? fast->next->next: NULL;
		}

		tailSlow->next = NULL;
		left = head;
		right = slow;
	}

	void printList(Node* h) {
		while (h) {
			cout << h->value;
			h = h->next;
		}

		cout << endl;
	}

	Node* merge_sort(Node* head) {

		printList(head);

		// if the list has only one element, it's already sorted.
		if (head == NULL || head->next == NULL)
			return head;

		Node* left = NULL, *right = NULL;
		break_list(head, left, right);

		Node* l = merge_sort(left);
		Node* r = merge_sort(right);

		head = merge(l, r);
		printList(head);
		return head;


	}

	Node* merge_two_lists(Node* head, Node* head2) {

		Node* h = merge_sort(head);
		printList(h);
		Node* h2 = merge_sort(head2);
		printList(h2);

		Node* r = merge(h, h2);
		printList(r);
		return r;
	}

- Laiq Ahmed March 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

the more efficient solution would be:
1. Have two pointers, P1 pointing to List 1 head, P2 pointing to List 2 head
2. Compare pointers P1 and P2 and select and add the smallest to the resultant list L3
Note: Addition is another loop, where you basically place the node in a sorted order in List 3.

This is again O(n2), but a more small and neat code,

- Obaid May 28, 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