## Google Interview Question

• 0
of 0 votes

Country: United States

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

``````#include <iostream>
#include <list>

using namespace std;

// unary predicates implemented as classes
struct is_odd {
bool operator() (const int& value) { return (value%2)==1; }
};

struct is_even {
bool operator() (const int& value) { return (value%2)==0; }
};

// function Google wants
void READ(list<double> *odd, list<double> *even);

// main with test data to make sure my function works
int main() {

list<double> odds;  // list for odds
list<double> evens; // list for evens

double myDoubles[] = {1, 5, 4, 6, 2, 3, 8, 7};  // test data
double moreDoubles[] = {11, 15, 14, 19, 9, 12}; // test data
odds.assign(myDoubles, myDoubles + 8);          // give first set of test data to odd list
evens.assign(moreDoubles, moreDoubles + 6);     // give second set of test data to even list

READ(&odds, &evens);    // function call

// printing of the odd list
for (auto &itr : odds) {
cout << itr << endl;
}

cout << endl;   // printing newline for neatness

// printing the even list
for (auto &itr : evens) {
cout << itr << endl;
}

return 0;

}

// implementation of Google function
void READ(list<double> *odd, list<double> *even)
{
// look at each element in odd list
for (auto & itr: *odd) {
// if it is even
if ((int)itr % 2 == 0) {
// put that same value in the even list
even->push_back(itr);
}
}

// remove all evens from odd list
odd->remove_if(is_even());

// look at each element in the even list
for (auto & itr: *even) {
// if the element is odd
if ((int)itr % 2 == 1) {
// put that same value in the odd list
odd->push_back(itr);
}
}

// remove all odds from the even list
even->remove_if(is_odd());

// sort odd list
odd->sort();

// sort even list
even->sort();

}``````

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

``````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);
}

}``````

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

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?

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

Not sure on how the skip list would help here, unless the skiplist higher level nodes can point to those odd elements in even list and wise versa.

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

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.

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

correct, skip list could help to insert for log(n) time

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

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

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

Does the question say doubly linked list specifically?

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

``````#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;``````

}

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

``````#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;``````

}

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