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

- Anonymous September 25, 2016 | Flag Reply
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
 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;
}

- LetsCode792 September 21, 2016 | Flag Reply
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])

- akak18183 September 22, 2016 | Flag Reply
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);
        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;

    }

}

- JohnnyUtah September 22, 2016 | Flag Reply
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();
            }
            ranges.add(r);
        }

        return ranges;

    }
}

- JohnnyUtah September 22, 2016 | Flag Reply
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;
				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;
}

- guilhebl September 22, 2016 | Flag Reply
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;
	}
}

- shahzaib1019 September 22, 2016 | Flag Reply
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);
}

- Guy September 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- vmahajanin September 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What is a shard? and a range?

- K October 05, 2016 | Flag Reply
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++

- kevseb1993 October 17, 2016 | Flag Reply
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);
            ranges.add(range);

            shardP++;
        }

        return ranges;
    }

- jsayyy November 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Hi. Are the shards and keys sorted?

- shahzaib1019 September 22, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

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.

Learn More

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.

Learn More