Google Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
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;
}
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;
}
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))));
}
}
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))));
}
}
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;
}
}
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;
}
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.
there are other interpretations of the question, but this one is particularly convenient :-)
- Chris May 28, 2017