在 Devin 中试用 DeepWiki 处理私有仓库
DeepWiki

kdn251/面试

菜单

其他公司面试问题

相关源文件

本页面提供本仓库中没有专门章节的公司技术面试题的全面概述。虽然亚马逊、谷歌、Facebook 和微软等大型科技公司都有自己的专属章节（参见亚马逊面试题、谷歌面试题、Facebook 面试题和微软面试题），但本节重点介绍来自领英、爱彼迎、优步、Snapchat、Palantir、雅虎和 Adobe 等其他知名公司的问题。

涵盖的公司

本节涵盖以下公司的面试问题

公司常见问题类型
领英动态规划，图算法
爱彼迎哈希表，数组操作，动态规划
优步字符串操作，哈希表，图算法
Snapchat矩阵操作，哈希表
Palantir数组操作，数据结构
雅虎哈希表，数组操作
Adobe数组算法，计数问题
苹果矩阵操作，验证问题

来源：company/linkedin/HouseRobber.java company/airbnb/HouseRobber.java company/airbnb/ContainsDuplicate.java company/uber/ValidSudoku.java company/uber/GenerateParentheses.java company/snapchat/ValidSudoku.java company/apple/ValidSudoku.java company/palantir/ContainsDuplicate.java company/yahoo/ContainsDuplicate.java company/adobe/MajorityElement.java company/apple/ValidSudoku.java

按公司划分的问题分布

下图展示了公司与其常考问题类型之间的分布和关系

来源：company/linkedin/HouseRobber.java company/airbnb/HouseRobber.java company/airbnb/ContainsDuplicate.java company/uber/ValidSudoku.java company/uber/GenerateParentheses.java company/snapchat/ValidSudoku.java company/apple/ValidSudoku.java company/palantir/ContainsDuplicate.java company/yahoo/ContainsDuplicate.java company/adobe/MajorityElement.java company/apple/ValidSudoku.java

跨公司的常见面试问题

有几个问题在多家公司的面试中频繁出现。下图将具体问题实现映射到常问这些问题的公司

来源：company/linkedin/HouseRobber.java company/airbnb/HouseRobber.java company/airbnb/ContainsDuplicate.java company/uber/ValidSudoku.java company/snapchat/ValidSudoku.java company/apple/ValidSudoku.java company/palantir/ContainsDuplicate.java company/yahoo/ContainsDuplicate.java company/uber/GenerateParentheses.java company/adobe/MajorityElement.java

关键问题与解决方案

动态规划示例

房屋抢劫犯

打家劫舍问题是领英和爱彼迎常问的经典动态规划问题。

问题描述：你是一名专业窃贼，计划沿着一条街道抢劫房屋。每栋房屋都藏有一定数量的钱。阻止你抢劫每栋房屋的唯一限制是，相邻的房屋都连接着安全系统，如果两栋相邻的房屋在同一个晚上被闯入，系统会自动联系警方。

解决方案：该解决方案使用动态规划方法，其中每个索引的状态表示到该房屋为止可以抢劫的最大金额。

主要实现细节

  • 创建一个 DP 数组，其中 dp[i] 表示到房屋 i 为止可以抢劫的最大金额
  • 基本情况：dp[0] = nums[0] 和 dp[1] = max(nums[0], nums[1])
  • 递推关系：dp[i] = max(dp[i-2] + nums[i], dp[i-1])

实现可以在company/linkedin/HouseRobber.java5-26 和 company/airbnb/HouseRobber.java5-26

来源：company/linkedin/HouseRobber.java company/airbnb/HouseRobber.java leetcode/dynamic-programming/HouseRobber.java

哈希表示例

存在重复元素

包含重复项问题是爱彼迎、Palantir 和雅虎常问的常见哈希表问题。

问题描述：给定一个整数数组，判断数组中是否存在重复元素。如果某个值在数组中出现至少两次，则函数返回 true；如果数组中的每个元素都互不相同，则返回 false。

解决方案：该解决方案使用 HashMap 来跟踪已见的元素

  • 遍历数组
  • 对于每个元素，检查它是否已在 HashMap 中
  • 如果是，则返回 true（找到重复项）
  • 如果不是，则将其添加到 HashMap
  • 如果我们完成迭代而没有找到重复项，则返回 false

实现可以在company/airbnb/ContainsDuplicate.java4-17 company/palantir/ContainsDuplicate.java4-17 和 company/yahoo/ContainsDuplicate.java4-17

来源：company/airbnb/ContainsDuplicate.java company/palantir/ContainsDuplicate.java company/yahoo/ContainsDuplicate.java leetcode/hash-table/ContainsDuplicate.java

有效的数独

有效的数独问题是一个使用哈希集进行矩阵验证的问题，它出现在苹果、Snapchat 和优步的面试中。

问题描述：确定一个 9x9 的数独棋盘是否有效。只需根据以下规则验证已填充的单元格

  1. 每行必须包含 1-9 的唯一数字
  2. 每列必须包含 1-9 的唯一数字
  3. 每九个 3x3 的子方块必须包含 1-9 的唯一数字

