Logically Consistent Book - Google Top Interview Questions

                        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