腾讯微信事业部暑期实习生面试

发表于 2020-03-11 更新于 2026-04-28 分类于 interview Disqus：

一面

time: 2020-03-11 10:28:43

上周HR联系沟通了下意向工作城市，但是没约具体面试时间。

昨晚8点半忽然接到广东深圳的电话，问是否方便，直接开始了面试（惊不惊喜，刺不刺激？）。面试官网还不太好，中间出了不少问题。比如手撕代码时，对方网站内容不能及时刷新。

计算机基础

分布式、深度学习

BN层，dropout。如何计算？
BN: mean, valence。

单机训练和多机训练区别。

多机训练时，如何把各个单机得到的loss reduce下。

数据并行训练和模型并行训练。

阅读全文 »

阿里巴巴蚂蚁金服后端开发暑期实习生

发表于 2020-03-09 更新于 2026-04-28 分类于 interview Disqus：

一面

time: 2020-03-09 16:45:44

简历经历

对各段项目的介绍。根据项目随时提问，如RESTful API, SOAP之类的知识。

计算机基础

HashMap 的实现

Hash值如何映射到桶中？？？？
hashcode和equals函数的要求（修改equals为什么必须要修改hashcode)
扩容机制和均摊复杂度

Java 开箱和装箱机制。（一开始没反应过来，说不会。在面试官的提醒下，基础类型和对象类型的关系，我才会了。因为之前看的都是英文材料，box和unbox，对中文不是很敏感。）

算法题

编辑距离的递推公式

阅读全文 »

LeetCode weekly contest 179

发表于 2020-03-08 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (3)	Q2 (4)	Q3 (5)	Q4 (6)
539 / 6242	YoungForest	18	1:09:53	0:05:43	0:13:09	0:24:01	1:04:53 1

1374. Generate a String With Characters That Have Odd Counts

如果n为偶数，则一个a，剩下都为b；
如果n为奇数，则全为a.

时间复杂度: O(n),
空间复杂度: O(n).

之前写代码从来不过重注意输入的合法性检查。因为Leetcode本身对输入有限制。但是现实面试的时候，面试官有时会关注你对输入的预设和检查，毕竟实际生产过程中的输入永远是无法预料的。

class Solution {
public:
    string generateTheString(int n) {
        if (n <= 0) return "";
        string ans;
        if (n % 2 == 1) {
            ans.append(n, 'a');
        } else {
            ans.push_back('a');
            ans.append(n - 1, 'b');
        }
        return  ans;
    }
};

1375. Bulb Switcher III

观察有：蓝色灯永远是前连续个，意味着蓝色灯的状态可以用index最高的灯表示，同时这个index是单调非递减的。所以只需要比较它和最大亮着的灯的下标是否相同即可。且每次亮灯都试图增大这个blue_index。

时间复杂度: O(N),
空间复杂度: O(N).

class Solution {
public:
    int numTimesAllBlue(vector<int>& light) {
        int max_turn_on_index = -1;
        int blue_index = -1;
        const int n = light.size();
        vector<bool> turn_on(n);
        int ans = 0;
        for (int i : light) {
            turn_on[i - 1] = true;
            max_turn_on_index = max(max_turn_on_index, i - 1);
            while (blue_index + 1 < n && turn_on[blue_index +  1] == true) {
                ++blue_index;
            }
            if (blue_index == max_turn_on_index)
                ++ans;
        }
        return ans;
    }
};

阅读全文 »

LeetCode biweekly contest 21

发表于 2020-03-08 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (4)	Q2 (4)	Q3 (5)	Q4 (6)
175 / 4729	YoungForest	19	1:05:07	0:21:38	0:39:43	0:50:40	1:05:07

整体难度不大，尤其是后2题并没有该有的难度。

1370. Increasing Decreasing String

直接模拟构造结果字符串的过程即可。这里寻找字符串的过程可以使用二分查找，因为原始字符串需要更新，所以使用二叉查找树这一数据结构较好。

时间复杂度: O(N * log N),
空间复杂度: O(N).

