[LeetCode] 428. Serialize and Deserialize N-ary Tree

 Problem: https://leetcode.com/problems/serialize-and-deserialize-n-ary-tree/

Use preorder traversal to dump the given tree. To make the deserialize process simpler, we dump the size of children list after the node value to indicate how many children node is needed under current node.

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Codec:
    def serialize(self, root: 'Node') -> str:
        """Encodes a tree to a single string.
        
        :type root: Node
        :rtype: str
        """
        
        def preorder(node):
            yield str(node.val)
            yield str(len(node.children))
            
            for nxt in node.children:
                yield from preorder(nxt)
            
        return ','.join(preorder(root)) if root else ''
	
    def deserialize(self, data: str) -> 'Node':
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: Node
        """
        
        data = data.split(',') if data else []
        

        def helper(index):
            if index >= len(data):
                return None, index
            
            node = Node(val=int(data[index]), children=[])
            index += 1
            size = int(data[index])
            index += 1
            
            for _ in range(size):
                child, index = helper(index)
                node.children.append(child)
                
            return node, index
                
        return helper(0)[0]

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

[LeetCode] 381. Insert Delete GetRandom O(1) - Duplicates allowed

 Problem: https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/

Similar to the problem # 380, to get O(1) time complexity for deleting operation, we need to save the index of each value in the value list.  Because it allows duplicated value be inserted and deleting item from bidirectional linked list is O(1). we can manage nodes with same value in a bidirectional linked list. Then the hash table saves the index of the last item of one value's bidirectional linked list. 

class Node:
    def __init__(self, val, pre, nxt):
        self.val = val
        self.pre = pre
        self.nxt = nxt
        
        
class RandomizedCollection:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        
        # nodes with same value are linked as a bidirectional linked list
        # dict[K] save the index of the last node of number K's linked list 
        self.dict = defaultdict(lambda: -1)
        
        # save all values
        self.list = []
        

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
        """
        
        index = len(self.list)
        
        if self.dict[val] == -1:
            node = Node(val = val, pre = -1, nxt = -1)
            
            self.dict[val] = index
            self.list.append(node)
            
            return True
        else:
            pre = self.dict[val]
            node = Node(val = val, pre = pre, nxt = -1)
            
            # append to the existing bidirectional link
            
            preNode = self.list[pre]
            preNode.nxt = index
            
            self.dict[val] = index
            self.list.append(node)
            
            return False

    def remove(self, val: int) -> bool:
        """
        Removes a value from the collection. Returns true if the collection contained the specified element.
        """
        
        if self.dict[val] == -1:
            return False
        
        # use the last item of self.list to replace the removed item
        # and update the the altered item indices
        
        index = self.dict[val]
        node = self.list[index]
        
        if node.pre == -1:
            self.dict[val] = -1
        else:
            # remove from the removed node's bidirectional linked list
            self.dict[val] = node.pre
            self.list[node.pre].nxt = -1
            
        tailIndex = len(self.list) - 1
        tailNode = self.list.pop()

        if index != tailIndex:
            self.list[index] = tailNode

            # update tailNode's bidirectional linked list
            if self.dict[tailNode.val] == tailIndex:
                self.dict[tailNode.val] = index

            if tailNode.pre != -1:
                self.list[tailNode.pre].nxt = index

            if tailNode.nxt != -1:
                self.list[tailNode.nxt].pre = index
                
        return True
    
    def getRandom(self) -> int:
        """
        Get a random element from the collection.
        """
        
        index = random.randint(0, len(self.list) - 1)
        return self.list[index].val


# Your RandomizedCollection object will be instantiated and called as such:
# obj = RandomizedCollection()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

P.S. We can also use hash set to save all list item indices of a given value. Deleting item from hash set is also O(1).

[LeetCode] 380. Insert Delete GetRandom O (1)

Problem : https://leetcode.com/problems/insert-delete-getrandom-o1/ 

The crux is using the last element of the list to replace the element needs to be removed to meet the requirement of O(1) deleting operation.

import random

