Logically Consistent Book - Google Top Interview Questions
Problem Statement :
You are given a two-dimensional list of integers lists.
Each element contains [start, end, type], meaning that from pages [start, end] inclusive, there's either an even number of words (type = 0) or an odd number of words (type = 1).
Return whether lists is logically consistent.
Constraints
n ≤ 100,000 where n is the length of lists
Example 1
Input
lists = [
[1, 5, 1],
[6, 10, 0],
[1, 10, 0]
]
Output
False
Explanation
If there are an odd number of words from pages [1, 5] and an even number of words from pages [6, 10],
that must mean there's an odd number from pages [1, 10]. So this is a contradiction.
Example 2
Input
lists = [
[0, 2, 0],
[2, 4, 0],
[0, 4, 0]
]
Output
True
Explanation
If there are an even number of words from pages [0, 2] and an even number of words from pages [2, 4],
that means there can be an even number from pages [0, 4]. So there's no contradiction.
Example 3
Input
lists = [
[0, 2, 1],
[3, 4, 1],
[0, 4, 0]
]
Output
True
Explanation
If there are an odd number of words from pages [0, 2] and an odd number of words from pages [3, 4], that must mean there's an even number from pages [0, 4]. So there's no contradiction.
Solution :
Solution in C++ :
unordered_map<int, vector<pair<int, int>>> edges;
bool solve(vector<vector<int>>& lists) {
unordered_map<int, int> parity;
edges.clear();
for (auto& edge : lists) {
edges[edge[0] - 1].emplace_back(edge[1], edge[2]);
edges[edge[1]].emplace_back(edge[0] - 1, edge[2]);
}
for (auto edge : edges) {
int src = edge.first;
if (parity.count(src)) continue;
parity[src] = 0;
queue<int> q;
q.push(src);
while (q.size()) {
int curr = q.front();
q.pop();
for (auto edge : edges[curr]) {
int nparity = parity[curr] ^ edge.second;
if (parity.count(edge.first) && parity[edge.first] != nparity) return false;
if (!parity.count(edge.first)) {
parity[edge.first] = nparity;
q.push(edge.first);
}
}
}
}
return true;
}
Solution in Java :
import java.util.*;
class Solution {
public boolean solve(int[][] nums) {
Comparator c = new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
if (a[0] != b[0])
return a[0] - b[0];
else
return a[1] - b[1];
}
};
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(c);
for (int[] range : nums) pq.add(range);
while (pq.size() >= 2) {
int[] r1 = pq.poll();
int[] r2 = pq.peek();
if (r1[0] == r2[0]) {
if (r1[1] == r2[1]) {
if (r1[2] != r2[2])
return false;
} else {
pq.add(new int[] {r1[1] + 1, r2[1], Math.abs(r1[2] - r2[2])});
}
}
}
return true;
}
}
Solution in Python :
class Solution:
def solve(self, lists):
graph = defaultdict(list)
for i, j, p in lists:
graph[i].append([j + 1, p])
graph[j + 1].append([i, p])
state = {}
def dfs(node, color):
state[node] = color
for nei, w in graph[node]:
if nei not in state:
if not dfs(nei, color ^ w):
return False
elif state[nei] != color ^ w:
return False
return True
for node in graph:
if node not in state and dfs(node, 0) is False:
return False
return True
View More Similar Problems
Array-DS
An array is a type of data structure that stores elements of the same type in a contiguous block of memory. In an array, A, of size N, each memory location has some unique index, i (where 0<=i<N), that can be referenced as A[i] or Ai. Reverse an array of integers. Note: If you've already solved our C++ domain's Arrays Introduction challenge, you may want to skip this. Example: A=[1,2,3
View Solution →2D Array-DS
Given a 6*6 2D Array, arr: 1 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 An hourglass in A is a subset of values with indices falling in this pattern in arr's graphical representation: a b c d e f g There are 16 hourglasses in arr. An hourglass sum is the sum of an hourglass' values. Calculate the hourglass sum for every hourglass in arr, then print t
View Solution →Dynamic Array
Create a list, seqList, of n empty sequences, where each sequence is indexed from 0 to n-1. The elements within each of the n sequences also use 0-indexing. Create an integer, lastAnswer, and initialize it to 0. There are 2 types of queries that can be performed on the list of sequences: 1. Query: 1 x y a. Find the sequence, seq, at index ((x xor lastAnswer)%n) in seqList.
View Solution →Left Rotation
A left rotation operation on an array of size n shifts each of the array's elements 1 unit to the left. Given an integer, d, rotate the array that many steps left and return the result. Example: d=2 arr=[1,2,3,4,5] After 2 rotations, arr'=[3,4,5,1,2]. Function Description: Complete the rotateLeft function in the editor below. rotateLeft has the following parameters: 1. int d
View Solution →Sparse Arrays
There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results. Example: strings=['ab', 'ab', 'abc'] queries=['ab', 'abc', 'bc'] There are instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0]. Fun
View Solution →Array Manipulation
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu
View Solution →