Google Interview Question Software Engineer / Developers
Country: United States
In #1, If you are sorting the whole list (based on A) anyway, then it how is it lazy? Can you please elaborate what you had in mind?
It's only lazy with respect to B values. Yes, of course you'd have to sort the As, which is at least 50% of the work. I didn't mean to overstate the advantage.
I did not see the benefit of 1> yet. I can see that if the countable sort could be done in A and B separately, we would choose 3>, which may have O((N+Ka) + (N+Kb)) time efficiency, but you got extra space for maximum(Ka, Kb). If Ka or Kb is too big, or the A or B only support comparison sort, 2> is better, which has complexity O(NlogN), may support in space sorting, no extra space requirement.
@chenic626 All three of these options can be done in constant space and NlogN time. I think option 2 is gonna make the most sense for most people, and most languages have a fairly idiomatic way to sort with a compare function or key function that looks at two fields. I don't understand your Ka/Kb notation, so maybe I'm missing something.
Maybe this (in python):
def two_func_sort(collection, cmp1, cmp2):
first_sorted = list(sorted(collection, cmp1))
ret = []
prev = first_sorted[0]
aux = [prev]
for val in first_sorted[1:]:
if cmp1(prev, val) == 0:
aux.append(val)
else:
ret.extend(sorted(aux, cmp2))
aux = [val]
prev = val
ret.extend(sorted(aux, cmp2))
return ret
Even a more elegant solution:
def two_func_sort2(collection, cmp1, cmp2):
def two_cmp(x, y):
res1 = cmp1(x, y)
if res1 != 0:
return res1
return cmp2(x, y)
return sorted(collection, two_cmp)
Python sort () and sorted() have supported a key argument for a while, which allows you to specify a key for sorting. Python also sorts tuples lexographically. So, it's easy to compose a key function from two other key functions:
def sorted2(lst, key1, key2):
def f(v): return (key1(v), key2(v))
return sorted(lst, key=f)
I think this is simple。 Why do we need to consider stable sort or blablabla...
import java.util.Arrays;
class Test implements Comparable<Test> {
String value1;
String value2;
public Test(String value1, String value2) {
super();
this.value1 = value1;
this.value2 = value2;
}
@Override
public int compareTo(Test o) {
if (this.value1.compareTo(o.value1) == 0) {
return this.value2.compareTo(o.value2);
} else {
return this.value1.compareTo(o.value1);
}
}
@Override
public String toString() {
return "value1: " + value1 + " value2:" + value2;
}
}
public class SecondarySorting {
public static void main(String[] args) {
Test[] tests = new Test[10];
tests[0] = new Test("a", "b");
tests[1] = new Test("a", "a");
tests[2] = new Test("a", "b");
tests[3] = new Test("d", "c");
tests[4] = new Test("d", "d");
tests[5] = new Test("d", "a");
tests[6] = new Test("b", "a");
tests[7] = new Test("b", "e");
tests[8] = new Test("c", "a");
tests[9] = new Test("c", "r");
Arrays.sort(tests);
for (Test t : tests) {
System.out.println(t);
}
}
}
Upvoted. The way the question is question is phrased, I think the interviewer is looking for an answer like yours. If I were the interviewer, my follow up question would be something like this: "Now suppose you're given a very large dataset that's already sorted by field A, but now you want to use B as a tiebreaker..."
If you have a list sorted by A, then iterate through the list and find runs of common A values and then sort them in place by B. The only problem here is that some languages might not have a handy library method that can sort a subrange of a list. If that's the case, I would just code up my own version of in-place quicksort that takes a list and a range.
You mean let's say given:
{(4, 2), (3, 3), (3, 2)}
sort by using A without using B gives you:
{(3, 3), (3,2), (4,2)}
and using A and B gives you:
{(3,2), (3, 3), (4, 2)}
package com;
import java.util.Comparator;
import java.util.List;
public class MultiSort<T> implements Comparator<T>{
private List<Comparator<T>> comparators;
public MultiSort(List<Comparator<T>> comparators){
this.comparators = comparators;
}
@Override
public int compare(T t1, T t2) {
int i=0;
int r=0;
Comparator<T> c;
while(i<comparators.size() && r==0){
c = comparators.get(i++);
r = c.compare(t1, t2);
}
return r;
}
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
class MultiSort<T> implements Comparator<Item<T>>{
private List<Comparator<Item<T>>> comparators;
public MultiSort(List<Comparator<Item<T>>> comparators){
this.comparators = comparators;
}
@Override
public int compare(Item<T> t1, Item<T> t2) {
// Compare surnames
boolean ret = t1.a.equals( t2.a );
if( ret == true ){ //Compare givennames if surnames are the same
ret = t1.b.equals( t2.b );
}
if(ret)
return 0;
else
return -1;
}
}
class Item<T>
{
T a;
T b;
public Item(T a, T b)
{
this.a = a;
this.b = b;
}
public String toString()
{
return "(" + a + ", " + b + ")";
}
}
public class Subsorting {
public static void main(String[] args)
{
//List<Item<Integer>> list = new ArrayList<Item<Integer>>();//{(4, 2), (3, 3), (3, 2)}
Item<Integer> item1 = new Item<Integer> (4, 2);
Item<Integer> item2 = new Item<Integer> (3, 3);
Item<Integer> item3 = new Item<Integer> (3, 2);
//list.add(item1);
//list.add(item2);
//list.add(item3);
Item[] items = {item1, item2, item3};
Arrays.sort(items, new MultiSort(list));
for(Item<Integer> item : items)
System.out.println(item.toString());
}
}
Three approaches come to mind.
- showell30@yahoo.com February 23, 20131) Sort on A, then scan the list for runs of elements with the same value for A, then sort each sublist for field B.
2) Sort on A/B simultaneously by using a compare function or key function that uses both fields.
3) Sort the list on B, then stable-sort the list on A.
A nice feature of approach #1 is that you can do it lazily, i.e. only sort the sublists when the second field is queried.