## Google Interview Question for SDE1s

Country: United States
Interview Type: Phone Interview

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

can anyone explain the algo or logic behind solution of this problem

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

``````List<Range> getRanges(List<Shard> shards,List<Key> keys){

List<Range> rangeList = new List<Range>();
for (Shard sh : shards)
{
int rangeStart=Integer.MAX_VALUE;
int rangeEnd = Integer.MIN_VALUE;
int start = sh.getStart();
int end = sh.getEnd();
for (Key k : keys)
{
int keyStart = keys.getStart();
int keyEnd = keys.getEnd();

KStart = computeKStart(keyStart,keyEnd, start,end) // make it return -1 -1 if doesnt come within the shard scope
KEnd = computeKEnd(keyStart,keyEnd, start,end)
if(kStart!=-1 && kEnd!=-1)
{
if (rangeStart > kStart)
{

rangeStart = kStart;
}
if(rangeEnd < kEnd)
{
rangeEnd =kEnd;
}

}
}
if(rangeStart!=Integer.MAX_VALUE || rangeEnd != Integer.MIN_VALUE) //Atleast one  key comes in this category

}
}

int computeKStart (int keyStart, int keyEnd, int shardStart, int shardEnd)  // if key starts before shard start and covers shards part then return start as shard start
{
if(keyStart < shardStart && keyEnd >=shardStart)
return shardStart;
if(keyStart < shardStart && keyEnd <shardStart)
return -1;
if(keyStart >=shardStart && keyStart <=shardEnd)
return keyStart;
if(keyStart >shardStart && keyStart >shardEnd)
return -1;
}
int computeKEnd (int keyStart, int keyEnd, int shardStart, int shardEnd)  // if key starts before shard start and covers shards part then return start as shard start
{
if(keyEnd > shardEnd && keyStart < shardEnd)
return shardEnd;
if(keyEnd > shardEnd && keyStart >=shardEnd)
return -1;
if(keyEnd <=shardEnd && keyEnd >shardStart)
return keyEnd;
if(keyEnd <shardStart && keyEnd <shardStart)
return -1;
}``````

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

T:O(s+k), S:O(s)

``````class Interval:
def __init__(self, start, end):
self.start, self.end = start, end

class Solution(object):
def sol(self, shards, keys):
if not shards or not keys:
return []
i, j, ret = 0, 0, [None] * len(shards)
while i < len(shards) and j < len(keys):
sh = shards[i]
while j < len(keys):
k = keys[j]
if self.intersect(sh, k):
if not ret[i]:
ret[i] = Interval(max(sh.start, k.start), min(sh.end, k.end))
else:
ret[i].start = max(min(ret[i].start, k.start), sh.start)
ret[i].end = min(max(ret[i].end, k.end), sh.end)
if k.end > sh.end:
i += 1
break
else:
j += 1
else:
if k.end <= sh.start:
j += 1
else:
i += 1
break
return [x for x in ret if x]

def intersect(self, sh, k):
return (k.end <= sh.end and k.end > sh.start) or \
(k.end >= sh.end and k.start < sh.end)

if __name__ == "__main__":
sh1 = Interval(1, 9)
sh2 = Interval(12, 59)
sh3 = Interval(100, 999)
k1 = Interval(2,3)
k2 = Interval(6,8)
k3 = Interval(11,20)
k4 = Interval(200,220)
for i in Solution().sol([sh1,sh2,sh3],[k1,k2,k3,k4]):
print([i.start, i.end])
for i in Solution().sol([sh1,sh2,sh3],[Interval(1,1000)]):
print([i.start, i.end])
for i in Solution().sol([sh1,sh2,sh3],[Interval(4,16), Interval(59,100)]):
print([i.start, i.end])``````

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

If you can use features of java (and it seems so by the way the question was asked)

``````public class Ranges {

static class Range {
public int min;
public int max;
public Range(int min, int max) {
this.min = min;
this.max = max;
}
}

public static List<Range> getRanges(List<Range> shards, List<Range> keys) {

List<Range> ranges = new ArrayList<Range>();

Iterator<Range> shardIterator = shards.iterator();
Iterator<Range> keyIterator = keys.iterator();

Range curKey = keyIterator.next();
Range curShard = shardIterator.next();
Range curRange = new Range(curKey.min, curKey.max);
do {
if(curKey.max < curShard.max) {
curRange.max = curKey.max;
curKey = keyIterator.next();
}
if (curKey.max >= curShard.max) {
curShard = shardIterator.next();
curRange = new Range(curKey.min, curKey.max);
}
} while (shardIterator.hasNext() && keyIterator.hasNext());

return ranges;

}

}``````

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

Even shorter:

