Problem statement

https://leetcode.com/problems/clone-binary-tree-with-random-pointer/

Solution

This problem is similar to problem 133 Clone graph. The idea is to create hash table of connections between old and new trees. We traverse tree with dfs and each time when we see that node is not visited, we create new pair in hash table. Also we run mapping[node].left = dfs(node.left), that is recursevily create pairs for left children, similarly for right and random.

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def copyRandomBinaryTree(self, root):
        def dfs(node):
            if not node: return 
            if node not in mapping: 
                mapping[node] = NodeCopy(node.val)
                mapping[node].left = dfs(node.left)
                mapping[node].right = dfs(node.right)
                mapping[node].random = dfs(node.random)
            return mapping[node]
        
        mapping = {}
        return dfs(root)

Remark

Also you can solve it in almost the same way I did for problem 133, but then you first need to run dfs for usual tree and then once again another dfs only for random pointers.

1490 Clone N-ary Tree

[tree, hash table, dfs, bfs]

Solution

This problem is exactly the same as 133 Clone Graph

Complexity

Time and space complexity is O(n).

Code

class Solution:
    def cloneTree(self, root: 'Node') -> 'Node':
        def dfs(node):
            mapping[node] = Node(node.val)
            for neigh in node.children:
                if neigh not in mapping: dfs(neigh)
                mapping[node].children += [mapping[neigh]]
        
        if not root: return root
        mapping  = {}
        dfs(root)
        return mapping[root]

1500 Design a File Sharing System

[design, hash table, heap]

Solution

We need to keep the following pieces of information:

  1. self.chunk_user is connection: for each chunk we keep all users that have it.
  2. self.user_chunk is for every user we keep all chunks it have.
  3. self.heap is heap of avaliable id.

The functions will work like this:

  1. join(ownedChunks). First, we need to find id of new user: if we have elements in heap, extract it from it, if not, allocate maximum we have +1. Also we need to update chunk_user and user_chunk.
  2. leave(userID): we need to update chunk_user and delete user_chunk. Also we add new id to our heap.
  3. request(userID, chunkID): first we create candidates: all users who have this chunk. Then if candidates are not empty, we update chunk_user and user_chunk: only in this case this user can get this chunk.

Complexity

Time complexity for join is O(S + log T), where S = len(ownedChunks) and T = len(heap). Time complexity for leave is O(S + log T). Time complexity of cands is O(S log S).

Code

class FileSharing:
    def __init__(self, m: int):
        self.chunk_user = defaultdict(set)
        self.user_chunk = defaultdict(set)
        self.heap = []  #queue of free ids
        
    def join(self, ownedChunks):
        user = heappop(self.heap) if self.heap else len(self.user_chunk) + 1
        for i in ownedChunks: self.chunk_user[i].add(user)
        self.user_chunk[user] = set(ownedChunks)
        return user
        
    def leave(self, userID):
        for chunk in self.user_chunk[userID]:
            self.chunk_user[chunk].remove(userID)
            
        heappush(self.heap, userID)
        del self.user_chunk[userID]
        
    def request(self, userID, chunkID):
        cands = sorted(list(self.chunk_user[chunkID]))
        
        if cands:
            self.chunk_user[chunkID].add(userID)
            self.user_chunk[userID].add(chunkID)
        
        return cands