20190804 阿里面试编程题总结

  • 阿里数据库岗,二面技术面,最后一题编程题

    # Merge two sorted linked lists and
    # return it as a new list.The new list should be made
    # by splicing together the nodes of the first two lists.
    # Example:
    # Input: 1->2->4, 1->3->4
    # Output: 1->1->2->3->4->4
    
  • 用list很容易,但是重新把列表作为一个类出现得时候脑子开始空白。

    # Definition for singly-linked list.
    class ListNode(object):
        def __init__(self, x):
        self.val = x
        self.next = None
    
    class Solution(object):
        def mergeTwoLists(self, l1, l2):
    
  • 没有仔细看这个类是怎么定义得,只看到了示例数据得格式,结果陷入得怎么也没办法把测试数据声明成这样类得困境,在短时间内没有解决问题。记录一下。

  • 后来发现是Leetcode 的第21题,看完解法之后才发现自己思路是对的,但是错误就在没看类的定义导致自己全盘都乱了。

伪代码,错误示范

11.next = 11.val
if 11.next != None:
    if 11.val > 12.val:
    11.next = 12.val

解法

  • 因为Node 记录的是val和next,这两个列表其实直接比较大小,得出哪个是head,哪个是tail就可以解决问题,自己把问题复杂化。

    if l1 == None:
        return l2
    if l2 == None:
        return l1
    
    if l1.val <= l2.val:
        head = l1 
        head.next = self.mergeTwoLists(l1.next, l2)
    else:
        head = l2
        head.next = self.mergeTwoLists(l1, l2.next)
    
    return head 
    

内置库的解法

# Solution 1
# using sorted()
# to combine two sorted lists
res = sorted(test_list1 + test_list2)

## Solution 2 heapq.merge
from heapq import merge
# to combine two sorted lists
res = list(merge(test_list1, test_list2))

# printing result
print("The combined sorted list is : " + str(res))

在我忘记sort是升序还是降序的情况下,复杂解法

def two(list_a, list_b):
list_c = []
while len(list_a) > 0 and len(list_b) > 0:
    if list_a[0] < list_b[0]:
        list_c.append(list_a[0])
        del list_a[0]
    else:
        list_c.append(list_b[0])
        del list_b[0]
list_c.extend(list_a)
list_c.extend(list_b)
return list_c

ret = two([1, 2, 4], [1, 3, 4])
print(ret)

总结

  • 代码不够熟练度不够。读题不够仔细,没看清楚类的声明是最大的问题。
  • 心态不能崩,崩了之后智商为0。不够冷静。