``````public class Ranges {

static class Range {
public int min;
public int max;
public Range(int min, int max) {
this.min = min;
this.max = max;
}
}

public static List<Range> getRanges(List<Range> shards, List<Range> keys) {

List<Range> ranges = new ArrayList<Range>();

Iterator<Range> keyIterator = keys.iterator();

Range curKey = keyIterator.next();
for (Range shard: shards) {
Range r = new Range(curKey.min, curKey.max);
while(curKey.max < shard.max && keyIterator.hasNext()) {
if (r.max < curKey.max) {
r.max = curKey.max;
}
curKey = keyIterator.next();
}
}

return ranges;

}
}``````

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

For each shard, try to merge list of Keys sequentially.
Boundary of each range (Start-End) will be:

Start - Max (shard.start, key.start)
End - Min (shard.end, key.end)

Start 2 iterators i for Shards and j for keys.
If current shard i contains key advance j
else merge last boundary for shard and key and advance i, advance j if key intersects with newly created range.

``````public static List<Range> getRanges(List<Shard> shards, List<Key> keys) {
List<Range> r = new ArrayList<>();
Range range = null;
int i = 0;
int j = 0;
Shard shard = null;
Key key = null;

while (i < shards.size() && j < keys.size()) {
shard = shards.get(i);

// set start of new Range
if (range == null) {
range = new Range();
range.i = Math.max(shard.i, keys.get(j).i);
}

// check for each key if it is part of range
while(j < keys.size()) {
key = keys.get(j);
// if key fits in shard
if (shard.i <= key.i && shard.j >= key.j) {
j++;
} else if (shard.j < key.i) {
range.j = j > 0 ? Math.min(keys.get(j - 1).j, shard.j) : shard.j;
i++;
range = null;
break;
} else if (shard.j > key.i && shard.j < key.j) {
i++;
j++;
break;
} else {
j++;
}
}
}

// set last Range End
if (i < shards.size() && range.j == 0 && j > 0) {
range.j = Math.min(keys.get(j - 1).j, shard.j);
}

return r;
}``````

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

``````#include <vector>
#include <iostream>
#include <limits>
using namespace std;

class Shard{
public:
int start;
int end;
Shard(int s, int e): start(s), end(e) {}
};

class Key{
public:
int start;
int end;
Key(int s, int e): start(s), end(e) {}
};

class Range{
public:
int start;
int end;
Range(int s, int e): start(s), end(e) {}
};

vector<Range> getRanges(const vector<Shard>& shards, const vector<Key>& keys){
// error check
if (shards.size() == 0 || keys.size() == 0)
return  {};
vector<Range> rs(shards.size(), Range(numeric_limits<int>::max(),numeric_limits<int>::min()));
int index = 0;
for (auto key: keys){
bool cond = false;
while (!cond){
if (index >= shards.size()) break;
// (1,9) - > (2,3)
if (shards[index].start <= key.start && shards[index].end >= key.end){
rs[index].start = min(rs[index].start,key.start);
rs[index].end = max(rs[index].end,key.end);
cond = true;
}
// (12,30) -> 11,25 = (12,25)
else if (shards[index].start > key.start && shards[index].start<key.end && shards[index].end>= key.end){
rs[index].start = shards[index].start;
rs[index].end = max(rs[index].end,key.end); // store max
cond = true; // good and done with this key
}
// (12,30) -> (11,300) = (12,30) && change (11,300)-> (31,300)
else if (shards[index].start>= key.start && shards[index].end < key.end){
rs[index].start = shards[index].start ; // this is the new start
rs[index].end = shards[index].end; // this is end
// now change keys statrt
key.start = shards[index].end + 1; // dont change cond because we are still not done with this
++index;
}
// (12,30) -> (15- 300) = (15,30) && change key to (31,300)
else if (shards[index].start < key.start && shards[index].end > key.start&& shards[index].end < key.end){
rs[index].start = min(rs[index].start,key.start);
rs[index].end = shards[index].end;
key.start = shards[index].end + 1; // dont change cond because we are still not done with this
++index;
}
// not in range
else if(shards[index].start > key.end)
cond = true;
else{
++index;
}
}
}
return rs;
}

int main(){
vector <Shard> shard = {Shard(1,9), Shard(12,59), Shard(100,999)};
vector<Key> keys = {Key(2,3),Key(6,8),Key(11,99),Key(69,1200)};
auto v = move (getRanges(shard,keys));
for (auto& r: v){
cout << r.start<< " "<<r.end<<endl;
}
}``````

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

``````struct Shard
{
int start;
int end;

Shard(int s, int e)
:
start(s),
end(e)
{}

Shard()
:
start(-1),
end(-1)
{
}
};

struct Key
{
int start;
int end;

Key(int s, int e)
:
start(s),
end(e)
{}

Key()
:
start(-1),
end(-1)
{
}
};

