Google Interview Question for SDE1s


Country: India
Interview Type: Written Test




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

This would be a simple iterative simulation...

public class Car{
    public static final double HANDLING_FACTOR= .8d;

    public int team;
    public double speed;
    public double nextSpeed;
    public double topSpeed;
    public double accel;
    public boolean hasNitro;
    public double positionFromEnd;
    public dounle nextPositionFromEnd;

    public Car(int i, double trackLength){
        this.team = i;
        //meters per 2 sec
        this.topSpeed = (150d + 10d * (double)i)/1.8d;
        // meters per 2 sec2
        this.acce l= 2 * (double)i;
        this.accel *= this.accel;
        this.hasNitro = true;
        this.positionFromEnd = trackLength + 200d * (double)i;
    }

    public void update(){
        this.speed = this.nextSpeed;
        this.positionFromEnd = this.nextPositionFromEnd;
    }
}

public class FinishInformation{
    public int team;
    public int finishTime;
    public double finalSpeed;

    public FinishInformation(int team, int finishTime, double finalSpeed){
        this.team = team;
        this.finishTime = finishTime;
        this.finalSpeed = finalSpeed;
    }
}

public static Collection<FinishInformation> getCompletionData(int numTeams, double trackLength){
    //initialize the teams
    ArrayList<Car> cars = new ArrayList<Car>(numTeams);
    for(int i = 0; i < numTeams; i++){
        cars.add(new Car(i, trackLength));
    }

    //initialize the output
    ArrayList<FinishInformation> results = new ArrayList<FinishInformation>();

    Comparator<Car> carSorter = new Comparator<Car>(){
        @Override
        public int compare(Car c1, Car c2){
            return c1.positionFromEnd - c2.positionFromEnd;
        }
    }

    //while there are cars still racing
    int iterations = 0;
    while(cars.size() > 0){
        //sort the list based on the positions.
        Collections.sort(cars, carSorter);
        
        //now, nearby cars are used for the Handling checks and the last car will always use nitro
        double lastNearbyCar
        for(int i = 0; i < cars.size(); i++){
            Car car = cars.get(i);
            //check for nearby-ness
            boolean notNearby = true;
            if(i > 0){
                if(Math.abs(cars.get(i-1).positionFromEnd - car.positionFromEnd) <= 10d){
                    notNearby = false;
                }
            }
            if(i < cars.size() -1){
                if(Math.abs(cars.get(i+1).positionFromEnd - car.positionFromEnd) <= 10d){
                    notNearby = false;
                }
            }

            //compute next speed
            if(notNearby){
                car.nextSpeed = car.speed + car.accel;
                if(car.nextSpeed > car.maxSpeed){
                    car.nextSpeed = car.maxSpeed;
                }
            }
            else{
                car.nextSpeed = car.speed * Car.HANDLING_FACTOR;
            }
             
            //compute next position
            car.nextPositionFromEnd -= car.nextSpeed;
        }

        //compute usage of nitro
        Car lastCar = cars.get(cars.size() -1);
        if(lastCar.hasNitro){
            lastCar.hasNitro = false;
            lastCar.nextSpeed = car.speed * 2d;
            if(lastCar.nextSpeed > lastCar.maxSpeed){
                lastCar.nextSpeed = lastCar.maxSpeed;
            }
        }

        //complete the movements
        iterations++;
        for(int i = 0; i < cars.size(); i++){
            cars.get(i).update();
        }

        //process finishers
        Car car = cars.get(0);
        while(car.positionFromEnd <= 0d){
            removeIndex++;
            results.add(new FinishInformation(car.team, iterations<<1, car.speed));
            cars.remove(0);
            car = cars.get(0);
        }
    }
    return results;
}

}

- zortlord May 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How long is the track?

- SK May 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is quite clear in the question that number of teams and track length is input to the function. So, you can take any value for input parameters.

- Nitin Gupta May 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Python,

#!/usr/bin/python

#Global Vars
teams = 10
hf = 0.8
objTeamList = []
track = 10000   #10 Km
timer = 2
usedNitro = []
completed = []

#Class Def
class Team:
        speed = 0
        distance = 0
        time = 0
        top_speed = 0
        hasNitro = 1

        def __init__(self, index):
                self.speed = 0
                self.time=0
                self.distance = 200 * (teams - index)
                self.top_speed = 150 + 10 * index
                self.accelaration = 2 * index

        def __lt__(self, team1):
                return self.distance < team1.distance

        def __str__(self):
                return "Time:[%s] Speed:[%s]" % (self.time, self.speed)

        def useNitro(self):
                if self.speed * 2 < self.top_speed:
                        self.speed = self.speed * 2
                else:
                        self.speed = self.top_speed

        def updateStats(self, timer):
                self.distance += self.speed * timer + 0.5 * self.accelaration * timer ** 2
                self.speed += self.accelaration * timer
                self.speed *= hf
                self.time += timer

        def getDistance(self):
                return self.distance

def GetMin(array):
        index=0
        min = array[index]
        for i in range(len(array)):
                if i in completed:
                        continue
                elif(array[i] < min):
                        index = i
                        min = array[i]

        return index


########## Code ###########
#Starting Point
for i in range(teams):
        t = Team(i+1)
        objTeamList.append(t)
time_elapsed =0

#Ready, Steady, Go!
while(1):
        if(len(completed) == teams):
                print "----------------------------Race Completed-------------------------\n"
                for i in range(teams):
                        print "%s:" % (i+1), objTeamList[i]
                print "\n-----------------------------------------------------------------\n"
                exit(1)

        time_elapsed += timer

        #Update & Reassessment
        for i in range(teams):
                if i not in completed:
                        objTeamList[i].updateStats(timer)

        #Nitro
        last1 = GetMin(objTeamList)
        if last1 not in usedNitro:
                objTeamList[last1].useNitro()
                usedNitro.append(last1)

        #Check for Winner(s)
        for i in range(teams):
                if i not in completed:
                        if objTeamList[i].getDistance() >= track:
                                completed.append(i)

- iKaul May 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I need this coding in C language

- ziya July 12, 2015 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More