Google Interview Question for Software Engineer / Developers


Country: Israel
Interview Type: In-Person




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

Both the methods are O(n)

Method 1. by using extra space ( HashMap )
Method 2. by modifying linked list structure ie by removing the prev pointers of nodes

class DDL_Pointer{
        private static void resultType_DLL( node arr[] , node head ){
                node curr = head;

                for( int i = 0 ; i < arr.length; i++ ){
                        node n = arr[i];
                        if( n.next != null )
                                n.next.prev = null;
                }

                while( curr.next != null ){
                        if( curr.next.prev == null )
                                System.out.println( curr.val );
                        else
                                System.out.println();
                        curr = curr.next;
                }
        }

        private static void resultType_HashMap( node arr[] , node head ){
                HashMap hm = new HashMap();
                for( int i = 0 ; i < arr.length ; i++ ){
                        node n = arr[i];
                        hm.put( n.val, 1);
                }

                node curr = head;
                while(curr.next != null){
                        if( hm.containsKey(curr.val) )
                                System.out.println( curr.val );
                        else
                                System.out.println();
                        curr = curr.next;
                }
        }
	        public static void main( String args[] ){
                node Node1 = new node( 1, null, null);
                node Node2 = new node( 2, Node1 ,null);
                node Node3 = new node( 3, Node2 ,null);
                node Node4 = new node( 4, Node3 ,null);
                node Node5 = new node( 5, Node4 ,null);
                node Node6 = new node( 6, Node5 ,null);
                node Node7 = new node( 7, Node6 ,null);
                node Node8 = new node( 8, Node7 ,null);
                node Node9 = new node( 9, Node8 ,null);

                Node1.next = Node2;
                Node2.next = Node3;
                Node3.next = Node4;
                Node4.next = Node5;
                Node5.next = Node6;
                Node6.next = Node7;
                Node7.next = Node8;
                Node8.next = Node9;

                node head = Node1;

                node arr[] = { Node9,Node1,Node3,Node7,Node8,Node5,Node2};
                // using hashmap
                resultType_HashMap( arr, head );
                // modifying structure of linked list
                resultType_DLL( arr, head );
                }
}

class node{
        int val;
        node next;
        node prev;

        public node( int val, node prev, node next ){
                this.val = val;
                this.next = next;
                this.prev = prev;
        }
}

- Source January 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you explain your code? how does it solve the problem? what is your return value? It doesn't clear to me exactly what are you trying to achieve here.

- pavelkushtia February 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@pavelkushtia :
Here i'm copying elements from Array {9,1,3,7,8,5,2 } into an hashtable

then while iterating over linked list, i check whether that value is in hashtable , if exists then printing the value , else simply escaping the node in linked list.

hence the output is : 1 2 3 5 7 8 9

I'm only printing the above output on screen , one can easily count these chunks!!!

Also i've mentioned an approach in which i'm modifying the structure of linked list.

as array contains pointers to the nodes , so on one iteration over that array i'm making the pointed node's previous pointer as null

and afterwards, iterating over linked list with the help of next pointer we'll print all the nodes which are having previous pointer as null and escaping those whose previous pointer is not null.

do revert if anything is not clear!!!

- Source February 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Method2 may be what the interviewer wanted

- biolxj12 February 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Small bug under: resultType_DLL
You have:
...

if( curr.next.prev == null )

It should be:

if (current.next != null && current.next.previous == null)

- Doug March 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Iterate through the elements in pointer array updating the doublyLinkedList node's visited to true. After that iterate through the doublyLinkedList to find the number of visited node sequences.

- Din January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think you can create MinHeap with the array elements and then Pop off root each time.
When the difference is more than root+1 then you increment the result.
eg.
9,1,3,7,8,5,2.

1
/\
2 3
/\ /\
5 7 8 9

- roshenw January 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Here is my solution:
1) Sort the array according to the values of pointers.
2) Scan the array and when the [next element] not equals to [previos + 1] increment the result.
Time complexity O(nlogn), memory complexity O(logn) - sorting recursion stack size.

