Google Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
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
rangeList.add(new Range(rangeStart,rangeEnd))
}
}
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;
}
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])
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);
ranges.add(curRange);
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);
ranges.add(curRange);
}
} while (shardIterator.hasNext() && keyIterator.hasNext());
return ranges;
}
}
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();
}
ranges.add(r);
}
return ranges;
}
}
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;
r.add(range);
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);
r.add(range);
}
return r;
}
#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;
}
}
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);
}
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
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) {
List<Range> result = new LinkedList<Range>();
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) {
result.add(new Range(rangeStart, rangeEnd));
}
}
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);
List<Shard> shards = new LinkedList<Shard>();
Collections.addAll(shards, shard1, shard2, shard3);
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>();
Collections.addAll(keys, key1, key2, key3, key4);
List<Range> ranges = getRanges(shards, keys);
for (Range range : ranges) {
System.out.println(range.start + "," + range.end);
}
}
}
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);
ranges.add(range);
shardP++;
}
return ranges;
}
can anyone explain the algo or logic behind solution of this problem
- Anonymous September 25, 2016