Google Interview Question Software Engineers
Country: Switzerland
Interview Type: Phone Interview
Complexity = O (n log n) due to the sorting of the stream
memory = n
public static void main(String args[]) {
// pair = id, weight
Pair itemOne[] = { new Pair<Integer, Integer>(2, 5), new Pair<Integer, Integer>(5, 10), new Pair<Integer, Integer>(1, 10), new Pair<Integer, Integer>(4, 12) };
Pair itemTwo[] = { new Pair<Integer, Integer>(3, 7), new Pair<Integer, Integer>(2, 10), new Pair<Integer, Integer>(1, 10) };
Pair<Integer,Integer> merged[]=mergeById(itemOne,itemTwo);
Arrays.stream(merged).forEach(System.out::println);
}
@SuppressWarnings("unchecked")
public static Pair<Integer,Integer>[] mergeById(Pair<Integer, Integer>[] first, Pair<Integer, Integer>[] second) {
Map<Integer, Integer> reduced = Stream.concat(Arrays.stream(first), Arrays.stream(second))
.collect(Collectors.groupingBy(Pair::getKey,
Collectors.reducing(0, Pair::getValue, Integer::sum)));
Pair<Integer,Integer>[] pairs=(Pair<Integer, Integer>[])reduced.entrySet()
.stream()
.map(entry -> new Pair<Integer,Integer>(entry.getKey(),entry.getValue()))
.sorted((p1,p2)-> p1.getValue().compareTo(p2.getValue()))
.toArray(Pair[]::new);
return pairs;
}
public class Solution {
public Obj [] mergeObjArray(Obj [] array1, Obj [] array2) {
List<Obj> results = new ArrayList<>();
Arrays.sort(array1, new SortById());
Arrays.sort(array2, new SortById());
int index1 = 0;
int index2 = 0;
int index = 0;
while (index1 < array1.length && index2 < array2.length) {
if (array1[index1].id == array2[index2].id) {
results.add(new Obj(array1[index1].id, array1[index1].weight + array2[index2].weight));
index1++;
index2++;
} else if (array1[index1].id < array2[index2].id) {
results.add(new Obj(array1[index1].id, array1[index1].weight));
index1++;
} else {
results.add(new Obj(array2[index2].id, array2[index2].weight));
index2++;
}
}
while (index1 < array1.length) {
results.add(new Obj(array1[index1].id, array1[index1].weight));
index1++;
}
while (index2 < array2.length) {
results.add(new Obj(array2[index2].id, array2[index2].weight));
index2++;
}
Arrays.sort(array1, new SortByWeight());
Arrays.sort(array2, new SortByWeight());
Obj [] resultArray = (Obj [])results.toArray();
Arrays.sort(resultArray, new SortByWeight());
return resultArray;
}
}
class Obj {
final int id;
int weight;
public Obj(int id, int weight) {
this.id = id;
this.weight = weight;
}
}
class SortById implements Comparator {
@Override
public int compare(Object o1, Object o2) {
return Integer.compare(((Obj) o1).id, ((Obj) o2).id);
}
}
class SortByWeight implements Comparator {
@Override
public int compare(Object o1, Object o2) {
return Integer.compare(((Obj) o1).weight, ((Obj) o2).weight);
}
}
Algorithm:
1)First scan both arrays to create a hashmap to hold values of id and weight. This will allow us to get final weight of every id. ~o(n) time
2) Now create a new array that is equal to size of this hashmap. Construct this array from the elements of hashmap
3) Finally compare array elements based on weight to get final result. (o(n lg n))
4) Total time complexity is o(n)+ o(n lg n) and ~o(n) space
public class ObjectSort {
public static void main(String[] args) {
Item[] arr1 = new Item[3];
//first create some items for first array
Item i1 = new Item(1,10);
Item i2 = new Item(2,20);
Item i3 = new Item(3,30);
arr1[0] = i1;
arr1[1] = i2;
arr1[2] = i3;
//create items for second array
Item[] arr2 = new Item[3];
Item i11 = new Item(2,10);
Item i12 = new Item(3,20);
Item i13 = new Item(4,30);
arr2[0] = i11;
arr2[1] = i12;
arr2[2] = i13;
Item[] sortedArray = sortObjectArrays(arr1,arr2);
for(int i = 0 ; i<sortedArray.length;i++){
System.out.println("Id:"+sortedArray[i].id+" and weight:"+sortedArray[i].weight);
}
}
private static Item[] sortObjectArrays(Item[] arr1, Item[] arr2) {
// step 1: create an hashmap with id to weight values :o(n)
HashMap<Integer,Integer> IdToWeightMap = getIdToWeightMap(arr1, arr2);
//step 2: Now, we have all the ids have their final weight, we will create array from hashMap
Item[] arr = new Item[IdToWeightMap.size()];
int count = 0;
//create array from map
for(Integer i : IdToWeightMap.keySet()){
arr[count] = new Item(i,IdToWeightMap.get(i));
count++;
}
//sort this array based on weights and return
//uses lambda expression to compare 2objects.
Arrays.sort(arr,(a,b)->((Integer)a.weight).compareTo((Integer)b.weight));
return arr;
}
public static HashMap<Integer,Integer> getIdToWeightMap(Item[] arr1, Item[] arr2){
HashMap<Integer,Integer> IdToWeightMap = new HashMap<>();
//scan first array
for(int i = 0 ; i<arr1.length;i++){
if(IdToWeightMap.containsKey(arr1[i].id)){
IdToWeightMap.put(arr1[i].id,IdToWeightMap.get(arr1[i].id)+arr1[i].weight);
}else{
IdToWeightMap.put(arr1[i].id, arr1[i].weight);
}
}
//scan second array
for(int i = 0 ; i<arr2.length;i++){
if(IdToWeightMap.containsKey(arr2[i].id)){
IdToWeightMap.put(arr2[i].id,IdToWeightMap.get(arr2[i].id)+arr2[i].weight);
}else{
IdToWeightMap.put(arr2[i].id, arr2[i].weight);
}
}
return IdToWeightMap;
}
public static class Item{
public int id;
public int weight;
public Item(int id,int weight){
this.id = id;
this.weight = weight;
}
}
}
/*
1. Copy the two arrays into one (v3)
2. Sort it according to it's Id's
3. Remove duplicates
4. Resize
5. Sort again according to weights
note: the fact the input is sorted was not used, there might be a better solution I couldn't spot
*/
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
struct Item
{
int id;
int weight;
};
vector<Item> Merge(const vector<Item>& v1, const vector<Item>& v2)
{
vector<Item> v3(v1.size() + v2.size());
copy(v2.begin(), v2.end(), copy(v1.begin(), v1.end(), v3.begin()));
sort(v3.begin(), v3.end(), [](Item& a, Item&b) { return a.id < b.id; });
int j = 0;
for (int i = 1; i < v3.size(); ++i)
{
if (v3[j].id == v3[i].id)
{
v3[j].weight += v3[i].weight;
}
else
{
v3[++j] = v3[i];
}
}
v3.resize(j+1);
sort(v3.begin(), v3.end(), [](Item& a, Item& b) {return a.weight < b.weight; });
return v3;
}
int main()
{
vector<Item> v1{ {1,2}, {2,3}, {4, 8}, {-1, 2} };
vector<Item> v2{ {3,1}, {2,7}, {9, 2}, {-1, 1}, {-1,1} };
auto res = Merge(v1, v2);
for_each(res.begin(), res.end(), [](Item& a) { cout << "item id: " << a.id << " weight " << a.weight << endl; });
}
// the class with id and weight
class SomeObj {
int id;
int weight;
SomeObj(int id, int weight) {
this.id = id;
this.weight = weight;
}
}
// the two arrays
SomeObj[] array1 = new SomeObj[] { ... };
SomeObj[] array2 = new SomeObj[] { ... };
SomeObj[] merge(SomeObj[] a1, SomeObj[] a2) {
// maps id to obj
Map<Integer, SomeObj> map = new HashMap<>();
// add objects in a1 to map
for(SomeObj o: a1) {
SomeObj entry = map.get(o.id);
if (entry == null) {
entry = new SomeObj(o.id, o.weight);
map.put(o.id, entry);
}
else {
// if same id is found, update its weight
entry.weight += o.weight;
}
}
// same for a2
for(SomeObj o: a2) {
SomeObj entry = map.get(o.id);
if (entry == null) {
entry = new SomeObj(o.id, o.weight);
map.put(o.id, entry);
}
else {
entry.weight += o.weight;
}
}
// convert the set of values to array and sort it based on weight
SomeObj[] result = new SomeObj[map.size()];
Arrays.sort(map.values().toArray(result), new Comp());
}
class Comp<SomeObj> implements Comparator<SomeObj> {
int compare(SomeObj o1, SomObj o2) {
return o1.weight - o2.weight;
}
}
public static void main(String[] args) {
List<Obj> list1 = new ArrayList<>();
list1.add(new Obj(1,20));
list1.add( new Obj(2,25));
list1.add(new Obj(4,30));
List<Obj> list2 = new ArrayList<>();
list2.add(new Obj(1,10));
list2.add( new Obj(2,5));
list2.add(new Obj(3,15));
Comparator<Obj> sortByWeight = new SortByWeight();
List<Obj> list3 = Stream.concat(list1.stream(), list2.stream())
.collect(Collectors.groupingBy(e -> e.getId(), Collectors.summingInt(e -> e.getWeight())))
.entrySet()
.stream()
.map(e -> new Obj(e.getKey(), e.getValue()))
.sorted(sortByWeight)
.collect(Collectors.toList());
System.out.println("The consolidated, sorted list is " + list3);
}
static class SortByWeight implements Comparator <Obj> {
@Override
public int compare(Obj obj1, Obj obj2) {
return Integer.compare(obj1.getWeight(), obj2.getWeight());
}
}
import collections
import itertools
class Item(object):
def __init__(self, id, weight):
super(Item, self).__init__()
self.id = id
self.value = weight
def merge(l1, l2):
d = collections.defaultdict(int)
for item in itertools.chain(l1, l2):
d[item.id] += item.weight
res = []
for k, v in d.items():
res.append(Item(k, v))
return sorted(res, key=lambda x: x.weight)
If the two input arrays are already sorted by weight and you want the output array sorted the same way, it's just mergesort without the the recursion, and the running time is linear:
package main
import "fmt"
type elem struct {
id int
weight float32
}
var (
first []elem = []elem{
elem{1, 1.0079},
elem{2, 4.0026},
elem{3, 6.941},
elem{4, 9.0122},
elem{5, 10.811},
elem{6, 12.011},
elem{7, 14.007},
elem{8, 15.999},
}
second []elem = []elem{
elem{6, 12.012},
elem{7, 14.006},
elem{8, 16.01},
elem{9, 18.998},
elem{10, 20.180},
elem{11, 22.990},
elem{12, 24.305},
elem{13, 26.982},
elem{14, 28.086},
}
)
func main() {
fmt.Println(merge(first, second))
}
// merge
func merge(a, b []elem) []elem {
result := []elem{}
m := map[int]int{}
for len(a) > 0 && len(b) > 0 {
var e elem
if a[0].weight < b[0].weight {
e = a[0]
a = a[1:]
} else {
e = b[0]
b = b[1:]
}
result = insert(result, e, m)
}
for len(a) > 0 {
e := a[0]
a = a[1:]
result = insert(result, e, m)
}
for len(b) > 0 {
e := b[0]
b = b[1:]
result = insert(result, e, m)
}
return result
}
func insert(elems []elem, e elem, m map[int]int) []elem {
if i, ok := m[e.id]; ok {
elems[i].weight = (elems[i].weight + e.weight) / 2
} else {
m[e.id] = len(elems)
elems = append(elems, e)
}
return elems
}
Implemented Logic:
1. First create a new result array which is nothing but appending array1 to array2. O(n)
2. Sort this result object array by id. O(nlogn)
3. Iterate through result array and add the weights of the items having same Ids. O(n)
(And keep track of unique elements, overwrite repeated id. Refer code for actual implementation.)
4. Sort the result array by weight. O(nlogn)
Overall time Complexity = O(nlogn)
Space Complexity = O(n)
- settyblue July 28, 2016public class Main { public static void main(String[] args) { Item[] array1 = {new Item(2,5),new Item(5,10),new Item(1, 10), new Item(4,12)}; Item[] array2 = {new Item(3,7),new Item(2,10),new Item(1, 10)}; print(array1);print(array2); mergeAndPrint(array1,array2); } public static class Item { int id, weight; Item(int id, int weight){ this.id = id; this.weight = weight; } public String toString(){return "("+id+", "+weight+")";} } public static class compareById implements Comparator<Item>{ public int compare(Item i1, Item i2) { return i1.id - i2.id; } } public static class compareByWeight implements Comparator<Item>{ public int compare(Item i1, Item i2) { return i1.weight - i2.weight; } } public static void print(Item[] array){ System.out.println(Arrays.toString(array)); } public static void mergeAndPrint(Item[] array1, Item[] array2){ Item[] result = new Item[array1.length + array2.length]; System.arraycopy(array1, 0, result, 0, array1.length); System.arraycopy(array2, 0, result, array1.length, array2.length); Arrays.sort(result,new compareById()); int count = 0; for(int i=1; i<result.length; i++){ if(result[count].id == result[i].id){ result[count].weight += result[i].weight; }else{ count++; result[count] = result[i]; } } result = Arrays.copyOf(result, count+1); Arrays.sort(result,new compareByWeight()); print(result); } }