一个记录

Intern Interview

作者 Lutein 日期 2018-05-01
Python Coding Record
一个记录

流程


一面全过，二面后开始刷人，如果前两面都是negative，就没有三面。三面后当场可以从HR那里得到大致结果。

一面会根据简历问一些相关问题，都不难，比如机器学习相关的问了聚类和k-means。然后手写代码。二面跟一面差不多，简要介绍以后直接写代码。三面是主管面，内容取决于面试官的性格，可能不写。

代码部分

  1. 二分搜索返回下标

    def BinarySearch(nums, left, right):
    	if left >= right:
    		return right

    	mid = (left +right) //2
    	#print mid
    	if nums[mid] < num:
    		return BinarySearch(nums,mid+1, right)
    	elif nums[mid] > num:
    		return BinarySearch(nums, left, mid)
    	else:
    		return mid

  2. 给出二叉树的前序和中序，重建二叉树

    def construct_tree(preorder=None, inorder=None):
        if not preorder or not inorder:
            return None
        idx = inorder.index(preorder[0])
        left = inorder[:idx]
        right = inorder[idx+1:]

        root = TreeNode(preorder[0])

        root.left = construct_tree(preorder[1:1+len(left)], left)
        root.right = construct_tree(preorder[-len(right)], right)

        return root

  3. 快速排序

    def quicksort(nums):
    	if len(nums) < 2:
    		return nums
    	pivot = nums[0]
    	less = [i for i in nums[1:] if i <= pivot]
    	greater = [i for i in nums[1:] if i > pivot]
    	return quicksort(less) + [pivot] + quicksort(greater)

  4. 选择排序

    def selectionsort(nums):
    	for fill in range(len(nums)-1, 0, -1):
    		maxloc = 0
    		for loc in range(1, fill+1):
    			if nums[loc] > nums[maxloc]:
    				maxloc = loc
    		nums[fill], nums[maxloc] = nums[maxloc], nums[fill]
    	return nums

  5. 希尔排序

    step = len(nums) // 2
    while step > 0:
    	for i in range(step, len(nums)):
    		while i >= step and nums[i] < nums[i - step]:
    			nums[i], nums[i-step] = nums[i-step], nums[i]
    			i -= step
    	step /= 2
    return nums

  6. 堆排序

    import numpy as np
    def adjust_heap(nums, i):
    	if 2*i + 1 < len(nums):
    		children = nums[2*i+1:2*i+3]
    		n = np.argmax(children)
    		if max(children) > nums[i]:
    			if n == 0:
    				nums[2*i+1], nums[i] = nums[i], nums[2*i+1]
    				adjust_heap(nums, 2*i+1)
    			else:
    				nums[2*i+2], nums[i] = nums[i], nums[2*i+2]
    				adjust_heap(nums, 2*i+2)
    				
    def build_heap(nums):
    	for i in range((len(nums)-1)//2, -1, -1):
    		adjust_heap(nums,i)
    		
    def heapsort(nums):
        i = len(nums) - 1
        n = np.argmax(nums)
        nums[0], nums[n] = nums[n], nums[0]    
        build_heap(nums)
        while i >= 0:
            n = nums.pop(0)
            nums.append(n)
            num = nums[:i]
            adjust_heap(num, 0)
            nums[:i] = num
            i -= 1
    	return nums

  7. $n$根绳子，长度为$l_1-l_n$，剪成$k$段，每段长度相同，怎样使每段的长度最大
    这道题与剑指offer中剪绳子的那道颇为相似，但是可以用递归来破解，以下是我的一种解法。

    #recursive version
    def Divide(nums, k, length):
    	count = 0
    	for i in nums:
    		if i == length:
    			count += 1
    		elif i > length:
    			count += i // length
    		if count >= k:
    			return True
    	return False

    def Find(nums, k, length):
    	if k == 1:
    		return k, nums[-1]
    	if length < 1:
    		return None
    	if Divide(nums, k, length):
    		return k, length
    	else:
    		return Find(nums, k, length - 1)
    #test
    nums = [4,3, 2,1]
    nums = sorted(nums)
    k = 3
    sum = sum(nums)
    length = sum // k
    print Find(nums, k, length)

  8. 字符串s：abbacdbab, 字符串p：abb。找s中的字串满足该子串中字母及每个字母对应的个数与p相同，求这样子串的个数
    LeetCode 438

    class Solution(object):
        def findAnagrams(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: List[int]
            """
            res = []
            n, m = len(s), len(p)
            if n < m: return res
            phash, shash = [0]*123, [0]*123
            for x in p:
                phash[ord(x)] += 1
            for x in s[:m-1]:
                shash[ord(x)] += 1
            for i in range(m-1, n):
                shash[ord(s[i])] += 1
                if i-m >= 0:
                    shash[ord(s[i-m])] -= 1
                if shash == phash:
                    res.append(i - m + 1)
            return res

  9. 链表遍历

  10. 冒泡排序

    def bubblesort(nums):
    	for times in range(len(nums)-1, 0, -1):
    		for i in range(times):
    			if nums[i]>nums[i+1]:
    				nums[i], nums[i+1] = nums[i+1], nums[i]
    	return nums

  11. 求给定字符串中包含该字符串所有出现过的字母的最短字串

    def ShortestSubstring(str):
        if not str:
            return None
        record = []
        count = {}
        for s in str:
            if s in record:
                count[s] += 1
            else:
                record.append(s)
                count[s] = 1
        left, right = 0, len(str) - 1
        while left <= right:
            if count[str[left]] == 1 and count[str[right]] == 1:
                return str[left:right+1]
            if count[str[left]] > 1:
                count[str[left]] -= 1
                left += 1
            if count[str[left]] == 1 and count[str[right]] > 1:
                count[str[right]] -= 1
                right -= 1 
    print ShortestSubstring("abaacdab")

  12. 非递归版快排

  13. 插入排序
    def insertsort(nums):
    	for loc in range(1, len(nums)):
    		currentval = nums[loc]
    		position = loc
    		while position > 0 and nums[position-1] > currentval:
    			nums[position] = nums[position-1]
    			position -= 1
    		nums[position] = currentval
    	return nums

非代码部分

  1. 判断链表是否有环，如何找出入环点。
    使用快慢指针，初始化为链表头，慢指针每次向后移动1，快指针移动2，遍历链表，如果快慢指针指到同一个位置，说明有环；如果快指针指向了null，说明无环。
    Alt text
    假设在第$t$步快慢指针到达同一个位置，那么此时快指针走了$2t$，而慢指针走了$t$。
    设环的长度为$R$，入环点距离链表头距离为$len$，指针距离入环点为$x$，快指针共绕环$n(n\in[1,2,\ldots])$次，那么可以得到等式：

    可以证明，$n=1$，那么$len=R-x$。
    Alt text
    定义一个currnet指针，初始化为链表头，一个inter指针，指向快慢指针的交汇点，两个指针一起向后移动，交汇时即为入环点。

  2. 给出一个$n\times n$数值矩阵，从左到右、从上到下依次递增，如何从中快速找到目标值并分析时间复杂度。
    从左下角或右上角开始比较，每次可以去掉一行/一列，时间复杂度是O(n)。

  3. 概率题：10个红球，10个绿球，放入A,B两个箱子中，如何放置才能使随机取一个箱子中的一个球是红球的概率最大。
    考虑边界情况的概率最大：A中放10个绿球，9个红球，B中放1个红球，取得红球的概率为

    如何确定是9个红球：
    设A中放$x$个红球则A中取得红球的概率为$f(x)=\frac{x}{10+x},x\in[1,2,\ldots,9]$，在定义域上是递增的，因此取9个红球。

欢迎在评论区交流补充😀

FEATURED TAGS
Python Coding Record