留给码农的时间不多了, 这些题都不会, 怎么过海关？[来offer独家习题讲解]

如果你正在找工作，以下文章对你有帮助：

二叉查找树(Binary Search Tree, BST) 是一种非常高效而功能强大的的数据结构。它能够高效地以递增的顺序存取元素，且稍加拓展就能够快速回答各种复杂的query。

对于平衡的BST，大多数操作都可以在O(logn)完成。但如果BST不平衡，最坏经常需要O(n)时间，效率大打折扣。

静态构建BST经常会产生不平衡的树，实际应用中经常要保持二叉搜索树平衡以确保操作的效率。最近就有人被问到了如何平衡一个BST：

    要答出二叉查找树才能证明    

“我是软件工程师”   

2月26日，28岁的尼日利亚软件工程师Celestine Omin持短期签证第一次来到美国。在JFK机场入境时，他被海关人员要求回答程序相关题目，证明他确为软件工程师之后才被允许入境。

图片来源：Celestine Omin Twitter

据Omin回忆，他告知海关人员自己是美国科技创业公司Andela的软件工程师，对方询问了他一些问题后，将他带到一个单独房间。他们给了他一张纸，要求他回答纸上的两个问题：

1. 设计一个功能，以验证二叉搜索树是否平衡（Write a function to check if a Binary Search Tree is balanced）

2. 什么是抽象类，你为什么需要它？

（What is an abstract class, and why do you need it? ）

Omin在事后接受LinkedIn采访时表示，他认为海关人员对计算机科学专业并不了解，这些问题就像是“临时从Google上搜‘拿什么问软件工程师’而找来的题目”。

      “回答错误”，一波三折      

由于刚经历了23小时长途飞行，Omin疲惫得难以思考。当他完成作答、将答案交给工作人员时，却被告知他都答错了。

“如果我给的不是Wikipedia上的答案，就会被认为是错误答案吧。”Omin在Twitter上表示。

此间Omin试图询问为何海关人员要考这些问题，对方都让他保持安静。

图片来源：Celestine Omin Twitter

庆幸的是Omin最后还是被顺利放行，并不是因为他答对了题目，而是海关致电了Omin服务的公司Andela，确认了他软件工程师的身份。

Omin回忆，临走时海关人员对他说：“我放你走，但你并没有让我相信你。”

来offer独家习题讲解

祝你过海关一臂之力

这里我们把这个问题严格地定义一下：

写一个函数，输入一个BST，输出一个balanced BST。

一个BST是balanced的当且仅当它是empty的，或者左右子树都是balanced BST且左右子树高度差不超过1。

 方法1 

in-order traverse BST，把元素按递增顺序存入list，再用分治法(divide and conquer)构建平衡二叉树：

时间复杂度分析分两部分：in order traversal和build tree。

in order traversal本质上是一个tree的dfs，复杂度是O(n)。

build tree本质上做了一遍tree traversal，所以是O(n)。

所以时间复杂度是O(n) + O(n) = O(n)。

因为需要一个list存所有的nodes，所以空间复杂度因为O(n)。

把BST变成sorted linked list，TreeNode的right指向next node。然后再把linked list用divide and conquer的方法转换成balance。时间复杂度上我们难以提高，但空间复杂度任然有改进空间。利用tree node中已有的field来存储信息，就可以不利用额外的空间来表示一个sorted list。

 方法2 

ced bst。

// Convert the first n elements of list "head" into a balanced BST.

 // "head" will be set to the head of the rest of the list when this method returns.

上面的代码利用全局变量head和size减少了不必要的参数传递。

时间复杂度的分析和方法1一致。

空间使用主要体现在recursive call的stack frame空间消耗上。recursion的最大深度原树的高度H，要优于O(n)。

时间：O(n)

空间：O(H)

 方法3 

理论上最优的方法是 Day–Stout–Warren algorithm (DSW algorithm) ，可以做到O(n)时间，O(1)空间。

DSW algorithm利用tree rotation的技巧，在不破坏BST特性的前提下改变tree的结构。

整个算法分两步：

1.把BST通过反复的right rotation转换成linked list（算法中叫做vine）

2.通过反复的left rotation把linked list转换成balanced BST

时间复杂度分3部分：

treeToVine：每right rotate一次，dummy向右走的链表长度就增加1，所以最多rotate O(n)次

vineSize：O(n)

vineToTree: left rotate n / 2 + n / 4 + n / 8 + …. = O(n)次

总体时间复杂度是O(n)

整个算法iterative方式实现，stack frame的消耗是O(1)，且没有额外的创建新object，所以空间复杂度是O(1)。

 平衡二叉搜索树 看似一个简单地问题，然而要做到最优却需要非常巧妙地算法。面试时如能答出方法1或者2就足够过关，而能给出方法3的candidate就能够给面试官留下深刻印象。

无独有偶

    澳码农过关被考Python    

无独有偶，就在Omin遭遇考验前，2月已发生另一起程序员被海关拦下的事件。在欧洲学习的24 岁澳大利亚程序员David Thornton，来到美国度假时在Newark机场被要求解答一系列Python相关问题。

“他（海关人员）给我来了个计算机科学测试，不是像在Google做的那种专业级测试，但也是一个不折不扣的考验。” David Thornton后来接受news.com.au访问,回忆起当时的谈话内容：对方先是问了他的停留之间等常规问题，而后开始仔细询问他的职业：

- 你是做什么工作的？

- 我是计算机工程师。

- 你知道Python吗？

- 知道，这是一种编程语言，就像C or Java那样。

- 我有个问题，我想写个计算机程序，你能帮我吗？

- 当然可以。（感到有些吃惊）

