Massive Algorithms: Apple Interview Misc

https://instant.1point3acres.com/thread/171890
我面的是localizationtool engineer，在linkedin上找的。过程是HR联系，Hiringmanager 30 minutes phone interview， 2 teamengineers back to back 30 minutes phone interview, onsite。

除了infiniteloop上面之外，creekblvd上面都是apple的小department 面试是从早上10点到下午4点，一共7轮，包括最后一轮HR聊天。是不是见不到manager就必定会挂的啊？我去的那天恰好department那个manager不在，悲剧。。每一轮都是有两个面试官跟你在一个小会议室里面试。第一轮：Hiringmanager和teammanager面试。可以理解为两个team的manager吧。先介绍自家department的组成，分三个小team，每个team负责不一样的工作。大概跟我之前的组差不多，只是Apple的组更大一些。然后问简历，问之前实习的内容。然后问一个具体工作中出现的问题，应该如何解决。感觉主要都是考察对xml和localization的熟悉程度。第二轮：面完第一轮水都没来得及喝就第二轮了。两个engineer，问了一下简历，然后就开始做coding，unixscripting。说有folder1/X/Y/Z/pic.jpg之类的，将Zfolder底下的所有图片文件（假设后缀为.img和.jpg）重命名为 X_Y_Z_pic.jpg 然后复制到 folder2 底下去。用了个Javahardcode，没用unix，实在没做过不会啊。。只会一些很基本的command。第三轮：感觉跟第二轮差不多，也是问简历，问之前实习的内容，然后问很基本的unixcommand的问题。过了吧。中间的实在是记忆不太深刻。午餐：manager有interviewcoupon，就不用我出钱，跟他们去了苹果另外一栋楼的一个餐厅里，点了个鸡胸肉。没有亚洲食物的确不太好。然后就跟着他们组去到另外一栋楼里的露天阳台吃饭。一共9个人。他们一直在开玩笑，我只能陪笑。。插不上话呀。==。。感觉午餐也是一个面试，实在是心累。第四轮：午餐回来没有休息就立刻下一轮面试了。两个engineers，问简历，实习上的问题。然后就问了unix的问题说如果有一个文件，如何找出所有name。我就说用grep来找，特点是首字母都是大写。就写一个regularexpression就好了。然后这有个缺点，就是He和She，这些中文姓名但是在英语里不算是姓名的就有问题。就笑场了。。他自己就说这个就另外考虑。第五轮：也是两个engineer，问跟之前电面的问题差不多，还是unix的问题，问如何找出含有error的行数，然后怎么用sort和uniq，其实sort –u就不用sort| uniq了。然后另外一个engineer问C++里的intmain(int argc, char* argv) 中的char*argv 叫什么名字。然后就问了SQL，有三个table，其中一个table里的两个column的值是另外两个table的foreignerkey，写一个SQLquery。还挺简单的，不过就不太够时间。第六轮：也是两个engineer，问了唯一一道coding题，http://www.lintcode....在leetcode上找不到了。。然后followup就是加 if divide 7, then print “xxx”。主要还是考察写code的习惯吧，我用python写的，出了点bug，之后在提醒下fix了。还讨论了挺久的。。第七轮：HR，问我还对这职位感兴趣吗？当然感兴趣啊。。==，聊一下之后的安排，然后就送我出门了。一开始以为面试会很短，整个过程下来还是很累的啊。。总结：如果不是Apple的intern的话，他家还是不怎么考coding，不像FLAG那些公司考那么多coding和design题目，反而很注重交流和实际工作能力和问题解决能力。
http://www.1point3acres.com/bbs/thread-180286-1-1.html
1，两个engineer，实现一个ring buffer，其实就是画了一个数组，你能够往里面add number，read number，然后要是像一个环一样，读到最后一个又回到开头来开始读。还有一道比较简单，根据一个数组里面的数，去另一个数组里面把不包含在第一个数组的数都打印出来，follow up是有分布式情况要怎么处理，如果数组在很多台机器上的情况；
2，小team manager问简历和项目，让画diagram说项目；
3，embeded software engineer面，进来说是Apple希望面试官多元化，所以安排了硬件的人来面试。让画了garage door的状态转换图state machine，就是车库门，开和关之间的装换。问了软件上怎么处理开关的问题（LZ答的是用数字来表示状态，比如0-100），然后在硬件上可以用什么来处理车库门是否完全打开或关闭的问题（答了sensor，面试官说其实硬件层面上有个motor可以很好地处理）；第二题是经典老题，检查一个list是否有环；
4，Lunch interview，本来以为是聊天，结果大姐还真出题目，也是醉了饭都没吃完。。关于抛硬币的概率brain tester
5，Project Manager面，也是Apple为了让面试多元化的安排吧，主要是behavioral question，考察你对于team work和product dev上面的想法；
6，大team manager面，简历，然后问了如果有个shopping网站，库存数据都存在后台很多台机器上，每次有人购买了一件商品，然后又另一个人也在浏览网站，如何设计system来保证数据不会显示错误，不会有人购买一个已经被别人买了的商品。

