from collections import deque
# Initializing a queue
q = deque()
# Adding elements to a queue
q.append('a')
q.append('b')
q.append('c')
print("Initial queue")
print(q)
# Removing elements from a queue
print("\nElements dequeued from the queue")
print(q.popleft())
print(q.popleft())
print(q.popleft())
print("\nQueue after removing elements")
print(q)
# Uncommenting q.popleft()
# will raise an IndexError
# as queue is now empty
常见的面试问题：
反转队列的前 k 个元素
使用链表实现队列
使用队列实现栈
3、栈
用 list 实现，push 操作使用 append() 方法，pop 操作使用 pop()
stack = []
# append() function to push
# element in the stack
stack.append('a')
stack.append('b')
stack.append('c')
print('Initial stack')
print(stack)
# pop() function to pop
# element from stack in
# LIFO order
print('\nElements popped from stack:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
print('\nStack after elements are popped:')
print(stack)
# uncommenting print(stack.pop())
# will cause an IndexError
# as the stack is now empty
常见的面试问题：
使用栈实现一个队列
使用栈计算后缀表达式
使用栈的获取第二大元素
使用栈创建 main 函数
4、链表
链表主要用于创建高级数据结构，如图和树，或者用于需要经常在整个结构中添加/删除元素的任务。
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3
常见的面试问题：
打印给定链表的中间元素
从排序的链表中删除重复的元素
检查单链表是否为回文
合并 k 排序链表
查找两个链表的交点
5、循环链表
标准链表的主要缺点是必须始终从 Head 节点开始。循环链表通过将 Tail 节点的空指针替换为指向 Head 节点的指针来修复这个问题。
这种设置的优点是可以从任何节点开始遍历整个列表。
常见的面试问题：
检测链表中的循环
反转循环链表
以给定大小的组来反转循环链表（Reverse circular linked list in groups of a given size）
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
def insert(self, data):
# Compare the new value with the parent node
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the tree
def PrintTree(self):
if self.left:
self.left.PrintTree()
print( self.data),
if self.right:
self.right.PrintTree()
# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)
root.PrintTree()
常见的面试问题：
检查两个二叉树是否相同
实现二叉树的层次序遍历
打印二叉查找树的周长
沿着一条路径求所有节点的和
连接一个二叉树的所有兄弟节点
7、图
有向图 & 无向图
当用纯文本编写时，图有一个顶点和边的列表：
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
在 Python 中，图最好使用字典来实现，每个顶点的名称作为键，边列表作为值。
# Create the dictionary with graph elements
graph = {"a": ["b", "c"],
"b": ["a", "d"],
"c": ["a", "d"],
"d": ["e"],
"e": ["d"]
}
# Print the graph
print(graph)
常见的面试问题：
检测有向图中的循环
在有向图中查找父节点
计算无向图中的边数
检查两个顶点之间是否存在路径
求两个顶点之间的最短路径
8、哈希表
（这个图画的很棒，于是偷过来了）
import pprint
class Hashtable:
def __init__(self, elements):
self.bucket_size = len(elements)
self.buckets = [[] for i in range(self.bucket_size)]
self._assign_buckets(elements)
def _assign_buckets(self, elements):
for key, value in elements: # calculates the hash of each key
hashed_value = hash(key)
# positions the element in the bucket using hash
index = hashed_value % self.bucket_size
# adds a tuple in the bucket
self.buckets[index].append((key, value))
def get_value(self, input_key):
hashed_value = hash(input_key)
index = hashed_value % self.bucket_size
bucket = self.buckets[index]
for key, value in bucket:
if key == input_key:
return(value)
return None
def __str__(self):
# pformat returns a printable representation of the object
return pprint.pformat(self.buckets)
if __name__ == "__main__":
capitals = [
('France', 'Paris'),
('United States', 'Washington D.C.'),
('Italy', 'Rome'),
('Canada', 'Ottawa')
]
hashtable = Hashtable(capitals)
print(hashtable)
print(f"The capital of Italy is {hashtable.get_value('Italy')}")
#!/usr/bin/env python3
import logging
import os
import time
import sys
from watchdog.observers import Observer
from watchdog.events import LoggingEventHandler
# load variables from environment variables
verbose = int(os.environ.get('VERBOSE', 1))
directory = os.environ.get('DIRECTORY', os.path.join('tmp'))
if __name__ == "__main__":
if verbose:
logging.basicConfig(stream=sys.stdout, level=logging.INFO)
event_handler = LoggingEventHandler()
observer = Observer()
observer.schedule(event_handler, directory, recursive=True)
observer.start()
try:
while True:
time.sleep(1)
finally:
observer.stop()
observer.join()
requirements.txt
watchdog==2.0.2
Dockerfile
# first stage
FROM python:3.8 AS builder
COPY requirements.txt .
# install dependencies to the local user directory (eg. /root/.local)
RUN pip install --user -r requirements.txt
# second stage
FROM python:3.8-slim
WORKDIR /code
# copy only the dependencies that are needed for our application and the source files
COPY --from=builder /root/.local /root/.local
COPY ./src .
# update PATH
ENV PATH=/root/.local:$PATH
# make sure you include the -u flag to have our stdout logged
CMD [ "python", "-u", "./main.py" ]
