Google Interview Question


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();

}

- Anonymous February 08, 2016 | Flag Reply
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);
        }
      
    }

- abhay0609 February 08, 2016 | Flag Reply
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?

- EPavlova February 09, 2016 | Flag Reply
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.

- Vs February 10, 2016 | Flag
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.

- Vs February 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous February 11, 2016 | Flag Reply
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).

- mehraz February 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Does the question say doubly linked list specifically?

- temp March 09, 2016 | Flag Reply
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;

}

- Anonymous April 24, 2016 | Flag Reply
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;

}

- ccc April 24, 2016 | 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