public static class Node{
		public Node left;
		public Node right;
		public Integer value;
		public Node(int v){
			value = v;
		}
	}
	private void exch(Node [] arr, int p, int q){
		Node t = arr[p];
		arr[p] = arr[q];
		arr[q] = t;
	}
	private int partition(Node [] arr, int left, int right){
		if(left > right) return -1;
		int pivot = left;
		int thresh = pivot;
		for(int i = left + 1; i <= right; i++){
			if(arr[pivot].value > arr[i].value)
				exch(arr, ++thresh, i);    
		}
		exch(arr, thresh, pivot);
		return thresh;
	}
	private void quickSort(Node [] arr, int left, int right){
		int pivot = partition(arr, left, right);
		if(pivot < 0) return;
		quickSort(arr, left, pivot - 1);
		quickSort(arr, pivot + 1, right);
	}
	public int getResult(Node [] arr){
		quickSort(arr, 0, arr.length - 1);
		
		int result = 1;
		for(int i = 0; i < arr.length - 1; i++){
			if(arr[i].value + 1 != arr[i + 1].value)
				result += 1;
		}
		return result;
	}
	public static void main(String [] args){
		Node [] arr = new Node[7];
		problem_4 d = new problem_4();
		arr[0] = new Node(9);
		arr[1] = new Node(1);
		arr[2] = new Node(3);
		arr[3] = new Node(7);
		arr[4] = new Node(8);
		arr[5] = new Node(5);
		arr[6] = new Node(2);
		System.out.println(d.getResult(arr));
	}

- denys.o.p January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I believe your solution assumes nodes in the linked list reside in consecutive memory addresses, which is very likely not true.

- Victor January 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Keep a list that contains pairs of sets.
1. set of elements that are in a sequence.
2. set of elements that should be neighbours of the elements in the sequence (their left and right pointers).

For every pointer in the pointer array, iterate through this list of ours checking if this pointer is in the set of should-be neighbours. If it is, we merge both sets.

At the end, our defined list will have one structure element for each sequence.

I know my description wasn't very good. I hope you can understand it.

m: size of pointer array
d: number of sequences of elements
Complexity: O(m*d) time

#include <vector>
#include <unordered_set>
#include <list>

class Node {
	public:
	Node *left;
	Node *right;
};

typedef std::vector<Node*> PointerArray;
typedef std::unordered_set<Node*> NodeSet;
typedef std::pair<NodeSet, NodeSet> NodeSetPair;
typedef std::list<NodeSetPair> NPList;

int sequences(const PointerArray &A)
{
	int n = A.size();
	int i;

	NPList l;

	for (i = 0; i < n; ++i) {
		Node *p = A[i];
		NodeSetPair newpair;

		// create sets for this new element
		newpair.first.insert(p);
		newpair.second.insert(p->left);
		newpair.second.insert(p->right);

		NPList::iterator lit, lend;
		for (lit = l.begin(), lend = l.end(); lit != lend; ) {
			const NodeSet &key = lit->first;
			const NodeSet &neighbours = lit->second;

			// merge sets
			if (neighbours.count(p)) {
				newpair.first.insert(key.begin(), key.end());
				newpair.second.insert(neighbours.begin(), neighbours.end());
				
				lit = l.erase(lit);
			}
			else {
				++lit;
			}
		}
		l.push_back(move(newpair));
	}

	return l.size();
}

- Victor January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your logic has a worst case O(n^2) complexity. For example if the list contains all odd numbers. Also, have you tested the implementation? inserting the left and right as neighbors doesn't seems right to me.

- pavelkushtia February 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#define MAX_ELEM 10

typedef struct node_t {
    int elem;
    struct node_t *left;
    struct node_t *right;
}node_type;

void find_groups (node_type* root_p, node_type** node_p_arr_test) {

    int group_count = 0;
    int series = 0;
    int i;
    node_type *current_node_p, *prev_node_p;

    current_node_p = root_p;
    prev_node_p = root_p;

    // make the 1st node left ptr point to itself (temp)
    root_p->left = root_p;

    i = 0;
    printf("nodes passed \n");
    while(node_p_arr_test[i] != NULL) {
        printf("%d \t", node_p_arr_test[i]->elem);
        (node_p_arr_test[i])->left = NULL;
        i = i+1;
    }
    printf("\n");

    current_node_p = root_p;
    prev_node_p = root_p;

    while(current_node_p != NULL) {
        if(current_node_p->left == NULL) {
            current_node_p->left = prev_node_p;
            printf("%d \t", current_node_p->elem);
            if(!series) {
                series = 1;
                group_count = group_count + 1;
            }
        } else {
            if(series){
                series = 0;
                printf("group %d\n", group_count);
            }
        }
        prev_node_p = current_node_p;
        current_node_p = current_node_p->right;
    }
    root_p->left = NULL;
    printf("group %d\n", group_count);
}

