# 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:

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.

Share It, If You Like It.