class Solution {
public:
    string sortString(string s) {
        string ans;
        multiset<char> container;
        for (char c : s) {
            container.insert(c);
        }
        while (!container.empty()) {
            char smallest = *container.begin();
            container.erase(container.begin());
            ans.push_back(smallest);
            decltype(container.begin()) it;
            while ((it = container.upper_bound(smallest)) != container.end()) {
                ans.push_back(*it);
                smallest = *it;
                container.erase(it);
            }
            if (!container.empty()) {
                char largest = *(prev(container.end()));
                container.erase(prev(container.end()));
                ans.push_back(largest);
                while ((it = container.lower_bound(largest)) != container.begin()) {
                    ans.push_back(*prev(it));
                    largest = *prev(it);
                    container.erase(prev(it));
                }
            }
        }
        return ans;
    }
};

1371. Find the Longest Substring Containing Vowels in Even Counts

观察有：奇数减奇数等于偶数，偶数减偶数等于偶数。所以问题可以转化为，寻找最左边计数为奇数（或偶数）的位置。因为有5个元音字母，分奇偶，共32种状态。

时间复杂度: O(N),
空间复杂度: O(1).

class Solution {
public:
    int findTheLongestSubstring(string s) {
        vector<int> left_state(32, -2);
        left_state[0] = -1;
        auto code = [&](unordered_map<char, int>& m) -> unsigned int {
            const static vector<char> position = {'a', 'e', 'i', 'o', 'u'};
            unsigned  int ans = 0;
            for (unsigned  int i = 0; i < position.size(); ++i) {
                if  (m[position[i]] % 2 == 1) {
                    ans |= (1 << i);
                }
            }
            return ans;
        };
        unordered_map<char, int> m;
        int ans = 0;
        for (int i = 0; i < s.size(); ++i) {
            ++m[s[i]];
            auto c = code(m);
            if (left_state[c] != -2) {
                ans = max(ans, i - left_state[c]);
            } else {
                left_state[c] = i;
            }
        }
        return ans;
    }
};

阅读全文 »

阿里钉钉服务器开发暑期实习生面试

发表于 2020-03-04 更新于 2026-04-28 分类于 interview Disqus：

通过钉钉电话视频面试，手撕代码通过阿里在线平台完成。

算法题2道：

1. 实现一个双向链表的数据结构。

2. twoSum。寻找数组中2数和等于target的下标。

难度属于LeetCode Easy吧。但是面试时，需要自己和面试官询问沟通好理解题目。并且面试官很注重代码的整洁和效率。比如函数参数的检查，实现本身的预设。

//评测题目: 实现一个简单的双向链表，要求完成 node和list的构造函数，以及 list类的void push_back(node*), void remove(node*) 方法

class node{
public:
	node* prev;
	node* next;

public:
    node() {
      prev = nullptr;
      next = nullptr;
    }
};

class list{
private:
	node* head;
	node* tail;
public:
	list() {
      head = nullptr;
      tail = nullptr;
    }
	
	void push_back(node* n) {
      // 假设n不在list中
    	if (n) {
          if (tail) {
          	tail->next = n;
          } else {
            head = n;
          }
          n->prev = tail;
          tail = n;
        }
    }
	void remove(node* n) {
      if (n == nullptr) return;
      auto current = head;
      while (current) {
        if (current == n) {
          // find
          if (current->prev && current->next) {
            auto p = current->prev;
            auto n = current->next;
            p->next = n;
            n->prev = p;
          } else if (current->prev) {
            tail = current->prev;
            tail->next = nullptr;
            current->prev = nullptr;
          } else if (current->next) {
            head = current->next;
            head->prev = nullptr;
            current->next = nullptr;
          } else {
            head = nullptr;
            tail = nullptr;
          }
          break;
        }
        current = current->next;
      }
      
    }
};

