狗家Fall Intern电面

catherineycycy 发表于 2017-7-13 07:41
快一周的时间，挺快的

谢谢LZ，那估计我也快了。。。

catherineycycy 发表于 2017-7-13 07:41
快一周的时间，挺快的

再问一下楼主～你是收到回复是通过email还是电话啊，我想心里有个底

第二题个人感觉应该属于人工智能领域的CSP问题，类似八皇后问题，本身是NP-hard，但也有很多优化方法，这里感觉考官就是靠暴力的backtracking吧？
但是似乎也可以用 Bottom-up 的DP解，如果没错的话应该是n的三次方：
n = word.length
Let M[ ] [ ]  be a 2-D share matrix with shape of (n,n)  
For i = 0 to n:
        set = [ ]
        for dice in all dices:
                if dice has char[ i ]
                set.append( {dices-dice} ) (one possible state after crossing this one )
         if set.isEmpty():
                return "don’t exist!"
                m[ i ][ i ] = set
For offset = 0 to n-1:
        for i = 0 to n - offset:
                j = i + offset
                //fill M[ i ][ j ]:
                for dice_set in M[ i+1 ][ j ]:
                        keep_dice_set = false
                        for dice in dice_set:
                                if dice has char[ i ]
                                remove this dice from this dice_set
                                keep_dice_set = true // this state is possible
                                if char[ i ] is last char:
                                        return “Yes, there exits!”  //goal test
                                break
                        if keep_dice_set is false:
                                remove this dice_set  (the state is impossible or unsatisfactory)
                for dice_set in M[ i ][ j-1 ]:
                        do the same as M[ i+1 ][ j ] case
                M[ i ][ j ] =  Natural join(M[ i+1 ][ j ], M[ i ][ j-1 ] )
                If M [ i ][ j ] is an empty set:
                        return  “don’t exists!”
return “don’t exits” // the algorithm will probably never reach this line

fengqi1994 发表于 2017-7-13 08:10
再问一下楼主～你是收到回复是通过email还是电话啊，我想心里有个底

先是给我打了个电话，紧跟着又发了封邮件

catherineycycy 发表于 2017-7-12 12:33
不一定的，她给我举的例子里面有同样的骰子好几个的，也有都不一样的，我说数量可以很多的意思是，骰子的 ...

那感觉这个题目就是搜索+网络流。第一步搜索枚举每种骰子投什么字母，然后第二步用网络流算可不可行。当然，第二步搜索也是可以算的，只不过复杂度很高，没必要。

zhangsikai123 发表于 2017-7-13 10:26
第二题个人感觉应该属于人工智能领域的CSP问题，类似八皇后问题，本身是NP-hard，但也有很多优化方法，这里 ...

可以DP做？方便简单说一下思路，描述下状态转移方程吗？谢谢

秋季intern 还能投吗？？网上找不找

knight0clk 发表于 2017-7-14 13:15
可以DP做？方便简单说一下思路，描述下状态转移方程吗？谢谢

Dp的伪代码我已经写再回复下面了啊。你可以试一试。匈牙利算法反正肯定是对的

zhangsikai123 发表于 2017-7-14 13:43
Dp的伪代码我已经写再回复下面了啊。你可以试一试。匈牙利算法反正肯定是对的

主要是看不懂伪代码，所以需要你简单说下状态如何表达的。另外这个题目不是二分图匹配，是网络流，楼主已经说明了每种骰子不是一个，是多个。

edyyy 发表于 2017-7-14 13:27
秋季intern 还能投吗？？网上找不找

已经截止了