Read N Characters Given Read4 II - Call multiple times - Python Solution

 Given a file and assume that you can only read the file using a given method read4, implement a method read to read n characters. Your method read may be called multiple times.

 

Method read4:

The API read4 reads 4 consecutive characters from the file, then writes those characters into the buffer array buf.

The return value is the number of actual characters read.

Note that read4() has its own file pointer, much like FILE *fp in C.

Definition of read4:

    Parameter:  char[] buf4
    Returns:    int

Note: buf4[] is destination not source, the results from read4 will be copied to buf4[]

Below is a high level example of how read4 works:

File file("abcde"); // File is "abcde", initially file pointer (fp) points to 'a'
char[] buf = new char[4]; // Create buffer with enough space to store characters
read4(buf4); // read4 returns 4. Now buf = "abcd", fp points to 'e'
read4(buf4); // read4 returns 1. Now buf = "e", fp points to end of file
read4(buf4); // read4 returns 0. Now buf = "", fp points to end of file

 

Method read:

By using the read4 method, implement the method read that reads n characters from the file and store it in the buffer array buf. Consider that you cannot manipulate the file directly.

The return value is the number of actual characters read.

Definition of read:

    Parameters:	char[] buf, int n
    Returns:	int

Note: buf[] is destination not source, you will need to write the results to buf[]

 

Example 1:

File file("abc");
Solution sol;
// Assume buf is allocated and guaranteed to have enough space for storing all characters from the file.
sol.read(buf, 1); // After calling your read method, buf should contain "a". We read a total of 1 character from the file, so return 1.
sol.read(buf, 2); // Now buf should contain "bc". We read a total of 2 characters from the file, so return 2.
sol.read(buf, 1); // We have reached the end of file, no more characters can be read. So return 0.

Example 2:

File file("abc");
Solution sol;
sol.read(buf, 4); // After calling your read method, buf should contain "abc". We read a total of 3 characters from the file, so return 3.
sol.read(buf, 1); // We have reached the end of file, no more characters can be read. So return 0.

 

Note:

• Consider that you cannot manipulate the file directly, the file is only accesible for read4 but not for read.
• The read function may be called multiple times.
• Please remember to RESET your class variables declared in Solution, as static/class variables are persisted across multiple test cases. Please see here for more details.
• You may assume the destination buffer array, buf, is guaranteed to have enough space for storing n characters.
• It is guaranteed that in a given test case the same buffer buf is called by read.

# The read4 API is already defined for you.

# def read4(buf4: List[str]) -> int:

class Solution(object):

    def __init__(self):

        self.tmp = [None] * 4

        self.tmppoint = 0

        self.tmpcount = 0

    def read(self, buf: List[str], n: int) -> int:

        total = 0

        while total < n:

            if self.tmppoint == 0:

                self.tmpcount = read4(self.tmp)

            if self.tmpcount == 0: break

            while self.tmppoint < self.tmpcount and total < n:

                buf[total] = self.tmp[self.tmppoint]

                total+=1

                self.tmppoint+=1

            

            if self.tmppoint == self.tmpcount: self.tmppoint = 0

            if self.tmpcount < 4: break

        return total

TC:O(n)

SC:O(n) buffer space 

Longest String Chain Python Solution

 Given a list of words, each word consists of English lowercase letters.

Let's say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2.  For example, "abc" is a predecessor of "abac".

A word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.

Return the longest possible length of a word chain with words chosen from the given list of words.

 

Example 1:

Input: ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        if not words:
            return 1
        words.sort(key=len)
        cache = {}
        res = 0
        for word in words:
            longest = 0
            for i in range(len(word)):
                child = word[0:i]+word[i+1:]
                longest = max(longest,cache.get(child,0)+1)
            cache[word] = longest
            res = max(res,longest)
        return res

TC:O(N log n) or O(N * max(len(word))) SC: O(N)

Open the Lock - Leetcode Python

 You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.

The lock initially starts at '0000', a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

 

Example 1:

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2:

Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation:
We can turn the last wheel in reverse to move from "0000" -> "0009".

Example 3:

Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
Explanation:
We can't reach the target without getting stuck.

Example 4:

Input: deadends = ["0000"], target = "8888"
Output: -1

class Solution:
    def openLock(self, deadends: List[str], target: str) -> int:
        deadset = set(deadends)
        def neighbors(node):
            nodes = []
            for i in range(4):
                x = int(node[i])
                for k in (-1,1):
                    y = (x+k) % 10
                    nodes.append(node[:i]+str(y)+node[i+1:])
            return nodes
        
        queue = deque([('0000',0)])
        seen = {'0000'}
        while queue:
            node,depth = queue.popleft()
            if node == target:
                return depth
            if node in deadset: continue
            for nei in neighbors(node):
                if nei not in seen:
                    seen.add(nei)
                    queue.append((nei,depth+1))
        return -1

