Microsoft Azure on site interview

Microsoft Azure on site interview

Round one: system design
Behavior Questions: Most challenge project
System design: 设计一个event calendar service，要求用户能够通过这个create event，并且系统能够识别时间冲突（比如event1 选了10：00 - 11:00，那event2就不同选这个时间）
写完之后具体问了nosql和sql的区别，然后让写了一下detect event time overlap的算法，有点像merge interval的变形
之后再问现在允许至多两个event重合，现在怎么修改算法（还是刚刚那个例子，event2现在可以选10:00 - 11:00了，但如果再来event3就不可以）


Round two: Coding
没有behavior questions，直接上题，约瑟夫环，我记得很久之前在leetcode上做过，但面完去找也没找到。题目可以上google搜一下，要求不能用数学公式。
给了double link-list的解，接着开始优化
1. 先讨论step = 0 和 step = 1的case
2. 讨论 step > total solider number的case
3. 然后问我还有没有优化的点。。。我想了一会才发现，如果solider是5，step是4，那其实clockwise走4步，和anti-clockwise走1步是一个效果。


Round three  Coding
Alian Dictionary，但我没做过，上来试了各种想法都被否了，最后在他的循循善诱下说是个可以拓扑排序，这时大概只有10分钟了，他说你赶紧吧，能写多少是多少。
紧赶慢赶，写完了construct graph的部分
留了两分钟，面试官说对我简历的某个项目挺感兴趣的，问了我一下

【转载 From MITBBS】Google, Microsoft, Zenefits 面经

Google
电面了2轮，题目有：
一个grid，点代表城市，边代表道路，输入是一个起始点跟一堆destination,还有哪些
路被blocked 打印所有能到的点
老题，2d matrix的row跟column都是sorted, 在里面搜某个数
oil pipeline problem, 下面这个链接的10.3-9
http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap10
补充问题是如果有2根pipeline，怎么放

Microsoft
电面了2个组，记得的题目：
best time to sell stock变种，每天只能买0或者1个，可以卖任意多个 
BST输出给定范围内的节点 
棒球比赛，有N个batter，要记录每人打中的球的数目，还要按分数排序输出batter名
字，写数据结构+伪代码
还问一些操作系统，数据结构基本概念 

Zenefits
在线做题，3个小时2道题，可以去搜面筋，重复率很高
可以在线跑test case然后改，会告诉你pass几个fail几个，但是不告诉你具体哪个
case fail
第一个题目是下面这个链接的第一题
http://www.meetqun.com/thread-7939-1-1.html
第2题 rank of permutation 

[转载 From MITBBS] Asana, Microsoft, Zenefits Interview Questions

Asana:
(1)    Given an array, return an array of product without current value
example:
given [1,2,3,4] => return [24,12,8,6]
(2)    OOP: 如何solve拼图
(3)    Regular expression match, 不是leetcode的那个题，主要考点是计算reverse
index，没让写code，主要讨论想法
(4)    中午吃饭前三道编程题 （1） 不用除号实现除法 （2） 设计data structure
存储java script file （3） 拓扑排序
(5)    饭后讨论三道编程题
(6)    Powof4， OOP design国际象棋 （从来没下过，纯粹现想）

Microsoft:
(1)    Anagrams
(2)    Sorting (考点是counting sort, 题目大概是，给你一个数组，但数组里面的
数保证范围在1 – 100 之间) 这样对于数组很大的情况把每个数都数一遍更快，一开
始没想到，耽误了一点时间
(3)    计算reverse index， 类似与merge sort的题目，一个g内存，16g文件要求输
出reverse index of each word of the given file
(4)    Populate binary tree next pointer

Zenefits:
四轮全是烙印
(1)    一轮两个题，第一题是DFS 具体题目忘了，另外一道是打印公司所有雇员名单
，要求自己选data structure，input 文件是每一个公司职员的名称，如果是manager,
还会有这个manage管理人的名单。要求输出是给一个人名，输出这个下面的所有report
  chain，每一级要缩进。 这一轮面的不错，第二题把意思一讲面试官说ok，就写了几
个主要function，感觉他还挺满意
(2)    给一个array， 找出最高点或最低点，例子如下
【1,2,3,2,1】 => 3
【3,2,1,2,3】=> 1
  [1,2,3,4,5] =>-1
第二题是simple calculator (leetcode)
(3)    设计一个cache，要求实现如下功能:
1.    Add
2.    Search
3.    Delete 
4.    Delete all
要求每个function的时间都是O(1)，catch是这个cache只会存储 1 – 500M的数字；挺
有意思的一道题，当时想出来了，面试官看起来还挺满意
(4)    Manager behavior questions