class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        
        self.dict = {}
        self.list = []
        

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        """
        
        res = val not in self.dict
        
        if res:
            self.dict[val] = len(self.list)
            self.list.append(val)
        return res

    def remove(self, val: int) -> bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        """
        res = val in self.dict
        if res:
            # use the last element to replace the removed element
            index = self.dict[val]
            del self.dict[val]
            
            if index != len(self.list) - 1:
                self.list[index] = self.list[-1]
        
                # update element index and popup the last element from list
                self.dict[self.list[index]] = index
                
            self.list.pop()
        return res
        

    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """
        
        pick = random.randint(0, len(self.list) - 1)
        
        return self.list[pick]
        


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

[LeetCode] 335. Design Twitter

 Problem : https://leetcode.com/problems/design-twitter/

- Tweet be posted later may have smaller tweetId. So we need to save the time when the tweet be post.

- Should not allow user to follow themselves.

- Should not allow user to unfollow not-followed user.

from operator import itemgetter

class Twitter:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.timer = 1
        self.follows = defaultdict(set)
        self.tweets = defaultdict(list)

    def postTweet(self, userId: int, tweetId: int) -> None:
        """
        Compose a new tweet.
        """
        self.tweets[userId].append((self.timer, tweetId))
        self.timer += 1
        

    def getNewsFeed(self, userId: int) -> List[int]:
        """
        Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
        """
        
        allTweets = self.tweets[userId][:]
        
        for f in self.follows[userId]:
            allTweets.extend(self.tweets[f])
            
        
        allTweets.sort(reverse = True, key = itemgetter(0))
        allTweets = allTweets if len(allTweets) <= 10 else allTweets[:10]
        
        return [tweetId for _, tweetId in allTweets]
                

    def follow(self, followerId: int, followeeId: int) -> None:
        """
        Follower follows a followee. If the operation is invalid, it should be a no-op.
        """
        
        if followerId != followeeId:
            self.follows[followerId].add(followeeId)
        

    def unfollow(self, followerId: int, followeeId: int) -> None:
        """
        Follower unfollows a followee. If the operation is invalid, it should be a no-op.
        """
        
        if followerId != followeeId and followeeId in self.follows[followerId]:
            self.follows[followerId].remove(followeeId)
        


# Your Twitter object will be instantiated and called as such:
# obj = Twitter()
# obj.postTweet(userId,tweetId)
# param_2 = obj.getNewsFeed(userId)
# obj.follow(followerId,followeeId)
# obj.unfollow(followerId,followeeId)

[LeetCode] 341. Flatten Nested List Iterator

 Problem : https://leetcode.com/problems/flatten-nested-list-iterator/

Use stack to cache the expanded lists.

Must filter out the empty nested lists in hasNext() method.

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
#    def isInteger(self) -> bool:
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        """
#
#    def getInteger(self) -> int:
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        """
#
#    def getList(self) -> [NestedInteger]:
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        """

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = []
        for n in reversed(nestedList):
            self.stack.append(n)
    
    def next(self) -> int:
        return self.stack.pop().getInteger()
        
    def hasNext(self) -> bool:
        while self.stack and not self.stack[-1].isInteger():
            # expand non-empty nested list
            nestedList = self.stack.pop().getList()
            if nestedList:
                for n in reversed(nestedList):
                    self.stack.append(n)

        return self.stack
         

# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