https://instant.1point3acres.com/thread/176386
第一个 Siri Performance
1 介绍自己 2 数组里面两个数的和加起来会不会达到一个给定的数, 数组不排序,口述解法,复杂度,顺势问了哈希表的get为什么是常数时间复杂度...然后问哈希两个key的哈希值一样怎么办,这个东西叫什么(没答出来,告我叫chaining, orz,这也值得一问) 3 一堆基础知识,什么java的垃圾怎么回收的,js的三个等号和两个等号的区别,用没用过python,多少分,java的volatile什么意思, 早忘了,没答上,然后问synchronized什么意思,问有没有hadoop之类的经验

第二个地图组一个母语是西班牙语的人. 醉了!!根本听不懂他说话!!!楼主自以为听力不错,熟练掌握各种印度口音,结果折在这人上!!真心真心听不懂,好在他把题copy了过来,不然题都不知道是什么. 题都巨简单,第一题,给一个list of string有重复, 输出没有重复的版本.一分钟写完他问了followup,别问我followup是什么,根本没听懂!只知道是换一种方法,磨叽了半天他换下一题了. 第二题用一个排好序的数组构建平衡二叉搜索树. 没问什么java基础知识,问了问最challenge的project.
http://www.1point3acres.com/bbs/thread-161588-1-1.html
给一个string remove Consecutive Char. 比如： abbc -> ac ， aa -> ""， acccbdd -> ab，"" -> ""，abbabb-> ""， aa->''
要求先列出Test case , 然后我把思路讲了下，面试官表示同意，写代码，并在 coderpad.io 上在线跑。一开始有几个test cases没有通过，吓出一身汗，调试2次后fix了所有test cases.

先把所有test case写出来，这样可以知道所有的corner case避免bug,我觉得这个策略挺好的，以后做题应该都这样干，这次是考官要求的。
思路：
扫描input string, 每次把当前的char跟input里前一个char以及当前output里的最后一个char做比较，然后再做相应的处理。你先想想，代码我以后再贴。

我们是得把我们自己写的test case放到OJ里来用我们写的code去跑？还是test case只用随便写写目的只是为了让我们肉眼debug的时候用？？

先写出了肉眼看，然后放到OJ里跑这些test cases

public String removeConsective(String str) {
      Stack<Character> stack = new Stack<Character>();
      if (str.length() <= 1) {
               return str;
      }
      stack.push(str.charAt(0));
      int count = 1;
      while (count < str.length()) {
            if (stack.isEmpty()) {
               stack.push(str.charAt(count));
               continue;
            }
            char prev = stack.peek();
            char curr = str.charAt(count);
            if (prev != curr) {
               stack.push(curr);
               continue;
            }
            while (count < str.length()) {
               curr = str.charAt(count);
               if (curr != prev) {
                  break;                }
               count ++;
            }
            stack.pop();
         }

         StringBuilder sb = new StringBuilder();
         while (!stack.isEmpty()) {
            sb.append(stack.pop());
         }
         return sb.reverse().toString();
}

写了个递归版本的
string removeConsecutiveChar(string str)
{
if (str.size() <= 1)return str;
string localRes;
int i = 0;
int j = 0;
while (j < str.size())
{
while (j < str.size() - 1 && str[j] == str[j + 1])
{
j++;
}
if (i == j)
{
localRes.push_back(str[i]);
i = j + 1;
j = i;
}
else
{
i = j + 1;
j = i;
}
}
if (localRes == str)return localRes;
return removeConsecutiveChar(localRes);
}

https://instant.1point3acres.com/thread/134010
Why webkit?
web technology part:
what will happen after typing a url in the browser
what http status codes do you know? explain how code 304 works
How does browser tell if the entered text is a url or a search term
When does included JavaScript download?

C++:
Difference between reference and pointer
What's virtual function and how does it work? When to use it?
Where is the virtual table? What's in it?
When to use virtual destrcutor?
What is "this"? Why and when we want to call "delete this"? What might happen afterward
. from: 1point3acres.com/bbs

Safari:
Why Safari?
Which part of Safari are you interested in working on?
coding: given a n-ary tree, find the lowest common ancestor of two nodes (you can define the node structure by urself)
Maps API and framework:. 1point3acres.com/bbs
C++:
Difference between reference and pointer
what is unique_ptr, shared_ptr? when to use it? compare them with reference
explain why we usually use reference instead of pointer when designing APIs
explain how does hashmap work and how is it implemented
compare unordered_map and ordered_map. when will you use ordered_map instead of unordered_map

Siri speech platform:
Give the class Node. Implemented a queue with a linked list constructed by Node. implement enqueue() and dequeue()
follow up: make the queue thread-safe. When the queue is empty, the callee thread of dequeue should wait

