2020春招-美团笔试-编程题4道

美团笔试编程题

Posted by weber on April 9, 2020

公司:美团

岗位:推荐算法实习生

题型:编程题 5 道 (最后一道没看到题)

1. 时间

描述:给定一个时间,包括星期,时,分,然后再给一个分钟数n,输出给定时间往前n分钟的星期、时、分,时分都是2位,不足首位补0。

输入示例:

3

18:30

300

输出示例:

3 (还是星期3)

13:30

思路:先把往前推的天数对10080取余,也就是一周的分钟数,然后对week,h,m的修改分别求出来,通过一个标志位判断是否借位。

def get_time(week,h,m,n):
    n = n % 10080 
    week_ = n // 1440
    n = n % 1440
    h_ = n // 60
    m_ = n % 60
    carry = 0
    carry_w = 0

    if m < m_:
        carry = 1
        m += 60 - m_
    else:
        m -= m_

    if h < h_ + carry:
        carry_w = 1
        h += 24 - (h_ + carry)
    else:
        h -= h_ + carry 

    week_ += carry_w
    if week <= week_:
        week += 7 - week_
    else:
        week -= week_

    h,m = str(h),str(m)
    if len(h) == 1:
        h = '0' + h
    if len(m) == 1:
        m = '0' + m
  
    return str(week), str(h) + ":" + str(m)

2. 运动员跑步

描述:

有n个运动员,给2个长为n的数组,分别为出发时各个位置上运动员的编号和到达时运动员的编号,那么问到达时超过了别人的运动员有几个。

输入示例:

5 [5, 3, 1, 4, 2] [2, 4, 5, 1, 3]

输出示例:

3

思路:双指针

def over_num(n, a, b):
    s = set()
    idx1, idx2 = 0,0
    res = 0
    while idx1 < n:
        if a[idx1] in s:
            idx1 += 1
            continue
        while b[idx2]!=a[idx1]:
            s.add(b[idx2])
            idx2 += 1
            res += 1
        idx1 += 1
        idx2 += 1
    return res

3. 修bug

描述:

给n和k,求使得 [x] + [x/k] + [x/k^2] + …大于等于n的最小x。 [x]为向下取整,总有一个时刻[x/k^m]=0,因此等于求满足条件的前m项和。

输入示例:

10 3

输出示例:

8 (因为8 + 2 >= 10)

思路:x从1开始会超时,所以可以二分

def fix_bug(n,k):
    l,r = 0, n
    res = n
    while l<=r:
        mid = (l+r)//2
        x = mid
        sum = 0
        while sum < n and x >= 1:
            sum += x
            x //= k
        if sum >= n:
            res = min(res,mid)
            r = mid - 1
        else:
            l = mid + 1 
    return res

4. 金字塔

描述:

四面体的四个顶点S,A,B,C,问经过n步回到s的不同路径有多少条

输入示例:

3

输出示例:

6

思路:dp。S是从ABC过来的,ABC其实是一样的,同等地位的,所以dp[n](S) = 3 * dp[n-1](A),然后就是ABC的规律了。A是从SBC过来的,因此dp[n](A) = dp[n-1](S) + 2 * dp[n-1](B),所以结果就是 :

def count(n):
  s,a = 1,0
  for i in range(n):
    s,a = (3*a)%1000000007, (s+2*a)%1000000007
  return s

5. 总结

考察知识点:

问题分类,双指针,二分,动态规划,数学

参考链接:

https://www.nowcoder.com/discuss/404178

https://www.nowcoder.com/discuss/404230