解决方案：该解决方案在一次遍历棋盘时检查所有三个条件

  • 创建三组 HashSet：一组用于行，一组用于列，一组用于 3x3 方块
  • 遍历棋盘
  • 对于每个单元格，检查该数字是否已在对应的行、列或方块 HashSet 中
  • 如果是，则返回 false；否则，将其添加到相应的集合中
  • 如果我们在遍历整个棋盘后没有找到重复项，则返回 true

实现可以在company/apple/ValidSudoku.java8-30 company/snapchat/ValidSudoku.java8-30 和 company/uber/ValidSudoku.java8-30

来源：company/apple/ValidSudoku.java company/snapchat/ValidSudoku.java company/uber/ValidSudoku.java leetcode/hash-table/ValidSudoku.java

回溯法示例

生成括号

生成括号问题是优步常问的经典回溯法问题。

问题描述：给定 n 对括号，编写一个函数来生成所有格式正确的括号组合。

解决方案：该解决方案使用回溯法来构建有效组合

  • 使用递归探索所有可能的组合
  • 跟踪开括号和闭括号的数量
  • 只有当开括号的数量多于闭括号的数量时才添加闭括号
  • 当字符串长度达到 2*n 时，将其添加到结果列表

实现可以在company/uber/GenerateParentheses.java2-23

来源：company/uber/GenerateParentheses.java leetcode/string/GenerateParentheses.java leetcode/backtracking/GenerateParentheses.java

数组操作示例

多数元素

多数元素问题是 Adobe 常问的一个数组计数问题。

问题描述：给定一个大小为 n 的数组，找到多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 次的元素。

解决方案：该解决方案使用 HashMap 来计数出现次数

  • 遍历数组
  • 对于每个元素，在 HashMap 中增加其计数
  • 如果计数超过 n/2，则返回该元素作为多数元素

实现可以在company/adobe/MajorityElement.java4-24

来源：company/adobe/MajorityElement.java leetcode/array/MajorityElement.java

问题解决方法

下图展示了应对这些公司面试中常见问题类型的一般方法

来源：基于所有已检查代码示例的分析。

公司特有模式

每家公司都倾向于关注特定类型的问题或编码方面

领英

领英侧重于考察算法设计基础的问题，特别是动态规划。打家劫舍问题就是这种对最优子结构和状态转移关注的例证。

来源：company/linkedin/HouseRobber.java

爱彼迎

爱彼迎的问题常涉及数据结构优化和边缘情况处理。他们的诸如打家劫舍和包含重复项等问题，既考察算法知识，也考察对细节的关注。

来源：company/airbnb/HouseRobber.java company/airbnb/ContainsDuplicate.java

优步

优步的面试问题通常涉及几何问题、字符串操作和验证问题。有效的数独和生成括号问题展示了他们对约束满足和处理复杂规则的重视。

来源： company/uber/ValidSudoku.java company/uber/GenerateParentheses.java

Snapchat 和 苹果

两家公司都侧重于矩阵和网格类问题，这从它们使用“有效数独”问题可见一斑，该问题需要高效地遍历和验证二维结构。

来源： company/snapchat/ValidSudoku.java company/apple/ValidSudoku.java

Palantir 和 雅虎

这些公司强调高效的数据结构使用和数组操作，经常使用“包含重复元素”等问题来测试候选人优化时间复杂度与空间复杂度的能力。

来源： company/palantir/ContainsDuplicate.java company/yahoo/ContainsDuplicate.java

Adobe

Adobe 的面试题倾向于考察计数问题和高效数组算法，例如“多数元素”问题，该问题需要追踪元素频率。

来源： company/adobe/MajorityElement.java

准备策略

为了准备这些公司的面试，请考虑以下策略：

  1. 注重基础: 掌握基本数据结构（数组、哈希表、树、图）和算法（排序、搜索、动态规划、回溯）。

  2. 针对公司进行准备: 根据本文概述，复习目标公司常问的问题类型。

  3. 练习实现: 练习为上述问题类型编写简洁、高效的代码。

  4. 时间与空间复杂度分析: 对于每个问题，分析并优化你解决方案的时间和空间复杂度。

  5. 边界情况: 特别注意边界情况，例如空数组、单元素输入和边界条件。

  6. 测试驱动开发: 在实现解决方案之前练习编写测试用例，以确保正确性。

来源：基于所有已检查代码示例的分析。

结论

尽管每家公司都有自己的侧重点，但各公司面试问题的类型存在显著重叠。掌握本文讨论的核心问题类型将使你为 LinkedIn、Airbnb、Uber、Snapchat、Palantir、Yahoo、Adobe、Apple 以及类似公司的面试做好充分准备。

本仓库提供的实现方案为这些常见的面试问题提供了高效、结构良好的宝贵示例。学习它们不仅是为了算法方法，也是为了学习编码风格、边界情况处理和优化技术。