Apple SWE New Grad面试题和答案
New Grad Interview Questions & Answers
苹果SWE New Grad面经，感觉身体被掏空
刚面完Apple的SWE New Grad岗，趁着记忆还热乎，赶紧来复盘一下，真的是一场硬仗。希望能给后来的小伙伴们一些参考，少走点弯路。
我的timeline：九月初海投 -> 十月中收到OA -> 十一月初Virtual Onsite -> 然后就是漫长的等待...
【OA - Online Assessment】 OA是在HackerRank上做的，给了7天时间，一旦开始就是90分钟倒计时。一共两道Coding题，难度大概是LC Medium。
第一道题是关于Array的，给了个unsorted array，让找一个triplet (a, b, c) 满足 a + b = c。这题不难，是Two Pointers的变种。先把Array排序，然后外层一个for loop遍历c，内层用Two Pointers在c的左边找a和b。Time Complexity是O(n^2)，Space Complexity是O(1)（如果不算排序的额外空间）。说实话，这题算是热身，没什么特别的坑。
第二道题稍微复杂一点，是关于Graph的。题目大意是给了一堆员工的直属关系，类似一个N叉树，然后给了两个员工ID，让找他们的LCA (Lowest Common Ancestor)。这题我当时卡了一下，因为给的不是一个标准的Tree结构，而是一个List of edges。所以第一步是先用HashMap把这个edge list转换成一个adjacency list来表示这个Graph/Tree。然后就可以用DFS来解了。先做一个DFS找到从root到两个目标员工的path，然后比较这两条path，最后一个相同的节点就是LCA。这道题的重点是建图，图建好了，剩下的就是常规的Tree traversal。
【Virtual Onsite】 Onsite是重头戏，我被安排在一天面完，一共四轮，每轮45分钟，连着来，中间就给15分钟休息，强度很大。
第一轮：Coding Round 面试官是个很nice的白人小哥，上来先聊了聊项目，然后出题。是一道关于String的题，判断一个String可不可以通过删除字符变成另一个String的subsequence。这题可以用Two Pointers做，一个pointer指向长String，一个指向短String，如果字符匹配，两个pointer都动，不匹配就只动长String的pointer。很简单，15分钟搞定。然后小哥又追问，如果有很多短String要判断，怎么优化？我当时提了用DP，预处理长String，建一个index，记录每个字符出现的位置。小哥表示满意。
第二轮：Coding Round 这轮的面试官看起来比较严肃，是个国人大哥。题目是经典的LRU Cache。这题踩过坑的人都知道，关键是要用对数据结构。一个HashMap来存key和value，实现O(1)的get，一个Doubly LinkedList来维护访问顺序。每次get或者put一个已有的key，都要把对应的node移到list的头部。如果put一个新key并且cache满了，就删掉list的尾部。这题我写的比较顺，因为之前刷到过好几次。写完代码，大哥让我解释了一下Time Complexity和Space Complexity，然后又问了些concurrency相关的问题，比如如果在多线程环境下，这个LRU Cache会有什么问题，怎么解决。我说可以用lock，大哥点了点头。
第三轮：System Design 终于到了System Design环节。不得不说，New Grad被问到System Design还是有点慌的。题目是设计一个类似iCloud Photo Library的系统，重点关注upload和storage。我当时就按照上课学的框架来，先clarify a few requirements，比如支持的file type，QPS，DAU等。然后画了high-level的architecture，包括client, load balancer, application server, metaData database, 和object storage (like S3)。我重点讲了upload的流程，比如client先跟application server要一个pre-signed URL，然后直接传到S3，这样可以减轻我们自己server的压力。面试官追问了几个问题，比如怎么处理duplicate files，怎么保证photo的durability和availability。总的来说，感觉New Grad的System Design更看重的是沟通和trade-off的分析能力，不要求你设计得多完美。
第四轮：Behavioral + Coding 最后一轮是Hiring Manager面。先是Behavioral Question，问了“Tell me about a time you had a conflict with your teammate”和“Why Apple?”。血泪教训，BQ一定要提前准备好故事，用STAR原则套。我当时就有一个故事没讲好，感觉有点减分。然后HM又出了一道很简单的Coding题，Find peak element in an array。用Binary Search就可以在O(logn)时间解决。感觉这轮的Coding只是想看看你还会不会写代码，重点还是在BQ。
【总结】 总的来说，Apple的面试还是挺看重基础的，Coding题不一定是最难的，但一定要bug-free，思路清晰。System Design和BQ也越来越重要。感觉自己这次表现一般般，希望能有好运吧。也祝大家都能拿到心仪的Offer！
#北美求职 #软件工程师 #面经 #Apple #SWE #NewGrad #CS #Coding #SystemDesign #面试经验
