程序员社区
当前位置：IDEA激活码 > 未分类 > 正文

30个苹果编程面试题（含解决方案）

2022-02-03 分类：未分类 阅读(167)

【译文】原文地址
进入苹果工作是很多开发者的梦想--但是编程面试准备不是件容易的事。为了让使你生活更简单，我们整理了30个最有可能你希望在苹果面试中碰到的面试题。

我们从软件工程师正常的面试流程开始，然后用代码和复杂度拆解苹果top面试题。源文使用c++实现，这里我改成自己Go实现。
先过下目录：

  • 苹果面试流程
  • 数组和图问题
  • 链表问题
  • 树问题
  • 字符串问题
  • 动态规划问题
  • Math，统计和回溯
  • 搜索和设计问题
  • 行为面试题
  • 面试准备小贴士

苹果面试流程

苹果软件工程师面试流程和其他的大公司不同，因为它有自己的面试轮次和现场流程。如果苹果联系你进行面试，一般流程如下：

  • 招聘人员预筛选：从投简历到第一次联系将持续一周左右。招聘人员将电话联系你，大概15-30分钟，不会问很专业的问题。一般是你为什么想到苹果工作？或者是你最喜欢苹果的哪款产品或服务？
  • 电话技术面：一般一周过后，将会联系你下一轮的技术面试。将会有一到两个关于你简历问题以及数据结构和算法编程问题的电话面试。编程面试大概45-60分钟-以及30分钟完成挑战。
  • 现场面试：现场面试将持续大概六个小时。你将和8-12个苹果员工会面，包含行为、领域知识和编程混合面试。每轮大概45分钟到一个小时，你将被问到技术问题。行为问题当然对招聘主管来说也很重要。
    你需要知道的数据结构：数组、链表、栈、队列、树、图、堆、哈希集合、哈希表。
    你应该知道的算法：深度优先搜索、广度优先搜索、二分查找、快速排序、归并排序、动态规划和分治法。

数组和图问题

找三个数和

这个练习的目标是找到三个数的和等于给定的值。
问题描述：给定一个整型数组和一个值，判断数组是否存在三个整数和等于给定的值。如下图所示：

30个苹果编程面试题（含解决方案）插图

package main

import (
    "fmt"
    "sort"
)

func findSumOfTwo(array []int, value int, startIndex int) bool {
    sort.Ints(array)
    j := len(array) -1
    for startIndex < j{
        sum := array[startIndex] + array[j]
        if sum == value{
            fmt.Println(startIndex)
            return true
        }
        if sum < value{
            startIndex += 1
        } else {
            j -= 1
        }
    }
    return false
}

func findSumOfThree(array []int, requiredSum int) bool {
    sort.Ints(array)
    for i:=0; i < len(array) -2; i++{
        remainSum := requiredSum - array[I]
        if findSumOfTwo(array, remainSum, i+1){
            fmt.Println(i)
            return true
        }
    }
    return false
}

func main() {
    var s= []int{-25, -10, -7, -3, 2, 4, 8, 10}
    fmt.Println(findSumOfThree(s, -8))
    fmt.Println(findSumOfThree(s, -25))
    fmt.Println(findSumOfThree(s, -42))
    fmt.Println(findSumOfThree(s, 22))
    fmt.Println(findSumOfThree(s, -7))
    fmt.Println(findSumOfThree(s, -3))
    fmt.Println(findSumOfThree(s, 2))
    fmt.Println(findSumOfThree(s, 4))
    fmt.Println(findSumOfThree(s, 8))
    fmt.Println(findSumOfThree(s, 7))
    fmt.Println(findSumOfThree(s, 1))
}

在这个算法中我们先排序切片。然后固定一个元素e并找到另外一对整数(a,b)的值等于给定值减去固定元素e，那剩下的就是a+b。迭代数组中的每个元素e，然后找到一对(a,b)满足要求。如果找到了a,b，也就找到了a，b，e其和等于给定值即可停止循环。否则就重复以上步骤查看每个元素e。
时间复杂度：O(n2)
空间复杂度：O(n)

合并重叠间隔

给定的数组元素是两个整数组成的，要合并每组整数重合的部分，使得整个数组的各整数组合没有重叠。其中数组是根据整数组合的第一个数来排序过的。如以下这个数组（1，5），（3，7），（4，6），（6，8），这个数组所有的元素都有重合部分，最后合并成（1，8）。类似的（10，12）和（12，15）也要算重合的，合并后为（10，15）。

