Broadway 三轮VO 面经集合

Job Hunting Interview
, , , , ,
1

第一轮高冷白人小哥

task scheduler 就是有prequisite的那种

用hashmap记录就好

一个矩阵 只能下山 问你每个点最低到多少 dfs+dp

然后改成可以上山 问你刺杀国王最少要多少绳子 用dijskra

第二轮黑哥哥

打印binary tree边界

以及一个我也没听懂的一队人同时演奏怎么搞

我就乱说的:joy:

第‍‍‍‍‍‍‍‍‌‌‌‌‌‍‍‍‌‌‍三轮 白人大叔

双联表插入数据

设计hashMap

四轮面试，每轮一小时，上午两轮下午两轮。考题比较偏数据结构基础，没有像on campus那样虐我sliding window maximum....

Round 1是白人大叔，coding + data structure。

coding是一个sorted的成环双向链表，给定一个随机起点，给定一个input value，插入这个input。

data structure是手写实现generic variable的hashmap的底层，实现put和get，并处理hashing collision, 和loadfactor超过之后怎样expand和rehash。

Round 2是天竺叔叔，两道coding。

第一题我至今没明白他到底point是啥… 原题是“想象一个marching band，所有人站成一排，每个人只能跟自己左边和自己右边的人交换一个note，请设计一个算法，让他们所有人可以同时开始演奏”。。。我：???

不让换位置，所以没得树状传播信息啊？这是想考什么… 懵逼了几个来回之后天竺叔叔说你想想怎么count这一排的总人数。。。。我说那我暴力了啊，左边右边同时开始报数，然后每个人就知道自己左边多少人右边多少人了，然后加上自己就知道总人数了。。。。他说对的，请问big O和space complexity是多少。。。。。我：所以你只是想问这个？？？？？他说是啊这虽然很简单，但的确是一个algorithm啊。。。。我：@_@

第二题终于正常了，给一个binary tree，想象它是一个左边、底边、右边的三角形，打印所有处于边缘上的node。注意左边和右边是可以拐弯的，一直打印到leaf才能停。

Round 3是白人高傲小哥，OO design + 问project。

设计一个task scheduler，用户可以添加任务并定义该任务的先行任务，可以开始任务，可以结束任务，可以获取当前可以开始的所有任务。光写API不够，代码要全写出来。

proj是自己选一个用了很多library并且写了很多代码的项目，然后问到database schema design，问到REST API，问到你到底写了哪些内容，问到为什么这么设计、为什么这么写、为什么选用这个tool，以及怎么test。

Round 4是白人和蔼小哥，data structure + coding。

data structure是问arraylist和linkedlist的区别，分别分析两者的implementation，问insert(index, value), append(value), delete(index), get(index)在两者的big O，以及space complexity（我愣了一波然后明白他其实是想问linked list的pointer会占用几个字节…卧槽）。然后说如果你设计一个win记事本类似的程序，你要怎么优化它的查找时间（他引导我往linkedlist of arraylist的方向说…）

（其实他说记事本的时候我一直以为是想问自动补全然后问trie…结果一直是设计设计设计设计设计。。。不过小哥讲的设计我真心服气）

coding是给一个m*n矩阵（地图），每个格子里面都有一个数字（想象海拔高度），只能上下左右四个方向滑，只能从大数字滑到小数字（往山下滑）。如果一个格子的上下左右都比它自己大，那就停了（停在谷底）。要求output这个矩阵的每一个格子作为起点会停在哪里。用dfs + memorization写了。followup是给你其中一个谷底，给你一个山上的目的地，上山需要用绳子，绳子长度为数字之差（高度差），下山不用绳子，问最少需要多少绳子，以及怎么走。用dijkstra做就可以。

问及“对萌新有何建议么”，曰，每天刷几道题 :slight_smile: （捂脸遁走…

早上状态没调动起来，Round1的逻辑很顺畅但是写码磕磕巴巴的，Round2没明白第一题到底搞什么，吃完午饭的Round3一开始‍‍‍‍‍‍‍‍‌‌‌‌‌‍‍‍‌‌‍想搞topological sort但是后来只写了暴力解，只有Round4比较无暇。最近精神状态不太好，尽力了，move on。。。。