Another approach of using stack. It's similar to how compiler maintains call-stack.

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
#    def isInteger(self) -> bool:
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        """
#
#    def getInteger(self) -> int:
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        """
#
#    def getList(self) -> [NestedInteger]:
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        """

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = [[nestedList, 0]]
    
    def next(self) -> int:
        nlist, nindex = self.stack[-1]
        
        self.stack[-1][1] += 1
        return nlist[nindex].getInteger()
        
    
    def hasNext(self) -> bool:     
        while self.stack:
            nlist, nindex = self.stack[-1]

            if nindex == len(nlist):
                self.stack.pop()
                continue

            if nlist[nindex].isInteger():
                break

            self.stack[-1][1] += 1
            childList = nlist[nindex].getList()
            if childList:
                self.stack.append([childList, 0])
        
        return self.stack
         

# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

Edited on 04/13/2021. Add the second stack based approach.

[LeetCode] 297. Serialize and Deserialize Binary Tree

 Problem : https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

Use BFS to serialize and deserialize the tree.

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        output = []
        
        queue = deque([root])
        
        while queue:
            tmp = deque()
            
            while queue:
                node = queue.popleft()
                if not node:
                    output.append('#')
                else:
                    output.append(str(node.val))
                    tmp.append(node.left)
                    tmp.append(node.right)
                    
            queue = tmp
        
        return ','.join(output) if output[0] != '#' else ''
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        
        if not data:
            return None
        
        data = data.split(',')
        
        root = TreeNode(int(data[0]))
        i = 1
        
        queue = deque([root])
        
        while i < len(data):
            tmp = deque()
            
            while queue:
                node = queue.popleft()
                
                if data[i] == '#':
                    node.left = None
                else:
                    node.left = TreeNode(int(data[i]))
                    tmp.append(node.left)
                
                i += 1
                
                if data[i] == '#':
                    node.right = None
                else:
                    node.right = TreeNode(int(data[i]))
                    tmp.append(node.right)
                
                i += 1
            
            queue = tmp
        
        return root
                    
        
        

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

[LeetCode] 295. Find Median from Data Stream

 Problem : https://leetcode.com/problems/find-median-from-data-stream/

Use insert sort to keep the data cache in ascending order.

Then median = ( nums[len(nums) // 2 ] + nums[(len(nums) - 1) // 2] ) / 2

Time Complexity = O ( Log N ) +  O ( N ) ≈ O ( N )

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.nums = []
        

    def addNum(self, num: int) -> None:
        
        def lowerBoundary(n):
            left, right = 0, len(self.nums)
            
            while left < right:
                mid = left + (right - left) // 2
                
                if self.nums[mid] == n:
                    right = mid
                elif self.nums[mid] < n:
                    left = mid + 1
                elif self.nums[mid] > n:
                    right = mid
            
            return left if left - 1 >= 0 else 0
            
        # insert sort   
        self.nums.insert(lowerBoundary(num), num)
        

    def findMedian(self) -> float:
        
        l = len(self.nums)
        
        return (self.nums[l//2] + self.nums[(l-1)//2]) / 2.0
        


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

[LeetCode] 284. Peeking Iterator

 Problem : https://leetcode.com/problems/peeking-iterator/

# Below is the interface for Iterator, which is already defined for you.
#
# class Iterator:
#     def __init__(self, nums):
#         """
#         Initializes an iterator object to the beginning of a list.
#         :type nums: List[int]
#         """
#
#     def hasNext(self):
#         """
#         Returns true if the iteration has more elements.
#         :rtype: bool
#         """
#
#     def next(self):
#         """
#         Returns the next element in the iteration.
#         :rtype: int
#         """

class PeekingIterator:
    def __init__(self, iterator):
        """
        Initialize your data structure here.
        :type iterator: Iterator
        """
        self.iterator = iterator
        self.peeked = None
        

    def peek(self):
        """
        Returns the next element in the iteration without advancing the iterator.
        :rtype: int
        """
        if self.peeked:
            return self.peeked
        
        self.peeked = self.iterator.next()
        return self.peeked
        

    def next(self):
        """
        :rtype: int
        """
        
        if self.peeked:
            tmp = self.peeked
            self.peeked = None
            return tmp
        
        return self.iterator.next()
        

    def hasNext(self):
        """
        :rtype: bool
        """
        
        if self.peeked:
            return True
        
        return self.iterator.hasNext()

# Your PeekingIterator object will be instantiated and called as such:
# iter = PeekingIterator(Iterator(nums))
# while iter.hasNext():
#     val = iter.peek()   # Get the next element but not advance the iterator.
#     iter.next()         # Should return the same value as [val].