30个苹果编程面试题（含解决方案）插图1
package main

import (
    "fmt"
)

type point struct {
    first  int
    second int
}

func mergeIntervals(p []point) []point {
    result := make([]point, 0)
    if len(p) == 0 {
        return p
    }
    result = append(result, p[0])
    for i := 1; i < len(p); i++ {
        x1 := p[i].first
        y1 := p[i].second
        //x2 := result[len(result)-1].first
        y2 := result[len(result)-1].second
        if y2 >= x1 {
            result[len(result)-1].second = max(y1, y2)
        } else {
            result = append(result, p[I])
        }
    }
    return result
}

func max(a, b int) int {
    if a >= b {
        return a
    } else {
        return b
    }
}

func main() {
    p := []point{
        {1, 5},
        {4, 6},
        {6, 7},
        {6, 8},
        {10, 12},
        {11, 15}}
    fmt.Println(mergeIntervals(p))
}

这个问题可以通过线性遍历来解决。给定间隔整数数组，我们将和result进行合并。数组中的每个组合进行合并：

  • 如果元素和结果中的最后一个有重叠，就将这两个合并然后更新result最后一个元素组合。
  • 否则就将这个组合直接添加到result结果中。
    时间复杂度：O(n)
    空间复杂度：O(n)

克隆有向图

该练习指的是使用hashtable和深度优先来克隆有向图并打印图。
问题描述：给定有向图的根节点，通过深度拷贝来克隆图。克隆的图要有相同的边和节点。

30个苹果编程面试题（含解决方案）插图2
type Node struct {
    data int
    neighbors []*Node
}

func cloneRec(root *Node, nodeComplete map[*Node]*Node) *Node {
    if root == nil{
        return nil
    }
    pNew := &Node{root.data, make([]*Node,0)}
    nodeComplete[root] = pNew
    for _, p := range root.neighbors{
        if _, ok := nodeComplete[p];ok{
            pNew.neighbors = append(pNew.neighbors, p)
        } else {
            pNew.neighbors = append(pNew.neighbors, cloneRec(p, nodeComplete))
        }
    }
    return pNew
}

使用深度优先遍历，在遍历的过程中为每个节点创建一个拷贝。使用map来存储已经遍历过的节点防止重复遍历。map的key是源图中的节点，value是对应克隆过的节点。
时间复杂度：O(n)
空间复杂度：O(n)

链表问题

求两个整数和

这个练习的目标是求两个链表中对应整数和。
问题描述：给定两个列表头指针，每个链表存有整数，求对应两整数和返回新的链表。

30个苹果编程面试题（含解决方案）插图3
type LinkedListNode struct {
    data int
    next *LinkedListNode
}

func addInteger(integer1, integer2 *LinkedListNode) *LinkedListNode {
    var result, last *LinkedListNode
    var carry int
    for integer1 != nil || integer2 != nil || carry > 0 {
        var first, second int
        if integer1 == nil {
            first = 0
        } else {
            first = integer1.data
        }
        if integer2 == nil {
            second = 0
        } else {
            second = integer2.data
        }
        sum := first + second + carry
        pNew := &LinkedListNode{sum % 10, nil}
        carry = sum / 10
        if result == nil {
            result = pNew
            last = result
        } else {
            last.next = pNew
        }
        last = pNew
        if integer1 != nil {
            integer1 = integer1.next
        }
        if integer2 != nil {
            integer2 = integer2.next
        }
    }
    return result
}

为了更好的理解，我们可以考虑一个例子。假如要将整数9901和237相加。结果是10138。为了简便，整数的各个位数在链表中是反向存储的。最重要的是链表的最后一个数的处理。先从链表开头求和。每次迭代，将链表当前值相加并将和除以10的余数作为新链表的值。保存当前和的进位。求完两个列表中所有的整数和后。看哪个链表先结束，我们将继续迭代另一个链表。等两个链表都遍历结束并且没有进位，程序就结束了。
时间复杂度：O(n)
空间复杂度：O(n)

合并两个有序链表

问题描述：给定两个排序的链表，合并后链表还是有序的。