struct Range
{
int start;
int end;
Shard *S;

Range(int s, int e,Shard *sh)
:
start(s),
end(e),
S(sh)
{
}

Range()
:
start(-1),
end(-1),
S(NULL)
{
}
};

vector<Range> GetRanges(vector<Shard> &Shards, vector<Key> &Keys)
{
sort(Shards.begin(), Shards.end(), [](const Shard &S1, const Shard &S2)->bool
{
return S1.start < S2.start || (S1.start == S2.start && S1.end < S2.end);
});

sort(Keys.begin(), Keys.end(), [](const Key &S1, const Key &S2)->bool
{
return S1.start < S2.start || (S1.start == S2.start && S1.end < S2.end);
});

vector<Range> Result;

int SP = 0;
int KP = 0;

while (SP < Shards.size() && KP < Keys.size())
{
Key &K1 = Keys[KP];
Shard &S1 = Shards[SP];

if (K1.end < S1.start)
{
continue;
}

if (S1.end < K1.start)
{
SP++;
continue;
}

//overlap

Range R1(max(S1.start, K1.start), min(S1.end, K1.end), &S1);

if (Result.empty() || (R1.S != Result.back().S))
{
Result.push_back(R1);
}
else
{
Result.back().end = max(Result.back().end, R1.end);
}

KP++;
}

return (Result);
}

int main()
{
vector<Shard> S;
S.push_back(Shard(1, 9));
S.push_back(Shard(12, 59));
S.push_back(Shard(100, 999));

vector<Key> K;
K.push_back(Key(2, 3));
K.push_back(Key(6, 8));
K.push_back(Key(11, 20));
K.push_back(Key(200, 220));

vector<Range> Res =
GetRanges(S, K);

for (auto &R : Res)
{
cout << R.start << "," << R.end << endl;
}

return (0);
}``````

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

``````import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
*/
public class GetRanges {

static class Shard {
int start;
int end;

public Shard(int start, int end) {
this.start = start;
this.end = end;
}
}

static class Key {
int start;
int end;

public Key(int start, int end) {
this.start = start;
this.end = end;
}
}

static class Range {
int start;
int end;

public Range(int start, int end) {
this.start = start;
this.end = end;
}
}

static List<Range> getRanges(List<Shard> shards, List<Key> keys) {
int i = 0;
Key curKey;
for (Shard shard : shards) {
if (i >= keys.size()) {
break;
}
curKey = keys.get(i);
Integer rangeStart = null, rangeEnd = null;
while (overlapping(shard, curKey)) {
if (rangeStart == null) {
rangeStart = Math.max(shard.start, curKey.start);
}
rangeEnd = Math.min(shard.end, curKey.end);
if (curKey.end < shard.end) {
// another key potentially overlaps with shard
i++;
if (i < keys.size()) {
curKey = keys.get(i);
} else {
break;
}
} else {
break;
}
}
if (rangeStart != null) {
}
}
return result;
}

private static boolean overlapping(Shard shard, Key curKey) {
return (curKey.start >= shard.start && curKey.start < shard.end) || (curKey.end > shard.start && curKey.end <= shard.end);
}

public static void main(String[] args) {
Shard shard1 = new Shard(1, 9);
Shard shard2 = new Shard(12, 59);
Shard shard3 = new Shard(100, 999);
System.out.println(shards);

Key key1 = new Key(2, 3);
Key key2 = new Key(6, 8);
Key key3 = new Key(11, 20);
Key key4 = new Key(200, 220);
List<Key> keys = new ArrayList<Key>();

List<Range> ranges = getRanges(shards, keys);
for (Range range : ranges) {
System.out.println(range.start + "," + range.end);
}
}
}``````

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

What is a shard? and a range?

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

1) Sort all shards and keys
2) If key.x > shard.y shard++
3) else key++

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

O(s+k), where s is number of shards, k number of keys.
1) Iterate over the list of Shard
2) For current shard, iterate over List of Key until currentKey.start < currentShard.end

``````public List<Range> getRanges(List<Shard> shards, List<Key> keys){
List<Range> ranges = new ArrayList<>();
int shardP = 0;
int keyP = 0;

while(shardP < shards.size()){
Shard shard = shards.get(shardP);
Key key = keys.get(keyP);

while(keyP < keys.size() && keys.get(keyP).start < shard.end ){
keyP++;
}
int rangeEnd = Math.min(keys.get(keyP-1).end, shard.end);
int rangeStart = Math.max(key.start, shard.start);

Range range = new Range(rangeStart, rangeEnd);

shardP++;
}

return ranges;
}``````

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

Hi. Are the shards and keys sorted?

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.

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

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