# Maximize Social Distancing - Google Top Interview Questions

### Problem Statement :

```You are given a list of integers seats containing 1s and 0s.
Each element seats[i] represents a seat and is either occupied if seats[i] = 1 or empty if seats[i] = 0.

Given that there’s at least one empty seat and at least one occupied seat, return the maximum distance from an empty seat to the closest occupied seat.

Constraints

n ≤ 100,000 where n is the length of seats

Example 1

Input

seats = [1, 0, 1, 0, 0, 0, 1]

Output

2

Explanation

We can sit at seats.

Example 2

Input

seats = [1, 0, 0, 0]

Output

3

Explanation

We can sit at seats.```

### Solution :

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

int solve(vector<int>& seats) {
int ans = 1, last = -1;
for (int i = 0; i < seats.size(); ++i) {
if (seats[i] == 1) {
if (last == -1)
ans = max(ans, i);
else
ans = max(ans, (i - last) / 2);
last = i;
}
}
ans = max(ans, (int)seats.size() - last - 1);
return ans;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public int solve(int[] seats) {
int pre = 0;
boolean seen = false;

int maxConsecutives = 0;
int currConsecutives = 0;

for (int i = 0; i < seats.length; i++) {
if (seats[i] == 0) {
currConsecutives++;
maxConsecutives = Integer.max(maxConsecutives, currConsecutives);

if (!seen) {
pre++;
}
} else if (seats[i] == 1) {
seen = true;
currConsecutives = 0;
}
}

return Integer.max(
Integer.max(pre, currConsecutives), (int) Math.ceil(maxConsecutives / 2.0));
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, seats):
indices = [i for i, s in enumerate(seats) if s]
d = max(((i2 - i1) // 2) for i1, i2 in zip(indices, indices[1:])) if len(indices) > 1 else 0
d = max(indices, d, len(seats) - indices[-1] - 1)
return d```
```

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