M*******a
发帖数: 1633 | 1 Given an 2D array of characters. Find words in the array (either vertical or
horizontal). a character cannot be part of 2 words. Maximize the number of
characters used. Hint: 1D variant can be solved by Dynamic programming in
linear time.
onsite都做不出来
出这题的人脑子进水了 |
f**h
发帖数: 46 | 2 哥onsite时比这个描述还复杂，而且没有hint，跪了
or
of
【在 M*******a 的大作中提到】
: Given an 2D array of characters. Find words in the array (either vertical or
: horizontal). a character cannot be part of 2 words. Maximize the number of
: characters used. Hint: 1D variant can be solved by Dynamic programming in
: linear time.
: onsite都做不出来
: 出这题的人脑子进水了
|
d********i
发帖数: 582 | |
M*******a
发帖数: 1633 | 4 是不是印度人？
有没有冲他树中指。
有没有反问他我给你出个这么难得您现场做得出么。
【在 f**h 的大作中提到】
: 哥onsite时比这个描述还复杂，而且没有hint，跪了
:
: or
: of
|
f**h
发帖数: 46 | 5 白人经理，应该是bar raiser，第一个面试官，还迟到10分钟，一出这题我就懵了，我
面得是entry level呀，搞懂题意就花了好长时间，后来草草写了两行时间就到了。
leetcode已刷两遍，但运气真是差到家
【在 M*******a 的大作中提到】
: 是不是印度人？
: 有没有冲他树中指。
: 有没有反问他我给你出个这么难得您现场做得出么。
|
g*********e
发帖数: 14401 | 6
or
of
这题好像cracking the coding interviews里面有。
【在 M*******a 的大作中提到】
: Given an 2D array of characters. Find words in the array (either vertical or
: horizontal). a character cannot be part of 2 words. Maximize the number of
: characters used. Hint: 1D variant can be solved by Dynamic programming in
: linear time.
: onsite都做不出来
: 出这题的人脑子进水了
|
M*******a
发帖数: 1633 | 7 您说的是最后一章最后一道把，不一样的。
【在 g*********e 的大作中提到】
:
: or
: of
: 这题好像cracking the coding interviews里面有。
|
d********i
发帖数: 582 | 8
请问你什么时候面的A家？ 小弟下星期一面onsite。 害怕中。。
【在 f**h 的大作中提到】
: 白人经理，应该是bar raiser，第一个面试官，还迟到10分钟，一出这题我就懵了，我
: 面得是entry level呀，搞懂题意就花了好长时间，后来草草写了两行时间就到了。
: leetcode已刷两遍，但运气真是差到家
|
g*********e
发帖数: 14401 | 9 恩 好像不一样
【在 M*******a 的大作中提到】
: 您说的是最后一章最后一道把，不一样的。
|
M*******a
发帖数: 1633 | |
|
|
R*********d
发帖数: 34 | 11 这题可以用BFS加减枝吗？
Given an 2D array of characters. Find words in the array (either vertical or
horizontal)........
【在 M*******a 的大作中提到】
: Given an 2D array of characters. Find words in the array (either vertical or
: horizontal). a character cannot be part of 2 words. Maximize the number of
: characters used. Hint: 1D variant can be solved by Dynamic programming in
: linear time.
: onsite都做不出来
: 出这题的人脑子进水了
|
S******1
发帖数: 216 | 12
or
of
可以了，比Google那个密码问题简单了
【在 M*******a 的大作中提到】
: Given an 2D array of characters. Find words in the array (either vertical or
: horizontal). a character cannot be part of 2 words. Maximize the number of
: characters used. Hint: 1D variant can be solved by Dynamic programming in
: linear time.
: onsite都做不出来
: 出这题的人脑子进水了
|
l**********1
发帖数: 415 | 13 这个find words是要求字母必须连续还是subsequence就算？ |
x**i
发帖数: 2627 | 14 move on, good luck!!
【在 f**h 的大作中提到】
: 白人经理，应该是bar raiser，第一个面试官，还迟到10分钟，一出这题我就懵了，我
: 面得是entry level呀，搞懂题意就花了好长时间，后来草草写了两行时间就到了。
: leetcode已刷两遍，但运气真是差到家
|
l**********1
发帖数: 415 | |
M*******a
发帖数: 1633 | 16 就是，我就觉得phone interview能知道一维怎么做就不错了吧。
【在 l**********1 的大作中提到】
: 求1D DP的O（n）解法。只想出了n^2的
|
M*******a
发帖数: 1633 | 17 就是，我就觉得phone interview能知道一维怎么做就不错了吧。
【在 l**********1 的大作中提到】
: 求1D DP的O（n）解法。只想出了n^2的
|
t*****s
发帖数: 416 | 18 DP的nature就是n^2，但是利用字符不能重用的条件应该可以在计算实际cost的时候降
阶到O(n)
【在 l**********1 的大作中提到】
: 求1D DP的O（n）解法。只想出了n^2的
|
g*******i
发帖数: 110 | 19 谁能提供个1D数组，O(n)的思路？
比如给cat,
c的时候，发现不是word，
ca的时候要看"ca",
cat的时候既要看"cat", 也要看"at", 这样就不是O(n)了。 |
c*****m
发帖数: 315 | 20 上次面一个entry level的contract的职位，onsite的时候也问了个类似的问题，没做
出来。面试官是印度人。 |
|
|
M*******a
发帖数: 1633 | 21 这种做法通常都是2^n了吧，不是polynomial了吧。
or
【在 R*********d 的大作中提到】
: 这题可以用BFS加减枝吗？
:
: Given an 2D array of characters. Find words in the array (either vertical or
: horizontal)........
|
M*******a
发帖数: 1633 | 22 google 密码题是哪道？
【在 S******1 的大作中提到】
:
: or
: of
: 可以了，比Google那个密码问题简单了
|
M*******a
发帖数: 1633 | 23 显然要求连续么
【在 l**********1 的大作中提到】
: 这个find words是要求字母必须连续还是subsequence就算？
|
M*******a
发帖数: 1633 | 24 我现在一想好象一维也只有O(n^2)思路么，怎么整成O(n)？
【在 g*******i 的大作中提到】
: 谁能提供个1D数组，O(n)的思路？
: 比如给cat,
: c的时候，发现不是word，
: ca的时候要看"ca",
: cat的时候既要看"cat", 也要看"at", 这样就不是O(n)了。
|
c********r
发帖数: 107 | |
l***i
发帖数: 1309 | 26 dp(m,n) = max_{i,j} dp(i,j) + row_word[j]
or dp(i,j) + col_word[i]
dp(i,j) is the max number of char can be used in matrix[0..i-1][0..j-1]
row_word[j] is max number of char can be used in some row to make one word
in submatrix[0..m-1][j..n-1]
col_word[i] is max number of char can be used in some col to make one word
in submatrix[i..m-1][0..n-1] |
M*******a
发帖数: 1633 | 27 好像不大对still
要是word分布是这样的，你这做法行不行？
【在 l***i 的大作中提到】
: dp(m,n) = max_{i,j} dp(i,j) + row_word[j]
: or dp(i,j) + col_word[i]
: dp(i,j) is the max number of char can be used in matrix[0..i-1][0..j-1]
: row_word[j] is max number of char can be used in some row to make one word
: in submatrix[0..m-1][j..n-1]
: col_word[i] is max number of char can be used in some col to make one word
: in submatrix[i..m-1][0..n-1]
|
o***g
发帖数: 2784 | 28 没太看懂题目
这个words有字典么？还是给定一个word？
or
of
【在 M*******a 的大作中提到】
: Given an 2D array of characters. Find words in the array (either vertical or
: horizontal). a character cannot be part of 2 words. Maximize the number of
: characters used. Hint: 1D variant can be solved by Dynamic programming in
: linear time.
: onsite都做不出来
: 出这题的人脑子进水了
|
s*****B
发帖数: 32 | |
M*******a
发帖数: 1633 | 30 显然有字典的意思
【在 o***g 的大作中提到】
: 没太看懂题目
: 这个words有字典么？还是给定一个word？
:
: or
: of
|
|
|
s******c
发帖数: 1920 | 31 可以和1维那样类似的想法来2维dp
只是每隔子问题的解不能简单用dp_sol[i]来表示,
而是用一个长度n的 vector来index每个子问题的解dp_sol[i1,i2,...i_n]，
i1,i2,...i_n 描述了一个把2d矩阵切成两块的一个界面
i_k表示第k列上这个界面的坐标.
对每一个子问题, 从界面的边界开始尝试添加word
总共有n^n个子问题, 然后每个子问题的递推式可以在n^2时间搞定
(需要preprocess这个矩阵, 计算从每点出发可以cover那些word)
or
of
【在 M*******a 的大作中提到】
: Given an 2D array of characters. Find words in the array (either vertical or
: horizontal). a character cannot be part of 2 words. Maximize the number of
: characters used. Hint: 1D variant can be solved by Dynamic programming in
: linear time.
: onsite都做不出来
: 出这题的人脑子进水了
|
M*******a
发帖数: 1633 | 32 看不大懂啊同学。
首先你这做法时间复杂度是polynomial还是指数
其次你这上就一分为二的做法如果是上面这个图的情况能不能得到最优解还？
【在 s******c 的大作中提到】
: 可以和1维那样类似的想法来2维dp
: 只是每隔子问题的解不能简单用dp_sol[i]来表示,
: 而是用一个长度n的 vector来index每个子问题的解dp_sol[i1,i2,...i_n]，
: i1,i2,...i_n 描述了一个把2d矩阵切成两块的一个界面
: i_k表示第k列上这个界面的坐标.
: 对每一个子问题, 从界面的边界开始尝试添加word
: 总共有n^n个子问题, 然后每个子问题的递推式可以在n^2时间搞定
: (需要preprocess这个矩阵, 计算从每点出发可以cover那些word)
:
: or
|