总结：Apple 大体上很重视过去的经验和domain knowledge 即便题做对了也不一定pass 或许因为lz不是new grad
http://www.1point3acres.com/bbs/thread-105658-1-1.html
A(白人geek)：问兴趣方向是什么，hashmap是什么，hashmap怎么处理冲突数据？一道算法题，给你一个String[ ] 把每个String的subString存到map中，key是这个subString value是这个相同subString的出现个数。
B（中国人）:很nice，一些datastructure的小问题，大家肯定都会，我就不写。一道矩阵蛇形环绕遍历输出那道题。
C(中国人)：merge two sorted Array（leetcode 原题）然后就是一些java的常见题。

D(白人)：让用linkedlist实现stack，编完他问push的方法两个thread同时访问会怎么样？怎么避免。。。还有network，输入URL后network发生什么。。。还有好多database问题，只记得问relational database和nosql database区
E(白人)：他问的我唯一会的就是那道算法题返回一个String中最长的回文长度。然后一大堆分布式系统的设计，解决，案例分析题，想哭，只会mapreduce，说了说他说我问你的事realtime的，不能用mapreduce。。。。题感觉我用文字描述不
F(白人)：被前五个人都提醒过最后一个人最难做好准备。结果这哥们真心感觉再给我放水。只让编了一个斐波那契数列不用递归，space O(1)的编发，这个我之前就会。

1，两位qa组成员 behaviour questions: - 一位组员不给力怎么半？有亲身经历么？ - 好多组员不给力怎么半？有亲身经历么？ - deadline到了，你10个test feature不能全完成，怎么半？以及延伸，和amazon oa2 work simulation极像
2，dev组manager 讨论qa dev组的联系。此mgr先做了4年qa再转的开发，正好当时（10年前或更早？）apple支持qa转开发。
3，qa manager问简历，一些technical。

4，qa小哥一起case study，手机屏幕会在无意间被碰到的情况，如放口袋，蒸汽房；如果开发了一个camera算法只有探测到脸的时候才允许解锁，算法会碰到什么问题，即有意想碰屏开机时却开不了。
5，2年工作qa小哥聊简历，聊真实工作中遇到的bug以及如何解决。感觉苹果真是务实，hr强调我们base可能低，但是我们有加班费，1.5倍哦；我们relocation不是给一笔固定的钱，而是你用多少给多少

https://instant.1point3acres.com/thread/176705
问了个问题是问怎么做tokenization比如说awesomejob怎么tokenize成awesome job，我一开始说用Trie做greedy的match后来他说那怎么handle ambiguity……我心想这个好像很难啊，大概说了类似于dynamic programming, HMM之类的idea但是很显然我自己也知道并不对……所以就没有再问了。然后给了一个ImmutablePoint的class问哪儿写错了，我发现是copy constructor里面没有copy char*我就改了一下，他就问有没有更好的写法……我就很懵……懵了一会之后他说你可以直接用string……WTF我也不知道还可以直接改类里面成员的定义啊。。。然后把后面一个函数的return type从reference改成了value。最后实现了一个binary search……就这样了……这面试官让我对Apple简直兴趣全无，最后我问他那个tokenization怎么做他说dynamicprogramming，我实在不是很懂这个怎么dynamic programming…[查了一下大概明白了，应该确实是可以dynamic programming的，就用类似于f表示这个地方的best score和last word然后去乘transitional probability.]
不完全，不是要你返回所有的或者是任意一个break的方式，而是要你返回一个maximize probability的方式

http://www.1point3acres.com/bbs/thread-140107-1-1.html
LCA, O(NlogN) 和O(N)都要写
Maximum Point On One Line

数据结构设计, 存储不考虑无限大，确保get --> O(1), query --> O(1)
栗子：
Car registry
(Toyota, Prius, Blue, VIN) 现在要实现add和get操作。
Follow up:
query (Toyota, Null, Blue, Null), should return all Toyota and Blue cars' VIN
query (null, Prius, null, null), should return all Prius cars' VIN

楼主第二题没看懂要求是什么？要做一个DS，保证插入和检索O（1）？
HashMap<String, List<String>>
key -> car model
value -> list of VINs 不就可以解决了吗？
由于没有memory限制，把每个possible key combinations 都放入HashMap:

Map<String, List<String>> map = new HashMap<>();
public void add(String brand, String model, String color, String vin) {
String [] keys = {brand, model, color, brand + model, brand + color, model + color, brand + model + color};
for(String k : keys) {.1point3acres缃�
if(!map.containsKey(k)) {. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
map.put(k, new ArrayList<String>());
}
map.get(k).add(vin);.鏈枃鍘熷垱鑷�1point3acres璁哄潧
}
}
public List<String> query(String brand, String model, String color, String vin) {
String key = token(brand) + token(model) + token(color) + token(vin);
return map.get(key);
}
public String token(String k) {
return k == null ? "" : k;
}

Apple Interview Misc

Labels

Popular Posts