朋友发来几个面试题

第一题

You want to spend your next vacation in a foreign country. In the summer you are free for N consecutive days. You have consulted Travel Agency and learned that they are offering a trip to some interesting location in the country every day. For simplicity, each location is identified by a number from 0 to N - 1. Trips are described in a non-empty array A: for each K (0 <K< N), A[K] is the identifier of a location which is the destination of a trip offered on day K. Travel Agency does not have to offer trips to all locations, and can offer more than one trip to some locations.
You want to go on a trip every day during your vacation. Moreover, you want to visit all locations offered by Travel Agency. You may visit the same location more than once, but you want to minimize duplicate visits. The goal is to find the shortest vacation (a range of consecutive days) that will allow you to visit all the locations offered by Travel Agency.
For example, consider array A such that:
A[0]=7
A[1]=3
A[2]=7
A[3]=3
A[4]=1
A[5]=3
A[6]=4
A[7]=1
Travel Agency offers trips to four different locations (identified by numbers 1, 3, 4 and 7). The shortest vacation starting on day 0 that allows you to visit all these locations ends on day 6 (thus is seven days long). Travel Agency offers trips to four different locations (identified by numbers 1, 3, 4 and 7). The shortest vacation starting on day 0 that allows you to visit all these locations ends on day 6 (thus is seven days long). However, a shorter vacation of five days (starting on day 2 and ending on day 6) also permits you to visit all locations. On every vacation shorter than five days, you will have to miss at least one location.
Write a function:
class Solution { public int solution(int[] A); } that, given a non-empty array A consisting of N integers, returns the length of the shortest vacation that allows you to visit all the offered locations.
For example, given array A shown above, the function should return 5, as explained above.
Given A = [2, 1, 1, 3, 2, 1, 1, 3], the function

密密麻麻的 字母我都认识 连起来 我就不知道怎么回事了！

def solution(a):
	pass

第二题

Jack has completed his very first programming test and is now wondering about his score. He received an email containing the final report about the task he solved in the test, but it omitted the score. Nathan never gives up, so he decided to compute his result from the report. He found out that:
his program was tested on several test cases;every test case has given one of the following results: passed, failed, timeout, error;test cases were organized into groups numbered by consecutive natural numbers;his program scored points for a group only when the result of every test case in the group was “passed”.
In the report, test cases are named according to the following rule: if the test case is the only test case in the group, its name is [task name] + [group number]. If there is more than one test in the group, its name is extended by a lowercase English letter which is different for each test case. Example test case names are: test1, test2a, test2b. In this example, test2a and test2b form one group and test1 forms another. Jack’s score is the number of groups his program passed multiplied by 100 and divided by the total number of groups. If the result is fractional, the number of points is rounded to the highest integer not greater than the result.
For example, if the program passed two groups out of three, the result is 2 * 100 / 3 = 66.(6), so Nathan would gain 66 points.
Write a function
solution(String[] n, String[])that, given the names and results of all the test cases, returns the number of points Jack scored. n and r are arrays (containing strings). n[i] is the case name; r[i] is the result;
for example
n = [‘test1’,‘name2a’,‘name2b’,‘haha3a’,‘haha3b’,‘haha3c’,‘jack4a’,‘jack4b’];
r = [‘passed’,‘failed’,‘passed’,‘passed’,‘passed’,‘passed’,‘timeout’,‘failed’];We have 4 groups, and only 2 groups passed the test, thus the result is 50;

def solution(n, r):
    _list = [chr(i) for i in range(97, 123)]
    group_dict = {
    }
    for index, item in enumerate(n):
        if item[-1] in _list:
            group_name = item[:-1]
        else:
            group_name = item
        temp = r[index] == 'passed'
        if group_name in group_dict:
            group_dict[group_name].append(temp)
        else:
            group_dict[group_name] = [temp]
    passed = len([1 for item in group_dict.values() if all(item)])
    groups = len(group_dict.keys())
    return passed*100//groups

第三题

You are keeping score for a baseball game with strange rules. The game consists of several rounds, where the scores of past rounds may affect future rounds’ scores.
At the beginning of the game, you start with an empty record. You are given a list of strings ops, where ops[i] is the ith operation you must apply to the record and is one of the following:
An integer x - Record a new score of x.
“+” - Record a new score that is the sum of the previous two scores. It is guaranteed there will always be two previous scores.
“D” - Record a new score that is double the previous score. It is guaranteed there will always be a previous score.
“C” - Invalidate the previous score, removing it from the record. It is guaranteed there will always be a previous score.
Return the sum of all the scores on the record. The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: ops = [“5”,“2”,“C”,“D”,“+”]
Output: 30
Explanation:
“5” - Add 5 to the record, record is now [5].
“2” - Add 2 to the record, record is now [5, 2].
“C” - Invalidate and remove the previous score, record is now [5].
“D” - Add 2 * 5 = 10 to the record, record is now [5, 10].
“+” - Add 5 + 10 = 15 to the record, record is now [5, 10, 15].
The total sum is 5 + 10 + 15 = 30.Example 2:

Input: ops = [“5”,“-2”,“4”,“C”,“D”,“9”,“+”,“+”]
Output: 27
Explanation:
“5” - Add 5 to the record, record is now [5].
“-2” - Add -2 to the record, record is now [5, -2].
“4” - Add 4 to the record, record is now [5, -2, 4].
“C” - Invalidate and remove the previous score, record is now [5, -2].
“D” - Add 2 * -2 = -4 to the record, record is now [5, -2, -4].
“9” - Add 9 to the record, record is now [5, -2, -4, 9].
“+” - Add -4 + 9 = 5 to the record, record is now [5, -2, -4, 9, 5].
“+” - Add 9 + 5 = 14 to the record, record is now [5, -2, -4, 9, 5, 14].
The total sum is 5 + -2 + -4 + 9 + 5 + 14 = 27.Example 3:

Input: ops = [“1”,“C”]
Output: 0
Explanation:
“1” - Add 1 to the record, record is now [1].
“C” - Invalidate and remove the previous score, record is now []

def solution(s:list):
    operator = ['+', 'D', 'C']
    res = []
    for item in s:
        if item in operator:
            if item == '+':
                res.append(sum(res[-2:]))
            if item == 'D':
                res.append(2*res[-1])
            if item == 'C':
                res.pop(-1)
        else:
            res.append(int(item))

    return sum(res)

总结一下

我是菜逼， 最后他才告诉我，第一题是最难的！30分， 第二、第三题是20分；我看了一眼第一题之后就后悔跟他说大话了。
最后 耐着性子，先看了第三题，题目都没读懂的时候就入手写代码，20多分钟左右 终于是写出来了！然后接了一个电话，开始第二题，
过程很艰难，原本不该报错的， 只是最后才发现 是写错变量名了，因为很少接触 TDD 的开发模式, 很不适应 报错信息看着也不够清晰！
不过在最后的一秒钟 有一个括号 不知道删没删掉，再也不说大话了。还是要多做算法题，后面这种思维要多扩展一下！
写文章的时候回顾了一下 还是不敢去看第一题，但是 如果是中文题，我现在觉得后面两道题有点过于简单，或者是我想的太简单了！