type LinkedListNode struct {
    data int
    next *LinkedListNode
}

func mergeSortedList(head1, head2 *LinkedListNode) *LinkedListNode {
    //如果两个链表都空，合并后还是空的
    //如果其中一个是空的，那另一个就是合并后的结果
    if head1 == nil {
        return head2
    } else if head2 == nil {
        return head1
    }
    var mergeHead *LinkedListNode
    if head1.data <= head2.data {
        mergeHead = head1
        head1 = head1.next
    } else {
        mergeHead = head2
        head1 = head1.next
    }
    mergeTail := mergeHead
    for head1 != nil && head2 != nil {
        var temp *LinkedListNode
        if head1.data <= head2.data {
            temp = head1
            head1 = head1.next
        } else {
            temp = head2
            head1 = head2.next
        }
        mergeTail.next = temp
        mergeTail = temp
    }
    if head1 != nil {
        mergeTail.next = head1
    } else {
        mergeTail.next = head2
    }
    return mergeHead
}

为合并后的链表创建一个头节点和尾节点。比较两个链表的头节点，哪个小就是合并后节点的头节点。对两个链表后续的所有节点遍历，哪个节点小就先添加到合并后节点上去。将指针指向下一个节点。如果存在链表没有遍历完的节点，直接将其和后续的节点添加到合并链表尾部。初始状态合并链表是nil空的。
时间复杂度：O(m+n)，m和n分别是两个链表长度
空间复杂度：O(1)

树问题

判断二叉树是否相同

比较两颗二叉树，判断是否相同
问题描述：给定两个二叉树的根节点，判断是否相同。相同树节点分布和节点值相同。

30个苹果编程面试题（含解决方案）插图4
type TreeNode struct {
    data  int
    left  *TreeNode
    right *TreeNode
}

func areIdentical(root1, root2 *TreeNode) bool {
    if root1 == nil && root2 == nil {
        return true
    }
    if root1 != nil && root2 != nil {
        return (root1.data == root2.data) && areIdentical(root1.left, root2.left) &&
            areIdentical(root1.right, root2.right)
    }
    return false
}

使用递归解决。递归结束条件是两个节点都是nil空的或其中一个为空。两棵树A和B相同的条件是：

  • 根节点值相等或都为空
  • A的左子树和B的左子树相同
  • A的右子树和B的右子树相同
    使用深度优先同时遍历两棵树，比较每层来解决问题。
    时间复杂度：O(n)
    空间复杂度：最优情况O(h)，如果是平衡二叉树：O(logn)，最叉情况O(n)

反射二叉树节点

使用深度优先和自底向上将反射二叉树节点。
问题描述：给定二叉树根节点，必须交换左右子树节点

30个苹果编程面试题（含解决方案）插图5
type TreeNode struct {
   data  int
   left  *TreeNode
   right *TreeNode
}

func mirrorTree(root *TreeNode) {
   if root == nil {
       return
   }
   //将后续遍历二叉树
   if root.left != nil {
       mirrorTree(root.left)
   }
   if root.right != nil {
       mirrorTree(root.right)
   }
   //交换当前层左右节点
   temp := root.left
   root.left = root.right
   root.right = temp
}

后续遍历二叉树。对每个节点，将左右孩子节点进行交换。我们使用深度优先遍历，因此每个节点返回时，其所有的孩子节点都访问并交换过了。
时间复杂度：O(n)
空间复杂度：最差情况O(n)。

字符串问题

找出所有的回文子字符串

该练习的目标是给定字符串找出其中的回文子串。
问题描述：给定一个字符串，找出非单个字母的回文子字符串，给定字符串为“aabbbaa”。

package main

import "fmt"

func findPalindromeSubstring(input string, j, k int) int {
    count := 0
    for j >= 0 && k < len(input) {
        if input[j] != input[k] {
            break
        }
        fmt.Println(input[j : k+1])
        j -= 1
        k += 1
        count += 1
    }
    return count
}

func findAllPalindromeSubstring(s string) int {
    count := 0
    for i := 0; i < len(s); i++ {
        count += findPalindromeSubstring(s, i-1, I+1)
        count += findPalindromeSubstring(s, i, I+1)
    }
    return count
}

func main() {
    str := "aabbbaa"
    fmt.Println(findAllPalindromeSubstring(str))
}

