## Google Interview Question

**Country:**United States

```
public static LinkNode insertSortedWay(LinkNode head,LinkNode newNode){
if(head == null || head.data > newNode.data){
newNode.next = head;
head = newNode;
}else {
LinkNode current = head;
while (current.next != null && current.next.data < newNode.data) current = current.next;
newNode.next = current.next;
current.next = newNode;
}
return head;
}
public static void read(int[] nums, LinkNode head1, LinkNode head2){
for(int num : nums){
LinkNode newNode = new LinkNode(num);
if(num % 2 == 0) head1 = insertSortedWay(head1, newNode);
else head2 = insertSortedWay(head2,newNode);
}
}
```

I think that it is a little tricky question - actually you can do insertion sort for both lists with O(n^2) complexity, but if you use skip lists , complexity will be O(nlog(n)), suppose that there was a place for conversation. Jasper could you elaborate whether interviewer asked you to optimize O(n^2) complexity or pushed you to proceed to the next question?

Problem statement says that Read would read a set of numbers and add odd number to the odd list and even number to the even list. This essentially meant just a sorted insert for each of the numbers. Solutions above tries to remove even numbers from odd list and vice versa, which is not correct.

The brute force solution would be add each number to its related linked list. Since insertion can take O(n), the total complexity would be O(n^2). One way to reduce the complexity is to reduce the insertion time. Since it is doubly linked list, we can have a BST fo each even and odd numbers, instead. We can later convert the BST to doubly linked list in O(n) in place. So,the total complexity would be O(nlogn) and space O(n).

```
#include <stdio.h>
#include <cstdlib>
#include <iostream>
using namespace std;
class Node
{
public:
Node(int _value, Node* _node)
{
value = _value;
next = _node;
}
Node *getNext()
{
return next;
}
void setNext(Node *node)
{
next = node;
}
int getNumber()
{
return value;
}
private :
int value;
Node * next;
};
void SortOddEven(Node *evenList, Node *oddList)
{
for(int m = 0; m < 100; m++)
{
int number = rand() % 100;
printf("%i ",number);
fflush(stdout);
if( number % 2 == 0 )
{
if( evenList == NULL )
{
evenList = new Node(number, NULL);
}
else
{
Node *head = evenList;
Node *prevNode = NULL;
bool success = false;
while( evenList != NULL)
{
if(number < evenList->getNumber() )
{
Node *node = new Node(number, evenList);
if(prevNode != NULL )
prevNode->setNext(node);
else
head = node;
success = true;
break;
}
prevNode = evenList;
if( evenList->getNext() )
evenList = evenList->getNext();
else
break;
}
if(success == false)
{
Node *node = new Node(number, NULL);
evenList->setNext(node);
}
evenList = head;
}
}
else
{
if( oddList == NULL )
{
oddList = new Node(number, NULL);
}
else
{
Node *head = oddList;
Node *prevNode = NULL;
bool success = false;
while( oddList != NULL)
{
if(number < oddList->getNumber() )
{
Node *node = new Node(number, oddList);
if(prevNode != NULL )
prevNode->setNext(node);
else
head = node;
success = true;
break;
}
prevNode = oddList;
if( oddList->getNext() )
oddList = oddList->getNext();
else
break;
}
if(success == false)
{
Node *node = new Node(number, NULL);
oddList->setNext(node);
}
oddList = head;
}
}
}
cout << endl;
while( evenList != NULL )
{
cout << evenList->getNumber() << " ";
evenList = evenList->getNext();
}
cout << endl;
while( oddList != NULL )
{
cout << oddList->getNumber() << " ";
oddList = oddList->getNext();
}
cout << endl;
}
int main()
{
SortOddEven(NULL, NULL);
return 0;
```

}

```
#include <stdio.h>
#include <cstdlib>
#include <iostream>
using namespace std;
class Node
{
public:
Node(int _value, Node* _node)
{
value = _value;
next = _node;
}
Node *getNext()
{
return next;
}
void setNext(Node *node)
{
next = node;
}
int getNumber()
{
return value;
}
private :
int value;
Node * next;
};
void SortOddEven(Node *evenList, Node *oddList)
{
for(int m = 0; m < 100; m++)
{
int number = rand() % 100;
printf("%i ",number);
fflush(stdout);
if( number % 2 == 0 )
{
if( evenList == NULL )
{
evenList = new Node(number, NULL);
}
else
{
Node *head = evenList;
Node *prevNode = NULL;
bool success = false;
while( evenList != NULL)
{
if(number < evenList->getNumber() )
{
Node *node = new Node(number, evenList);
if(prevNode != NULL )
prevNode->setNext(node);
else
head = node;
success = true;
break;
}
prevNode = evenList;
if( evenList->getNext() )
evenList = evenList->getNext();
else
break;
}
if(success == false)
{
Node *node = new Node(number, NULL);
evenList->setNext(node);
}
evenList = head;
}
}
else
{
if( oddList == NULL )
{
oddList = new Node(number, NULL);
}
else
{
Node *head = oddList;
Node *prevNode = NULL;
bool success = false;
while( oddList != NULL)
{
if(number < oddList->getNumber() )
{
Node *node = new Node(number, oddList);
if(prevNode != NULL )
prevNode->setNext(node);
else
head = node;
success = true;
break;
}
prevNode = oddList;
if( oddList->getNext() )
oddList = oddList->getNext();
else
break;
}
if(success == false)
{
Node *node = new Node(number, NULL);
oddList->setNext(node);
}
oddList = head;
}
}
}
cout << endl;
while( evenList != NULL )
{
cout << evenList->getNumber() << " ";
evenList = evenList->getNext();
}
cout << endl;
while( oddList != NULL )
{
cout << oddList->getNumber() << " ";
oddList = oddList->getNext();
}
cout << endl;
}
int main()
{
SortOddEven(NULL, NULL);
return 0;
```

}

- Anonymous February 08, 2016