字节跳动2018校招后端方向(第二批)

3.7
(3)

前言

从今天开始每天晚上转战牛客网练习啦,这次做题体验还可以,考察了模拟、滑动窗口、动态规划。对于模拟和滑动窗口是必拿选项,对于动态规划呢,则是诸神之战,与我小渣渣无缘(不过以后也要多多刷才行)。而对于设计题则考察了一个二分查找挑毛病,这里考察的点也是实际中最基础的问题,二分查找虽然简单,但是极其容易出错,非常容易刷掉一批基础不是很牢固的同学(想当初大三面试就被问了二分查找,当时的窘态暴露无遗…)好在掌握了二分的左闭右开、上下界等关键点,这道题改错十分容易(就是套模板),此外当掌握左闭右开和上下界的知识点呢,可以让你照着你的模板写出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全家桶来说升级扩容也是很方便的……但是具体这道题要来如何回答,什么样的答案才让面试官满意,回头还要琢磨一下系统设计相关问题。

这篇文章是否对您有帮助?

请您为我打分吧!

平均分数 3.7 / 5. 投票数量: 3

发表评论

电子邮件地址不会被公开。 必填项已用*标注