字节跳动2018校招后端方向第四批.pdf

1、 问 答 题 题 目 描 述以 下 函 数 用 于 将 一 颗 二 叉 搜 索 树 转 换 成 一 个 有 序 的 双 向 链 表 。 要 求 不 能 创 建 任 何 新 的 节 点 ， 只 能 调 整 树 种 节 点 指 针 的 指 向 。如 输 入 下 图 中 左 边 的 二 叉 搜 索 树 ， 则 输 出 转 换 后 的 排 序 双 向 链 表 ：1 0/ 6 1 4/ / 4 8 1 2 1 6转 换 成 ：4 6 8 1 0 1 2 1 4 1 6请 指 出 程 序 代 码 中 错 误 的 地 方 （ 问 题 不 止 一 处 ， 请 尽 量 找 出 所 有 你 认 为 错 误 的 地

2、 方 ） ：1 # i n c l u d e 2 u s i n g n a m e s p a c e s t d ;34 s t r u c t T r e e N o d e 5 i n t v a l ;6 T r e e N o d e * l e f t , * r i g h t ;7 ;89 T r e e N o d e * C o n v e r t ( T r e e N o d e * r o o t ) 1 0 i f ( r o o t = = N U L L )1 1 r e t u r n r o o t ;1 21 3 T r e e N o d e * l

3、 i s t H e a d = N U L L ;1 4 T r e e N o d e * l i s t L a s t N o d e = N U L L ;1 51 6 s t a c k s ;1 7 w h i l e ( r o o t ) 1 8 w h i l e ( r o o t ) 1 9 r o o t = r o o t - l e f t ;2 0 s . p u s h ( r o o t ) ;2 1 2 2 r o o t = s . t o p ( ) ;2 3 s . p o p ( ) ;2 4 i f ( l i s t H e a d = = N

4、 U L L ) 2 5 l i s t H e a d = r o o t ;2 6 e l s e 2 7 l i s t L a s t N o d e - r i g h t = r o o t ;2 8 2 9 l i s t L a s t N o d e = r o o t ;3 0 r o o t = r o o t - r i g h t ;3 1 3 2 r e t u r n l i s t H e a d ;3 3 问 答 题 题 目 描 述对 于 广 告 投 放 引 擎 ， 广 告 库 索 引 服 务 是 基 础 服 务 ， 每 次 广 告 请 求 会 从 广 告 索

5、 引 中 找 出 匹 配 的 广 告 创 意 列 表 。 假 设 每 一 次 请 求 会 携 带 地域 、 运 营 商 、 设 备 机 型 、 网 络 接 入 方 式 等 信 息 ， 每 个 广 告 策 略 都 可 以 设 置 地 域 、 运 营 商 、 设 备 机 型 、 网 络 接 入 方 式 的 投 放 定 向 （ 即 只能 投 放 到 定 向 匹 配 的 请 求 ， 比 如 只 投 放 特 定 地 域 ） 。 每 个 广 告 策 略 下 包 含 N ( N = 1 ) 个 广 告 创 意 。 设 计 一 个 广 告 库 索 引 模 块 ， 需 要 支 持以 下 几 点 ：1 . 支 持

6、 多 线 程 广 告 请 求 可 以 快 速 的 找 到 匹 配 的 所 有 广 告 创 意2 . 支 持 广 告 库 数 据 的 热 更 新3 . 支 持 十 万 级 广 告 策 略 ， 百 万 级 广 告 创 意4 . 支 持 高 并 发 请 求请 给 出 广 告 库 索 引 服 务 整 体 系 统 设 计 以 及 所 使 用 到 的 数 据 结 构 设 计 ； 编 程 题 编 程 题 1时 间 限 制 ： 2 秒空 间 限 制 ： 6 5 5 3 6 K有 三 只 球 队 ， 每 只 球 队 编 号 分 别 为 球 队 1 ， 球 队 2 ， 球 队 3 ， 这 三 只 球 队 一 共

7、需 要 进 行 n 场 比 赛 。 现 在 已 经 踢 完 了 k 场 比 赛 ， 每 场 比 赛不 能 打 平 ， 踢 赢 一 场 比 赛 得 一 分 ， 输 了 不 得 分 不 减 分 。 已 知 球 队 1 和 球 队 2 的 比 分 相 差 d 1 分 ， 球 队 2 和 球 队 3 的 比 分 相 差 d 2 分 ， 每 场比 赛 可 以 任 意 选 择 两 只 队 伍 进 行 。 求 如 果 打 完 最 后 的 ( n - k ) 场 比 赛 ， 有 没 有 可 能 三 只 球 队 的 分 数 打 平 。 输 入 描 述 :第 一 行 包 含 一 个 数 字 t ( 1 = t =

8、 1 0 )接 下 来 的 t 行 每 行 包 括 四 个 数 字 n , k , d 1 , d 2 ( 1 = n = 1 0 1 2 ; 0 = k = n , 0 = d 1 , d 2 = k )输 出 描 述 :每 行 的 比 分 数 据 ， 最 终 三 只 球 队 若 能 够 打 平 ， 则 输 出 “ y e s ” ， 否 则 输 出 “ n o ”输 入 例 子 1 :23 3 0 03 3 3 3输 出 例 子 1 :y e sn o例 子 说 明 1 :c a s e 1 : 球 队 1 和 球 队 2 差 0 分 ， 球 队 2 和 球 队 3 也 差 0 分 ， 所