//给定一个vecotr<int>v和一个目标target，找到v中两个数字的和等于target，返回数字在原数组中的下标（多个解的返回任意一个即可），无解返回空vector。
//Example:  v=[7,11,2,15],target=9,
//因为nums[0]+nums[2]=7+2=9, 
//return[0,2].
vector<int> helper(vector<int>& v,int target) {
	vector<int> copy = v;
    sort(copy.begin(), copy.end());
    int left = 0, right = v.size() - 1;
    while (left < right) {
        int current_sum = copy[left] + copy[right];
    	if (current_sum == target) {
          return {copy[left], copy[right]};
        } else if (current_sum < target) {
          ++left;
        } else {
          --right;
        }
    }
    return {};
}
vector<int> twoSum(vector<int>& v,int target) {
    if (v.size() <= 1) return {};
	auto values = helper(v, target);
  	if (values.empty()) return {};
    vector<int> ans(2);
    int index =  0;
  	
      if (values[0] == values[1]) {
        for (int i = 0; i < v.size(); ++i) {
          if (v[i]  == values[0])  {
            ans[index] = i;
            ++index;
            if (index == 2)
              break;
          }
        }
      } else {
        for (int i = 0; i < v.size(); ++i) {
          if (v[i] == values[0]) {
            ans[0] = i;
          } else if (v[i] == values[1]) {
            ans[1] = i;
          }
        }
      }
    }
  
    return ans;
}

我的主语言是C++，所以问了很多C++相关的题目。

从我的简历里，看了我的GitHub主页。询问了最想介绍的项目。我介绍了自己大三时实现的编译器。然后询问了编译的一些过程和数据结构，如词法分析、语法分析、中间代码生成、目标代码生成、优化，符号表、DAG图优化等。

