# Window Limits - Google Top Interview Questions

### Problem Statement :

```You are given a list of integers nums and integers window and limit.

Return whether abs(nums[i] - nums[j]) ≤ limit for every i, j such that abs(i - j) < window.

Constraints

1 ≤ n ≤ 100,000 where n is the length of nums

1 ≤ window ≤ n

0 ≤ limit < 2 ** 31

Example 1

Input

nums = [1, 3, 7, 5]

window = 2

limit = 4

Output

True

Explanation

Every number within a window of size 2 has pair differences of at most 4 (from 3 and 7).

Example 2

Input

nums = [1, 3, 7, 5]

window = 3

limit = 4

Output

False

Explanation

Within a window size of 3 we have abs(1 - 7) > 4, so this is above the limit.```

### Solution :

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

bool solve(vector<int>& nums, int window, int limit) {
multiset<long long> dp;
for (int i = 0; i < nums.size(); i++) {
dp.insert(nums[i]);
if (i >= window) dp.erase(dp.find(nums[i - window]));
if (*dp.rbegin() - *dp.begin() > limit) return false;
}
return true;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public boolean solve(int[] nums, int window, int limit) {
Deque<Integer> q = new ArrayDeque();
Deque<Integer> q2 = new ArrayDeque();
int r = 0;
while (r < nums.length) {
while (!q.isEmpty() && q.peekFirst() <= r - window) {
q.removeFirst();
}
while (!q2.isEmpty() && q2.peekFirst() <= r - window) {
q2.removeFirst();
}
while (!q.isEmpty() && nums[q.peekLast()] < nums[r]) {
q.removeLast();
}
while (!q2.isEmpty() && nums[q2.peekLast()] > nums[r]) {
q2.removeLast();
}
q.offerLast(r);
q2.offerLast(r++);
int max = nums[q.peekFirst()];
int min = nums[q2.peekFirst()];
if (max - min > limit) {
return false;
}
}
return true;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, nums, window, limit):
minq = deque()  # <idx, val>
maxq = deque()  # <idx, val>
for i, x in enumerate(nums):
while minq and minq[-1] >= x:
minq.pop()
while maxq and maxq[-1] <= x:
maxq.pop()
minq.append((i, x))
maxq.append((i, x))
if minq <= i - window:
minq.popleft()
if maxq <= i - window:
maxq.popleft()
if maxq - minq > limit:
return False
return True```
```

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