字节跳动2018校招后端方向（第二批）

Posted on by Dennis

前言

从今天开始每天晚上转战牛客网练习啦，这次做题体验还可以，考察了模拟、滑动窗口、动态规划。对于模拟和滑动窗口是必拿选项，对于动态规划呢，则是诸神之战，与我小渣渣无缘（不过以后也要多多刷才行）。而对于设计题则考察了一个二分查找挑毛病，这里考察的点也是实际中最基础的问题，二分查找虽然简单，但是极其容易出错，非常容易刷掉一批基础不是很牢固的同学（想当初大三面试就被问了二分查找，当时的窘态暴露无遗…）好在掌握了二分的左闭右开、上下界等关键点，这道题改错十分容易（就是套模板），此外当掌握左闭右开和上下界的知识点呢，可以让你照着你的模板写出16中二分算法，面试官怎么考都不怕。

而对于系统设计题，由于我这方面还不是太了解，得多多看一些相关系统设计一类的书才是。

第一题

为了不断优化推荐效果，今日头条每天要存储和处理海量数据。假设有这样一种场景：我们对用户按照它们的注册时间先后来标号，对于一类文章，每个用户都有不同的喜好值，我们会想知道某一段时间内注册的用户（标号相连的一批用户）中，有多少用户对这类文章喜好值为k。因为一些特殊的原因，不会出现一个查询的用户区间完全覆盖另一个查询的用户区间(不存在L1<=L2<=R2<=R1)。

输出描述:
输出：一共q行，每行一个整数代表喜好值为k的用户的个数


输入例子1:
5
1 2 3 3 5
3
1 2 1
2 4 5
3 5 3


输出例子1:
1
0
2


例子说明1:
样例解释:
有5个用户，喜好值为分别为1、2、3、3、5，
第一组询问对于标号[1,2]的用户喜好值为1的用户的个数是1
第二组询问对于标号[2,4]的用户喜好值为5的用户的个数是0
第三组询问对于标号[3,5]的用户喜好值为3的用户的个数是2

解题思路：这道题有两种方案，一种是把每个用户存储到一个列表中，然后根据系统的输入进行for循环求解，时间复杂度是平方。但是这种接法不是最高效的，在本题中，我们使用了一个Map用来存取所有偏好值相同的用户下标，之后对用户下标做查询，由于用户下标是有序的，因而可以考虑用二分搜索来进行求解，不过在这道题中我直接使用了线性查找，时间也足够。

还有一个问题是，当我使用C++牛客网的C++11编译的时候，内存超限，但是用C++14编译的时候却直接AC，不太懂这是为什么…？C++14优化得好吗？

最初想法：第一眼看到这道题的时候，看到了区间，以为是区间查找，要用到树状数组，后来发现一点都用不上....

#include<iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int main() {
    int n;  cin>>n;
    map<int, vector<int>> v;
    for(int i = 1; i <= n; ++i) {
        int tmp; cin>>tmp;
        v[tmp].push_back(i);
    }
    int m;
    cin>>m;
    while(m--) {
        int a, b, t;
        cin>>a>>b>>t;
        int cnt = 0;
        for(int i = 0; i < v[t].size(); ++i) {
            if(v[t][i] > b) break;
            if(a <= v[t][i] && v[t][i] <= b) ++cnt;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

第二题

作为一个手串艺人，有金主向你订购了一条包含n个杂色串珠的手串——每个串珠要么无色，要么涂了若干种颜色。为了使手串的色彩看起来不那么单调，金主要求，手串上的任意一种颜色（不包含无色），在任意连续的m个串珠里至多出现一次（注意这里手串是一个环形）。手串上的颜色一共有c种。现在按顺时针序告诉你n个串珠的手串上，每个串珠用所包含的颜色分别有哪些。请你判断该手串上有多少种颜色不符合要求。即询问有多少种颜色在任意连续m个串珠中出现了至少两次。

输入描述:
第一行输入n，m，c三个数，用空格隔开。(1 <= n <= 10000, 1 <= m <= 1000, 1 <= c <= 50) 接下来n行每行的第一个数num_i(0 <= num_i <= c)表示第i颗珠子有多少种颜色。接下来依次读入num_i个数字，每个数字x表示第i颗柱子上包含第x种颜色(1 <= x <= c)


输出描述:
一个非负整数，表示该手链上有多少种颜色不符需求。


输入例子1:
5 2 3
3 1 2 3
0
2 2 3
1 2
1 3


输出例子1:
2


例子说明1:
第一种颜色出现在第1颗串珠，与规则无冲突。
第二种颜色分别出现在第 1，3，4颗串珠，第3颗与第4颗串珠相邻，所以不合要求。
第三种颜色分别出现在第1，3，5颗串珠，第5颗串珠的下一个是第1颗，所以不合要求。
总计有2种颜色的分布是有问题的。 
这里第2颗串珠是透明的。

使用滑动窗口处理，这道题的难度在于理解题意，并编程实现。

#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

int main() {
    int n, m, c;
    cin>>n>>m>>c;
    vector<vector<int>> v(n, vector<int>(c, 0));
    vector<int> window(c, 0);
    set<int> s;
    for(int i = 0; i < n; ++i) {
        int t; cin>>t;
        while(t--) {
            int q; cin>>q;
            v[i][q-1]++;
        }
    }
    //初始化窗口
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < c; ++j) {
            window[j] += v[i][j];
        }
    }
    
    for(int i = 0; i < n; ++i) {
        //检查是否有超出阈值的
        for(int j = 0; j < c; ++j)
            if(window[j] >= 2) s.insert(j);
        if(i == n - 1) break;
        //添加下一个元素 下一个元素为 (i + c) % n
        int next =  (i + m) % n;
        for(int j = 0; j < c; ++j) window[j] += v[next][j];
        //移除当前的元素
        for(int j = 0; j < c; ++j) window[j] -= v[i][j];
    }
    cout<<s.size()<<endl;
    return 0;
}

