# Matrix Relations - Google Top Interview Questions

### Problem Statement :

```You are given an integer n and a two-dimensional list of integers relations.

You want to fill an n by n matrix using relations, which defines the spatial ordering of some cell values in the matrix. Each element relations[i] contains (x, y, type) which means that

x is left of y if type = 0

x is right of y if type = 1

x is above y if type = 2

x is below y if type = 3

Return the n by n matrix following the constraints in relations. Since some cells may not have a value,
set it to -1. You can assume each defined cell in the matrix will have a unique value. Also, there is one
unique solution.

Constraints

n ≤ 500

1 ≤ m ≤ 100,000 where m is the length of relations

Example 1

Input

n = 3

relations = [

[1, 2, 0],

[2, 3, 0],

[1, 2, 2],

[2, 3, 2]

]

Output

[

[1, -1, -1],

[-1, 2, -1],

[-1, -1, 3]

]

Explanation

The relations says:

1 is left of 2

2 is left of 3

1 is above 2

2 is above 3

Other unfilled squares are set to -1.```

### Solution :

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

vector<vector<int>> solve(int n, vector<vector<int>> &relations) {
unordered_map<int, vector<int>> left, above;
unordered_map<int, int> indegLeft, indegAbove;
unordered_map<int, pair<int, int>> mp;
for (int i = 0; i < relations.size(); i++) {
int x = relations[i][0], y = relations[i][1], type = relations[i][2];
mp[x] = {-1, -1};
mp[y] = {-1, -1};
if (type == 0 || type == 1) {
if (type == 1) {
swap(x, y);
}
left[y].push_back(x);
indegLeft[x]++;
indegLeft[y] = indegLeft[y];
} else {
if (type == 3) {
swap(x, y);
}
above[y].push_back(x);
indegAbove[x]++;
indegAbove[y] = indegAbove[y];
}
}

queue<int> q;
for (auto it = indegLeft.begin(); it != indegLeft.end(); it++) {
if (it->second == 0) {
q.push(it->first);
}
}

int j = n - 1;
while (!q.empty()) {
int s = q.size();
while (s--) {
int p = q.front();
q.pop();
mp[p].second = j;
vector<int> &l = left[p];
for (int i = 0; i < l.size(); i++) {
indegLeft[l[i]]--;
if (indegLeft[l[i]] == 0) {
q.push(l[i]);
}
}
}
j--;
}

for (auto it = indegAbove.begin(); it != indegAbove.end(); it++) {
if (it->second == 0) {
q.push(it->first);
}
}
int i = n - 1;
while (!q.empty()) {
int s = q.size();
while (s--) {
int p = q.front();
q.pop();
mp[p].first = i;
vector<int> &l = above[p];
for (int j = 0; j < l.size(); j++) {
indegAbove[l[j]]--;
if (indegAbove[l[j]] == 0) {
q.push(l[j]);
}
}
}
i--;
}

vector<vector<int>> res(n, vector<int>(n, -1));
for (auto it = mp.begin(); it != mp.end(); it++) {
int val = it->first;
int x = it->second.first, y = it->second.second;
res[x][y] = val;
}
return res;
}```
```

```                        ```Solution in Java :

import java.util.*;

class Solution {
public int[][] solve(int n, int[][] r) {
int[][] ans = new int[n][n];

// Initialize the matrix
for (int[] row : ans) {
Arrays.fill(row, -1);
}
Map<Integer, Set<Integer>> downTo = new HashMap<>();
Map<Integer, Set<Integer>> rightTo = new HashMap<>();
Map<Integer, Set<Integer>> upTo = new HashMap<>();
Map<Integer, Set<Integer>> leftTo = new HashMap<>();
Map<Integer, Integer> xaxis = new HashMap<>();
Map<Integer, Integer> yaxis = new HashMap<>();

for (int i = 0; i < r.length; i++) {
// I change all the right or below direction to left or above

if (r[i][2] == 1 || r[i][2] == 3) {
r[i][2]--;
int tmp = r[i][0];
r[i][0] = r[i][1];
r[i][1] = tmp;
}
int x = r[i][0];
int y = r[i][1];

// Build set if a map doesn't have the key.
rightTo.computeIfAbsent(x, k -> new HashSet<>());
rightTo.computeIfAbsent(y, k -> new HashSet<>());
leftTo.computeIfAbsent(x, k -> new HashSet<>());
leftTo.computeIfAbsent(y, k -> new HashSet<>());
downTo.computeIfAbsent(x, k -> new HashSet<>());
downTo.computeIfAbsent(y, k -> new HashSet<>());
upTo.computeIfAbsent(x, k -> new HashSet<>());
upTo.computeIfAbsent(y, k -> new HashSet<>());
if (r[i][2] == 0) {
// x left to y
} else {
// x up to y
}
}

// If degree is 0 then we add it to the queue
for (int k : rightTo.keySet()) {
if (rightTo.get(k).size() == 0) {
q.offer(k);
}
}
int idx = n - 1;
while (!q.isEmpty()) {
int size = q.size();
while (size > 0) {
size--;
int cur = q.poll();
// System.out.println(cur);
yaxis.put(cur, idx);
for (int p : leftTo.get(cur)) {
rightTo.get(p).remove(cur);
if (rightTo.get(p).size() == 0) {
q.offer(p);
}
}
}
idx--;
}

for (int k : downTo.keySet()) {
if (downTo.get(k).size() == 0) {
q.offer(k);
}
}
idx = n - 1;
while (!q.isEmpty()) {
int size = q.size();
while (size > 0) {
size--;
int cur = q.poll();
// System.out.println(cur);
xaxis.put(cur, idx);
for (int p : upTo.get(cur)) {
downTo.get(p).remove(cur);
if (downTo.get(p).size() == 0) {
q.offer(p);
}
}
}
idx--;
}

for (int key : xaxis.keySet()) {
ans[xaxis.get(key)][yaxis.get(key)] = key;
}

return ans;
}
}```
```

```                        ```Solution in Python :

class Solution:
def solve(self, N, relations):
rindegree = collections.Counter()
cindegree = collections.Counter()
rlist = collections.defaultdict(list)
clist = collections.defaultdict(list)
keys = set()

# Parsing queries
for x, y, t in relations:

if t == 0:
rindegree[y] += 1
rlist[x].append(y)
elif t == 1:
rindegree[x] += 1
rlist[y].append(x)

if t == 2:
cindegree[y] += 1
clist[x].append(y)
elif t == 3:
cindegree[x] += 1
clist[y].append(x)

# Get the rows (or cols) mapping of the indegree and list
def topsort(indegree, elist):
ans = {}
q = collections.deque()
for x in keys:
if indegree[x] == 0:
q.append((x, 0))

while len(q) > 0:
index, d = q.popleft()
ans[index] = d

for v in elist[index]:
if indegree[v] > 0:
indegree[v] -= 1
if indegree[v] == 0:
q.append((v, d + 1))
return ans

rans = topsort(rindegree, rlist)
cans = topsort(cindegree, clist)

ans = [[-1] * N for _ in range(N)]

for x in keys:
ans[cans[x]][rans[x]] = x

return ans```
```

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