字节跳动2018校招前端方向第二批.pdf

1、 编 程 题 用 户 喜 好时 间 限 制 ： 3 秒空 间 限 制 ： 2 6 2 1 4 4 K为 了 不 断 优 化 推 荐 效 果 ， 今 日 头 条 每 天 要 存 储 和 处 理 海 量 数 据 。 假 设 有 这 样 一 种 场 景 ：我 们 对 用 户 按 照 它 们 的 注 册 时 间 先 后 来 标 号 ， 对 于 一 类 文 章 ， 每 个 用 户 都 有 不 同 的 喜 好值 ， 我 们 会 想 知 道 某 一 段 时 间 内 注 册 的 用 户 （ 标 号 相 连 的 一 批 用 户 ） 中 ， 有 多 少 用 户 对这 类 文 章 喜 好 值 为 k 。 因 为 一

2、 些 特 殊 的 原 因 ， 不 会 出 现 一 个 查 询 的 用 户 区 间 完 全 覆 盖 另一 个 查 询 的 用 户 区 间 ( 不 存 在 L 1 = L 2 = R 2 = R 1 ) 。输 入 描 述 :输 入 ： 第 1 行 为 n 代 表 用 户 的 个 数 第 2 行 为 n 个 整 数 ， 第 i 个 代 表 用 户 标 号 为 i 的 用 户 对 某 类 文 章 的 喜 好 度 第 3 行 为 一 个 正 整 数 q代 表 查 询 的 组 数 第 4 行 到 第 （ 3 + q ） 行 ， 每 行 包 含 3 个 整 数 l , r , k 代 表 一 组 查 询 ，

3、 即 标 号 为 l = i = r 的 用 户 中 对 这 类 文 章 喜 好 值 为k 的 用 户 的 个 数 。 数 据 范 围 n = 3 0 0 0 0 0 , q = 3 0 0 0 0 0 k 是 整 型输 出 描 述 :输 出 ： 一 共 q 行 ， 每 行 一 个 整 数 代 表 喜 好 值 为 k 的 用 户 的 个 数输 入 例 子 1 :51 2 3 3 531 2 12 4 53 5 3输 出 例 子 1 :102例 子 说 明 1 :样 例 解 释 :有 5 个 用 户 ， 喜 好 值 为 分 别 为 1 、 2 、 3 、 3 、 5 ，第 一 组 询 问 对 于

4、 标 号 1 , 2 的 用 户 喜 好 值 为 1 的 用 户 的 个 数 是 1第 二 组 询 问 对 于 标 号 2 , 4 的 用 户 喜 好 值 为 5 的 用 户 的 个 数 是 0第 三 组 询 问 对 于 标 号 3 , 5 的 用 户 喜 好 值 为 3 的 用 户 的 个 数 是 2 编 程 题 手 串时 间 限 制 ： 1 秒空 间 限 制 ： 6 5 5 3 6 K作 为 一 个 手 串 艺 人 ， 有 金 主 向 你 订 购 了 一 条 包 含 n 个 杂 色 串 珠 的 手 串 每 个 串 珠 要 么无 色 ， 要 么 涂 了 若 干 种 颜 色 。 为 了 使 手

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

6、 珠 中 出 现 了 至 少 两 次 。输 入 描 述 :第 一 行 输 入 n ， m ， c 三 个 数 ， 用 空 格 隔 开 。 ( 1 = n = 1 0 0 0 0 , 1 = m = 1 0 0 0 , 1 = c = 5 0 ) 接 下 来 n 行 每 行 的 第 一 个数 n u m _ i ( 0 = n u m _ i = c ) 表 示 第 i 颗 珠 子 有 多 少 种 颜 色 。 接 下 来 依 次 读 入 n u m _ i 个 数 字 ， 每 个 数 字 x 表 示 第 i 颗 柱 子 上 包 含 第x 种 颜 色 ( 1 = x = c )输 出 描 述 :一

7、 个 非 负 整 数 ， 表 示 该 手 链 上 有 多 少 种 颜 色 不 符 需 求 。输 入 例 子 1 :5 2 33 1 2 302 2 31 21 3输 出 例 子 1 :2例 子 说 明 1 :第 一 种 颜 色 出 现 在 第 1 颗 串 珠 ， 与 规 则 无 冲 突 。第 二 种 颜 色 分 别 出 现 在 第 1 ， 3 ， 4 颗 串 珠 ， 第 3 颗 与 第 4 颗 串 珠 相 邻 ， 所 以 不 合 要 求 。第 三 种 颜 色 分 别 出 现 在 第 1 ， 3 ， 5 颗 串 珠 ， 第 5 颗 串 珠 的 下 一 个 是 第 1 颗 ， 所 以 不 合 要

8、求 。总 计 有 2 种 颜 色 的 分 布 是 有 问 题 的 。这 里 第 2 颗 串 珠 是 透 明 的 。 问 答 题 题 目 描 述以 下 函 数 使 用 二 分 查 找 搜 索 一 个 增 序 的 数 组 ， 当 有 多 个 元 素 值 与 目 标 元 素 相 等 时 ， 返 回最 后 一 个 元 素 的 下 标 ， 目 标 元 素 不 存 在 时 返 回 - 1 。 请 指 出 程 序 代 码 中 错 误 或 不 符 最 佳 实践 的 地 方 （ 问 题 不 止 一 处 ， 请 尽 量 找 出 所 有 你 认 为 有 问 题 的 地 方 ）i n t B i n a r y S

9、e a r c h M a x ( c o n s t s t d : : v e c t o r & d a t a , i n t t a r g e t )i n t l e f t = 0 ;i n t r i g h t = d a t a . s i z e ( ) ;w h i l e ( l e f t r i g h t ) i n t m i d = ( l e f t + r i g h t ) / 2 ;i f ( d a t a m i d = t a r g e t )l e f t = m i d + 1 ;e l s er i g h t = m i d - 1

10、 ;i f ( d a t a r i g h t = = t a r g e t )r e t u r n r i g h t ;r e t u r n - 1 ; 问 答 题 题 目 描 述1 .设 计 一 个 T O D O L i s t ， 页 面 结 构 如 下 图 所 示 ， 要 求 ：2 .1 .使 用 H T M L 与 C S S 完 成 界 面 开 发2 .3 .实 现 添 加 功 能 ： 输 入 框 中 可 输 入 任 意 字 符 ， 按 回 车 后 将 输 入 字 符 串 添 加 到 下 方 列 表 的 最后 ， 并 清 空 输 入 框4 .5 .实 现 删 除 功 能 ： 点 击 列 表 项 后 面 的 “ X ” 号 ， 可 以 删 除 该 项6 .7 .实 现 模 糊 匹 配 ： 在 输 入 框 中 输 入 字 符 后 ， 将 当 前 输 入 字 符 串 与 已 添 加 的 列 表 项 进 行 模 糊匹 配 ， 将 匹 配 到 的 结 果 显 示 在 输 入 框 下 方 。 如 匹 配 不 到 任 何 列 表 项 ， 列 表 显 示 空8 .注 ： 以 上 代 码 实 现 需 要 能 在 浏 览 器 中 正 常 显 示 与 执 行 。