## Google Interview Question for Software Engineers

• 3

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
5
of 7 vote

Looking for interview experience sharing and coaching?
Visit A++ Coding Bootcamp at aonecode.com.

Given by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greedy and other advanced algo problems),
and mock interviews.

Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.

Feel free to email us aonecoding@gmail.com with any questions. Thanks!

Simulating rain
Break down the 1 meter walkway to 100 centimeters. Originally the whole centimeter is dry
so left = 0, right=0.01(meter); When the rain drop falls between on centimeter i (covers 0.4 centimeters of i)and centimeter i+1( 0.6 centimeters of i + 1), push the right boundary of centimeter[i] to the left by centimeter[i].right - 0.004. Same thing push the left boundary of centimeter[i] + 1 to 0.006.
Whenever a centimeter gets to left >= right, increment the fully wet centimeter count (wetCnt) by 1. When wetCnt hits 100, the whole meter is covered in rain.

``````public class RainDrop {

static class Interval {
double left = 0, right = 0.01;
boolean isWet() {
return left >= right;
}
}

public static void main(String[] args) {
simulateRainDrop();
}

public static void simulateRainDrop() {

Interval[] sidewalk = new Interval;
for (int i = 0; i < 100; i++) {
sidewalk[i] = new Interval();
}
int cnt = 0, wetCnt = 0;
while (wetCnt < 100) {
++cnt;
double p = Math.random();
double left = p - 0.005;
double right = p + 0.005;
if (left >= 0) {
int idx = (int) (left / 0.01);
if (!sidewalk[idx].isWet()) {
double iright = left - idx * 0.01;  //update seg[i].right with left bound of rain
if (iright < sidewalk[idx].right) {
sidewalk[idx].right = iright;
if (sidewalk[idx].isWet())
++wetCnt;
}
}
}
if (right <= 1) {
int idx = (int) (right / 0.01);
if (!sidewalk[idx].isWet()) {
double ileft = right - idx * 0.01;//update seg[i + 1].left with right bound of rain
if (ileft > sidewalk[idx].left) {
sidewalk[idx].left = ileft;
if (sidewalk[idx].isWet())
++wetCnt;
}
}
}
}
System.out.println(cnt);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <set>

using std::set;

class Pavement
{

private:
set< float > impl;
unsigned int numRaindrops;

public:
const float pavementLength;

Pavement( float length = 1.0f, float raindropDiameter = 0.01f )
: pavementLength( length ),
numRaindrops( 0u )
{
impl = set< float >();
}

void SetRaindrop( float newVal )
{
impl.insert( newVal );
numRaindrops += 1u;
}

bool GetIsComplete() const
{
if( numRaindrops == 0 )
{
return false;
}
if( numRaindrops == 1 )
{
return( pavementLength < raindropRadius * 2.0f );
}

set< float >::const_iterator rightElt = impl.begin();
set< float >::const_iterator leftElt = rightElt++;      //< Note postfix notation very important!

while( rightElt != impl.end() )
{
{
return false;
}

++leftElt;
++rightElt;
}

return( ( *leftElt + raindropRadius ) > pavementLength );
}

unsigned int GetNumRaindrops() const
{
return numRaindrops;
}
};

int main()
{
// Seed our random number generator.
srand( time( NULL ) );

const float PAVEMENT_SIZE = 1.0f;

Pavement pavement( PAVEMENT_SIZE );
const float RAND_MAX_AS_FLOAT = (float)RAND_MAX;

// First seed the pavement with the absolute minimum number of raindrops; no need to check if it works before then.
int minNumRaindrops = (int)( pavement.pavementLength / ( pavement.raindropRadius * 2.0f ) );
for( int i = 0; i < minNumRaindrops; ++i )
{
float normalizedRand = (float)( rand() ) / RAND_MAX_AS_FLOAT * PAVEMENT_SIZE;
pavement.SetRaindrop( normalizedRand );
}

// Now we're into good ol' O( n log n ), with serious fragmentation implications.
while( !pavement.GetIsComplete() )
{
float normalizedRand = (float)( rand() ) / RAND_MAX_AS_FLOAT * PAVEMENT_SIZE;
pavement.SetRaindrop( normalizedRand );
}

std::cout << "Operation complete! It took " << pavement.GetNumRaindrops() << " raindrops to fill the pavement!";

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I was thinking about it for a long time. This is a classic case of discretisation making itself away into scale variance. What does that mean? Here is how it works out.
Here, I present two ways to solve the same problem .

Continuous Algorithm.

1. Make uniform distribution rain falling as in a point between [0,1].
2. Widen the point, to create an interval to [p - 0.005, p + 0.005 ] to make the drop fall.
3. This way, we are creating intervals, and they are kept sorted - and then they are merged.
4. Continue till the intervals merged into a some intervals such that the total length is very close
to 1.000.
5. All while count the no of rain drops ( intervals ) fell.
---> Observation, there is a clear mode near about 500 to 800.

Discrete Algorithm.

1. Create pixelated buckets with scale number of pixels per rain drop.
2. That makes the length L ( 1 m ) into 100 * scale.
3. Let the rain drop uniformly between [ 0, 99*scale + 1] , and then
4. Once the rain drop falls, in position pos, mark the buckets [pos, pos + scale) filled.
5. Check if all buckets are marked. That, gives you -- whole road is wet.
Now, this is where fractal nature of world comes in. This simulation discretised the world, and thus, does not have a fixed mean, with scale, the mean increases.
Here are the codes.

This is for the discrete simulation. It is amazing how simply you can think about it after pixelation.

``````// This is discrete simulate
def discrete_simulate(){
scale = 10
count = 0
s = set()
max = 100 * scale
span = max - scale + 1
while ( size(s) != max ){
pos = random(span)
for ( [pos:pos + scale ] ){ s+= \$ }
count += 1
}
count // return this
}``````

Here is *real* continuous one. Interestingly, these two distributions of number of rain drops will not match.

``````def merge2(slice1, slice2 ){
if ( slice1.x2 < slice2.x1 || slice2.x2 < slice1.x1 ) {
return null // not overlap
}
if ( slice1.x1 <= slice2.x1 ){
#(min,max) = minmax( slice1.x2 , slice2.x2  )
return { 'x1' : slice1.x1 , 'x2' : max }
} else {
#(min,max) = minmax( slice1.x2 , slice2.x2 )
return { 'x1' : slice2.x1 , 'x2' : max }
}
}
def merge_into( new_slice, sorted_slices ){
if ( empty(sorted_slices) ){
sorted_slices += new_slice
return sorted_slices
}
// from left
i = index ( sorted_slices ) where { new_slice.x1 <= \$.o.x2 }
if ( i < 0 ){
sorted_slices += new_slice
return sorted_slices
}
slice = merge2 ( new_slice, sorted_slices[i] )
if ( slice == null ){
return sorted_slices
}
sorted_slices[i] = slice
if ( i + 1 < size(sorted_slices) ){
slice = merge2 ( sorted_slices[i], sorted_slices[i+1])
if ( slice != null ){
sorted_slices[i] = slice
sorted_slices.remove(i+1)
}
}
sorted_slices
}

def simulate(){
sorted_slices = list()
tot = 0.0
count = 0
while ( 1.0 - tot > 0.0001 ){
pos = random(0.0)
x1 = pos - 0.005
x1 = x1 < 0.0 ? 0.0 : x1
x2 = pos + 0.005
x2 = x2 > 1.0 ? 1.0 : x2
slice = { 'x1' : x1, 'x2' : x2 }
sorted_slices = merge_into( slice, sorted_slices )
//println(slice)
//println(sorted_slices)
tot = sum( sorted_slices ) as {  \$.o.x2 - \$.o.x1 }
count += 1
//printf('>>>>> Count : %d Total %f %n', count, tot)
}
//println( sorted_slices )
return count // well
}``````

This is a pretty non trivial problem, and I see why PHD folks were asked this. The nature of simulation is, here, getting fractalised.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Not sure if the code is correct but the idea is maintain an array of contiguous zones and check if we reached the limits.

``````function initializeSidewalk() {
return {
zones: [],
left: false,
right: false,
};
}

if (raindrop + 1 < 0 || raindrop > 100) {
return;
}

const zones = sidewalk.zones.splice(0, sidewalk.zones.length);
const parent = zones.map((_, i) => i);

function find(i) {
while(i !== parent[i]) {
const prev = i;
i = parent[i];
parent[prev] = i;
}
return i;
}

function union(i, j) {
return parent[find(i)] = find(j);
}
zones.push([raindrop, raindrop + 1]);
parent.push(parent.length);

for (let i = 0; i < zones.length - 1; i++) {
if ((raindrop <= zones[i] && raindrop >= zones[i]) ||
(raindrop + 1 <= zones[i] && raindrop + 1 >= zones[i])) {
union(parent.length - 1, i);
}
}

let minLeft = 100;
let maxRight = 0;
for (let i = 0; i < zones.length; i++) {
if (find(parent.length - 1) === find(i)) {
minLeft = Math.min(minLeft, zones[i]);
maxRight = Math.max(maxRight, zones[i]);
} else {
sidewalk.zones.push(zones[i]);
}
}
sidewalk.zones.push([minLeft, maxRight]);

if (raindrop <= 0 && raindrop + 1 >= 0) {
sidewalk.left = true;
}

if (raindrop <= 100 && raindrop + 1 >= 100) {
sidewalk.right = true;
}
}

function isCompletelyWet(sidewalk) {
return sidewalk.left && sidewalk.right && sidewalk.zones.length == 1;
}``````

// Insertion: O(1) because the maximum number of zones is constant.
// Query: O(1)
// Memory: O(1)

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.

### 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.