Google Interview Question for SDE1s


Country: United States
Interview Type: Phone Interview




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

I would guess the question sais, you are given a set of pointers from multiple doubly linked lists and you need to determine how many doubly linked lists the pointers come from:

assuming that the first and last nodes are special in the list in a way their next and previous pointers are null, I can simply count the nodes that only have one incoming edge, which means I have the number of start and end nodes. Divide that by two should lead to the result.

int countNoOfLists(vector<void*> list) {
	unordered_set<void*> set;
	for (void* ptr : list) {
		if (set.find(ptr) == set.end()) {
			set.insert(ptr);
		} else {
			set.erase(ptr);
		}
	}
	return set.size() / 2;
}

there are other interpretations of the question, but this one is particularly convenient :-)

- Chris May 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.

Given by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greedy, String and other advanced algo problems),
and mock interviews.

Our students got offers from G, U, FB, Amz, Yahoo and other top companies after weeks of training.

Welcome to email us aonecoding@gmail.com with any questions. Thanks for reading.


Solution by the interviewee:

public int findBlockCount(List<Node> pointers, Node head)
{
     HashMap<Node, Integer> map = new HashMap();
     for(Node n:pointers)
     {
          map.put(n, 1);
     }
     int block = 0;
     boolean newblock = true;
     Node itr = head;
     while(itr!=null)
     {
         if(map.containsKey(itr))
         {
              if(newblock)
              {
                   block++;
                   newblock = false;
              }
         }else
         {
              newblock = true;
         }
         itr = itr->next;
     } 
     return block;
}

- aonecoding May 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you please explain the question? Are only the pointers given ? Thanks

- practiceVasu May 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I couldnt follow the question either
Based on my understanding of the question
1) Look for independant blocks of the list.
for a given list, the independant block is the set of nodes until it merged into an existing list.
2) assumption: circular list but without loops.
3) if list at index i, has a node (any node, may be head node) point to a list at index k where k > i, the list k is considered a subset of list i, and list k will return pair<k, 0>
4) a list k without any node will return <k, 0> , thus requiring checking whether the 0 case is if the list is empty or exist entirely into an existing list

#include <iostream>
using namespace std;

#include<vector>
#include<unordered_set>

struct node {
  int v;
  node *next;
  node *prev;
    
};

vector<pair<int, int> > block_nodes(vector<node*> &vlist) {
    unordered_set<node*> lookup_set;
    vector<pair<int, int> > result_set;
    int count_list = 0;
    for(vector<node*>::iterator it = vlist.begin(); it!= vlist.end(); ++it) {
        node *chead = *it;
        if (!chead) {
            result_set.push_back(pair<int, int>(count_list++, 0));
            continue;
        }
        
        node *temp = chead;
        int count = 0;
        do {
            if(lookup_set.find(temp) != lookup_set.end()) {
                cout << "The list merged into another list\n";
                break; 
            }
            lookup_set.insert(temp);
            count++;
            temp = temp->next;
        } while(temp != chead);
        
        if (temp == chead) {
            cout << "This list is independant, located at index " << count_list << " and "
                " of size " << count <<"\n";
        }
        result_set.push_back(pair<int, int>(count_list, count));
        count_list++;
    }    
    return result_set;
}

int main() {
    vector<node*> vlist;
    vector<pair<int, int> > result = block_nodes(vlist);
    
	// your code goes here
	return 0;
}

- ali.kheam May 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;

class Node {

    Node prev;
    Node next;
    int val;
}

public class testT {

