CareerCup

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[100];
        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);
    }
}

#include <iostream>
#include <set>

using std::set;

class Pavement
{

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

public:
    const float pavementLength;
    const float raindropRadius;

    Pavement( float length = 1.0f, float raindropDiameter = 0.01f )
        : pavementLength( length ),
          raindropRadius( raindropDiameter / 2.0f ),
          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() )
        {
            if( *leftElt + raindropRadius < *rightElt - raindropRadius )
            {
                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;
}

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 [1].

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 ){
       sorted_slices.add(i, new_slice )
       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)
       //thread().sleep(10)
       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.

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

function addRaindrop(sidewalk, raindrop) {

	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][1] && raindrop >= zones[i][0]) ||
			(raindrop + 1 <= zones[i][1] && raindrop + 1 >= zones[i][0])) {
			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][0]);
			maxRight = Math.max(maxRight, zones[i][1]);
		} 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)