# Race to Finish Line - Google Top Interview Questions

### Problem Statement :

```You are driving a car in a one-dimensional line and are currently at position = 0 with speed = 1. You can make one of two moves:

Accelerate: position += speed and speed *= 2

Reverse: speed = -1 if speed > 0 otherwise speed = 1.

Return the minimum number of moves it would take to reach target.

Constraints

1 ≤ target ≤ 100,000

Example 1

Input

target = 7

Output

3

Explanation

We can accelerate 3 times to reach 7. 0 -> 1 -> 3 -> 7

Example 2

Input

target = 6

Output

5

Explanation

We can accelerate 3 times to reach 7. 0 -> 1 -> 3 -> 7. Then we reverse to change our speed to -1. Then we accelerate to reach 6.```

### Solution :

```                        ```Solution in C++ :

int dp[100005];
// dp[i] is the minimum time needed to travel exactly a distance of i

int solve(int target) {
if (dp[target]) {
return dp[target];
}
int time = 0;
int speed = 1;
int position = 0;
// this is achievable by accelerating, then reversing twice, repeating "target" times until we
// get to the target
int besttime = 3 * target;
while (true) {
position += speed;
time++;
if (position == target) {
besttime = min(besttime, time);
break;
}
// reverse once, but since we're after the target we don't continue traveling further
// forward
if (position > target) {
besttime = min(besttime, time + 1 + solve(position - target));
break;
}
// reverse twice to reset speed to 1
besttime = min(besttime, time + 2 + solve(target - position));
// reverse in the middle, but don't reverse all the way
if (speed > 1) {
int candtime = time + 2;
int candposition = target - position;
for (int revspeed = 1; candposition + revspeed < target; revspeed *= 2) {
candposition += revspeed;
candtime++;
besttime = min(besttime, candtime + solve(candposition));
}
}
speed *= 2;
}
dp[target] = besttime;
return besttime;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public int solve(int target) {
if (target == 0)
return 0;
boolean[][] ff = new boolean[38][target * 2 + 1];
ff[0][0] = true;
int lay = 0, count = 1;
while (!ll1.isEmpty()) {
int p = ll1.poll(), s = ll2.poll();
int speed = s < 19 ? 1 << s : -(1 << (s - 19));
if (p + speed == target)
return lay + 1;
if (p + speed >= 0 && p + speed < ff[0].length && !ff[s + 1][p + speed]) {
ff[s + 1][p + speed] = true;
}
s = s < 19 ? 19 : 0;
if (!ff[s][p]) {
ff[s][p] = true;
}
--count;
if (count == 0) {
++lay;
count = ll1.size();
}
}
return -1;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, target):
self.ans = int(1e9)
hi = 1
while (1 << hi) < target:
hi += 1
self.dfs(hi, 0, 0, 0, target)
return self.ans

def dfs(self, digit, cost, pos, neg, target):
tot = cost + max(2 * (pos - 1), 2 * neg - 1)
if tot >= self.ans:
return
if target == 0:
self.ans = min(self.ans, tot)
return
step = (1 << digit) - 1
if step * 2 < abs(target):
return
self.dfs(digit - 1, cost, pos, neg, target)
self.dfs(digit - 1, cost + digit, pos + 1, neg, target - step)
self.dfs(digit - 1, cost + digit * 2, pos + 2, neg, target - step * 2)
self.dfs(digit - 1, cost + digit, pos, neg + 1, target + step)
self.dfs(digit - 1, cost + digit * 2, pos, neg + 2, target + step * 2)```
```

## Castle on the Grid

You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal. Function Description Complete the minimumMoves function in the editor. minimumMoves has the following parameter(s):

## Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

## Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

## Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

## QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element