How to: Work at Google — Example Coding/Engineering Interview

In the following video they show you some algorithms, here is my implementation, that also compares performance.

And here is my code code:

	import java.util.Arrays;
	import java.util.HashSet;
	import java.util.Random;
	import java.util.concurrent.TimeUnit;
	/**
	*
	* @author franci
	*/
	public class WorkAtGoogleExample
	{
	static final int MAGIC = 8;
	public static void main(String[] args)
	{
	long nanos0 = 0;
	long nanos1 = 0;
	long nanos2 = 0;
	long nanos3 = 0;
	long count0 = 0;
	long count1 = 0;
	long count2 = 0;
	long count3 = 0;
	long limit = TimeUnit.SECONDS.toNanos(20);
	boolean changed = true;
	Random rand = new Random(0x123456);
	for(int i=0;changed&&i<10000;i++)
	{
	changed = false;
	int[] items0 = rand.ints(i*i).toArray();
	for(int j=0;j<items0.length;j++)
	{
	items0[j] = items0[j] % 32;
	}
	if(nanos0<limit)
	{
	long t0 = System.nanoTime();
	int[] ret0 = findRandom(items0, i);
	long t1 = System.nanoTime();
	nanos0 += (t1-t0);
	count0++;
	changed=true;
	}
	if(nanos1<limit)
	{
	long t0 = System.nanoTime();
	int[] items1 = items0.clone();
	Arrays.sort(items1);
	int[] ret1 = findSorted(items1, i);
	long t1 = System.nanoTime();
	nanos1 += (t1-t0);
	count1++;
	changed=true;
	}
	if(nanos2<limit)
	{
	long t0 = System.nanoTime();
	int[] ret2 = findTwoLoops(items0, i);
	long t1 = System.nanoTime();
	nanos2 += (t1-t0);
	count2++;
	changed=true;
	}
	long t3 = System.nanoTime();
	if(nanos2<limit)
	{
	long t0 = System.nanoTime();
	int[] items3 = items0.clone();
	Arrays.sort(items3);
	int[] ret3 = findTwoLoops(items3, i);
	long t1 = System.nanoTime();
	nanos3 += (t1-t0);
	count3++;
	changed=true;
	}
	long t4 = System.nanoTime();
	if(i%100==0)
	{
	System.out.println(i+"=>"+i*i);
	System.out.println("findRandom= "+count0+" => "+TimeUnit.NANOSECONDS.toMillis(nanos0)+" ms");
	System.out.println("findSorted= "+count1+" => "+TimeUnit.NANOSECONDS.toMillis(nanos1)+" ms");
	System.out.println("findTwoLoops= "+count2+" => "+TimeUnit.NANOSECONDS.toMillis(nanos2)+" ms");
	System.out.println("findTwoLoops+sort="+count3+" => "+TimeUnit.NANOSECONDS.toMillis(nanos3)+" ms");
	System.out.println("------------------------------------------");
	}
	}
	System.out.println("nanos0="+count0+" =>"+TimeUnit.NANOSECONDS.toMillis(nanos0)+" ms");
	System.out.println("nanos1="+count1+" =>"+TimeUnit.NANOSECONDS.toMillis(nanos1)+" ms");
	System.out.println("nanos2="+count2+" =>"+TimeUnit.NANOSECONDS.toMillis(nanos2)+" ms");
	System.out.println("nanos3="+count3+" =>"+TimeUnit.NANOSECONDS.toMillis(nanos3)+" ms");
	}
	static int[] findSorted(int[] sample, int x)
	{
	int d=0;
	int u=sample.length-1;
	while(d<u)
	{
	int dv = sample[d];
	int uv = sample[u];
	int X = dv+uv;
	if(X==x)
	{
	return new int[]{dv,uv};
	}
	if(X<x)
	{
	d++;
	}
	else
	{
	u--;
	}
	}
	return null;
	}
	static int[] findTwoLoops(int[] sample, int x)
	{
	for(int i=0;i<sample.length-1;i++)
	{
	for(int j=i+1;j<sample.length;j++)
	{
	if(sample[i]+sample[j]==x)
	{
	return new int[]{sample[i],sample[j]};
	}
	}
	}
	return null;
	}
	static int[] findRandom(int[] sample, int x)
	{
	HashSet<Integer> set = new HashSet<>();
	for(int i=0;i<sample.length;i++)
	{
	int s2nd = sample[i];
	int f1st = x-s2nd;
	if(set.contains(f1st))
	{
	return new int[]{f1st,s2nd};
	}
	set.add(s2nd);
	}
	return null;
	}
	}

view raw WorkAtGoogleExample.java hosted with ❤ by GitHub

The results are the following:

findRandom=       1409 => 20032 ms
findSorted=       1310 => 20013 ms
findTwoLoops=     216 => 20197 ms
findTwoLoops+sort=215 => 19917 ms

As you can see the best algorithm is findRandom performed 1409 times in the 20 seconds.

Happy Hacking!!!