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

2023-12-04 17:38

本文主要是介绍字节跳动2018校招后端方向(第二批)笔试题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

[编程题]手串

时间限制:C/C++ 1秒,其他语言2秒

空间限制:C/C++ 64M,其他语言128M

作为一个手串艺人,有金主向你订购了一条包含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 <bits/stdc++.h>
using namespace std;
int main(){int n, m, c, t, x, s=0, a[51], b[51];bool mp[51]={false};memset(a, -1, sizeof(a));scanf("%d%d%d", &n, &m, &c);for(int i=0;i<n;i++){scanf("%d", &t);for(int j=0;j<t;j++){scanf("%d", &x);if(mp[x])continue;// 有问题的颜色不再判断if(a[x]!=-1 && i-a[x]<m){s++; // 第二次出现 比上次 出现 小于mmp[x] = true;}if(a[x]==-1)b[x] = i;//首次出现a[x] = i;}}for(int i=1;i<=c;i++){if(mp[i] || b[i]==a[i])continue;//有问题 和 只出现一次的就不再考虑if(n-a[i]+b[i] < m)s++;// 第一次出现 和 最后一次出现的 间隔 是不是 小于 m }printf("%d\n", s);return 0;
}

[编程题]用户喜好

时间限制:C/C++ 3秒,其他语言6秒

空间限制:C/C++ 256M,其他语言512M

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

输入描述:
输入: 第1行为n代表用户的个数 第2行为n个整数,第i个代表用户标号为i的用户对某类文章的喜好度 第3行为一个正整数q代表查询的组数 第4行到第(3+q)行,每行包含3个整数l,r,k代表一组查询,即标号为l<=i<=r的用户中对这类文章喜好值为k的用户的个数。 数据范围n <= 300000,q<=300000 k是整型

输出描述:
输出:一共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

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int user = sc.nextInt();Map<Integer, List<Integer>> map = new HashMap<>();for (int i = 1; i <= user; i++) {int fav = sc.nextInt();if (!map.containsKey(fav)) {List<Integer> list = new ArrayList<>();list.add(i);map.put(fav, list);} else {List<Integer> list = map.get(fav);list.add(i);}}int group = sc.nextInt();for (int i = 0; i < group; i++) {int a = sc.nextInt();int b = sc.nextInt();int k = sc.nextInt();int sum = 0;List<Integer> list = map.get(k);if (list != null) {for (int j = 0; j < list.size(); j++) {if (list.get(j)>=a&&list.get(j)<=b) {sum++;}}}System.out.println(sum);}}
}

[编程题]字母交换

时间限制:C/C++ 1秒,其他语言2秒

空间限制:C/C++ 32M,其他语言64M

【编码题】字符串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连续出现。

/*
先是上面那位老哥的分析:
提取出相同字符的位置,比如ababa中a的位置为(0,2,4),b的位置为(1,3)。对每个位置向量用动态规划求解。
字符a的位置数组为arr,动态规划过程:
dp(i,j)表示字符a第i个位置到第j个位置的字符要全部相邻,至少要用需要多少次交换。
1. i==j时,表示一个字符,不用交换,dp(i,j)为0;
2. i+1==j时,表示两个字符,位置相差arr[j]-arr[i];
3.其他情况,dp(i,j) = dp(i+1,j-1) + arr[j]-arr[i] - (j - i);思路:
首先思考下第3种转移。因为[i+1,j-1]之间已经成了一个连续的段,所以左右两边都是往中间靠的,不管
怎么靠,交换的次数肯定都一样。然后就非常简单了
*/
#include<bits/stdc++.h>
using namespace std;
#define N 1005
int dp[N][N];//dp[i][j]表示第i个某种字符和相同的第j个字符成为一个连续段的花费
char str[2005];//我开了1005竟然说我越界,怀疑数据有问题
int main()
{int m, len, ans=1;scanf("%s %d", str, &m);len=strlen(str);for(int ch=0; ch<26; ch++){int siz=0;vector<int> v;memset(dp, 63, sizeof(dp));for(int i=0; i<len; i++)if(str[i]==(ch+'a')){v.push_back(i);siz++;dp[siz][siz]=0;}for(int i=siz-1; i>=0; i--){for(int j=i+1; j<siz; j++){int dis=v[j]-v[i]-(j-i);if(i+1!=j)dis+=dp[i+1][j-1];dp[i][j]=min(dp[i][j], dis);if(dp[i][j]<=m) ans=max(ans, j-i+1);}}}cout<<ans<<endl;return 0;
}

设计题

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

用户画像如何存储

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

机器宕机、负载均衡问题

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

