Basic: Interesting Skills For Code Test

There are some tricks which are not intuitive. But quite useful.



#padplaceholder: Padding items with place holders, thus we can simplify the corner cases.


#limitedrange: The dataset of the problem may be big, but data range is limited


## Blog link: https://code.dennyzhang.com/sliding-puzzle
for (ik, jk) in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
    i2, j2 = i0+ik, j0+jk
    if i2<0 or i2 >= 2 or j2<0 or j2>=3: continue
    matrix[i0][j0], matrix[i2][j2] = matrix[i2][j2], matrix[i0][j0]
    newState = self.toString(matrix)
    if newState not in visited:
        queue.append(newState)

# Use recursive to simplify the logic, when len(s) < len(t)
if len_s<len_t: return self.isOneEditDistance(t, s)

## Blog link: https://code.dennyzhang.com/shortest-word-distance
p1, p2, res = -1, -1, len(words)
for i in range(len(words)):
    if words[i] in [word1, word2]:
        if words[i] == word1:
            p1 = i
        else:
            p2 = i
        if p1 != -1 and p2 != -1:
            res = min(res, abs(p1-p2))
return res

## Blog link: https://code.dennyzhang.com/longest-consecutive-sequence
max_count = 0
for num in set(nums):
    # only search from the biggest value of current group
    if num + 1 not in nums:
        y = num - 1
        while y in nums:
            y = y -1
        max_count = max(max_count, num-y)
return max_count


From:

def myDepthSum(self, nestedList, level):
    """
    :type nestedList: List[NestedInteger]
    :rtype: int
    """
    if len(nestedList) == 0: return 0
    res = 0
    for item in nestedList:
        if item.isInteger():
            res += item.getInteger()*level
        else:
            res += self.myDepthSum(item.getList(), level+1)
    return res

To:

def myDepthSum(self, nestedList, level):
    """
    :type nestedList: List[NestedInteger]
    :rtype: int
    """
    res = 0
    for item in nestedList:
        if item.isInteger():
            res += item.getInteger()*level
        else:
            res += self.myDepthSum(item.getList(), level+1)
    return res

  • To keep the top 10 biggest element, we need to use minheap. Design Twitter
## Blog link: https://code.dennyzhang.com/design-twitter
# min heap
q = []
heapq.heapify(q)
for (id, tweetId) in self.tweet_dict[userId]:
    heapq.heappush(q, (id, tweetId))
    if len(q) > 10: heapq.heappop(q)

Data Structures:

  1. #trie, #heap
  2. #monotonestack

Algorithms:

  1. #countsort
  2. #bucketsort
  3. #radixsort: see here.
  4. #moorevoting
  5. #twocomplement: encoding for negative numbers
  6. #floydcycle: detect a loop with a fast and slow pointer.
  7. #fisheryatesshuffle: generate a random permutation of a finite sequence.
  8. #reservoirsampling: randomly choose a sample of k items from a very huge dataset. And we don’t know the size. See wikipedia.
  9. #discretetimesignal: See wikipedia.
  10. #backtracking
  11. #bfs
  12. #dfs
  13. #dynamicprogramming

Misc:

See more blog_posts.

linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.