西维蜀黍的OJ Blog

🐒 Software engineer | 📷 Photographer | 👹 Urban explorer

[Interview] Transactional Key Value Store

Squarepoint Capital interview Description Part 1: Create a class for a simple key-value store which supports the following methods: set(key, value) - add a new entry to the key-value store, or update it if it’s already there get(key) - get the value for the given key. Raise a KeyError if the key is not there delete(key) - delete the entry. Raise a KeyError if the key is not there Example:   ...


[Topic] Anagrams

解析 49. Group Anagrams # solution 1 - hashmap + sorting - myself # - time: O(N * max_char log max_char) # - space: O(n) def groupAnagrams(self, strs): m = {} for str in strs: sortedStr = "".join(sorted(str)) if sortedStr in m: m[sortedStr].append(str) else: m[sortedStr] = [str] return m.values() # solution 2 - hashmap - myself # - time: O(n * max_char) # - space: O(n) def groupAnagrams(self, strs:   ...


[Topic] BFS (Breadth-first Search)

BFS (Breadth-first Search) BFS 的核心思想应该不难理解的,就是把一些问题抽象成图,从一个点开始,向四周开始扩散。一般来说,我们写 BFS 算法都是用「队列」这种数据结构,每   ...


[Topic] Palindrome

解析 5. Longest Palindromic Substring # solution 1 - burte force: n * n^2 # - Get every possible substring (O(n^2)), and check whether it is a palindrome (O(n)) # solution 2 - sliding window # - time: O(n^2) def longestPalindrome(self, s: str) -> str: max_len = 0 res = "" for idx in range(len(s)): # odd: cbc l, r = idx, idx while l >= 0 and r   ...


[Topic] Prefix Sum

题目 238. Product of Array Except Self 209. Minimum Size Subarray Sum 解析 238. Product of Array Except Self 用hashmap记下乘积,先从左到右循环,再从右到左循环 # Approach 1 - more elegent def productExceptSelf(self, nums: List[int]) -> List[int]: res = [1] * len(nums) for idx in range(1,   ...