    public static int numOfBlocks(List<Node> list) {
        if (list == null) {
            return 0;
        }
        int count = 0;
        while (list.size() > 0) {
            Node node = list.get(0);
            list.remove(0);
            count++;
            Stack<Node> stack = new Stack<>();
            Set<Node> visited = new HashSet<>();
            stack.push(node);
            while (stack.size() > 0) {
                node = stack.pop();
                visited.add(node);
                if (node.prev != null) {
                    if (!visited.contains(node.prev)) {
                        stack.push(node.prev);
                    }
                    if (list.contains(node.prev)) {
                        list.remove(node.prev);
                    }
                }
                if (node.next != null) {
                    if (!visited.contains(node.next)) {
                        stack.push(node.next);
                    }
                    if (list.contains(node.next)) {
                        list.remove(node.next);
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Node node1 = new Node();
        Node node2 = new Node();
        Node node3 = new Node();
        node1.next = node2;
        node2.prev = node1;
        System.out.println(numOfBlocks(new ArrayList<>(Arrays.asList(node1, node2, node3))));
    }
}

- Anonymous May 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;

class Node {

    Node prev;
    Node next;
    int val;
}

public class testT {

    public static int numOfBlocks(List<Node> list) {
        if (list == null) {
            return 0;
        }
        int count = 0;
        while (list.size() > 0) {
            Node node = list.get(0);
            list.remove(0);
            count++;
            Stack<Node> stack = new Stack<>();
            Set<Node> visited = new HashSet<>();
            stack.push(node);
            while (stack.size() > 0) {
                node = stack.pop();
                visited.add(node);
                if (node.prev != null) {
                    if (!visited.contains(node.prev)) {
                        stack.push(node.prev);
                    }
                    if (list.contains(node.prev)) {
                        list.remove(node.prev);
                    }
                }
                if (node.next != null) {
                    if (!visited.contains(node.next)) {
                        stack.push(node.next);
                    }
                    if (list.contains(node.next)) {
                        list.remove(node.next);
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Node node1 = new Node();
        Node node2 = new Node();
        Node node3 = new Node();
        node1.next = node2;
        node2.prev = node1;
        System.out.println(numOfBlocks(new ArrayList<>(Arrays.asList(node1, node2, node3))));
    }
}

- efi May 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let me start by saying thanks to ChrisK as this solution is based on his however his solution doesnt take care of circular linked list. Here is the solution that will take care of that.
THis solution runs in O(N) time and O(N) memory.

public class DoublyLinkedListHelper {

public int getNumLinkedLists(List<Pointer> pointers) {
  if(pointers == null || pointers.size() == 0) {
    return 0;
  }

 // This set will contain the individual nodes belonging to one/same linkedlist
  Set<Set<Node>> setOfLinkedListNodes = new HashSet<>();
  for(Pointer p : pointers) {
    Iterator<Set<Node>> itr = setOfLinkedListNodes.iterator();
    boolean addNewSet = true;
    Set<Nodes> matchedSet = null;
    while(itr.hasNext) {
      Set<Node> nodes = itr.next();
      // Means we found an existing linked list node set where we can add the unadded nodes
      // There is a reason we havent overriden equals method as we want matching based on actual object reference
      if(nodes.contain(p.from) || nodes.contain(p.to)) {
        // This means that we had already found a matching list thus there is no need to keep this list
        // since it will end up joining the original list
        if(!addNewSet) {
          // Since two linked list are joining here we need to copy the elements from one to another before we remove it;
          matchedSet.addAll(nodes);
          itr.remove();
          // We will never have a case where a pointer is part of more than 2 sets as they must have been joined otherwise.
          break;
        }
        else {
          // Add the missing node
          nodes.add(nodes.contain(p.from) ? p.to : p.from);
          addNewSet = false;
          matchedSet = nodes;
        }
      }
    }
    if(addNewSet) {
      Set<Node> nodes = new HashSet<>();
      nodes.add(p.from);
      nodes.add(p.to);
      setOfLinkedListNodes.add(nodes);
    }
  }
  return setOfLinkedListNodes.size();
}

  public static class Pointer {
    public Node from;
    public Node to;
  }

  public static class Node {
    public int value;
    public Node prev;
    public Node next;
  }
}

- nk June 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I assume the input is not really nodes of the linked list, but some abstract pointers. A pointer only tells us that there is a connection (either using next or prev of a linked in node) between two nodes.
In this case terminal nodes will be mentioned exactly 2 times in the pointers. Interior nodes will be mentioned 4 times. Each independent block contains 2 terminal nodes (head and tail).

class Pointer {
	public:
		int from_node_;
		int to_node_;
};

int BlocksCount(vector<Pointer> const &pointers)
{
	unordered_map<int, int> node_counts;
	for (Pointer const &pointer : pointers) {
		++node_counts[pointer.from_node_];
		++node_counts[pointer.to_node_];
	}

	int terminal_nodes_count = 0;
	for (auto const &node_count : node_counts) {
		if (node_count.second == 2) {
			++terminal_nodes_count;
		} else if (node_count.second != 4) {
			cerr << "invalid data\n";
			exit(-1);
		}
	}

	if (terminal_nodes_count & 0x01) {
		cerr << "invalid data\n";
		exit(-1);
	}

	return terminal_nodes_count / 2;
}

- Alex June 13, 2017 | 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