TN: O(N*N) SC:O(N)

 

Split Array into Consecutive Subsequences - Leetcode Python

 Given an array nums sorted in ascending order, return true if and only if you can split it into 1 or more subsequences such that each subsequence consists of consecutive integers and has length at least 3.

 

Example 1:

Input: [1,2,3,3,4,5]
Output: True
Explanation:
You can split them into two consecutive subsequences : 
1, 2, 3
3, 4, 5

Example 2:

Input: [1,2,3,3,4,4,5,5]
Output: True
Explanation:
You can split them into two consecutive subsequences : 
1, 2, 3, 4, 5
3, 4, 5

Example 3:

Input: [1,2,3,4,4,5]
Output: False

Solution :

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        count = collections.Counter(nums)
        tails = collections.Counter()
        for x in nums:
            if count[x] == 0:
                continue
            elif tails[x] > 0:
                tails[x] -= 1
                tails[x+1] +=1
                count[x] -= 1
            elif count[x] > 0 and count[x+1] > 0 and count[x+2] > 0:
                count[x] -= 1
                count[x+1] -=1
                count[x+2] -=1
                tails[x+3] +=1
            else:
                return False
            
        return True

TC: O(n) SC:O(n)
        

Insert Delete GetRandom O(1) - Python Leetcode

 Implement the RandomizedSet class:

• bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
• bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
• int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

Follow up: Could you implement the functions of the class with each function works in average O(1) time?

 

Example 1:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

 

Constraints:

• -231 <= val <= 231 - 1
• At most 105 calls will be made to insert, remove, and getRandom.
• There will be at least one element in the data structure when getRandom is called.

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.

        """

        if val in self.dict:

            return False

        self.dict[val] = len(self.list)

        self.list.append(val)

        return True

        

    def remove(self, val: int) -> bool:

        """

        Removes a value from the set. Returns true if the set contained the specified element.

        """

        if val not in self.dict:

            return False

        idx = self.dict[val]

        lx = len(self.list)-1

        self.dict[self.list[lx]] = idx

        self.list[idx],self.list[lx]=self.list[lx],self.list[idx]

        self.list.pop()

        del self.dict[val]

        return True

    def getRandom(self) -> int:

        """

        Get a random element from the set.

        """

        return choice(self.list)

        

# 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()

Serialize and Deserialize Binary Tree - Python Leetcode

 Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

 

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

Input: root = [1,2]
Output: [1,2]

class Codec:
    '''       O(n) time and O(n) space, BFS traversal
    e.g., 1
         / \
        2   5
       / \
      3   4  , level order traversal, serialize will be '1,2,5,3,4,None,None,None,None,None,None,'; deserialize 
      with queue as well, convert back. Time and Space O(n).
    '''
    def serialize(self, root):
        if not root:
            return ''
        queue = collections.deque()
        queue.append(root)
        res = ''
        while queue:
            node = queue.popleft()
            if not node:
                res += 'None,'
                continue
            res += str(node.val) + ','
            queue.append(node.left)
            queue.append(node.right)
        return res
            
    def deserialize(self, data):
        if not data:
            return None
        ls = data.split(',')
        root = TreeNode(int(ls[0]))
        queue = collections.deque()
        queue.append(root)
        i = 1
        while queue and i < len(ls):
            node = queue.popleft()
            if ls[i] != 'None':
                left = TreeNode(int(ls[i]))
                node.left = left
                queue.append(left)
            i += 1
            if ls[i] != 'None':
                right = TreeNode(int(ls[i]))
                node.right = right
                queue.append(right)
            i += 1
        return root

        

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

Find Duplicate Subtrees - Python Leetcode

  Find Duplicate Subtrees

Given the root of a binary tree, return all duplicate subtrees.

For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with the same node values.

 

Example 1:

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

Example 2:

Input: root = [2,1,1]
Output: [[1]]

Example 3:

Input: root = [2,2,2,3,null,3,null]
Output: [[2,3],[3]]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
        count = collections.Counter()
        trees = collections.defaultdict()
        trees.default_factory = trees.__len__
        ans = []
        def lookup(root):
            if root:
                uid = trees[root.val,lookup(root.left),lookup(root.right)]
                count[uid]+=1
                if count[uid] == 2:
                    ans.append(root)
                return uid
        
        lookup(root)
        return ans
        

TC: O(n) SC: O(n)