## 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 ){

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

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 arr[] = { Node9,Node1,Node3,Node7,Node8,Node5,Node2};
// using hashmap
// modifying structure of linked list
}
}

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

Comment hidden because of low score. Click to expand.
0

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.

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!!!

Comment hidden because of low score. Click to expand.
0

Method2 may be what the interviewer wanted

Comment hidden because of low score. Click to expand.
0

Small bug under: resultType_DLL
You have:
...

``if( curr.next.prev == null )``

It should be:

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

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.

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

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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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.

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

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

break;

sequences++;
{
}
}

return sequences;
}``````

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.

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.

Comment hidden because of low score. Click to expand.
0

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

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

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)

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.