遍历字符串的每个字母，从对应字母向左右查询看看对应两边的字母是否相等，同时要考虑基数个字母和偶数个字母情况。如果没找到回文子串就遍历下一个字母。如果两边的字母相等就打印出该回文子串。
时间复杂度：O(n2)
空间复杂度：O(1)

逆序排列句子中的单词

对给定的句子，将每个单词逆序。注意每个单词是如何用空格分隔的。
问题描述：将给定的句子单词逆序排列。给定的句子为“Hello World!"。

package main

import "fmt"

func str_Rev(s []byte) {
    length := len(s)
    if length < 2 {
    }
    bytes := []byte(s)
    i := 0
    j := len(s) - 1
    for i < j {
        bytes[i], bytes[j] = bytes[j], bytes[I]

        i += 1
        j -= 1
    }
}

func reverseWords(s string) string {
    if len(s) == 0{
        return ""
    }
    bytes := []byte(s)

    str_Rev(bytes)
    var start, end int
    for end < len(bytes){
        if bytes[start] == ' '{
            start += 1
        }
        end = start + 1
        for end < len(bytes) && bytes[end] != ' '{
            end += 1
        }
        str_Rev(bytes[start:end])
        start = end
    }
    return string(bytes)
}

func main() {
    str := " Hello World1 find you "
    fmt.Println(reverseWords(str))
}

解决这个问题分两步。第对整个句子作为字符串，对字母逆序排列。然后找出每个单词进行逆序字母。
时间复杂度：O(n)
空间复杂度：O(n)，这里是用了byte转换。

动态规划问题

子数组最大和

该练习目标是使用动态规划和Kadane算法找到子数组最大和。
问题描述：找到子数组最大和。如下数组，子数组最大和从索引为2到6之间的数和为12。

30个苹果编程面试题（含解决方案）插图6

package main

import "fmt"

func findMaxSubArray(a []int, n int) int {
    if n < 1 {
        return 0
    }
    currMax := a[0]
    gloablMax := a[0]
    for i := 1; i < n; i++ {
        if currMax < 0 {
            currMax = a[I]
        } else {
            currMax += a[I]
        }
        if gloablMax < currMax {
            gloablMax = currMax
        }
    }

    return gloablMax
}
func main() {
    a := []int{-4, 2, -5, 1, 2, 3, 6, -5, 1}
    fmt.Println(findMaxSubArray(a, len(a)))
}

使用Kadane算法解决。基本的思路就是遍历整个数组，找到每个位置对应最大子数组的和。使用currMax来存储当前子数组最大和，然后和全局最大和比较。
时间复杂度：O(n)
空间复杂度：O(1)

数学和统计

数的幂

问题描述：给定两个数，x和一个整数n，写一个函数计算x的n次幂。
power(2,5)=32
power(3,4)=81
power(1.5,3)=3.375
power(2,−2)=0.25

package main

import "fmt"

func powerRec(x float64, n int) float64 {
    if n == 0 {
        return 1
    }
    if n == 1 {
        return x
    }
    temp := powerRec(x, n / 2)
    if n % 2 == 0 {
        return temp * temp
    } else {
        return x * temp * temp
    }
}

func power(x float64, n int)  float64{
    isNegative := false
    if n < 0{
        isNegative = true
        n *= -1
    }
    result := powerRec(x, n)
    if isNegative{
        return 1 / result
    }
    return result
}
func main() {
    fmt.Println(power(8, -1))
}

使用分治法可高效地解决这种问题。在分解这一步，递归将n除以2直到达到基准条件。在合的过程，得到子问题的结果r并使用两步来计算当前问题的结果：

  • 如果n是偶数，结果就是r * r，r是子问题结果。
  • 如果是奇数，结果就是x * r * r。
    时间复杂度：O(logn)
    空间复杂度：O(logn)

找到所有的组合

这个练习的目的是使用回溯来找到所有的组合。
问题描述：给定一个正整数target，打印所有的整数可能组合和等于targe。输出的结果将是二位列表。如下所示target是5：

1, 4
2, 3
1, 1, 3
1, 2, 2
1, 1, 1, 2
1, 1, 1, 1, 1

解决方案：

package main

import "fmt"