9、 以 可 能 的 赛 得 分 是 三 只 球 队 各 得 1 分c a s e 2 : 球 队 1 和 球 队 2 差 3 分 ， 球 队 2 和 球 队 3 差 3 分 ， 所 以 可 能 的 得 分 是 球 队 1 得 0 分 ， 球 队 2 得 3 分 , 球 队 3 得 0 分 ， 比 赛已 经 全 部 结 束 因 此 最 终 不 能 打 平 。 编 程 题 编 程 题 2时 间 限 制 ： 1 秒空 间 限 制 ： 6 5 5 3 6 K有 一 个 仅 包 含 a 和 b 两 种 字 符 的 字 符 串 s ， 长 度 为 n ， 每 次 操 作 可 以 把 一 个 字 符 做 一

10、次 转 换 （ 把 一 个 a 设 置 为 b ， 或 者 把 一 个 b 置 成 a ) ；但 是 操 作 的 次 数 有 上 限 m ， 问 在 有 限 的 操 作 数 范 围 内 ， 能 够 得 到 最 大 连 续 的 相 同 字 符 的 子 串 的 长 度 是 多 少 。输 入 描 述 :第 一 行 两 个 整 数 n , m ( 1 = m = n = 5 0 0 0 0 ) ， 第 二 行 为 长 度 为 n 且 只 包 含 a 和 b 的 字 符 串 s 。输 出 描 述 :输 出 在 操 作 次 数 不 超 过 m 的 情 况 下 ， 能 够 得 到 的 最 大 连 续 全 a

11、 子 串 或 全 b 子 串 的 长 度 。输 入 例 子 1 :8 1a a b a a b a a输 出 例 子 1 :5例 子 说 明 1 :把 第 一 个 b 或 者 第 二 个 b 置 成 a ， 可 得 到 长 度 为 5 的 全 a 子 串 。 编 程 题 附 加 题时 间 限 制 ： 1 秒空 间 限 制 ： 6 5 5 3 6 K存 在 n + 1 个 房 间 ， 每 个 房 间 依 次 为 房 间 1 2 3 . . . i ， 每 个 房 间 都 存 在 一 个 传 送 门 ， i 房 间 的 传 送 门 可 以 把 人 传 送 到 房 间 p i ( 1 = p i =

12、 i ) , 现 在 路人 甲 从 房 间 1 开 始 出 发 ( 当 前 房 间 1 即 第 一 次 访 问 ) ， 每 次 移 动 他 有 两 种 移 动 策 略 ：A . 如 果 访 问 过 当 前 房 间 i 偶 数 次 ， 那 么 下 一 次 移 动 到 房 间 i + 1 ；B . 如 果 访 问 过 当 前 房 间 i 奇 数 次 ， 那 么 移 动 到 房 间 p i ；现 在 路 人 甲 想 知 道 移 动 到 房 间 n + 1 一 共 需 要 多 少 次 移 动 ；输 入 描 述 :第 一 行 包 括 一 个 数 字 n ( 3 0 % 数 据 1 = n = 1 0 0

13、 ， 1 0 0 % 数 据 1 = n = 1 0 0 0 ) ， 表 示 房 间 的 数 量 ， 接 下 来 一 行 存 在 n 个 数 字 p i ( 1 = p i = i ) ,p i 表 示 从 房 间 i 可 以 传 送 到 房 间 p i 。输 出 描 述 :输 出 一 行 数 字 ， 表 示 最 终 移 动 的 次 数 ， 最 终 结 果 需 要 对 1 0 0 0 0 0 0 0 0 7 ( 1 0 e 9 + 7 ) 取 模 。输 入 例 子 1 :21 2输 出 例 子 1 :4例 子 说 明 1 :开 始 从 房 间 1 只 访 问 一 次 所 以 只 能 跳 到 p 1 即 房 间 1 ， 之 后 采 用 策 略 A 跳 到 房 间 2 ， 房 间 2 这 时 访 问 了 一 次 因 此 采 用 策 略 B 跳 到 房 间2 ， 之 后 采 用 策 略 A 跳 到 房 间 3 ， 因 此 到 达 房 间 3 需 要 4 步 操 作 。