## Google Interview Question for SDE1s

• 1
of 1 vote

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

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;
while(itr!=null)
{
if(map.containsKey(itr))
{
if(newblock)
{
block++;
newblock = false;
}
}else
{
newblock = true;
}
itr = itr->next;
}
return block;
}``````

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

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) {
result_set.push_back(pair<int, int>(count_list++, 0));
continue;
}

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;

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

return 0;
}``````

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

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

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 {

if(pointers == null || pointers.size() == 0) {
return 0;
}

// This set will contain the individual nodes belonging to one/same linkedlist
for(Pointer p : pointers) {
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
// Since two linked list are joining here we need to copy the elements from one to another before we remove it;
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 {
matchedSet = nodes;
}
}
}
Set<Node> nodes = new HashSet<>();
}
}
}

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

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

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

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.

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