狗家月初昂塞

11.2 Onsite MTV
11.15 送HC
11.21 过HC， team match

Round 1
1. LC 844 O(1) Space
2. 给你一些字符串，每个字符串有六个字符，代表一个骰子的六个面的字母，每个骰子拥有的字母不一样，然后给你一个target word，问你有没有可能通过扔这些骰子一次获得这个单词，返回true或者false。没有什么好的思路所以说用Brute force backtracking，小姐姐表示可以，最后差一点没写完，写了

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

序，固定min找max用二分查找(第一次找max用二分，之后找max直接往回遍历)。小姐姐说假定已经排序好，直接做，代码写的有些坑，最后说还有一点小问题但是no worries，本来还有一个follow up, 如果有重复的怎么办，没来得及做

Teddies 发表于 2018-12-7 23:41
首先补充一下这道题不用考虑空集，不过其实考不考虑就是答案加一的事，不影响做题。

在没有重复的时候 ...

感谢楼主分享。follow up我想可以这样：
例：[1 1 1 2 2 2 2 3 3] K = 4
把所有的unique数字和它们出现的次数提取出来：
unique数字：a = [1 2 3]
出现次数：   t = [3 4 2]

然后还按左右指针的办法，左指针i=0，右指针j=2。a[ 0 ]+ a [ 2 ] = 1 + 3 <=4。此时a[0..2]范围内的每一个数字a[k]都可以在subgroup在出现0, 1, ... 或t[k]次，即有(t[k]+1)种可能。不过a[0]必须要出现至少一次，所以有t[0]种可能。不同数字的出现次数是互不相关的，因此[0..2]这个范围内总共有(t[ 0 ] ) * (t[ 1 ] + 1) * (t[ 2 ] + 1) = 3 * 5 * 3 = 45种可能的subgroup的选择方法。接下来的指针移动方法和无重复数字的情况相同。

没有重复数字时，t其实就是[1 1 1]，所以[0..2]范围内就只有1 * (1+1)*(1+1) = 2^2 = 4种情况，这是上述一般方法的一个特例。

UUOlidd 发表于 2018-12-7 11:40
你好楼主，round 5可以举一个例子吗？“使得这些sub group满足 min(S) + max(S)

首先补充一下这道题不用考虑空集，不过其实考不考虑就是答案加一的事，不影响做题。

在没有重复的时候，我继续使用你的例子。[1,2,3] K=4的时候整个数组确实是符合条件的，所以一开始左指针指在1，右指针指在3，1+3 <= 4, 所以只需要在[2,3]中选择0个，1个或者2个元素，相当于排列组合的组合求和，C(2,0) + C(2,1) + C(2,2) = 1 + 2 + 1 = 4, 简化使用二项式定理得出一共有2^2=4种选法，对应的subGroup是[1],[1,2],[1,3],[1,2,3]. 然后左指针向右移动到2，2+3 > 4，不符合条件，右指针往回移动指到2，2 + 2 <= 4，从排列组合的角度看就是C(0,0) = 1, 只有一种选择，对应的subGroup是[2]，由于左右指针所指的数值相等，右指针不再移动，从这之后我们只需要移动左指针，直到左指针指向的元素值大于K为止，继续移动左指针指向3，3 <= 4, 答案 +1，左指针已经指向最后一个元素了，结束，返回答案4 + 1 + 1 = 6。如果考虑空集的情况就返回7。

对于有重复的，总体思路也是差不多的，不过不好意思我上一个帖子里稍微有些问题，不能再使用二项式定理直接计算了，因为这样还是会有重复的答案。比如[1,1,1,2,2,2,3,3,3] K = 4，一开始左指针指向1，右指针指向3，除了最小值的1以外还有8个元素可以选择，如果用二项式定理那么还会选到重复的结果，比如可能会出现多个[1,1,2]的subgroup, 所以目前我想到的一种使用hash set过滤重复，或者写一个helper函数，返回从某些特定元素种选择n个元素的不重复选法数量，即 int helper(vector<int>& v, int n)，这个helper函数最暴力的方法就是直接backtracking。我因为面试的时候没有回答道这一问，因此还没有细想过这个follow up, 如果有更好的解法欢迎大家讨论。

补充内容 (2018-12-7 23:44):
在有重复的时候，之前帖子里提到移动指针的时候跳过重复还是对的

jajaa 发表于 2018-11-22 20:41
赞美。

那要判断必须经过某一行 如果每一个点都加一遍是不是太慢了？

这个帖子讲的很详细了，狗家这道unique path的各种follow-up都覆盖了
https://www.1point3acres.com/bbs/thread-423857-1-1.html

lz是应届毕业么？还是在职找工作啊

jajaa 发表于 2018-11-22 04:49
lz是应届毕业么？还是在职找工作啊

"码农类General 硕士 全职@google - 内推 - Onsite  | Pass | fresh grad应届毕业生"

感谢，lz可以再分享一下Round1（2）的细节吗？一共多少个骰子？只投一次吗？

巫山云似盖 发表于 2018-11-22 09:22
感谢，lz可以再分享一下Round1（2）的细节吗？一共多少个骰子？只投一次吗？

一共任意多骰子，只扔一次，所有骰子一起扔，没有顺序要求，只要有可能扔出那个目标单词就返回true，如果无论怎么扔都扔不出来就返回false

请问Round2 follow up 2 必须经过一些指定的点怎么作呀？我只能想到暴力backtracking，dp可以做么？

mars0 发表于 2018-11-22 14:03
请问Round2 follow up 2 必须经过一些指定的点怎么作呀？我只能想到暴力backtracking，dp可以做么？

就是dp做，和第一问一样，类似LC62，63. 只不过把中间必须经过的点当作中途的小目标统计，比如中间要求必须经过A，B两个点，那么就先统计从起点到A有多少种走法，然后从A出发看到B有多少种走法，再从B出发看到终点有多少种走法。这道题因为走法比较特殊，所以其实每一列上只能又最多一个必须要经过的点，如果有一列上有多个必须要经过的点，那么直接返回0.

补充内容 (2018-11-22 14:41):
所以如果某一列上有一个必须要经过的点，那么就只用计算经过那个点的走法有多少种，那一列上的其他点的走法个数就标记为0.

Teddies 发表于 2018-11-22 14:40
就是dp做，和第一问一样，类似LC62，63. 只不过把中间必须经过的点当作中途的小目标统计，比如中间要求必 ...

赞美。

那要判断必须经过某一行 如果每一个点都加一遍是不是太慢了？  

jajaa 发表于 2018-11-22 20:41
赞美。

那要判断必须经过某一行 如果每一个点都加一遍是不是太慢了？

如果必须经过某一行，只需要用第一问的结果剪去不经过那一行的走法的个数，排除法。
建议你画图模拟一下这道题可能的走法， 对这道题目的走法的特殊性会有一个更深刻的理解。