2019亚麻最新onsite

Job Hunting Interview
, , ,
1

今年1月参加的面试，有五轮

  1. 给n个方块，要求输出可能的所有图形。方块不能独立，起码要有一个边相邻。先不考虑旋转和镜像
  2. 系统设计。设计一个系统用在两个不同设备上显示当前电量。
  3. 给一个词库和一个string，要求返回所有以string开头的所有词
  4. bq
  5. 对于0到n-1这n个数和一个int[][],例如[[1,2],[2,3],其中前一个是后一个的prerequisition.输出一个可行的顺序遍历所有数

啊，这次经历要吐槽一下。本来应该前一天下午飞机，结果延误到第二天早上2点半起飞，5点多到，直接就奔着考场去了。hr还不让我改时间，结果就是最后两场快睡着了，一个点说了又忘，连着问了三次。。。真的是非常尴尬。

P.S. 现在回去的航班也晚点了，真的是。。。

2

pat pat ， 亚麻 HR 太不人道了，一晚没睡，9点面试，太残忍了

3

这是graph的 topological sort
444. Sequence Reconstruction

题目内容

Check whether the original sequence org can be uniquely reconstructed from the sequences in seqs . The org sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 104. Reconstruction means building a shortest common supersequence of the sequences in seqs (i.e., a shortest sequence so that all sequences in seqs are subsequences of it). Determine whether there is only one sequence that can be reconstructed from seqs and it is the org sequence.

Input:
org: [1,2,3], seqs: [[1,2],[1,3]]

Output:
false

Explanation:
[1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed.

Input:
org: [1,2,3], seqs: [[1,2]]

Output:
false

Explanation:
The reconstructed sequence can only be [1,2].

Input:
org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]

Output:
true

Explanation:
The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].

Input:
org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]]

Output:
true

这题在 mock专场 mock 过

这题加锁，可以看博客

http://www.cnblogs.com/grandyang/p/6032498.html

4

这题就是 Trie 吧，基本的 Trie 的实现

5

求问大大第一题的思路。这种图形组合问题如何解决？

6

这里的方块是 square 还是 rectangle 区别很大

7

It may be similar to this

https://www.quora.com/How-many-different-shapes-can-we-create-by-combining-n-number-of-hexagons

8

请问第一题是什么意思？有具体例子么？谢了

9

如果都是square的话，个人理解就是这些square摆放的不同位置组合成不同的图形，比如四个方块可以摆成一长条，也可以摆成一个大的square，在不考虑旋转和镜像的情况下，一共多少种。至少一个边是连着的，就是不能有断开的情况。可以backtracking暴力打印所有情况，设计方法查重。

1 Like
10

我认为可以把第一个方块作为最左下的，然后可以选择上方或右方放剩下的方块。也就是dfs。

11

第一题DFS做到最后怎么去重的啊？

12

根据要添加方块的方向

13

不行吧。 根据方向只是dfs path去重啊。
最后结果能搞成同样shape的方法挺多的，就是不同path都可以搞成同样的shape,最后不是还要一次去重么。

14

假设最左下方的方块对应坐标 0,0
新加的方块都可以对应坐标的
可以维护一个visited，对应方块拼成的所有方块的坐标

15

我是记的它们相对的坐标，所以可以模拟图形在一个个直角坐标系里，最后对齐就可以查出来了。

16

只查两个方向是不是会查丢？我是四个方向都查，每次dfs的时候更新图形，每次在根据新的图形所有可行的位置都查一遍，虽然有点查太多次了，但是应该没有丢。

17

这里已经假设最左下方的方块对应坐标 0,0
然后是从该方块出发

18

相对坐标可以去除因为旋转和镜像形成的重复吗

19

哦，题目说不考虑旋转和镜像，那如果要考虑的话怎么办

20

何必呢