int main() {

    int i;
    node_type *new_node_p;
    node_type *root_p = NULL;
    node_type *prev_node_p = NULL;
    node_type* node_p_arr[10];
    node_type* node_p_arr_test[20];

    memset(node_p_arr_test, 0, sizeof(node_p_arr_test));

    for(i=0; i<MAX_ELEM; i++){
        new_node_p = (node_type*) malloc(sizeof(node_type));
        if(new_node_p == NULL) {
            printf("malloc failed\n");
            exit(0);
        }

        node_p_arr[i] = new_node_p;
        new_node_p->elem = (i+1)*100;
        new_node_p->right = NULL;
        new_node_p->left = prev_node_p;

        if(root_p == NULL){
            root_p = new_node_p;
        } else {
            prev_node_p->right = new_node_p;
        }

        prev_node_p = new_node_p;
    }
    node_p_arr_test[0] = node_p_arr[9];
    node_p_arr_test[1] = node_p_arr[7];
    node_p_arr_test[2] = node_p_arr[8];
    node_p_arr_test[3] = node_p_arr[9];
    node_p_arr_test[4] = node_p_arr[5];
    node_p_arr_test[5] = node_p_arr[2];
    node_p_arr_test[6] = node_p_arr[3];
    node_p_arr_test[7] = node_p_arr[7];
    node_p_arr_test[8] = node_p_arr[4];
    node_p_arr_test[9] = node_p_arr[9];
    node_p_arr_test[10] = node_p_arr[2];
    node_p_arr_test[11] = node_p_arr[4];
    node_p_arr_test[12] = node_p_arr[3];
    node_p_arr_test[13] = node_p_arr[0];

    find_groups(root_p, node_p_arr_test);

    return 0;
}

- snd January 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It seems like this can be answered much more simply than it looks. We can simply keep track of all visited nodes in a hash table. Then traverse the linked list looking for visited nodes, keeping track of connected sequences.

int CountSequences(node *head, vector<node*> nArray)
{
	unordered_set<int> visited;
	
	for (unsigned int i = 0; i < nArray.size(); i++)
	{
		int key = (int)nArray[i];
		if (visited.find(key) == visited.end())
		{
			visited.insert(key);
		}
	}

	int sequences = 0;
	while (head != NULL)
	{
		while (visited.find((int)head) == visited.end() && head)
		{
			head = head->next;
		}

		if (!head)
			break;
		
		sequences++;
		while (visited.find((int)head) != visited.end() && head)
		{
			head = head->next;
		}
	}

	return sequences;
}

- anonymoose February 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I could only come up a Time O(m+N), space O(m) solution, wish there is a better solution.

Go through the pointer array, store all nodes pointed into a hashset.
Go through the double-linked list, at each node, check prev and next of it, if(prev not included in set but next included), this node is the beginning of a group, so sum++.
return sum.

- flyingpig February 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Similar to couple other answers, traverse array keeping track of visited nodes. Also have an integer counter initially set to 0.
When visiting a node, it is either the only element, first, last, or middle element in the list (checked by looking at node.prev and node.next).
What to do in each case:
i) Only element: counter++
ii) First element: if node.next is not visited, counter++
iii) Last element: if node.prev is not visited, counter++
iv) Middle element: if node.prev is not visited and node.next is not visited, counter++
Basically we increment the counter whenever we are starting a new sequence. Otherwise, we are just adding to an existing sequence so we don't increment.
At the end, return counter.

- JW February 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This implementation is O(n) time and requires only a single pass of the elements.

- JW February 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1) For i=0 to Array.Length:
insert Element[i] into a hash set.
2) Set counter = 0
3) For i=0 to Array.Length:
if HashSet.Contains(Element[i])
{
Increment the counter,
Remove Element[i] from the HashSet
n = Element[i].Next; while(n != null) { Remove n from HashSet; n = n.Next }
p = Element[i].Prev; while(p != null) { Remove p from HashSet; p = p.Prev }
}

- Anonymous February 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Seems like this is a simple problem of sorting the array and figuring out the gaps in sequence which can be achieved in O(nlogn) + O(n) = O(nlogn)

- pc May 26, 2015 | 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