C++中输入>>和模版嵌套时’>>在编译时如何区分。我答应该是语法分析时就可以区别开。然后聊了些这个故事的历史，之前模版的>>必需写成> >`才能编译通过。

C++ HashMap容器的实现，和hash值如何映射到桶中。
STL 中vector的扩容实现。
new 和 malloc的区别。
move语义和右值引用。
weak_ptr, shared_ptr, unique_ptr的区别。

阅读全文 »

字节跳动暑期实习广告系统后端开发面试

发表于 2020-02-27 更新于 2026-04-28 分类于 interview Disqus：

HashMap
数据库
- 索引、优化、事务
- 聚簇索引和非聚簇索引
并发编程
网络编程，RPC
算法题:
- 编辑距离

算法题问了一道计算编辑距离(Levenshtein Distance)的问题。编辑距离的问题恰好我在之前度《图解算法》的时候有所涉及，用DP解决即可。但本题目稍微复杂度写，需要在很多字符串中，寻找距离最近的字符串。可以理解为"Fuzzy matching"。
题面大概为：

莱文斯坦距离，又称 Levenshtein 距离，是编辑距离的一种。指两个字串之间，由一个转成另一个所需的最少编辑操作次数。
允许的编辑操作包括：
插入一个字符
删除一个字符
将一个字符替换成另一个字符
需要你编写一个程序，实现以下功能：
给定一个字符串集合 S 以及一个模板串 P，从 S 中找出与 P 莱文斯坦距离最小的字符串 T，输出 T 以及其对应的编辑距离 D。如果 S 中出现多个满足条件的字符串，则取按字典序排列的第一个。

并没有想到很好的解法，暴力解法的话, 比较所有字符串和P的距离时间复杂度为: O(P.size() * sum(S_i.size()).

后在网上搜索解法，并不难找到。利用Trie以避免不同字符串的DP重复的计算，时间复杂度为: O(P.size() * Trie的节点数). 虽然最坏时间复杂度没有变好，但是实实在在的优化。应该这就是面试官想要的解法了。

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

struct Node {
    array, 26> children;
    vector distance;
    Node() = delete;
    Node(int n) {
        distance.resize(n);
    }
};

pair solve(const string& target, const vector& s) {
    const int k = target.size() + 1;
    auto root = make_shared(k);
    for (int i = 0; i distance.size(); ++i) {
        root->distance[i] = i;
    }
    int ans_distance = 0x3f3f3f3f,  ans_index = -1;
    for (int j = 0; j < s.size(); ++j) {
        const string& str = s[j];
        auto current = root;
        // cout << endl << "debug: " << str << endl;
        int distance_from_empty = 0;
        for (char c : str) {
            if (current->children[c - 'a'] == nullptr) {
                current->children[c - 'a'] = make_shared(k);
                auto next_current = current->children[c - 'a'];
                next_current->distance[0] = distance_from_empty;
                for (int i = 1; i < k; ++i) {
                    if (c == target[i - 1]) {
                        next_current->distance[i] = current->distance[i - 1];
                    } else {
                        next_current->distance[i] = min({
                            current->distance[i - 1],
                            current->distance[i],
                            next_current->distance[i - 1]
                        }) + 1;
                    }
                    // cout distance[i] << " ";
                }
                // cout << endl;
            }
            current = current->children[c - 'a'];
            ++distance_from_empty;
        }
        if (current->distance[k - 1] < ans_distance) {
            ans_distance = current->distance[k - 1];
            ans_index = j;
        } else  if (current->distance[k - 1] == ans_distance) {
            if (s[ans_index] > s[j])
                ans_index = j;
        }
    }
    return {ans_distance, s[ans_index]};
}

int main() {
    string P;
    cin >> P;
    int N;
    cin >> N;
    vector S(N);
    for (int i = 0; i < N; ++i) {
        cin >> S[i];
    }
    auto ans = solve(P, S);
    cout << ans.first << endl;
    cout << ans.second << endl;
    return 0;
}

阅读全文 »

LeetCode weekly contest 177

发表于 2020-02-23 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (4)	Q2 (5)	Q3 (5)	Q4 (6)
333 / 6106	YoungForest	20	1:04:22	0:25:00	0:33:40	0:43:21	0:59:22 1

手速和bug-free的场。

1360. Number of Days Between Two Dates

计算2个日期间的差值。本来想着手算来着，但写起来太复杂了。后来果断放弃，投机取巧用了Python日期处理的库函数。

时间复杂度: O(1),
空间复杂度: O(1).

from datetime import date

class Solution:
    def daysBetweenDates(self, date1: str, date2: str) -> int:
        delta = date.fromisoformat(date1) - date.fromisoformat(date2)
        return abs(delta.days)

1361. Validate Binary Tree Nodes

观察有，合法的二叉树为：

有且仅有一个节点没有父节点
剩下节点均只有一个父节点
没有孤儿，既没有父亲、也没有child（在节点数大于1的情况下）

第3个要求比较难想到，甚至是OJ一开始也是错的。我也就将错就错通过了。感谢votrubac的提示。

阅读全文 »

LeetCode biweekly contest 20

发表于 2020-02-23 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (3)	Q2 (4)	Q3 (5)	Q4 (6)
233 / 4347	YoungForest	18	0:41:39	0:03:32	0:13:58 1	0:24:13	0:31:39 1

本次比赛题目比较简单，又是一次手速和bug-free的比拼。
真的是错过比赛半年，连人数较少的双周赛都进不了前200了，吓～

1356. Sort Integers by The Number of 1 Bits

利用C++标准库中的排序函数和lambda表达式。

时间复杂度: O(n log n),
空间复杂度: O(1).

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), [](const auto& a, const auto& b) -> bool {
            auto aa = __builtin_popcount(a);
            auto bb = __builtin_popcount(b);
            if (aa == bb) {
                return a < b;
            } else {
                return aa < bb;
            }
        });
        return arr;
    }
};

1357. Apply Discount Every n Orders

考察对数据结构的熟悉程度。根据题意直接实现即可。
因为读题不仔细，把discount的定义搞错了（是减价多少，而不是剩下多少），导致了一次错误提交。

时间复杂度：O(product.length),
空间复杂度：O(getBill.length).

class Cashier {
    unordered_map<int, int> m;
    int d;
    int nn;
    int index = 0;
public:
    Cashier(int n, int discount, vector<int>& products, vector<int>& prices) {
        d = discount;
        nn = n;
        for (int i = 0; i < products.size(); ++i) {
            m[products[i]] = prices[i];
        }
        index = 0;
    }
    
    double getBill(vector<int> product, vector<int> amount) {
        ++index;
        bool discount = false;
        if (index == nn) {
            index = 0;
            discount = true;
        }
        double ans = 0;
        for (int i = 0; i < product.size(); ++i) {
            ans += amount[i] * m[product[i]];
        }
        if (discount)
            ans *= 1 - d / 100.0;
        return ans;
    }
};

/**
 * Your Cashier object will be instantiated and called as such:
 * Cashier* obj = new Cashier(n, discount, products, prices);
 * double param_1 = obj->getBill(product,amount);
 */

阅读全文 »

2019年终总结与 2020新年展望

发表于 2020-02-20 更新于 2026-04-28 分类于 dairy Disqus：

转发自我的博客

2020年注定对我是一个不平凡的一年，主要原因在于我面临着毕业和求职的关口。这一关口是我近2年面临的最重要的挑战和任务，我也为之筹备良久，期待可以厚积薄发。然而事实却并不如愿。

2019年工作回顾

在去年的规划中，我写了自己对2019年的规划和畅想。

LeetCode 刷题任务超额完成，如今已经刷了800+道了。

C的学习虽然没有按照预期学完C Primer，但是基本学完了 Effective C系列和 C Standard Library。也算是成为我的主语言了。（最近在搞Rust，学完C后学Rust有很多好处，2者有许多共性。不过这次折腾更多的是兴趣使然，不会改变C是我的主语言的身份。
CTCI 基本看完。
其他的书就几乎没有进展了，愧疚。

实际的面试，3月份参加了字节跳动广告系统的后端开发实习生面试，因为实习时间原因没过。8月底参加了为期一周的字节跳动夏令营的工程组。这个夏令营我只在6月份参加笔试，由于笔试成绩还可以，免了面试。11份收到参加A day with Google的邀请，但由于我已人在比利时，当然无法参加。好是遗憾。

大厂的实习依旧是0。上半年在商汤实习了半年，得到了一些技术上的历练。但总体还说不是很满意。首先，实习对课题研究起了负面作用，并没有之前预计的两者兼顾。其次，商汤的环境也不大令我满意。科研实力业界有目共睹，但工程技术方面的实力着实一般，内部项目管理也相当混乱。最后，商汤本身是个中厂。规模和产品、技术和快手都差一个档次。

强身健体方面更是不进则退，办了的健身卡，一年也去了只有大约20次。

去年的OKR完成度60%吧。

阅读全文 »

LeetCode weekly contest 176

发表于 2020-02-16 更新于 2026-04-28 分类于 LeetCode Disqus：

Rank	Name	Score	Finish Time	Q1 (3)	Q2 (5)	Q3 (5)	Q4 (6)
306 / 8105	YoungForest	19	1:36:07	0:02:47	0:23:09	0:54:53 1	1:26:07 1

本次比赛在最后关头终于AC，也是极其的惊现刺激。自从加入中国区的同学之后，我周赛的排名都很难进入前200了。比如本次就从229掉到了306。不得不承认，我国内卷之严重呀。

排名落后的主要原因在于第3题花费了很多时间调试和试，差点最后一题都没时间实现了。最近缺少练习也导致debug能力和一遍bug-free的能力急剧下降。

1351. Count Negative Numbers in a Sorted Matrix

利用横竖都是有序的条件，可以实现O(m + n)的计数。
和search-a-2d-matrix-ii类似。

时间复杂度: O(m + n),
空间复杂度: O(1).

class Solution {
public:
    int countNegatives(vector<vector<int>>& grid) {
        int ans = 0;
        const int m = grid.size();
        const int n = grid[0].size();
        int row = 0, col = n - 1;
        while (row < m && col >= 0) {
            if (grid[row][col] < 0) {
                ans += m - row;
                --col;
            } else {
                ++row;
            }
        }
        return ans;
    }
};

1352. Product of the Last K Numbers

记录最后0的位置和累计的乘积。判断最后K个数中是否有0，如果没有的话，借助最后的乘积除以倒数第k + 1个乘积即可。

时间复杂度:

阅读全文 »