You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

Example 1:

Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]] Output: true Example 2:

Input: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]] Output: false

Constraints:

1 <= 2000 <= n 0 <= edges.length <= 5000 edges[i].length == 2 0 <= ai, bi < n ai != bi There are no self-loops or repeated edges.

classSolution { public: boolvalidTree(int n, vector<vector<int>>& edges){ unordered_map<int, vector<int>> graph; unordered_map<int, int> parent; for (auto &edge : edges) { int a = edge[0]; int b = edge[1]; graph[a].push_back(b); graph[b].push_back(a); } for (int i = 0; i < n; i++) parent[i] = -1; unordered_set<int> seen; bool ret = dfs(graph, 0, seen, parent); return ret && seen.size() == n; } booldfs(unordered_map<int, vector<int>> &graph, int i, unordered_set<int> &seen, unordered_map<int, int> &parent){ if (seen.count(i)) returnfalse; seen.insert(i); for (int j : graph[i]) { if (parent[i] == j) continue; parent[j] = i; if (dfs(graph, j, seen, parent) == false) returnfalse; } returntrue; } };

classSolution { public: boolvalidTree(int n, vector<vector<int>>& edges){ if (edges.size() != n-1) returnfalse; unordered_map<int, vector<int>> graph; for (auto &edge : edges) { int a = edge[0]; int b = edge[1]; graph[a].push_back(b); graph[b].push_back(a); } unordered_set<int> seen; dfs(graph, 0, seen); return seen.size() == n; } voiddfs(unordered_map<int, vector<int>> &graph, int i, unordered_set<int> &seen){ seen.insert(i); for (int j : graph[i]) { if (seen.count(j) == 0) dfs(graph, j, seen); } } };

//UnionFind, path compression and union by size classSolution { public: boolvalidTree(int n, vector<vector<int>>& edges){ if (edges.size() != n - 1) returnfalse; for (int i = 0; i < n; i++) { parent.push_back(i); size.push_back(1); } for (auto &edge : edges) { int a = edge[0]; int b = edge[1]; if (Union(a, b) == false) returnfalse; } returntrue; } private: vector<int> parent; vector<int> size; boolUnion(int a, int b){ int p_a = Find(a); int p_b = Find(b); if (p_a == p_b) returnfalse; if (size[p_a] > size[p_b]) { parent[p_b] = p_a; size[p_a] += size[p_b]; } else { parent[p_a] = p_b; size[p_b] += size[p_a]; } returntrue; } intFind(int a){ if (parent[a] != a) parent[a] = Find(parent[a]); return parent[a]; } };

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

Implement a thread-safe bounded blocking queue that has the following methods:

BoundedBlockingQueue(int capacity) The constructor initializes the queue with a maximum capacity. void enqueue(int element) Adds an element to the front of the queue. If the queue is full, the calling thread is blocked until the queue is no longer full. int dequeue() Returns the element at the rear of the queue and removes it. If the queue is empty, the calling thread is blocked until the queue is no longer empty. int size() Returns the number of elements currently in the queue. Your implementation will be tested using multiple threads at the same time. Each thread will either be a producer thread that only makes calls to the enqueue method or a consumer thread that only makes calls to the dequeue method. The size method will be called after every test case.

Please do not use built-in implementations of bounded blocking queue as this will not be accepted in an interview.

Explanation: Number of producer threads = 1 Number of consumer threads = 1

BoundedBlockingQueue queue = new BoundedBlockingQueue(2); // initialize the queue with capacity = 2.

queue.enqueue(1); // The producer thread enqueues 1 to the queue. queue.dequeue(); // The consumer thread calls dequeue and returns 1 from the queue. queue.dequeue(); // Since the queue is empty, the consumer thread is blocked. queue.enqueue(0); // The producer thread enqueues 0 to the queue. The consumer thread is unblocked and returns 0 from the queue. queue.enqueue(2); // The producer thread enqueues 2 to the queue. queue.enqueue(3); // The producer thread enqueues 3 to the queue. queue.enqueue(4); // The producer thread is blocked because the queue’s capacity (2) is reached. queue.dequeue(); // The consumer thread returns 2 from the queue. The producer thread is unblocked and enqueues 4 to the queue. queue.size(); // 2 elements remaining in the queue. size() is always called at the end of each test case. Example 2:

Explanation: Number of producer threads = 3 Number of consumer threads = 4

BoundedBlockingQueue queue = new BoundedBlockingQueue(3); // initialize the queue with capacity = 3.

queue.enqueue(1); // Producer thread P1 enqueues 1 to the queue. queue.enqueue(0); // Producer thread P2 enqueues 0 to the queue. queue.enqueue(2); // Producer thread P3 enqueues 2 to the queue. queue.dequeue(); // Consumer thread C1 calls dequeue. queue.dequeue(); // Consumer thread C2 calls dequeue. queue.dequeue(); // Consumer thread C3 calls dequeue. queue.enqueue(3); // One of the producer threads enqueues 3 to the queue. queue.size(); // 1 element remaining in the queue.

Since the number of threads for producer/consumer is greater than 1, we do not know how the threads will be scheduled in the operating system, even though the input seems to imply the ordering. Therefore, any of the output [1,0,2] or [1,2,0] or [0,1,2] or [0,2,1] or [2,0,1] or [2,1,0] will be accepted.

Constraints:

1 <= Number of Prdoucers <= 8 1 <= Number of Consumers <= 8 1 <= size <= 30 0 <= element <= 20 The number of calls to enqueue is greater than or equal to the number of calls to dequeue. At most 40 calls will be made to enque, deque, and size.

Design a data structure that will be initialized with a string array, and then it should answer queries of the shortest distance between two different strings from the array.

Implement the WordDistance class:

WordDistance(String[] wordsDict) initializes the object with the strings array wordsDict. int shortest(String word1, String word2) returns the shortest distance between word1 and word2 in the array wordsDict.

1 <= wordsDict.length <= 3 * 10^4 1 <= wordsDict[i].length <= 10 wordsDict[i] consists of lowercase English letters. word1 and word2 are in wordsDict. word1 != word2 At most 5000 calls will be made to shortest.

classWordDistance { public: WordDistance(vector<string>& wordsDict) { int n = wordsDict.size(); for (int i = 0; i < n; i++) word_map[wordsDict[i]].push_back(i); } intshortest(string word1, string word2){ auto &index1 = word_map[word1]; auto &index2 = word_map[word2]; int i = 0, j = 0; int ans = INT_MAX; while (i < index1.size() && j < index2.size()) { if (index1[i] < index2[j]) { ans = min(ans, index2[j] - index1[i]); i++; } else { ans = min(ans, index1[i] - index2[j]); j++; } } return ans; } private: unordered_map<string, vector<int>> word_map; };

/** * Your WordDistance object will be instantiated and called as such: * WordDistance* obj = new WordDistance(wordsDict); * int param_1 = obj->shortest(word1,word2); */

Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes. More formally, the property root.val = min(root.left.val, root.right.val) always holds.

Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree.

If no such second minimum value exists, output -1 instead.

Example 1:

Input: root = [2,2,5,null,null,5,7] Output: 5 Explanation: The smallest value is 2, the second smallest value is 5. Example 2:

Input: root = [2,2,2] Output: -1 Explanation: The smallest value is 2, but there isn’t any second smallest value.

Constraints:

The number of nodes in the tree is in the range [1, 25]. 1 <= Node.val <= 2^31 - 1 root.val == min(root.left.val, root.right.val) for each internal node of the tree.

Given a string s containing only three types of characters: ‘(‘, ‘)’ and ‘*’, return true if s is valid.

The following rules define a valid string:

Any left parenthesis ‘(‘ must have a corresponding right parenthesis ‘)’. Any right parenthesis ‘)’ must have a corresponding left parenthesis ‘(‘. Left parenthesis ‘(‘ must go before the corresponding right parenthesis ‘)’. ‘*’ could be treated as a single right parenthesis ‘)’ or a single left parenthesis ‘(‘ or an empty string “”.