(4, 5); // return true because node 4 is unlocked. // Node 4 will now be locked by user 5. lockingTree.upgrade(0, 1); // return true because node 0 is unlocked and has at least one locked descendant (node 4). // Node 0 will now be locked by user 1 and node 4 will now be unlocked. lockingTree.lock(0, 1); // return false because node 0 is already locked.

Solution

Method 1

Code

[{"language":"Java","code":"class LockingTree {\n\tprivate int[] parent;\n\tprivate Map<Integer, Integer> locked; // {node: user}\n\tprivate Map<Integer, List<Integer>> children;\n\t\n\tpublic LockingTree(int[] parent) {\n\t\tthis.parent = parent;\n\t\tthis.locked = new HashMap<>();\n\t\tthis.children = new HashMap<>();\n\t\tfor (int i = 0; i < parent.length; i++) {\n\t\t\tchildren.put(i, new ArrayList<>());\n\t\t}\n\t\tfor (int i = 0; i < parent.length; i++) {\n\t\t\tif (parent[i] != -1) {\n\t\t\t\tchildren.get(parent[i]).add(i);\n\t\t\t}\n\t\t}\n\t}\n\t\n\tpublic boolean lock(int num, int user) {\n\t\tif (!locked.containsKey(num)) {\n\t\t\tlocked.put(num, user);\n\t\t\treturn true;\n\t\t}\n\t\treturn false;\n\t}\n\t\n\tpublic boolean unlock(int num, int user) {\n\t\tif (locked.containsKey(num) && locked.get(num) == user) {\n\t\t\tlocked.remove(num);\n\t\t\treturn true;\n\t\t}\n\t\treturn false;\n\t}\n\t\n\tpublic boolean upgrade(int num, int user) {\n\t\t// Check if num is unlocked\n\t\tif (locked.containsKey(num)) {\n\t\t\treturn false;\n\t\t}\n\t\t\n\t\t// Check if ancestors are not locked\n\t\tint cur = num;\n\t\twhile (cur != -1) {\n\t\t\tif (locked.containsKey(cur)) {\n\t\t\t\treturn false;\n\t\t\t}\n\t\t\tcur = parent[cur];\n\t\t}\n\t\t\n\t\t// Check if there is at least one locked descendant\n\t\tboolean hasLockedDescendant = hasLockedDescendant(num);\n\t\tif (!hasLockedDescendant) {\n\t\t\treturn false;\n\t\t}\n\t\t\n\t\t// Unlock all descendants\n\t\tunlockDescendants(num);\n\t\tlocked.put(num, user);\n\t\treturn true;\n\t}\n\t\n\tprivate boolean hasLockedDescendant(int num) {\n\t\tif (locked.containsKey(num)) {\n\t\t\treturn true;\n\t\t}\n\t\tfor (int child : children.get(num)) {\n\t\t\tif (hasLockedDescendant(child)) {\n\t\t\t\treturn true;\n\t\t\t}\n\t\t}\n\t\treturn false;\n\t}\n\t\n\tprivate void unlockDescendants(int num) {\n\t\tif (locked.containsKey(num)) {\n\t\t\tlocked.remove(num);\n\t\t}\n\t\tfor (int child : children.get(num)) {\n\t\t\tunlockDes

Related Tags