将存储用户画像的数据经过哈希函数运算后得到一个key值,然后用key%服务器机器数,得到的就是该用户画像数据归属的服务器,对该数据增添,查询删除都在此机器上进行。
但此设计会有一个问题,就是在对机器进行扩容或删减时,要对每一个数据重新获取哈希值,然后再对新的机器数进行取模运算,这样会造成大规模的数据迁移。
一致性哈希则可以解决这种问题。将数据经过哈希函数计算后得到的输出域想象成一个首尾相接的环形,将机器的数据经过哈希函数计算对应在环上,每一个数据经过哈希函数计算后也都会在环上有对应的位置。
此时每个数据对应的机器就是从此处顺时针向前找,最近的机器就是该数据的归属。当对机器进行增加时,只需将逆时针距离新加服务器最近的机器到此机器之间的数据进行迁移,删除机器时同理。
此时还会有负载不均衡的问题:若机器数太少,就会在环上分布不均匀,此时会造成机器负载不均衡的问题,可以引入虚拟节点技术解决,即同一机器经过不同的哈希函数计算出多个哈希值分布在环上,节点数变多了。平衡性自然会好。

这篇关于字节跳动2018校招后端方向(第二批)笔试题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/454330

相关文章

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

BUUCTF靶场[web][极客大挑战 2019]Http、[HCTF 2018]admin

目录   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 [web][HCTF 2018]admin 考点:弱密码字典爆破 四种方法:   [web][极客大挑战 2019]Http 考点:Referer协议、UA协议、X-Forwarded-For协议 访问环境 老规矩,我们先查看源代码

嵌入式方向的毕业生,找工作很迷茫

一个应届硕士生的问题: 虽然我明白想成为技术大牛需要日积月累的磨练,但我总感觉自己学习方法或者哪些方面有问题,时间一天天过去,自己也每天不停学习,但总感觉自己没有想象中那样进步,总感觉找不到一个很清晰的学习规划……眼看 9 月份就要参加秋招了,我想毕业了去大城市磨练几年,涨涨见识,拓开眼界多学点东西。但是感觉自己的实力还是很不够,内心慌得不行,总怕浪费了这人生唯一的校招机会,当然我也明白,毕业

理解分类器(linear)为什么可以做语义方向的指导?(解纠缠)

Attribute Manipulation(属性编辑)、disentanglement(解纠缠)常用的两种做法:线性探针和PCA_disentanglement和alignment-CSDN博客 在解纠缠的过程中,有一种非常简单的方法来引导G向某个方向进行生成,然后我们通过向不同的方向进行行走,那么就会得到这个属性上的图像。那么你利用多个方向进行生成,便得到了各种方向的图像,每个方向对应了很多

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述

两道笔试题

“char a='\72'”是什么意思? 这么理解:\为转义字符,\072转义为一个八进制数072,也就是十进制数的58买一送一,将转义字符对照表也一并贴给你吧:转义字符 意义 ASCII码值(十进制) \a 响铃(BEL) 007 \b 退格(BS) 008 \f 换页(FF) 012 \n 换行(LF) 010 \r 回车(CR) 013 \t 水平制表(HT) 009 \v 垂直制表(VT

JVM - 字节码文件详解

文章目录 目录 文章目录 1. 无关性基石 2. Class类文件结构 magic- 魔数 主副版本号 常量池 访问标志 类索引,父类索引与接口索引集合 字段 方法 属性 3. 类加载机制 类的生命周期 类加载过程 加载 连接 验证 准备 解析 初始化 4. 类加载器 类与类加载器 类加载器的分类 启动类加载器  扩展类加载器 应用程序类加

华为23年笔试题

消息传输 题目描述 在给定的 m x n (1 <= m, n <= 1000) 网格地图 grid 中,分布着一些信号塔,用于区域间通信。 每个单元格可以有以下三种状态:  值 0 代表空地,无法传递信号;  值 1 代表信号塔 A,在收到消息后,信号塔 A 可以在 1ms 后将信号发送给上下左右四个方向的信号塔; 值 2 代表信号塔 B,在收到消息后,信号塔 B 可以在 2ms

实现的动态规划问题华为笔试题C++实现

秋招刷力扣题,我觉得我对动态规划不是熟练,在此处做总结 动态规划(Dynamic Programming,DP)算法通常用于求解某种具有最优性质的问题。在这类问题中,可能会有许多可行解,每一个解都对应一个值,我们希望找到具有最优值的解。我觉得最大的问题就是对问题的分解,分解后的问题与分解前的问题具有相同的决策机制,将决策机制进行抽象,最终可以得到对应的解; 动态规划中开始介绍的爬楼梯等问题,答

2018秋招C/C++面试题总结

博主从8月中旬开始大大小小面试了十几家公司,至今也许是告一段落吧,希望后面会有好结果,因此总结记录一些C/C++方向常见的问题。和大家一起学习! 参考了互联网的各种资源,自己尝试归类整理,谢谢~ 一、C和C++的区别是什么? C是面向过程的语言,C++是在C语言的基础上开发的一种面向对象编程语言,应用广泛。 C中函数不能进行重载,C++函数可以重载 C++在C的基础上增添类,C是一个结构