## Interview Question for Software Engineer / Developers

Country: United States

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

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

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

Question is about the linked list, not normal list so this will not work.

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

I am inserting the list in sorted order
heres the code
{
}
else
{
{
}
else
{
while (curr != null)
{
if (curr.data > item)
{
return;
}
else
{
Prev = curr;
curr = curr.next;
}
}
}
}
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...
curr1 = prev.next;
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...

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

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.

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

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

Comment hidden because of low score. Click to expand.
0
of 2 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).

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

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++;
}
while (temp != null) {
System.out.print(temp.value + " ");
temp = temp.next;
}
System.out.println();
System.out.println("Count : " + count);

while (temp != null) {
System.out.print(temp.value + " ");
temp = temp.next;
}
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();
while (temp != null) {
System.out.print(temp.value + " ");
temp = temp.next;
}
}

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

}

public static Node merge(Node a, Node b) {
Node temp = new Node();
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;
}
}

public class Node {
int value;
Node next;

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

public Node() {
}
}``````

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

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

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)

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)

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

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

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

quick sort can be done in place

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

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.

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

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;
}
else {
tail->next = left;
tail = tail->next;
}

left = t;
}
else {

Node* t = right->next;
}
else {
tail->next = right;
tail = tail->next;
}

right = t;
}
}

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

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

}

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

return;

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

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

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

cout << endl;
}

// if the list has only one element, it's already sorted.

Node* left = NULL, *right = NULL;

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

}

printList(h);
printList(h2);

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

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,

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.

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