大众点评算法实习生电面

Posted on Edited on In Views: Disqus:

Dianping (the Chinese version of Yelp) tele-interviewed me today. This article records the process and content of the interview.

今天晚上参加了大众点评的一个电话面试，本文记录了面试的内容。

今天参加了大众点评的一个电话面试。

面试的内容比较简单，先是自我介绍，介绍一下自己的经历和做过的项目，面试官对我的实体链接项目很感兴趣，然后我又讲了半小时实体链接。。。

然后是限时编程测试，题目是三数之和，给定一个整型数组 array 和一个目标数 target，在 array 中找到三个整数 a, b, c，使得 a + b + c = target，返回所有这样的 a, b, c 的下标，三者下标不同。

我一上来想的是暴力法，用三个指针遍历数组，时间复杂度为 O(n^3)。

[C++ Code]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:    
    /**
     * @param numbers : Give an array numbers of n integer
     * @param target : Give an integer
     * @return : Find all unique triplets in the array which gives the sum of target.
     */
    vector<vector<int> > threeSum(vector<int> &nums, int target) {
        int size = nums.size();
        int i, j, k;
        vector<vector<int> > result;

        for (i=0; i<size-2; i++) {
            for (j=i+1; j<size-1; j++) {
                for (k=j+1; k<size; k++) {
                    if (nums[i] + nums[j] + nums[k] == target) {
                        vector<int> temp;
                        temp.push_back(i);
                        temp.push_back(j);
                        temp.push_back(k);

                        // 去重
                        if(find(result.begin(), result.end(), temp) == result.end()) {
                            result.push_back(temp);
                        }
                    }
                }
            }
        }
        return result;
    }
};

后来经过面试官提醒，可以先将数组进行排序，改进了一下算法，对于数组中的每个元素，用两个指针从数组的两端开始夹逼，这样时间复杂度降到 O(n^2)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:    
    /**
     * @param numbers : Give an array numbers of n integer
     * @param target : Give an integer
     * @return : Find all unique triplets in the array which gives the sum of target.
     */
    vector<vector<int> > threeSum(vector<int> &nums, int target) {
        int size = nums.size();
        sort(nums.begin(), nums.end());    // ascending order
        int i, j, k;
        vector<vector<int> > result;
          
        for (i=0; i<size-2; i++) {
            int j=i+1, k=size-1;

            while (j < k) {
                if (nums[i] + nums[j] + nums[k] == target) {
                    vector<int> temp;
                    temp.push_back(i);
                    temp.push_back(j);
                    temp.push_back(k);

                    // 去重
                    if(find(result.begin(), result.end(), temp) == result.end()) {
                        result.push_back(temp);
                    }

                    j++;
                    k--;
                }
                else if (nums[i] + nums[j] + nums[k] > target) {
                    k--;
                }
                else {
                    j++;
                }
            }
        }
        return result;
    }
};