Wish店面过筋

Job Hunting Interview
, , , , , , ,
1

是三番office，但是面试官在加拿大
第一轮， 加拿大hackrank video面，先聊半小时天，面试官介绍组的情况，然后聊聊简历，为什么想加入Wish，加入之后想做啥方向，面试官很nice，聊天过程蛮轻松。题目比较难，当时不会做，因为之前没刷过union find的题目：

题目：物品归类，输入是name, str1, str2, str3, str4的格式，name是物品名称，str1, str2, str3, str4是物品的四个属性，根据属性把物品分类，要求一个类里面的物品要有三个相同的属性，如：
INPUT:
item1， blue， ball-point, mini, cap
item2， blue， ball-point, cap, full-size
item3，ball-point, mini, red, cap
item4, blue, medium, ball-point, cap
item5, red, foundation, mini, cap

OUTPUT:

item1, item2, item4

item3, item5

第⼀组相同的blue, ball-point, cap, 第二组 mini, red, cap

第一题没写出来。但是面试官基本没人能写出来，他看重的是解决问题的能力。。。
我本来打算暴力解，但是还是没写完代码

第⼆轮：

亲戚关系，其他⾯经有提过，最终的算法要解决的case包括：

A brother B, B sister A, A friend B， B classmate C 这种A B环形, 或者多种关系的情况

上面这个例⼦，如果是A C的话， 输出[A brother B classmate C, A friend B classmate C]

2

你好，物品归类那题，有没有可能出现比如item1和item3是一组，然后item1和item4又是一组的情况呢？如果存在这种情况 求个思路 谢谢

有可能。所以我是根据先来后到做的。
电面结束后，我花了几个小时看union find和思考，终于写出来了代码，然后发给recruiter让他帮我转发给面试官

3

分享一个很straight forward的方法：
维护一个map，key是atrribute list，三个或者四个，value是list of item name
另外写一个计算两个attribute list相似度的方法，返回值最好是相似的attributes

每来一个新的item就去遍历map找一下有没有相似度为3的key，有的话把item加进value的list，
如果此时key是四个，要把它变成两者相同的三个atrributes。

没有的话就把自己的attribute作为新key加入。

4

有第二题的答案么。不会写那个edge case呀带cycle的

最后把graph那个map做成map<name, Map<name1,List>就可以解决A 跟 B有多种关系的数据了， 比如(A, {B: [father, friend]}). 这样在BFS的时候，拿出A的connections, 然后通过维护visited set来防止环，然后通过遍历B的 value list，把“A father B” 和 “A friend B" 分别加入queue里面。