Encode and Decode TinyURL Add Binary Diameter of Binary Tree Read N Characters Given Read4 II - Call multiple times Count of Smaller Numbers After Self
Top K Frequent Words Swap Nodes in Pairs Add Strings Climbing Stairs Interval List Intersections
Beta
EQ-1
Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
# 535. Encode and Decode TinyURL
classCodec: def__init__(self): self.urls = []
defencode(self, longUrl): # Encodes a URL to a shortened URL. self.urls.append(longUrl) return'http://tinyurl.com/' + str(len(self.urls) - 1)
defdecode(self, shortUrl): # Decodes a shortened URL to its original URL. returnself.urls[int(shortUrl.split('/')[-1])]
# Your Codec object will be instantiated and called as such: # codec = Codec() # codec.decode(codec.encode(url))
EQ-2
Given two binary strings, return their sum(also a binary string). The input strings are both non-empty and contains only characters 1 or 0.
1 2 3 4 5 6 7 8 9
# 67. Add Binary
class Solution: def addBinary(self, a: str, b: str) -> str: x, y = int(a, 2), int(b, 2) whiley != 0: x, y = x ^ y, (x & y) << 1 return bin(x)[2:]
EQ-3
Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
defmaxDepth(root: TreeNode) -> int: nonlocal maxDiameter if root isNone: return0 left = maxDepth(root.left) right = maxDepth(root.right) currDiameter = left + right
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.
@param buf, alist of characters @return an integer def read4(buf):
# Below isan example of how the read4 API can be called. file = File("abcdefghijk") # File is"abcdefghijk", initially file pointer (fp) points to'a' buf = [' '] * 4 # Create buffer with enough space to store characters read4(buf) # read4 returns 4. Now buf = ['a','b','c','d'], fp points to'e' read4(buf) # read4 returns 4. Now buf = ['e','f','g','h'], fp points to'i' read4(buf) # read4 returns 3. Now buf = ['i','j','k',...], fp points to end of file """
class Solution: def __init__(self): self._left = []
def read(self, buf, n): c, i = 0, 0 while n > 0and self._left: buf[i] = self._left.pop(0) n -= 1 i += 1 c += 1
for i in range(n//4): buf4 = ['']*4 n4 = read4(buf4) forj in range(n4): buf[c+j] = buf4[j] c += n4 if n % 4: buf4 = ['']*4 n4 = read4(buf4) for i in range(n % 4): buf[c+i] = buf4[i] c += min(n4, n % 4) for i in range(n % 4, n4): self._left.append(buf4[i])
def read(self, buf, n): """ :type buf: Destination buffer (List[str]) :type n: Number of characters toread (int) :rtype: The number of actual characters read (int) """ returnlen([buf.__setitem__(*x) forx in zip(range(n), self.chars)])
EQ-5
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i]. Input: [5,2,6,1] Output: [2,1,1,0]
classSolution: defcountSmaller(self, nums: List[int]) -> List[int]: rank, N, res = {val: i + 1for i, val in enumerate(sorted(nums))}, len(nums), [] BITree = [0] * (N + 1)
defupdate(i): while i <= N: BITree[i] += 1 i += (i & -i)
defgetSum(i): s = 0 whilei: s += BITree[i] i -= (i & -i) return s
for x in reversed(nums): res += getSum(rank[x] - 1), update(rank[x])
idx, res = [], [] for n in reversed(nums): p = bisect_left(idx, n) res.append(p) idx[p:p] = [n]#idx.insert(p, n) return res[::-1]
EQ-6
Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
# 692. Top K Frequent Words
classSolution: deftopKFrequent(self, words: List[str], k: int) -> List[str]: out = [] counts = collections.Counter(words) out = [(-f,w) for w,f in counts.items()] heapq.heapify(out) return [heapq.heappop(out)[1] for _ in range(k)]
classSolution1: deftopKFrequent(self, words: List[str], k: int) -> List[str]: return [w for w, v in sorted(collections.Counter(words).items(), key = lambda x: (-x[1], x[0])) [:k]]
EQ-7
Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the listâ€™s nodes, only nodes itself may be changed.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
# 24. Swap Nodes in Pairs
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None
classSolution: defswapPairs(self, head: ListNode) -> ListNode: pre, pre.next = self, head while pre.nextand pre.next.next: a = pre.next b = a.next pre.next, b.next, a.next = b, a, b.next pre = a returnself.next
EQ-8
Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.
temp = n1 + n2 + carry res.append(temp % 10) carry = temp // 10 if carry: res.append(carry) return''.join([str(i) for i in res])[::-1]
EQ-9
You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
classSolution: defclimbStairs(self, n: int) -> int: x = [1,2] for i in range(2,n): x.append(x[i-1]+x[i-2]) return x[n-1]
classSolution1: defclimbStairs(self, n: int) -> int: # fibonacci a = 1 b = 0 for i in range(n): res = a + b b = a a = res return res
EQ-10
Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
# 986. Interval List Intersections
class Solution: def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]: res = [] i = j = 0 while i < len(A) and j < len(B): if A[i][0] <= B[j][1] and B[j][0] <= A[i][1]: res.append([max(A[i][0], B[j][0]), min(A[i][1], B[j][1])]) if A[i][1] < B[j][1]: i+=1 else: j+=1 return res