# Shortest Cycle Containing Target Node - Google Top Interview Questions

### Problem Statement :

```You are given a two-dimensional list of integers graph representing a directed graph as an adjacency list. You are also given an integer target.

Return the length of a shortest cycle that contains target. If a solution does not exist, return -1.

Constraints

n, m ≤ 250 where n and m are the number of rows and columns in graph

Example 1

Input

Visualize

graph = [

[1],

[2],

[0]

]

target = 0

Output

3

Explanation

The nodes 0 -> 1 -> 2 -> 0 form a cycle

Example 2

Input

Visualize

graph = [

[1],

[2],

[4],

[],

[0]

]

target = 3

Output
-1```

### Solution :

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

vector<int> color;
vector<long long int> dist;
int dest;
long long int dfs(int u) {
if (u == dest) {
return 0;
}
color[u] = 1;  // gray
long long int mindist = INT_MAX;
for (int v : adj[u]) {
if (color[v] == 0) {
mindist = min(mindist, 1 + dfs(v));
} else if (color[v] == 2) {
mindist = min(mindist, 1 + dist[v]);
}
}
color[u] = 2;  // black
return dist[u] = mindist;
}

int solve(vector<vector<int>>& graph, int target) {
dest = target;
color.assign(graph.size(), 0);
dist.assign(graph.size(), 0);
long long int res = INT_MAX;
for (int i : graph[target]) {
res = min(res, 1 + dfs(i));
}
if (res == INT_MAX) return -1;
return res;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public int solve(int[][] graph, int target) {
boolean[] visited = new boolean[graph.length];

int level = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int tmp = q.remove();
visited[tmp] = true;

for (int neighbor : graph[tmp]) {
if (neighbor == target)
return level + 1;
else if (!visited[neighbor])
}
}

level++;
}

return -1;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, graph, target):
visited = set()
layer = [target]
length = 0

while layer:
length += 1
next_layer = []
for u in layer:
for v in graph[u]:
if v == target:
return length
if v in visited:
continue
next_layer.append(v)
layer = next_layer

return -1```
```

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