第三题

字符串S由小写字母构成，长度为n。定义一种操作，每次都可以挑选字符串中任意的两个相邻字母进行交换。询问在至多交换m次之后，字符串中最多有多少个连续的位置上的字母相同？

输入描述:
第一行为一个字符串S与一个非负整数m。(1 <= |S| <= 1000, 1 <= m <= 1000000)


输出描述:
一个非负整数，表示操作之后，连续最长的相同字母数量。


输入例子1:
abcbaa 2


输出例子1:
2


例子说明1:
使2个字母a连续出现，至少需要3次操作。即把第1个位置上的a移动到第4个位置。
所以在至多操作2次的情况下，最多只能使2个b或2个a连续出现。

这道题最开始想到用搜索，但是看到数据规模是1000000，如果每一次交换就新开一个栈的话，肯定会爆栈。因而这道题一定是要用到动态规划来处理的，但是怎么处理…emmmm明天学习一下状态转移方程。

第四题

以下函数使用二分查找搜索一个增序的数组，当有多个元素值与目标元素相等时，返回最后一个元素的下标，目标元素不存在时返回-1。请指出程序代码中错误或不符最佳实践的地方（问题不止一处，请尽量找出所有你认为有问题的地方）

int BinarySearchMax(const std::vector<int>& data, int target)

{

   int left = 0;

   int right = data.size();

   while (left < right) {

       int mid = (left + right) / 2;

       if (data[mid] <= target)

           left = mid + 1;

       else

           right = mid - 1;

   }

   if (data[right] == target)

       return right;

   return -1;

}

这道题就是套模板嘛，如果搞清楚了上下界很容易修改，以下给出两种方案。

int BinarySearchMax(const std::vector<int>& data, int target)

{

   int left = 0;

   int right = data.size();

   while (left < right) {

       int mid = (left + right) / 2;

       if (data[mid] < target)

            left = mid;

       else

            right = mid - 1;

   }

   if (data[left] == target)

       return left;

   return -1;

}
int BinarySearchMax(const std::vector<int>& data, int target)

{

   int left = 0;

   int right = data.size() - 1 ;

   while (left <= right) {

       int mid = (left + right) / 2;


       if(data[mid] == target) return mid;
       if (data[mid] < target)

            left = mid + 1;

       else

            right = mid - 1;

   }



   return -1;

}

问题5

【设计题】今日头条会根据用户的浏览行为、内容偏好等信息，为每个用户抽象出一个标签化的用户画像，用于内容推荐。用户画像的存储、高并发访问，是推荐系统的重要环节之一。现在请你给出一个用户画像存储、访问方案，设计的时候请考虑一下几个方面：

  1. 用户画像如何存储

  2. 如何保证在线高并发、低延迟地访问

  3. 机器宕机、负载均衡问题

  4. 如果用户增长很快，在你的方案下，该如何做扩容

从架构上来说，肯定是要用Hadoop全家桶了，对于用户画像，可以考虑使用Hbase或Hive来进行存储，为了保证在线高并发低延迟可以考虑使用非阻塞异步IO一类的东西进行优化？而对于机器宕机、负载均衡问题可以考虑使用主从备份等？对于Hadoop全家桶来说升级扩容也是很方便的……但是具体这道题要来如何回答，什么样的答案才让面试官满意，回头还要琢磨一下系统设计相关问题。

发表回复

您的电子邮箱地址不会被公开。