## Google Interview Question for Java Developers

Country: United States

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

I'd do something like this:

1. Store the intervals as nodes of a doubly-linked list. Each node contains from_, to_, val_, id_. id_ is uint32_t, unique among the nodes.

2. For each node in the linked list, dump into a min heap abs difference of the node's value and the node's next node's value. The min heap's element consists of the difference and uint64_t id, which is built out of the 2 linked list nodes' ids.

3. The min heap is updatable. I.e. it's possible to update or remove a node of it by id.

4. Get the top element from the heap, parse id of the element into ids of 2 linked list nodes, get pointers to the nodes using the ids.

5. Merge the 2 nodes, update value of the first node with average of the node's values, remove the second node from the linked list.

6. Update the min heap. I.e. remove the heap node with id equal to "second_linked_list_node->next_to_second_linked_list_node", update value of the heap node with id equal to "prev_to_first_linked_list_node->first_linked_list_node", and insert a new heap node, having id "first_linked_list_node->next_to_second_linked_list_node".

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

O(n) space, O(nlogn) time

Using min heap(priority queue) and array

``````#include <iostream>
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
class Point
{
public:
int value;
int start;
int end;
};
class myComparator
{
public:
int operator() (const Point* a, const Point* b)
{
return a->value > b->value;
}
};
int mod(int a)
{
return a < 0 ? (-1 * a) : a;
}
void MergeIntervals(int* a, int n, int threshold)
{
int parent[n];
for(int i=0; i<n; i++)
{
parent[i] = i;
}
priority_queue<Point*, vector<Point*>, myComparator> pq;
int min1 = mod(a - a);
int min2 = INT_MAX;
int a1 = 0;
int a2;
for(int i=1; i<n-1; i++)
{
if(mod(a[i] - a[i+1]) <= min1)
{
a2 = a1;
a1 = i;
min1 = mod(a[i] - a[i+1]);
min2 = min1;
}
else if(mod(a[i] - a[i+1]) <= min2)
{
a2 = i;
min2 = mod(a[i] - a[i+1]);
}
}
if(a1 == a2+1 || a2 == a1+1)
{
int min = INT_MAX;
for(int i=0; i<n-1; i++)
{
int x = mod(a[i] - a[i+1]);
if(x < min && x != min1 && x != min2)
{
a2 = i;
min = x;
}
}
min2 = min;
}

cout<<"a1 "<<a1<<endl;
cout<<"a2 "<<a2<<endl;
Point* p1 = new Point();
p1->value = min1;
p1->start = a1;
p1->end = a1+1;

Point* p2 = new Point();
p2->value = min2;
p2->start = a2;
p2->end = a2+1;

pq.push(p1);
pq.push(p2);

while(pq.size() != 1 && pq.top()->value <= threshold)
{
Point* p = pq.top();
pq.pop();
int startParent = p->start;
int endParent = p->end;
a[startParent] = (a[p->start] + a[p->end])/2;
a[endParent] = a[startParent];
parent[startParent] = endParent;
parent[endParent] = startParent;

Point* new_p = new Point();
int diff1 = INT_MAX;
int diff2 = INT_MAX;
if(startParent > 0)
{
diff1 = mod(a[startParent-1] - a[startParent]);
}
if(endParent < n-1)
{
diff2 = mod(a[endParent+1] - a[endParent]);
}
if(diff1 != INT_MAX || diff2 != INT_MAX)
{
if(diff1 < diff2)
{
Point* p_new = new Point();
p_new->value = diff1;
p_new->start = parent[startParent-1];
p_new->end = parent[startParent];
}
else
{
Point* p_new = new Point();
p_new->value = diff2;
p_new->start = parent[endParent];
p_new->end = parent[endParent+1];
}
}
}

int i =0;
while(i < n)
{
cout<<i<<" "<<parent[i];
i = parent[i] + 1;
cout<<endl;
}

}
int main() {
int n;
cin>>n;
int a[n];
for(int i=0; i<n; i++)
{
cin>>a[i];
}
int t;
cin>>t;
MergeIntervals(a, n, t);
}``````

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.