一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 590|回复: 7
收起左侧

Weixin 北京面经

[复制链接] |试试Instant~ |关注本帖
storypku 发表于 2017-11-1 23:02:52 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 硕士 全职@Tencent Weixin - 内推 - Onsite |Other在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
作为一股清流,我要贴一下今天面试微信岗位的面试题!求大家赏点大米吧。。。
.1point3acres缃
五道题,时间是1个半小时。有智力题,填空题,编程题……共5道。 还真是俱全。据说微信面试有八轮,这在国内也是罕见的了。看看自己能走多远吧。

话不多说,上面经:

***Attention: 附件跟这个帖子内容一样。***. 1point3acres.com/bbs
. 1point3acres.com/bbs

# Tencent WeiXin Onsite 复盘

### Question 1: 智力题:赛马
##### Description:. more info on 1point3acres.com
  64匹马,每场8赛道赛马。求决出前四名所需的最少比赛场数。(不能计时,但可以根据快慢推理,如A > B && B > C => A > C. more info on 1point3acres.com

##### Solution
- Step 1: 8 * 8 小组赛,每个组决出快慢顺序, 共8场
- Step 2: 冠军争夺战,八个小组的头名参加:设冠军的金牌为A组A1斩获,前四名所在的小组设为A,B,C,D,有A1 > B1 > C1 > D1。共1场。. 鍥磋鎴戜滑@1point 3 acres
- Step 3: 亚/季争夺战:A组2-4名,B组1-3名,C组1-2名 决出前三名。其中前两名分获银牌和铜牌。共1场。
- Step 4: 如果C1未能斩获铜牌,则D1已经确定无缘第四名,第四名由Step 3比赛中的第三名获得。否则D1与其进行一场加赛,决出最终谁是第四名。
- Conclusion: 共需比赛10场或者11场。

### Question 2 N个无序排列的数中的前K大的数.鏈枃鍘熷垱鑷1point3acres璁哄潧
#### Description
- N > 0, N >= K > 0.
- 最快算法的时间复杂度为多少?写出算法。

#### Solution
##### 常规思路: MinHeap, i.e., std::priority_queue in C++ STL
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
- O(nlogn) Time, O(n) Space

```c++
vector<int> topK(vector<int>& nums, unsigned k) {
    vector<int> result;. from: 1point3acres.com/bbs
    if (k == 0) return result;.鐣欏璁哄潧-涓浜-涓夊垎鍦
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    std::priority_queue<int, vector<int>, std::greater<int>> pq;
    for (auto& c : nums) {
        pq.push(c);
        if (pq.size() > k) {
            pq.pop();
        }
    }

    while (!pq.empty()) {
        result.push_back(pq.top());
        pq.pop();
    }
    std::reverse(result.begin(), result.end());
    return result;
}
```

##### BinarySearch

- O(n) Time, O(1) Space

```C++
-google 1point3acresvector<int> topK(vector<int>& nums, int k) {
    int left = INT_MAX, right = INT_MIN;. Waral 鍗氬鏈夋洿澶氭枃绔,
    for (auto& c : nums) {
        left = std::min(left, c);
        right = std::max(right, c);
    }

    while (left < right) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
        int midV = left + (right - left) / 2;
        int count = 0;
        for (auto& c : nums) {. from: 1point3acres.com/bbs
            count += (int)(c >= midV);
        }
        if (k >= count) {
            right = midV;
        } else { // k < count
            left = midV + 1;
        }
    }

    int kthV = left;

    vector<int> result;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
    for (auto& c : nums) {
        if (c >= kthV) {
            result.push_back(c);
        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
    }.鐣欏璁哄潧-涓浜-涓夊垎鍦
    // std::sort(result.begin(), result.end());
    return result;
}
```

### 逆序对的个数
. visit 1point3acres.com for more.
假设有一个数组nums,如果存在 i < j 且 nums > nums[j] 则称为一个逆序对。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
例如, 2 4 3 1 的逆序对为 3:1, 4:3, 4:1, 2:1 共1 + 2 + 1 = 4 对
又如, 2 6 8 9 5 1 的逆序对数为1 + 2 + 2 + 2 + 1 = 8 对. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

编码实现之。

```C++ 错误答案
int countReversePairs(vector<int>& nums) {
    std::stack<int> stk;
    int result = 0;
    for (auto iter = nums.rbegin(); iter != nums.rend(); ++iter) {
        int val = *iter;
        while (!stk.empty() && stk.top() >= val) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
            stk.pop();
        }
        result += stk.size();. from: 1point3acres.com/bbs
        stk.push(val);
    }
    return result;
}
```

~~~
```C++ 正确答案 Leetcode-493

#include <algorithm>
. 1point 3acres 璁哄潧
int sortAndCount(vector<int>::iterator s, vector<int>::iterator e) {
    int n = std::distance(s, e);
    if (n <= 1) return 0;. from: 1point3acres.com/bbs
    auto mid = s + n / 2;
    int result = sortAndCount(s, mid) + sortAndCount(mid, e);
    for (auto i = s, j = mid; i != mid; ++i) {
-google 1point3acres        while (j != e && (*i) > (*j)) {
            ++j;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        }
        result += j - mid;
    }
    std::inplace_merge(s, mid, e);
    return result;
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴}. 1point3acres.com/bbs

int countReversePairs(vector<int>& nums) {
    return sortAndCount(nums.begin(), nums.end());
}

```

#### Question 4: Regular Pattern Matching
- Description: 填空题
假设有通配符"$"表示一个或者多个数字'0'-'9', "*" 匹配任意多个字符,判断模式串和给定字符串是否匹配。

bool match(const string& str, const string& pattern);
.1point3acres缃
```C++. From 1point 3acres bbs
#include <cctype>

bool match(const string& str, const string& pat) {
    int sn = str.size(), pn = pat.size();
    int i = 0, j = 0;
    while (i < sn && j < pn) {
        const auto& c = pat[j];
        switch(c) {. from: 1point3acres.com/bbs
        case '*': {
            j++;
            for (int k = i; k < sn; ++k) {
                if (match(str.substr(k), pat.substr(j))) {
                    return true;
                }
            }
            i++;
        }
        break;

        case '$': {
            if (!isdigit(str)) {
                return false;
            }
            i++; j++;
            int k = i;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            while (k < sn && isdigit(str[k])) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
                if (match(str.substr(k), pat.substr(j))) {
                    return true;
                }
                ++k;
            }
        }
        break;
.1point3acres缃
        default: {.1point3acres缃
            if (str != pat[j]) {
                return false;.鐣欏璁哄潧-涓浜-涓夊垎鍦
            }
            i++;. 1point3acres.com/bbs
            j++;.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }
        break;.1point3acres缃
        }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
    }

    while (j < pn) {
        if (pat[j] == '*') {
            j++;
        }
    }
. more info on 1point3acres.com
    return j == pn && i == sn;. Waral 鍗氬鏈夋洿澶氭枃绔,
}
```  

#### Question 5: Reverse Linked List
- Leetcode 206


. more info on 1point3acres.com
. Waral 鍗氬鏈夋洿澶氭枃绔,

Weixin.Onsite.2017.11.01.tar.gz

210 Bytes, 阅读权限: 50, 下载次数: 0, 下载积分: 大米 -1 升

微信面经

评分

1

查看全部评分

huolongguo 发表于 2017-11-1 23:07:20 | 显示全部楼层
希望楼主拿到offer!
回复 支持 反对

使用道具 举报

wendingp 发表于 2017-11-1 23:08:33 | 显示全部楼层
code 就不用贴了吧...
回复 支持 反对

使用道具 举报

 楼主| storypku 发表于 2017-11-1 23:12:36 | 显示全部楼层
wendingp 发表于 2017-11-1 23:08
code 就不用贴了吧...

嗯,自己复盘写的看的。面完回忆重写了一遍。. 1point 3acres 璁哄潧
回复 支持 反对

使用道具 举报

eyannnnn 发表于 2017-11-2 11:46:53 | 显示全部楼层
楼主是怎么投的呀~
回复 支持 反对

使用道具 举报

cheese_harry 发表于 2017-11-2 12:07:20 | 显示全部楼层
这个是online test?
回复 支持 反对

使用道具 举报

 楼主| storypku 发表于 2017-11-2 14:27:02 | 显示全部楼层
eyannnnn 发表于 2017-11-2 11:46
楼主是怎么投的呀~

找人内推的。。。
回复 支持 反对

使用道具 举报

 楼主| storypku 发表于 2017-11-2 14:27:22 | 显示全部楼层
cheese_harry 发表于 2017-11-2 12:07
. visit 1point3acres.com for more.这个是online test?

不是,onsite
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-1-19 23:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表