Thornton对对方的要求感到有些吃惊，猜测对方可能是在设计耍他。但为了能入境，他还是乖乖同意答题了。

随后海关人员对着电脑开始给Thornton出题，给了他作答的纸笔，还对他的回答不断提出追问。所幸Thornton很快答出一长串问题，得以顺利入境开始假期。

“难道他们不允许不合格的软件工程师来美国吗？” Thornto事后打趣道。

      官方表态：恪尽职守      

据BBC报道，一名CBP（海关边境保护局）发言人表示：“对于来到美国的所有人，CBP人员都竭力以尊重相待。

“虽然由于隐私权法，我们不能讨论具体个例，但CBP不仅执行移民与海关相关法律，还有其它40多家机构的400多条规定。我们已经阻止了成千上万违反美国法律的人。”

图片来源：路透社

接连发生的两起与入境有关的新闻，不免使外界将此与美国加强入境管控的意图联系起来。Omin来自的尼日利亚并不是特朗普禁止发放签证的7个国家之一，但该国近年来也频受恐怖袭击困扰。

事实上美国、以及西方国家普遍都授予海关或边防警察非常大的权力，对于入境人员进行严格询问与检查，以确保国家安全。

上文提到的Omin被海关带去作答的小房间（也就是久负盛名的“小黑屋”），即CBP的接待室。如果过境人员在窗口遇到问题不能马上解决、需要进一步询问或检查，就会被带到接待室。接待室为工作人员提供接入签证处理系统和FBI系统的查询系统，以调查入境人员是否存在违规、造假等可能威胁国家安全的问题。

尽管美国对于保护公民隐私十分重视，但CBP仍具有广泛的权力，可以对入境人员的行李物品进行全盘检查、甚至进行人身搜查。近期沸沸扬扬的入境学生被查看微信聊天记录事件（见来Offer已推送文章链接），其实该项检查权力也早已被列入CBP的权力范围，即有权搜查电子设备中的内容(Border Search of Electronic Devices Containing Information).

当合格码农

      从容应对入境考验      

码农在海关被要求写代码的事件曝光后，网友们纷纷分享自己在过海关时的奇葩经历，不光是码农们，其他专业的同学也被测试了专业性：

@华晨宇要嫁人就嫁给我妹：上次入关那人问我OPT什么工作，我说建筑工程设计，他马上问我你们还在用AutoCAD吗？………我说嗯，有时候也用Revit…………他很满意

GGG不见了：我曾经说自己今后要读研。海关现场给我搜了一道GRE的数学题...我还能说什么 

@王扬王小呆：我入关的时候说自己在法学院，真的问了法律问题…

也有码农未雨绸缪地表示以后海关可能会问dynamic programming的问题了：

图片来源：新浪微博

尽管两位被拦下的程序员最后都顺利入境美国，但还是要提醒大家：

第一，在入境接受询问时要格外谨慎，避免不必要的麻烦。

第二，对自己专业基础不那么自信的同学，为了确保以后能够愉（sao）快（chu）顺（zhang）利(ai)地入境，送上Thornto的一句话共勉：

入境美国之前，一定要好好学习！

Just make sure you study up before you enter the United States!

消息来源

http://www.bbc.co.uk/news/blogs-trending-39127617

http://boingboing.net/2017/03/01/what-is-your-favorite-color.html

http://www.news.com.au/travel/travel-advice/travellers-stories/aussies-weird-immigration-interview-in-the-us/news-story/8222c65d2f12e6691ef27c9b1753e821

求职，你只需要一门课程

来Offer 2017年春季班2期

3月20号正式开课

Who We Are

来Offer网 (www.laioffer.com) 由清华大学计算机系在硅谷顶级科技公司（Google, Facebook,Uber）Director & Manager级别校友组成的职业培训机构。成员中有国际信息学奥赛International Olympiad in Informatics (IOI)中国国家队教练，Facebook 最早期的中国工程师经理和中国大陆招聘工程师负责人, 高考省理科状元，Stanford, CMU, Harvard, USC 等校CS Ph.D.组成。

What We Do

用最顶尖的师资力量带出高水平的学生：让强者更强，拿到一线大公司的Offer， 让转专业的同学迅速系统提高，拿到SponsorH1B的正规公司的Offer. 拿Offer不仅仅靠算法，而是系统素质的展现，包括英语表达沟通能力，Coding质量，多线程，System Design, OO Design，以及对美国职场最基本的理解。我们不仅仅是算法培训机构，而是一个培训同学们高成功率拿到Offer的职业培训机构。

• FLAG 级别 Manager Level班主任负责制，有问题直接语音问答；每班配备10+名主讲老师，精心为同学们课后答疑和 1对1 code review.

• 独立Online Coding训练系统 code.laioffer.com (300+最新大公司真题只对内部学员开放)

• Google/Facebook engineer 上机课手把手教你编程

• 每月一次跟踪考试, 老师1对1修改coding

• 英文口语/书面的提高

• 一线大公司Director/Manager level的老师， 内部推荐＋面试综合技术提高

• Internship level 3个月完成的实战project (可选课程)

• 免费重复听，直到找到工作

高成功率

高成功率是我们唯一的标准: 2013年成立以来我们已经帮助数百名同学拿到Offer，成功率稳定在 80%。 其中Google, Facebook, Uber, Box, Microsoft, Yahoo, Amazon, Indeed, Hulu, IBM 等大中型公司超过半数。真名实姓Offer榜请见www.laioffer.com

欢迎发送简历至[e-mail]报名

我们将在24小时内联系您

图片来自网络，版权属于原作者，侵删

本文版权归来offer所有，

未经允许，请勿转载