搜索

[24406] 2015-10-22_只有程序员看的懂的面试圣经｜如何拿下编程面试

文档创建者：s7ckTeam
浏览次数：42
最后更新：2025-01-18
2015-10-22_只有程序员看的懂的面试圣经｜如何拿下编程面试 只 有 程 序 员 看 的 懂 的 面 试 圣 经 ｜ 如 何 拿 下 编 程 面 试 L i n u x 中 国   2 0 1 5 - 1 0 - 2 2 当 我 最 初 开 始 参 加 编 程 面 试 的 时 候 ， 我 所 有 最 心 仪 的 公 司 都 忽 视 了 我 。 现 在 回 头 看 那 个 时 候 ， 我 发 现 自 己 当 时 去 参 加 面 试 都 完 全 没 做 任 何 准 备 。 虽 然 已 经 有 许 多 博 客 文 章 和 书 籍 在 讲 编 程 面 试 ， 但 现 在 的 我 作 为 面 试 官 ， 坐 在 桌 子 的 另 一 边 ， 还 是 能 看 到 许 多 来 参 加 编 程 面 试 的 人 没 做 任 何 准 备 ， 或 者 准 备 得 很 糟 糕 。 这 也 就 是 为 什 么 我 开 始 写 这 篇 指 南 的 原 因 ， 刚 毕 业 时 的 我 、 第 一 次 参 加 面 试 的 我 一 定 非 常 想 有 这 么 一 份 指 南 来 指 引 自 己 。 而 从 现 在 开 始 ， 我 自 己 也 会 照 着 这 份 指 南 去 做 。 多 年 以 来 ， 我 在 好 几 家 公 司 工 作 过 ， 所 以 我 的 面 试 技 巧 得 到 了 很 好 的 磨 炼 ， 而 且 我 参 与 面 试 的 过 程 也 教 会 了 我 该 说 什 么 、 该 做 哪 些 准 备 ， 以 及 如 何 面 试 。 在 这 篇 指 南 里 ， 你 会 了 解 到 面 试 的 概 况 、 面 试 取 得 成 功 的 六 大 步 骤 ， 以 及 我 在 考 察 数 据 结 构 和 算 法 时 所 考 虑 的 方 面 。 这 篇 指 南 无 法 确 保 你 找 到 工 作 ， 但 它 能 帮 助 你 尽 最 大 可 能 给 面 试 官 留 下 一 个 好 印 象 。 声 明 ： 本 文 中 的 观 点 完 全 出 自 个 人 视 角 ， 与 我 目 前 或 者 以 前 的 雇 主 没 有 关 系 。 声 明 ： 本 文 中 的 观 点 完 全 出 自 个 人 视 角 ， 与 我 目 前 或 者 以 前 的 雇 主 没 有 关 系 。 面 面 试 过 试 过 程 程 本 节 概 述 了 硅 谷 公 司 的 面 试 过 程 ， 仅 仅 是 个 情 况 介 绍 ， 大 家 可 以 跳 过 去 往 后 看 。 除 了 直 接 申 请 面 试 以 外 ， 一 般 说 来 ， 还 有 两 种 途 径 来 获 得 面 试 的 机 会 ： 由 现 在 的 雇 主 推 荐 ， 或 者 通 过 由 现 在 的 雇 主 推 荐 ， 或 者 通 过 L i n k e d I n 。 。 虽 然 前 者 会 快 一 些 、 更 尊 敬 一 些 ， 但 后 者 很 可 能 是 大 部 分 应 聘 者 所 走 的 路 径 。 事 实 上 ， 每 天 都 有 无 数 的 招 聘 人 员 趴 在 L i n k e d I n 上 ， 他 们 唯 一 的 工 作 就 是 寻 找 和 接 触 有 可 能 换 工 作 的 员 工 ， 所 以 一 定 要 保 证 自 己 的 信 息 是 最 新 的 ， 而 且 要 多 交 人 脉 、 多 请 别 人 来 认 可 自 己 的 技 能 ， 并 且 要 把 你 所 具 备 的 技 所 以 一 定 要 保 证 自 己 的 信 息 是 最 新 的 ， 而 且 要 多 交 人 脉 、 多 请 别 人 来 认 可 自 己 的 技 能 ， 并 且 要 把 你 所 具 备 的 技 能 、 做 过 的 个 人 项 目 或 者 对 开 源 软 件 所 做 的 贡 献 加 到 个 人 页 面 里 去 。 能 、 做 过 的 个 人 项 目 或 者 对 开 源 软 件 所 做 的 贡 献 加 到 个 人 页 面 里 去 。 最 初 的 接 触 一 般 是 通 过 电 子 邮 件 进 行 的 ， 然 后 招 聘 人 员 会 给 你 打 电 话 ， 大 概 了 解 一 下 你 的 技 术 背 景 。 如 果 你 的 技 能 和 他 们 正 在 寻 找 的 技 能 一 致 ， 他 们 就 会 安 排 一 次 电 话 面 试 电 话 面 试 ， 在 电 话 面 试 时 ， 你 可 能 就 会 被 要 求 在 一 份 共 享 的 在 线 文 档 里 编 程 。 那 么 你 就 会 知 道 ， 这 份 文 档 很 可 能 没 有 任 何 代 码 补 全 和 句 法 高 亮 的 功 能 。 电 话 面 试 会 持 续 半 小 时 到 4 5 分 钟 ， 如 果 你 表 现 不 错 ， 就 会 被 邀 请 去 参 加 现 场 面 试 。 现 在 如 果 没 有 电 话 面 试 、 或 者 在 电 话 面 试 之 外 ， 你 可 能 还 得 去 参 加 一 个 小 的 编 程 项 目 。 现 场 面 试 现 场 面 试 由 几 次 面 试 组 成 ， 总 体 会 持 续 4 5 分 钟 到 一 个 小 时 。 这 些 面 试 会 和 电 话 面 试 非 常 像 ， 只 是 问 题 会 更 难 — — 不 过 能 亲 眼 见 到 面 试 官 多 少 算 是 有 所 补 偿 。 现 场 面 试 数 周 之 后 ， 所 有 反 馈 应 该 都 被 看 过 、 招 聘 决 定 就 会 做 出 ， 招 谁 不 招 谁 也 就 定 了 。 如 果 你 没 拿 到 o f f e r ， 也 要 明 白 面 试 是 一 个 随 机 的 过 程 ， 包 含 运 气 的 成 分 ， 不 妨 把 它 看 作 是 一 次 学 习 的 经 历 。 可 能 你 还 会 想 起 B r i a n . A c t o n 布 莱 恩 · 阿 克 顿 面 试 F a c e b o o k 和 T w i t t e r 不 成 、 后
来 成 为 W h a t s A p p 联 合 创 始 人 的 故 事 。 理 论 上 讲 ， 用 哪 种 编 程 语 言 并 不 重 要 ， 但 你 面 试 需 要 用 某 种 特 定 语 言 来 完 成 的 工 作 时 除 外 ， 比 如 i P h o n e 开 发 者 或 者 前 端 开 发 者 。 我 强 烈 建 议 你 用 正 在 面 试 的 公 司 所 使 用 的 一 种 编 程 语 言 来 编 程 （ 以 及 练 习 面 试 问 题 ） 。 面 面 试 获 得 试 获 得 成 功 的 六 个 步 成 功 的 六 个 步 骤 骤 编 程 面 试 的 目 的 ， 是 为 了 确 定 你 的 编 程 水 平 有 多 高 。 一 般 来 说 ， 你 将 被 要 求 用 编 程 来 完 成 一 个 功 能 或 者 方 法 ， 但 有 时 候 ， 你 会 需 要 编 辑 一 个 类 的 定 义 ， 或 者 设 计 一 系 列 相 关 的 代 码 模 块 。 在 任 何 一 种 情 况 下 ， 你 都 要 有 条 不 紊 地 解 决 问 题 ， 并 遵 循 以 下 六 个 步 骤 ： 1 .   首 先 ， 要 确 保 你 理 解 了 面 试 官 的 问 题 。 首 先 ， 要 确 保 你 理 解 了 面 试 官 的 问 题 。 许 多 问 题 都 是 故 意 措 辞 模 糊 或 者 模 棱 两 可 ， 这 个 时 候 你 可 以 请 面 试 官 把 问 题 说 清 楚 ， 从 而 确 保 你 真 正 回 答 面 试 官 的 问 题 。 你 的 提 问 同 时 还 有 一 个 好 处 ， 就 是 它 能 给 你 自 己 一 些 时 间 ， 让 你 的 脑 子 转 起 来 。 2 .   用 一 到 两 个 例 子 来 确 定 问 题 的 限 制 条 件 和 要 求 （ 在 现 场 面 试 时 在 白 板 上 完 成 这 个 过 程 ， 在 电 话 面 试 时 在 笔 记 本 上 完 用 一 到 两 个 例 子 来 确 定 问 题 的 限 制 条 件 和 要 求 （ 在 现 场 面 试 时 在 白 板 上 完 成 这 个 过 程 ， 在 电 话 面 试 时 在 笔 记 本 上 完 成 ） 。 成 ） 。 尝 试 用 中 等 规 模 的 例 子 ， 以 便 覆 盖 到 一 些 特 殊 情 况 。 如 果 你 能 想 到 可 能 相 关 的 表 格 ， 就 把 它 画 出 来 。 事 实 上 ， 把 你 想 到 的 任 何 东 西 都 写 下 来 是 会 有 帮 助 的 ， 因 为 它 能 为 你 提 供 一 个 视 觉 锚 点 ， 从 而 让 你 在 走 不 通 时 或 者 思 考 过 程 中 随 时 返 回 某 一 个 点 。 3 .   把 话 说 清 楚 ， 这 可 能 是 最 重 要 的 一 步 。 把 话 说 清 楚 ， 这 可 能 是 最 重 要 的 一 步 。 要 试 着 让 面 试 尽 可 能 有 更 多 的 互 动 ， 面 试 官 不 知 道 你 在 想 什 么 ， 而 让 他 们 参 与 到 你 的 思 考 过 程 里 ， 会 让 她 给 你 一 些 有 用 的 提 示 ， 防 止 你 偏 向 错 误 的 方 向 。 你 的 目 标 就 是 要 先 和 面 试 官 确 证 你 的 答 案 ， 然 后 再 去 写 代 码 ， 而 且 你 考 虑 答 案 越 清 晰 、 越 高 效 ， 你 得 到 的 即 时 反 馈 也 就 越 好 。 4 .   通 过 应 用 以 下 技 巧 来 找 到 答 案 ： 通 过 应 用 以 下 技 巧 来 找 到 答 案 ： 回 想 一 下 你 遇 到 的 类 似 问 题 ， 再 想 想 它 们 是 如 何 被 解 决 的 ， 尝 试 各 种 不 同 的 算 法 （ 分 治 算 法 、 贪 心 算 法 、 递 归 、 排 序 ， 等 等 ） ， 把 问 题 分 解 成 更 小 的 、 可 处 理 的 小 问 题 （ 这 样 你 就 能 得 到 相 应 部 分 的 分 数 ） ， 最 后 再 通 览 一 遍 你 列 出 的 数 据 结 构 ， 因 为 有 时 候 ， 只 要 想 到 了 正 确 的 数 据 结 构 ， 就 能 给 出 正 确 的 答 案 。 5 .   当 你 向 面 试 官 问 清 楚 了 问 题 、 并 向 她 解 释 了 你 的 答 案 之 后 ， 就 可 以 开 始 写 代 码 了 。 当 你 向 面 试 官 问 清 楚 了 问 题 、 并 向 她 解 释 了 你 的 答 案 之 后 ， 就 可 以 开 始 写 代 码 了 。 要 记 住 ， 在 共 享 文 档 里 写 代 码 的 时 候 ， 你 可 以 复 制 粘 贴 、 写 评 论 ， 而 且 能 回 过 头 来 完 成 骨 架 算 法 和 功 能 。 但 在 白 板 上 写 代 码 就 不 一 样 了 ， 它 需 要 你 的 头 脑 很 清 醒 ， 而 且 需 要 你 具 备 管 理 白 板 空 间 的 技 能 。 如 果 足 够 幸 运 的 话 ， 现 在 当 你 开 始 在 白 板 左 上 角 动 笔 的 时 候 ， 应 该 非 常 明 白 你 要 写 些 什 么 东 西 ， 而 且 你 要 确 保 在 你 写 答 案 的 时 候 ， 没 有 挡 住 面 试 官 的 视 线 。 花 点 儿 时 间 把 代 码 写 得 紧 凑 而 美 观 一 点 儿 ， 因 为 你 的 代 码 也 会 是 面 试 反 馈 的 一 部 分 。 在 你 写 代 码 的 时 候 ， 要 大 声 解 释 你 在 写 什 么 ， 这 会 让 你 的 面 试 官 更 容 易 地 跟 上 你 的 思 路 。 6 .   最 后 ， 用 不 同 的 例 子 和 特 殊 案 例 验 证 一 下 你 的 代 码 ， 并 且 要 一 行 一 行 地 过 。 最 后 ， 用 不 同 的 例 子 和 特 殊 案 例 验 证 一 下 你 的 代 码 ， 并 且 要 一 行 一 行 地 过 。 这 会 展 示 你 的 思 考 过 程 ， 让 你 检 查 出 小 错 误 ， 并 告 诉 面 试 官 你 的 办 法 是 可 行 的 。 如 果 你 想 得 到 额 外 加 分 的 话 ， 甚 至 可 以 把 单 元 测 试 的 代 码 写 下 来 ！ 最 后 再 和 面 试 官 聊 一 下 你 的 答 案 在 空 间 和 时 间 利 用 方 面 的 复 杂 性 ， 然 后 结 束 整 场 面 试 。 电 电 话 话 面 面 试 试 中 提 示 出 的 中 提 示 出 的 问 题 问 题 电 话 面 试 值 得 特 别 一 提 ， 因 为 这 是 大 多 数 人 失 利 的 地 方 。 之 所 以 会 这 样 ， 部 分 原 因 在 于 电 话 面 试 是 招 聘 过 程 中 第 一 道 真 正 的 关 卡 ， 但 也 有 一 部 分 原 因 在 于 ， 这 种 形 式 容 易 造 成 沟 通 的 错 误 ， 而 且 缺 乏 可 视 化 线 索 ， 所 以 电 话 面 试 是 特 别 严 酷 的 。 电 话 面 试 有 两 大 障 碍 。 电 话 面 试 有 两 大 障 碍 。 第 一 大 障 碍 是 ， 在 电 话 面 试 的 一 开 始 ， 双 方 都 能 看 到 的 唯 一 的 东 西 就 是 一 个 空 白 的 共 享 文 档 。 这 会 让 面 试 者 倾 向 于 过 度 补 偿 非 语 言 沟 通 的 缺 失 ， 从 而 着 急 忙 慌 地 在 屏 幕 上 进 行 沟 通 。 令 人 遗 憾 的 是 ， 这 么 做 很 少 会 有 好 结 果 。 所 以 当 务 之 急 并 不 是 去 关 注 那 个 正 在 盯 着 你 的 空 白 文 档 ， 而 是 要 首 先 理 解 和 评 估 问 题 （ 也 就 是 完 成 上 述 六 个 步 骤 中 的 前 四 个 ） ， 同 时 通 过 尽 可 能 地 沉 浸 到 面 试 中 来 弥 补 现 实 存 在 感 的 缺 失 （ 要 记 住 ， 电 话 的 另 一 头 是 一 位 可 以 很 容 易 就 被 别 的 事 情 [ 比 如 查 看 邮 件 ] 分 心 的 面 试 官 ） 。 电 话 面 试 的 第 二 大 障 碍 ， 就 是 要 同 时 在 电 脑 上 打 字 和 在 电 话 上 聊 天 的 后 勤 保 障 问 题 。 电 话 面 试 的 第 二 大 障 碍 ， 就 是 要 同 时 在 电 脑 上 打 字 和 在 电 话 上 聊 天 的 后 勤 保 障 问 题 。 你 不 必 一 只 手 敲 代 码 、 一 只 手 打 电 话 ， 也 不 必 把 电 话 调 到 扬 声 器 模 式 ， 我 建 议 你 用 电 脑 上 的 G o o g l e   H a n g o u t s 接 面 试 电 话 （ 你 得 有 一 个 G o o g l e V o i c e 号 码 ， 而 且 得 在 面 试 前 测 试 一 下 ） 。 你 还 可 以 用 耳 麦 或 者 耳 机 来 进 一 步 降 低 不 好 的 接 收 效 果 、 提 高 沟 通 质 量 。 算 法 算 法 + 数 数 据 据 结 结 构 构 = 程 序 程 序 如 果 你 正 在 思 考 为 什 么 软 件 工 程 的 面 试 和 日 常 编 程 不 一 样 ， 那 你 可 能 有 兴 趣 读 一 下 Q u o r a 上 的 这 条 回 答 。 最 根 本 的 原 因 在 于 ： 面 试 是 为 了 测 试 你 在 计 算 机 技 术 方 面 的 基 础 ， 所 以 会 非 常 偏 重 算 法 和 数 据 结 构 ， 因 此 你 可 能 需 要 练 习 一 些 面 试 问 题 ， 从 而 让 自 己 具 备 解 决 面 试 问 题 的 心 态 。
从 短 期 来 看 ， 你 所 能 做 的 最 好 的 准 备 工 作 就 是 买 一 块 白 板 ， 并 通 读 一 遍 《 C r a c k i n g   T h e   C o d e   I n t e r v i e w 程 序 员 面 试 金 典 》 ， 里 面 都 是 很 好 的 建 议 ， 而 且 里 面 的 许 多 面 试 问 题 和 答 案 会 帮 助 你 确 定 问 题 所 在 ， 并 匹 配 好 回 答 模 式 。 请 参 阅 本 指 南 最 后 列 出 的 常 用 面 试 问 题 。 当 然 了 ， 长 远 来 看 ， 我 们 都 会 死 掉 ， 所 以 我 会 把 事 情 搞 简 单 ， 说 一 些 你 绝 对 应 该 复 习 一 下 的 关 键 概 念 。 数 组 数 组 / 字 符 串 字 符 串 大 部 分 数 组 和 字 符 串 是 可 互 换 的 ， 事 实 上 ， 你 遇 到 的 大 部 分 字 符 串 处 理 的 问 题 ， 都 可 以 在 理 解 数 组 的 基 础 上 得 到 解 决 。 记 住 这 一 点 之 后 ， 你 应 该 懂 得 如 何 遍 历 数 组 ， 知 道 如 何 访 问 、 转 换 和 调 换 其 中 的 每 一 个 元 素 ， 而 且 要 懂 得 如 何 对 它 们 进 行 各 种 不 同 的 集 合 运 算 。 和 其 他 算 法 相 比 ， B i n a r y   s e a r c h 二 分 法 检 索 可 能 会 更 多 地 成 为 面 试 问 题 的 核 心 内 容 （ 如 果 你 曾 经 碰 到 过 有 分 类 数 组 的 问 题 ， 那 么 二 分 法 检 索 有 可 能 应 该 是 你 答 案 的 一 部 分 ） ， 你 绝 对 必 须 知 道 如 何 使 用 它 。 排 序 和 数 组 密 切 相 关 的 ， 是 排 序 算 法 。 你 不 大 可 能 会 被 要 求 重 复 使 用 一 个 排 序 算 法 ， 但 很 可 能 你 至 少 知 道 排 序 是 如 何 在 O ( n l o g n ) 的 时 间 里 完 成 的 就 行 。 不 过 你 应 该 大 概 知 道 m e r g e   s o r t 归 并 排 序 或 者 q u i c k s o r t 快 速 排 序 和 r a d i x   s o r t 基 数 排 序 的 执 行 细 节 。 动 态 数 组 动 态 数 组 / 可 增 数 组 可 增 数 组 动 态 数 组 可 以 按 需 重 新 调 整 自 己 的 大 小 ， 同 时 依 然 提 供 分 时 平 摊 的 持 续 时 间 访 问 。 一 种 典 型 的 做 法 是 ， 当 在 一 个 全 排 列 数 组 中 增 加 一 个 元 素 的 时 候 ， 会 形 成 一 个 新 的 、 更 大 的 数 组 ， 而 旧 数 组 中 的 元 素 也 会 被 复 制 到 新 数 组 里 。 你 应 该 在 面 试 时 做 到 完 成 一 个 动 态 数 组 。 如 果 你 拿 到 一 个 非 数 组 类 问 题 ， 但 你 在 答 题 中 需 要 用 到 像 数 组 结 构 这 样 的 数 组 ， 不 妨 少 给 自 己 惹 麻 烦 ， 直 接 用 动 态 数 组 吧 。 哈 希 映 射 / 哈 希 表 / 词 典 / 哈 希 集 合 H a s h   t a b l e s 哈 希 表 是 编 程 时 的 瑞 士 军 刀 ， 很 多 不 同 类 型 的 问 题 （ 检 查 存 在 、 计 算 频 率 、 排 序 ， 等 等 ） 都 能 用 哈 希 表 来 完 美 解 决 。 它 几 乎 肯 定 会 出 现 在 你 的 面 试 中 ， 而 你 应 该 理 解 它 的 原 理 （ 哈 希 功 能 的 角 色 、 冲 突 如 何 解 决 、 什 么 时 候 要 调 整 大 小 、 为 什 么 ） 以 及 如 何 运 用 它 们 。 链 表 链 表 问 题 在 C 和 C + + 的 面 试 中 最 常 见 ， 因 为 它 们 是 弄 清 楚 应 聘 者 是 否 理 解 指 针 的 一 种 简 单 的 办 法 。 不 过 这 个 点 太 初 级 、 太 基 础 了 ， 所 以 不 管 用 哪 种 语 言 ， 你 都 应 该 知 道 该 如 何 从 零 做 起 应 用 它 们 。 而 且 由 于 大 部 分 链 表 问 题 不 过 是 与 人 所 周 知 的 遍 历 还 有 删 除 和 插 入 相 关 的 问 题 的 变 体 ， 所 以 链 表 问 题 准 备 起 来 很 容 易 ， 你 没 有 理 由 拿 不 到 这 部 分 分 数 。 许 多 链 表 问 题 中 都 会 用 到 一 个 小 技 巧 ， 那 就 是 慢 速 / 快 速 指 针 技 术 。 它 的 简 单 版 含 义 如 下 ： 使 用 两 个 指 针 迭 代 生 成 一 个 列 表 ， 其 中 一 个 指 针 在 另 一 个 指 针 的 前 面 。 快 速 模 式 下 的 指 针 可 能 会 是 一 个 位 于 前 面 的 固 定 数 值 （ 它 有 助 于 确 定 列 表 有 无 循 环 ， 或 者 找 到 列 表 中 的 第 k 个 元 素 ） ， 或 者 也 可 能 会 跳 过 慢 速 指 针 经 过 的 多 个 结 点 （ 打 个 比 方 ， 如 果 快 速 指 针 的 速 度 是 慢 速 指 针 的 两 倍 ， 那 么 当 它 到 达 列 表 末 尾 时 ， 慢 速 指 针 将 会 位 于 列 表 的 中 间 ） 。 请 注 意 ， 当 面 试 官 谈 到 链 表 时 ， 他 们 常 常 指 的 是 单 链 表 ， 但 你 无 论 如 何 都 应 该 问 清 楚 。 栈 / 队 列 栈 和 队 列 一 般 会 是 你 用 来 解 题 的 数 据 结 构 的 一 部 分 。 你 应 该 知 道 如 何 用 链 表 和 数 组 两 种 方 式 来 实 现 它 们 。 加 练 两 道 题 ： 利 用 两 个 队 列 实 现 一 个 栈 ， 以 及 利 用 两 个 栈 来 实 现 一 个 队 列 。 树 / 二 叉 树 / 二 叉 搜 索 树 （ B S T ） / 字 典 树 / 堆 你 可 能 不 会 每 天 都 见 到 树 和 图 ， 但 你 很 可 能 会 在 面 试 时 遇 到 它 们 ， 所 以 你 要 彻 底 地 看 一 下 这 些 数 据 结 构 。
树 最 一 般 的 定 义 ， 是 和 其 他 结 点 没 有 或 者 有 一 个 以 上 关 系 的 结 点 的 集 合 ， 但 在 实 践 中 ， 当 面 试 官 说 “ 树 树 ” 的 时 候 ， 他 们 指 的 是 一 种 叫 二 叉 树 的 东 西 。 二 叉 树 二 叉 树 是 一 种 树 的 类 型 ， 它 的 每 个 结 点 都 至 多 有 两 个 子 树 ， 一 般 被 称 为 左 子 树 和 右 子 树 。 你 不 应 该 把 二 叉 树 二 叉 树 和 二 叉 搜 索 树 二 叉 搜 索 树 混 淆 起 来 ， 后 者 是 一 种 特 殊 的 二 叉 树 ， 它 的 左 子 树 结 点 上 的 值 都 比 父 结 点 小 ， 而 右 子 树 结 点 上 的 值 都 比 父 结 点 大 或 者 相 等 。 二 叉 搜 索 树 的 优 点 是 ， 如 果 树 的 结 构 相 对 平 衡 （ 向 面 试 官 问 清 楚 这 个 问 题 ） ， 那 么 查 找 、 插 入 和 删 除 就 可 以 在 O ( l o g   n ) 的 时 间 里 完 成 。 二 叉 搜 索 树 的 其 他 重 要 属 性 ， 就 是 你 跟 着 所 有 的 左 子 树 走 ， 就 能 得 到 这 个 树 上 最 小 的 元 素 ， 而 跟 着 所 有 的 右 子 树 走 ， 就 能 得 到 这 个 树 上 最 大 的 元 素 。 请 注 意 ， 是 有 办 法 让 树 一 直 保 持 平 衡 的 ， 最 常 用 的 办 法 就 是 红 黑 树 和 A V L 树 。 我 不 会 去 弄 清 楚 它 具 体 实 现 的 细 节 ， 只 要 知 道 有 这 些 数 据 结 构 就 行 。 不 过 你 绝 对 必 须 知 道 t r e e   t r a v e r s a l 遍 历 树 算 法 ： b r e a d t h - f i r s t - s e a r c h 广 度 优 先 搜 索 、 d e p t h - f i r s t - s e a r c h 深 度 优 先 搜 索 ， 以 及 中 序 遍 历 中 序 遍 历 、 后 序 遍 历 后 序 遍 历 和 前 序 遍 历 前 序 遍 历 之 间 的 差 别 。 以 下 是 在 J a v a 实 现 中 序 遍 历 的 例 子 ， 它 可 以 打 印 出 一 个 树 的 所 有 值 （ 前 序 遍 历 和 后 序 遍 历 几 乎 和 这 个 一 样 ） ： t r i e 字 典 树 字 典 树 （ 读 “ t r e e ” ） 常 常 被 用 在 字 符 串 问 题 里 ， 它 是 一 个 n 元 树 ， 除 了 根 结 点 以 外 的 每 个 结 点 都 代 表 一 个 字 符 或 者 部 分 或 完 整 的 单 词 ， 而 且 沿 着 树 的 每 一 条 路 径 都 代 表 一 个 单 词 。 实 际 上 它 真 的 没 有 听 起 来 那 么 复 杂 ， 只 要 读 一 下 维 基 百 科 上 的 页 面 、 了 解 该 如 何 构 建 一 个 字 典 树 以 及 如 何 查 询 其 中 的 数 值 就 行 。 请 注 意 ， 你 可 以 通 过 前 序 遍 历 输 出 字 典 树 中 的 所 有 键 。 作 为 一 个 练 习 ， 你 可 以 想 一 想 自 己 会 如 何 利 用 字 典 树 实 现 自 动 完 成 功 能 。 最 后 是 h e a p s 堆 ， 它 也 被 称 为 优 先 队 列 ， 是 你 应 该 了 解 的 最 后 一 种 数 据 结 构 。 它 们 通 常 都 是 满 足 堆 属 性 堆 属 性 的 二 叉 树 ： 每 个 结 点 的 子 树 的 值 都 比 结 点 本 身 的 值 小 ， 或 者 与 它 相 等 。 所 以 根 结 点 的 值 总 是 最 大 的 ， 也 就 是 说 你 总 能 找 到 最 大 值 ， 但 代 价 就 是 寻 找 其 他 任 何 一 个 值 所 需 的 时 间 都 是 O ( n ) 。 插 入 和 删 除 所 需 的 时 间 依 然 是 O ( l o g   n ) 。 有 向 图 / 无 向 图 / 加 权 图 和 树 一 样 ， 图 也 是 由 带 子 集 的 结 点 组 成 的 ， 但 和 树 不 一 样 的 地 方 在 于 ， 这 些 结 点 可 以 有 多 个 父 结 点 ， 所 以 可 能 会 形 成 自 自 l o o p 环 环 或 者 c y c l e 圈 。 除 了 链 接 — — 也 被 称 作 e d g e s 边 — — 之 外 ， 两 个 结 点 之 间 可 能 地 有 比 指 针 更 多 的 信 息 ， 而 且 可 能 会 有 值 和 权 重 权 重 。 边 有 方 向 的 图 被 称 为 有 向 图 ， 而 只 有 双 向 指 针 的 图 被 称 为 无 向 图 。 边 上 有 权 重 的 图 被 称 为 加 权 图 。 有 三 种 方 法 来 表 示 图 ， 但 你 只 要 搞 清 楚 a d j a c e n c y   m a t r i c e s 邻 接 矩 阵 和 a d j a c e n c y   l i s t s 邻 接 表 就 行 了 。 你 应 该 了 解 它 们 计 算 的 复 杂 程 度 、 它 们 需 要 折 衷 的 地 方 ， 以 及 如 何 在 现 实 的 代 码 中 实 现 它 们 。 用 哪 种 方 法 取 决 于 你 有 的 图 的 类 型 ， 比 如 连 接 完 整 的 简 单 图 可 能 用 邻 接 矩 阵 来 实 现 更 好 ， 而 稀 疏 一 些 的 图 则 可 能 用 邻 接 表 来 表 示 更 好 。 请 注 意 ， 如 果 你 是 在 实 现 加 权 图 ， 很 可 能 需 要 定 义 一 个 E d g e 类 。 1 .   v o i d   i n O r d e r T r a v e r s a l ( N o d e   r o o t )   { 2 .     i f   ( r o o t   = =   n u l l )   r e t u r n ; 3 .     i n O r d e r T r a v e r s a l ( r o o t . g e t L e f t ( ) ) ; 4 .     / /   D o   s o m e t h i n g   w i t h   t h e   v a l u e 5 .     S y s t e m . o u t . p r i n t l n ( r o o t . g e t V a l u e ( ) ) ; 6 .     i n O r d e r T r a v e r s a l ( r o o t . g e t R i g h t ( ) ) ; 7 .   }
图 论 是 一 个 非 常 宽 泛 的 话 题 ， 所 以 很 难 知 道 一 个 人 应 该 为 一 场 面 试 去 熟 悉 多 少 种 图 论 算 法 ， 所 以 我 只 是 列 出 了 我 认 为 可 以 覆 盖 9 0 % 图 论 问 题 的 内 容 ： 你 绝 对 必 须 知 道 该 如 何 遍 历 一 个 图 （ 深 度 优 先 或 者 广 度 优 先 ） ， 以 及 如 何 做 t o p o l o g i c a l   s o r t i n g 拓 扑 排 序 ， 你 应 该 知 道 如 何 实 现 D i j k s t r a 迪 杰 斯 特 拉 的 最 短 路 径 算 法 （ 这 里 有 一 个 制 作 精 巧 的 视 频 解 释 了 这 一 算 法 ） ， 同 时 也 要 知 道 如 何 实 现 P r i m 普 里 姆 算 法 。 最 后 ， 如 果 你 还 知 道 如 何 实 现 A * 搜 索 算 法 ， 那 就 更 好 了 。 其 他 数 据 结 构 使 用 以 上 数 据 结 构 ， 你 就 可 能 解 决 绝 大 多 数 问 题 了 ， 但 也 请 尽 管 在 这 个 部 分 下 留 言 ， 为 其 他 读 者 推 荐 其 他 数 据 结 构 。 位 操 作 要 想 处 理 位 元 ， 你 必 须 先 得 知 道 在 t w o ’ s   c o m p l e m e n t 二 进 制 补 码 标 记 内 部 ， 数 字 是 如 何 表 示 的 — — 二 进 制 补 码 和 无 格 式 二 进 制 标 记 是 一 样 的 ， 只 是 负 数 要 “ 进 行 位 元 翻 转 之 后 再 加 1 ” 。 比 如 要 想 得 到 数 字 - 1 ， 你 要 从 用 8 位 二 进 制 整 数 表 示 是 0 0 0 0 0 0 0 1 的 1 开 始 。 对 每 一 个 位 元 进 行 翻 转 之 后 的 结 果 是 1 1 1 1 1 1 1 0 ， 再 加 上 1 就 是 1 1 1 1 1 1 1 1 ， 也 就 成 了 二 进 制 补 码 中 的 - 1 。 左 移 位 左 移 位 运 算 符 “ < < ” 会 把 位 元 移 向 左 边 ， 用 0 来 补 上 移 走 之 后 的 空 位 。 右 移 位 右 移 位 运 算 符 “ > > ” 会 把 一 个 位 模 式 向 右 移 ， 但 当 向 右 移 动 负 数 时 ， 它 的 作 用 在 不 同 编 程 语 言 中 也 不 一 样 ， 在 J a v a 中 ， 右 移 位 会 用 符 号 扩 充 的 办 法 ， 用 1 来 填 充 负 数 中 的 空 位 。 逻 辑 右 移 位 逻 辑 右 移 位 运 算 符 “ > > > ” 是 J a v a 和 J a v a s c r i p t 中 独 有 的 ， 无 论 数 值 是 多 少 ， 它 都 用 0 来 填 充 空 位 。 设 置 某 一 位 设 置 某 一 位 ： 可 以 用 按 位 或 按 位 或 运 算 符 （ | ） 。 清 除 某 一 位 清 除 某 一 位 ： 可 以 用 按 位 与 按 位 与 运 算 符 （ & ） ， 并 且 用 取 反 取 反 运 算 符 （ ~ ） 来 屏 蔽 所 有 你 不 想 清 除 的 位 元 。 清 除 一 直 到 清 除 一 直 到 i 的 所 有 有 效 位 元 的 所 有 有 效 位 元 ： 切 换 某 一 位 元 切 换 某 一 位 元 ： 可 以 用 按 位 异 或 按 位 异 或 运 算 符 （ ^ ） 获 得 一 个 位 元 获 得 一 个 位 元 ： 对 你 想 检 查 的 位 元 用 按 位 与 按 位 与 1 .   n u m   | =   1   < <   x ;   / / 这 行 代 码 将 会 设 置 位 元 x 1 .   n u m   & =   ~ ( 1   < <   x ) ;   / / 这 会 清 除 位 元 x 1 .   n u m   & =   ( 1   < <   ( i   +   1 ) )   - 1 ; 1 .   n u m   ^ =   1   < <   x ;   / / 这 会 切 换 位 元 x
设 计 模 式 / 面 向 对 象 编 程 和 面 向 对 象 编 程 相 关 的 问 题 ， 一 般 会 涉 及 到 设 计 相 关 类 里 的 集 ， 以 便 检 验 你 对 面 向 对 象 编 程 的 熟 悉 程 度 ， 并 了 解 你 是 如 何 架 构 代 码 的 。 你 可 以 使 用 界 面 和 / 或 抽 象 的 类 来 说 明 ， 并 记 住 用 S i n g l e t o n 单 例 模 式 、 F a c t o r y 工 厂 方 法 模 式 和 S t r a t e g y 策 略 模 式 来 解 决 这 类 问 题 ， 在 编 写 优 雅 而 可 维 护 的 代 码 方 面 ， 它 们 能 对 你 有 长 久 的 助 益 。 编 程 应 该 知 道 的 事 情 要 知 道 如 何 用 你 正 在 使 用 的 编 程 语 言 来 读 取 读 取 和 写 入 写 入 文 件 ， 并 且 要 知 道 如 何 生 成 随 机 数 随 机 数 。 数 学 你 并 不 是 在 面 试 数 学 相 关 的 职 位 ， 但 考 虑 到 我 们 被 计 数 和 测 量 的 问 题 所 包 围 ， 所 以 有 一 些 数 学 概 念 也 成 了 编 程 面 试 时 关 注 的 东 西 ， 比 较 重 要 的 有 质 数 、 b a s e   c o n v e r s i o n s 进 制 转 换 和 一 些 基 本 的 组 合 数 学 。 对 于 质 数 质 数 ， 要 大 概 知 道 为 什 么 它 们 很 重 要 ， 并 且 要 知 道 每 一 个 数 都 可 以 被 分 解 成 质 数 的 和 。 你 还 得 知 道 如 何 实 现 s i e v e   o f   E r a t o s t h e n e s 埃 拉 托 斯 特 尼 筛 法 。 对 于 基 本 的 组 合 数 学 ， 你 得 知 道 排 列 和 组 合 。 排 列 排 列 是 对 一 个 集 合 中 的 数 按 照 一 定 的 次 序 或 者 顺 序 进 行 整 理 。 比 如 对 于 集 合 { 1 , 2 , 3 } ， 就 有 6 种 排 列 的 方 式 ， 也 就 是 ( 1 , 2 , 3 ) 、 ( 1 , 3 , 2 ) 、 ( 2 , 1 , 3 ) 、 ( 2 , 3 , 1 ) 、 ( 3 , 1 , 2 ) 和 ( 3 , 2 , 1 ) 。 n 个 不 同 数 字 的 排 列 方 式 一 共 有 n ! 种 。 还 有 一 种 排 列 叫 部 分 排 列 部 分 排 列 ， 也 就 是 从 n 个 数 字 的 集 合 中 取 出 k 个 不 同 的 元 素 ， 然 后 再 进 行 排 序 。 这 种 排 列 可 以 用 下 面 的 公 式 来 表 达 ： 部 分 排 列 公 式 组 合 则 是 从 一 个 组 里 选 择 成 员 的 一 种 方 法 ， 因 此 选 择 的 顺 序 并 不 重 要 。 比 如 一 手 牌 可 以 被 描 述 成 是 从 5 2 张 一 摞 的 牌 堆 （ n = 5 2 ） 中 选 出 5 张 组 成 一 组 （ k = 5 ） 。 从 有 n 个 元 素 的 集 合 中 挑 出 k 个 元 素 ， 当 k > n 时 ， 不 存 在 相 应 的 组 合 ， 否 则 这 k 个 元 素 的 组 合 的 数 量 可 以 用 下 面 的 公 式 来 表 达 ： 当 k < = n 时 ， 从 有 n 个 元 素 的 集 合 中 挑 出 k 个 元 素 的 组 合 形 式 数 量 的 一 般 公 式 。 并 发 并 发 问 题 在 面 试 中 并 不 常 见 ， 但 也 确 实 有 过 ， 所 以 你 肯 定 不 想 到 时 候 毫 无 准 备 ， 那 就 再 去 看 一 下 如 何 生 成 线 程 、 使 用 同 步 以 及 锁 定 对 共 享 资 1 .   b i t   =   n u m   &   ( 1   < <   x ) ;
来 源 ： 简 书 原 文 ： h t t p s : / / m e d i u m . c o m / @ d e c l e r c q / h o w - t o - c r u s h - t h e - c o d i n g - i n t e r v i e w - 1 f c 8 a 4 6 9 5 d 7 c 作 者 ：   S t e f a n   D e   C l e r c q 译 文 ： h t t p : / / w w w . j i a n s h u . c o m / p / d 3 4 c 3 3 5 a 6 c f d / c o m m e n t s / 7 6 6 5 5 5 译 者 ：   N e x t o f f e r 源 的 访 问 ， 并 理 解 会 导 致 d e a d l o c k s 死 锁 的 几 种 情 况 。 准 备 这 个 话 题 有 一 个 好 办 法 ， 那 就 是 去 做 出 来 一 个 你 最 喜 欢 的 数 据 结 构 的 同 步 版 本 。 面 面 试 时 试 时 的 行 的 行 为 举 为 举 止 止 做 些 功 课 ， 了 解 一 下 要 面 试 的 公 司 ， 了 解 一 下 你 自 己 ， 以 及 为 什 么 你 要 去 这 家 公 司 做 些 功 课 ， 了 解 一 下 要 面 试 的 公 司 ， 了 解 一 下 你 自 己 ， 以 及 为 什 么 你 要 去 这 家 公 司 。 要 理 解 公 司 在 做 的 事 、 你 的 新 工 作 涉 及 哪 些 东 西 ， 以 及 它 最 让 你 激 动 的 地 方 是 什 么 。 换 工 作 是 件 大 事 ， 所 以 要 认 真 对 待 它 ， 提 前 做 些 研 究 。 保 持 积 极 心 态 。 保 持 积 极 心 态 。 保 持 一 个 好 的 情 绪 ， 要 微 笑 ， 不 要 谈 论 和 你 现 在 或 者 之 前 的 工 作 有 关 的 负 面 信 息 ， 当 描 述 挑 战 的 时 候 ， 要 保 持 乐 观 的 语 调 ， 并 强 调 你 从 中 学 到 的 积 极 的 东 西 。 本 条 是 前 一 条 里 说 的 不 要 向 面 试 官 传 递 负 面 信 息 的 必 然 结 果 。 本 条 是 前 一 条 里 说 的 不 要 向 面 试 官 传 递 负 面 信 息 的 必 然 结 果 。 一 些 面 试 官 会 问 你 现 在 感 觉 如 何 ， 千 万 别 说 你 之 前 受 不 了 某 一 位 或 两 位 面 试 官 ， 一 定 要 说 所 有 事 情 都 非 常 好 。 要 保 持 激 情 ！ 要 保 持 激 情 ！ 要 让 你 的 激 动 之 情 闪 亮 全 场 ， 并 展 示 出 你 对 软 件 开 发 、 技 术 和 解 决 重 大 问 题 的 热 情 。 要 问 问 题 。 要 问 问 题 。 要 真 正 对 你 的 面 试 官 每 天 都 在 做 什 么 抱 有 真 正 的 兴 趣 ， 问 问 他 们 工 作 中 遇 到 的 机 遇 与 挑 战 ， 提 前 准 备 几 个 程 式 化 的 问 题 ， 显 示 一 下 你 对 公 司 和 这 个 职 位 的 兴 趣 。 不 过 无 论 你 做 什 么 ， 都 别 问 对 方 “ 你 感 觉 如 何 ” 。 首 先 ， 你 很 可 能 会 收 到 同 样 程 式 化 的 回 答 ， 其 次 ， 把 面 试 你 的 人 摆 在 那 样 一 个 位 置 上 ， 也 不 是 什 么 好 主 意 。 保 持 亲 切 感 ， 并 形 成 闭 环 。 保 持 亲 切 感 ， 并 形 成 闭 环 。 当 你 结 束 面 试 之 后 ， 给 招 聘 你 的 人 发 一 句 简 短 的 感 谢 语 ， 让 他 们 知 道 你 对 这 次 面 试 的 感 觉 。 回 想 你 学 到 的 东 西 。 回 想 你 学 到 的 东 西 。 无 论 结 果 如 何 ， 你 都 能 学 到 一 些 东 西 — — 可 以 是 知 识 上 的 某 个 缺 失 ， 也 可 以 是 新 的 面 试 问 题 — — 所 以 要 做 自 我 反 思 ， 从 自 己 的 经 历 中 学 习 。 祝 各 位 职 场 和 面 试 好 运 ！
阅 读 原 文
回复

举报

高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver| 手机版| 小黑屋|
Powered by Discuz! X3.4 Copyright © 2001-2020, Tencent Cloud. 商业源码建议获取授权，如侵犯您的权益，请联系客服处理