他家onsite真的慷慨… 三晚世贸对面的hilton，每天管吃管住管酒管party，食物质量很高（一整个周末，白天各种吃吃玩玩bowling + laser tag + bubbleball，晚上拉去pub搞party，无限量供应牛排和龙虾卷和任意酒水，结束了还可以去after party继续喝，真的服气）… 感觉公司真的很有钱… 来onsite的人里随便抓一个都是一把实习和TA的经历。。。就我最weak chicken。。。。这波膜拜大神来得不亏>_<

image
image.jpg596×1240 277 KB

2

感觉用VO的公司一般budget紧张一点，为了省钱

3

为什么一个人是三轮，一个人是四轮？

4

第一个人是17年的面经。
第二个是19年刚刚面的
我自己在地里搜到的
感觉题目不是很简单

5

这一轮量这么大？ 考了scheduler就够答很多的了

6

不太清楚啊

7

这题难道不考虑多线程么？
感觉题目也没讲清楚，难道是自由发挥？

8

小公司就是这样，bar反而更高，本来招人也少
而且考的东西也更加practical，没时间train你

9

题目可参考去年这位大佬的昂赛面经：

题几乎一模一样

面试官1: 一个德州美国哥，他简单的自我介绍之后直接切入正题：
第一道题

去年那位大佬的面经题，什么乐队传note，每个人只能和左边和右边临近的人传，问怎么让乐队所有人同时歌唱。 不用写代码嘴巴说就行，我觉得这是道智力题。答出来之后有个followup，说如果传的note不可以写数字，怎么办。想了好久，在提示下做出来了。‍‍‍‍‍‍‍‍‌‌‌‌‌‍‍‍‌‌‍这里就不发答案了，希望各位能自己思考。提示：找队伍中间的人

第二道题

也是原题，利口唔似无。要求写代码，写testcase，并且跑代码

面试官2:一个不知道哪个国家的人，有一些口音但不影响交流
第一道题：

设计一个Task Scheduler类，也就是大佬面经里round3的第一题。是个OOD，有3个API，分别是addDependency；addCompletedTask；getRunnab‍‍‍‍‍‍‍‍‌‌‌‌‌‍‍‍‌‌‍leTasks。 基本思路也就是拓扑排序

第二道题：

大佬round4的第二题。dfs+dp 没啥好说的

面试官3:一个在多伦多的白人小哥

两道题和大佬round1一模一样。利口疑似妻和设计哈希表

总的来说题和一年前大佬的昂赛几乎一模一样，真是服了。。。以为不会考原题没仔细看，导致一些题没有bug free。。。

面试官非常喜欢让你自己想test case，一方面我代码确实有bug，另一方面就算bug free了面试官也想考察你思维是否缜密。建议多想想testcase。

10

这题怎么像脑筋急转弯

11

嗯是 不用写代码 是一个智力题 我跟同学到时候 讨论一下 反正我是自习群第一个面

12

Boundary of Binary Tree (LC原题)

Insertion Sort List（LC原题）
coding是一个sorted的成环双向链表，给定一个随机起点，给定一个input value，插入这个input。

data structure（基础知识 & coding）
是手写实现generic variable的hashmap的底层，实现put和get，并处理hashing collision, 和loadfactor超过之后怎样expand和rehash。

设计一个Task Scheduler类
是个OOD，有3个API，分别是addDependency；addCompletedTask；getRunna‍‍‍‍‍‍‍‍‌‌‌‌‌‍‍‍‌‌‍bleTasks。 基本思路也就是拓扑排序
设计一个task scheduler，用户可以添加任务并定义该任务的先行任务，可以开始任务，可以结束任务，可以获取当前可以开始的所有任务。

13 
package linkedin;

// Java program to demonstrate implementation of our
// own hash table with chaining for collision detection
import java.util.ArrayList;

// A node of chains
class HashNode<K, V> {
	K key;
	V value;

	// Reference to next node
	HashNode<K, V> next;

	// Constructor
	public HashNode(K key, V value) {
		this.key = key;
		this.value = value;
	}
}

// Class to represent entire hash table
public class CustomMap<K, V> {
	// bucketArray is used to store array of chains
	private ArrayList<HashNode<K, V>> bucketArray;

	// Current capacity of array list
	private int numBuckets;

	// Current size of array list
	private int size;

	// Constructor (Initializes capacity, size and
	// empty chains.
	public CustomMap() {
		bucketArray = new ArrayList<>();
		numBuckets = 10;
		size = 0;

		// Create empty chains
		for (int i = 0; i < numBuckets; i++) {
			bucketArray.add(null);
		}
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size() == 0;
	}