func PrintAllSumRec(target int, currSum int, start int, output *[][]int, result []int) {
    if target == currSum {
        *output = append(*output, result)
    }
    for i := start; i < target; i++ {
        tempSum := currSum + I
        if tempSum <= target {
            result = append(result, i)
            PrintAllSumRec(target, tempSum, i, output, result)
            result = (result)[:len(result)-1]
        } else {
            return
        }
    }
}

func PrintAllSum(target int) [][]int {
    var output [][]int
    var result []int
    PrintAllSumRec(target, 0, 1, &output, result)
    return output
}
func main() {
    fmt.Println(PrintAllSum(4))
}

递归查看所有的可能组合的和，当和与给定值相等时，将组合添加到输出列表中。算法将递归检查所有的值。在每次递归调用，有一个for循环从start到targe，其中start初始值为1。currSum随着递归调用递增。当currSum等于target，我们知道result列表保存了组合数字。递归调用之前，result会添加一个数字，调用之后会将数字移除。
时间复杂度：O(n2)
空间复杂度：O(n)

查找和设计问题

在旋转过的数组中查找，该练习目标是在旋转后的数组中，查找有序数组元素。使用二分查找来解决。
问题描述：查找一个有序数组中的元素，元素是不重复的，而且数组经过任意选定值进行旋转过。假设数组没有重复元素。如果值不存在返回-1。
下面是一个未经旋转的数组：

30个苹果编程面试题（含解决方案）插图7

执行6次旋转后，数组变成如下样子：

30个苹果编程面试题（含解决方案）插图8

package main

import "fmt"

func binarySerach(array []int, start, end, key int) int {
    //假设所有的值是唯一的
    if start > end {
        return -1
    }
    mid := start + (end-start)/2
    if array[mid] == key {
        return mid
    }
    if array[start] <= array[mid] && key <= array[mid] && key >= array[start] {
        return binarySerach(array, start, mid-1, key)
    } else if array[mid] <= array[end] && key >= array[mid] && key <= array[end] {
        return binarySerach(array, mid+1, end, key)
    } else if array[end] <= array[mid] {
        return binarySerach(array, mid+1, end, key)
    } else if array[start] >= array[mid] {
        return binarySerach(array, start, mid-1, key)
    }
    return -1
}

func binarySearchRotated(a []int, key int) int {
    return binarySerach(a, 0, len(a)-1, key)
}

func main() {
    a := []int{6, 7, 9, 1, 2, 3, 4, 5}
    fmt.Println(binarySearchRotated(a, 3))
}

以上算法是二分查找的变种。注意到至少一半的数组总是有序的。如果key是在有序的那一半范围内，那问题就转为二分查找问题。否则，就丢弃排序的一半然后检查为排序的那一半。
时间复杂度：O(logn)
空间复杂度：O(logn)

实现一个LRU缓存

这个设计练习目标是实现一个最近最少使用度缓存（LRU），一个常用的缓存策略，运用了双向链表和哈希。
问题描述：LRU定义了从缓存中淘汰元素的策略，当缓存满了为新元素腾出空间，意思就是优先将最近最少被使用的元素丢弃。举一个只有四个缓存空间的例子。将1，2，3和4进行缓存。下图表示第一次访问了四个元素后的状态。

30个苹果编程面试题（含解决方案）插图9

下面我们缓存元素5。

30个苹果编程面试题（含解决方案）插图10

下面再看下如果元素2被再次访问。元素3将成为下一次最有可能被淘汰的对象。

30个苹果编程面试题（含解决方案）插图11

赞(0) 打赏
未经允许不得转载：IDEA激活码 » 30个苹果编程面试题（含解决方案）

相关推荐

IDEA永久激活破解教程,IDEA激活码

pycharm激活破解教程,pycharm激活码

Java视频资源

Java电子书

DataGrip激活教程 Docker Git教程 IntellIJ idea IntelliJ IDEA激活码 Java Java IO Java基础 Java基础面试题 Java集合面试题 Java面试题 JVM JVM面试题 Linux MySQL MySQL面试题 Nginx PyCharm PyCharm激活 redis Redis SpringBoot SpringBoot SpringBoot面试题 Web开发 剑指Offer系列 多线程 多线程并发面试题 字符串面试题 数据库 数据库 数据结构与算法 未分类 爬虫 电子书 软件下载

一个分享Java & Python知识的社区