	// This implements hash function to find index
	// for a key
	private int getBucketIndex(K key) {
		int hashCode = key.hashCode();
		int index = hashCode % numBuckets;
		return index;
	}

	// Method to remove a given key
	public V remove(K key) {
		// Apply hash function to find index for given key
		int bucketIndex = getBucketIndex(key);

		// Get head of chain
		HashNode<K, V> head = bucketArray.get(bucketIndex);

		// Search for key in its chain
		HashNode<K, V> prev = null;
		while (head != null) {
			// If Key found
			if (head.key.equals(key))
				break;

			// Else keep moving in chain
			prev = head;
			head = head.next;
		}

		// If key was not there
		if (head == null)
			return null;

		// Reduce size
		size--;

		// Remove key
		if (prev != null) {
			prev.next = head.next;
		} else {
			bucketArray.set(bucketIndex, head.next);
		}

		return head.value;
	}

	// Returns value for a key
	public V get(K key) {
		// Find head of chain for given key
		int bucketIndex = getBucketIndex(key);
		HashNode<K, V> head = bucketArray.get(bucketIndex);

		// Search key in chain
		while (head != null) {
			if (head.key.equals(key))
				return head.value;
			head = head.next;
		}

		// If key not found
		return null;
	}

	// Adds a key value pair to hash
	public void add(K key, V value) {
		// Find head of chain for given key
		int bucketIndex = getBucketIndex(key);
		HashNode<K, V> head = bucketArray.get(bucketIndex);

		// Check if key is already present
		while (head != null) {
			if (head.key.equals(key)) {
				head.value = value;
				return;
			}
			head = head.next;
		}

		// Insert key in chain
		size++;
		head = bucketArray.get(bucketIndex);
		HashNode<K, V> newNode = new HashNode<K, V>(key, value);
		newNode.next = head;
		bucketArray.set(bucketIndex, newNode);

		// If load factor goes beyond threshold, then
		// double hash table size
		if ((1.0 * size) / numBuckets >= 0.7) {
			ArrayList<HashNode<K, V>> temp = bucketArray;
			bucketArray = new ArrayList<>();
			numBuckets = 2 * numBuckets;
			size = 0;
			for (int i = 0; i < numBuckets; i++)
				bucketArray.add(null);

			for (HashNode<K, V> headNode : temp) {
				while (headNode != null) {
					add(headNode.key, headNode.value);
					headNode = headNode.next;
				}
			}
		}
	}

	// Driver method to test Map class
	public static void main(String[] args) {
		CustomMap<String, Integer> map = new CustomMap<>();
		map.add("this", 1);
		map.add("coder", 2);
		map.add("this", 4);
		map.add("hi", 5);
		System.out.println(map.size());
		System.out.println(map.remove("this"));
		System.out.println(map.remove("this"));
		System.out.println(map.size());
		System.out.println(map.isEmpty());
	}
}
14

Data Structure
是问arraylist和linkedlist的区别，分别分析两者的implementation，问insert(index, value), append(value), delete(index), get(index)在两者的big O，以及space complexity（linked list的pointer会占用几个字节…卧槽）。然后说如果你设计一个win记事本类似的程序，你要怎么优化它的查找时间（他引导我往linkedlist of arraylist的方向说…）
（其实他说记事本的时候我一直以为是想问自动补全然后问trie）
coding
是给一个m*n矩阵（地图），每个格子里面都有一个数字（想象海拔高度），只能上下左右四个方向滑，只能从大数字滑到小数字（往山下滑）。如果一个格子的上下左右都比它自己大，那就停了（停在谷底）。要求output这个矩阵的每一个格子作为起点会停在哪里。用dfs + memorization写了。followup是给你其中一个谷底，给你一个山上的目的地，上山需要用绳子，绳子长度为数字之差（高度差），下山不用绳子，问最少需要多少绳子，以及怎么走。用dijkstra做就可以。

15

这题跟 leetcode 147 描述不太一样啊，另外要注意duplicate的情况

16

会有相等的情况吗？

17

这估计是要你考虑在test case里面的 我觉得

18

这有多种可能吧，如果有两个以上的方向是小的

19

哦哦 那我的理解 可能就是 最低的“谷底”？

20

或者是四个方向选最低的走，不然太难做了