d*******u
发帖数: 186 | 1 比较element和中间元素， 如果相同返回。
否则递归找该element在左边和右边：
左边: rotated sorted or sorted.
ratated sorted: recursive.
sorted: binary search.
similarly for the right side.
You |
|
|
|
x******g
发帖数: 41 | 4 考一下古吧，有很详细的推荐
基本就是那几本书
clrs
programming pearls
algorithms in c
programming interview exposed
careerup
还有本版的所有经验分享 |
|
P**********c
发帖数: 3417 | 5 Design an algorithm to figure out if someone has won a game of tic-tac-toe.
Approach #1, 用hashtable, 它说只有2万种可能，但是照它说的每一位0, 1, 2的话，
总共需要9位数， 也就是需要一个222222222＋1这个大的hashtable才行，似乎太浪费
了吧。有更好的hash方法吗？ |
|
P**********c
发帖数: 3417 | 6 20.11 Imagine you have a square matrix, where each cell is filled with
either black or white. Design an algorithm to find the maximum subsquare
such that all four borders are filled with black pixels.
书上给的解法是 O(n^2)么？我怎么觉得是O(n^4）呢。有人可以解释下为啥是O(n^2)吗？
她的基本思路就是：
从第一列开始
－－第一行开始从最大的正方形开始找，如果不满足，那么size--, 直到size小于当前
的maxSize
－－第一行找完后从第二行开始, 一直到剩下的最大size小于当前的maxSize
第一列找完后开始第二列，找到剩下的列小于当前的maxiSize为止。
这个方法为什么是O(n^2)呢？ |
|
|
P**********c
发帖数: 3417 | 8 书上这个解法用了DP保存状态吗？哪里体现出来的？ |
|
g***s
发帖数: 3811 | 9 没看过这本书。从你的转述来看，不像是O(n^2)。
这里早些时候有这题的讨论，还有这题的一些延伸。 |
|
s*****n
发帖数: 5488 | 10 因为是subsquare,所以还是一维的问题。 |
|
g**********y
发帖数: 14569 | 11 这是书上的答案，它把isSquare()当成O(1)的operation.
1 public static Subsquare findSquare(int[][] matrix){
2 assert(matrix.length > 0);
3 for (int row = 0; row < matrix.length; row++){
4 assert(matrix[row].length == matrix.length);
5 }
6
7 int N = matrix.length;
8
9 int currentMaxSize = 0;
10 Subsquare sq = null;
11 int col = 0;
12
13 // Iterate through each column from left to right
14 while (N - col > currentMaxSize) { // See step 4 above
15 for (int row = 0; row < matrix.length; row++){
16 // starting from ... 阅读全帖 |
|
P**********c
发帖数: 3417 | 12 就算isSquare是O(1), 是不是也应该是O(n^3)呢，对每一sub列worst case是要
比较O(n)个square的size吧。 |
|
s*****n
发帖数: 5488 | 13 当然不是，不用优化的话，两个for loop搞定了。 |
|
P**********c
发帖数: 3417 | 14 假设给的矩阵只有一个1， 其他的都是0， 我觉得每次从最大的开始，size--都要减很多次啊，肯定不是O(1)啊。 |
|
c*********t
发帖数: 2921 | 15 我觉得你说的是对的。应该是O(n^3).
另外，可以按行iterate也行。careercup上的是按列搜索。 |
|
c********t
发帖数: 5706 | 16 may I ask a question? Is n the total cell counts or the edge length?
If it is the previous, isn't O(n^2) correct?
吗？ |
|
d********y
发帖数: 2114 | 17 这个解法算brutal force吧。
应该是O(n4)。
isSquare()不能当做O(1)。 |
|
P**********c
发帖数: 3417 | 18 No. The book says the matrix is n*n.
Anyway, I think the book made a mistake in evaluating the time complexity.
Can someone provide a link to the dynamic programming solution? Is that one
O(n^2)? |
|
w*****p
发帖数: 215 | 19 我能坐到n^3. 通过一个n^2的预处理，可以做到 issquare() 在循环里面 O(1).
举个例子。0是白，1是黑。
10011
01110
01010
01111
做两个矩阵： 一个是对于每一个元素（i，j），同一行从它开始的最大连续1的个数。
同理，做一个矩阵，对于同列连续的1的个数。这两矩阵就n^2做到。
比如 行的矩阵 xcell，
10021
03210
01010
04321
和列的矩阵 ycell
10041
03030
02020
01011
给定任意个点(x,y)，和size k， 就可以判断 这个square是不是都是黑边的。
比如 (2,2,3), 只要看4个值，xcell[2,2]>=k, ycell[2,2]>=k, xcell[2+k,2]>=k and
ycell[2,2+k]>=k, 这里的 k=3.因为 成立，所以issquare 是成立的。
但是不管是dp还是非 dp，我都只能做到 n cube。 |
|
w*****p
发帖数: 215 | 20 SORRY, 是xcell[2+k-1,2]>=k 和 ycell[2,2+k-1]>=k |
|
a********m
发帖数: 15480 | 21 记得careerup书上有。
n是在第一个叔祖的下标，m是第二个，所以m=n-1.这样就只有一个未知数n。然后n在[1
,k]折半，关键是终止条件和折半的方法。 |
|
c*********t
发帖数: 2921 | 22 2.4 You have two numbers represented by a linked list, where each node
contains a single digit. The digits are stored in reverse order, such that
the 1’s digit is at the head of the list. Write a function that adds the
two numbers and returns the sum as a linked list.
1. 感觉这个递归，没有考虑 l1 == null && l2 == null, 但是carry==1的情形，这种
情况，还应该加个高位1
2. 应该是value>=10,就应该有进位carry,给的答案是>10
谢谢！ |
|
P**********c
发帖数: 3417 | 23 1. 一上来value=carry考虑了啊。
2. code里是>=10, 虽然前面描述是>10 |
|
P**********c
发帖数: 3417 | 24 不过这个感觉只考虑了正数，有没有人讲讲有一个是负数怎么处理？ |
|
d*******d
发帖数: 2050 | 25 不要迷信careercup, 那本书写得挺糙的，有题从第一版到第四版答案一直不对。 |
|
|
|
|
I******y
发帖数: 176 | 29 这个题新生成ListListNode为什么是（carry, null, null）啊。觉得一个node 一个
value, 一个指针就可以啊 |
|
|
m*p
发帖数: 1331 | 31 thanks for pointing out. the def of LinkedListNode doesn't make sense.
should be:
LinkedListNode{
int value;
LinkedListNode next;
} |
|
P**********c
发帖数: 3417 | 32 虽然不懂Java, 但是LinkedListNode是Java的standard class吧，人家默认是有
previous field的。 |
|
m*p
发帖数: 1331 | 33 i see. but it's not in java standard... anyway, i usually define my own
linkedlistnode, why bother with that? |
|
P**********c
发帖数: 3417 | 34 坐标是2个数啊。比如careerup上10.6上存直线都把slope和y intercept ｜了一下，那
还是Java code呢。 |
|
r*******g
发帖数: 1335 | 35 I saw this on careerup, not sure how to solve them. Thank you.
1, realize malloc() in C
What is key data structure here? What is the key point?
2 If [a1,a2,a3...,an,b1,b2...bn] is given input change this to [a1,b1,a2,b2.
....an,bn] , solution should be in-place
Anyone knows what is the most efficient solution? It is best if there is a
link provided.
3, Given an array of +ve and -ve integers, re-arrange it so that u have +ves
on one end and -ves on other,BUT RETAIN ORDER OF APPEARANCE..
for eg,
1... 阅读全帖 |
|
r*******g
发帖数: 1335 | 36 1，Given a n-ary tree. A random leaf node will be selected.Imagine that you
are now holding the tree with your hand from that node. All other nodes will
now fall under gravity. Write a function to perform this transformation.
n-ary tree又不是bst，这题什么意思，怎么也无法想象把一个节点提起来是什么感觉
2，Given two lists, each containing numbers, how would you find the
intersection of these two lists? What if these two lists are read from a
huge file that cannot fit in memory?
如果文件很大该怎么办，我能想到的是尝试一个number对应一位，但是如果memory实在
有限，numbe... 阅读全帖 |
|
c*********t
发帖数: 2921 | 37 2.2
implement an algorithm to find the nth to last element of a singly linked
list.
到底这个nth,指的什么？
n=0, 是最后一个element？
还是n=1,指的是最后一个element？
n是从0开始的，还是从1开始的？
比如有10个elements的一个singly linked list,
n可以是0, 1, 2, 3, 4, 5,6,7,8,9?
还是1， 2， 3， 4,5,6,7,8,9,10？ |
|
|
|
c*********t
发帖数: 2921 | 40 结果会不一样的。
会差一个位置的。
比如，如果n可以是0，那么n=0,是最后一个数，
如果n从1开始，那么，当n=1时，才是最后一个数。
概念上是没有区别，就是想知道通常这样的nth to last表达中，大家是如何理解的？ |
|
c****p
发帖数: 6474 | 41 我一般会要clarification；我自己写的话会给example。
实现上除了循环条件不同之外没什么差别。。 |
|
a********m
发帖数: 15480 | 42 1337还是careerup有。
示下才搞定。先让不知道答案的xdjm想想吧。回头贴我的做法。 |
|
a********m
发帖数: 15480 | 43 记错了。careerup里面的题目不容易。如果里面的难题你觉的都没问题应该机会很大。 |
|
m***n
发帖数: 2154 | 44 write a method to decide if two string are anagrams or not .
为啥不能
int count[256];
while(*str1 && *str2) {
count[*str1++]++;
count[*str2++]--;
}
if(*str1 || *str2) return false;
for(int i=0;i<256;++i)
if(count[i])
return false;
return true;
搞不清楚为啥他解法那么繁琐，还是有什么蹊跷？ |
|
i******e
发帖数: 273 | 45 是不是写错了， 遍历两个字符串， 一个应该加conuter, 一个应该减，最后再检查数
组有没有那个下标不为0. 还有如果不是ASCII encoding，数组放不下了. |
|
l*******a
发帖数: 67 | 46 额，请问怎么找版上的题？有合集吗还是站内搜索？
其实非常偶尔来MIT，不太熟悉哇。。。
刚下了个careerup 150，觉得太专业了，看的费劲 |
|
b**y
发帖数: 13 | 47 谢谢zhangchitc， 我大概看了一下careerup上的一个解答，它好像有个假设假定只有
两个单词组成
以前没用过trie，不知道你说的我是不是理解对了。如果要从code实现，先要把字典里
所有单词读出来构建一个Trie,然后从最长的单词开始枚举 （有没有比较好的trie的
opensource可以拿来直接用，是不是自己还要实现对Trie的单词长度排序呢？我以前没
用过Trie）
对每个单词用动态规划判断W是否是复合单词
for every position i(except n) in word W
if (W[i+1:n] is a word || isCompositeWord(W[i+1:n]))
return true;
return false
记录下最长的复合单词,可行吗？ |
|
b**y
发帖数: 13 | 48 谢谢zhangchitc， 我大概看了一下careerup上的一个解答，它好像有个假设假定只有
两个单词组成
以前没用过trie，不知道你说的我是不是理解对了。如果要从code实现，先要把字典里
所有单词读出来构建一个Trie,然后从最长的单词开始枚举 （有没有比较好的trie的
opensource可以拿来直接用，是不是自己还要实现对Trie的单词长度排序呢？我以前没
用过Trie）
对每个单词用动态规划判断W是否是复合单词
for every position i(except n) in word W
if (W[i+1:n] is a word || isCompositeWord(W[i+1:n]))
return true;
return false
记录下最长的复合单词,可行吗？ |
|
a********m
发帖数: 15480 | 49 不错。赞。
dp定义确实有点混乱。俺也是从careerup开始真正学，所以以前经常把top-down算dp，
bottom-up不算。现在习惯了，不管3728全算。反正思路是一样的。 |
|
a********m
发帖数: 15480 | 50 careerup确实有不少可以提高的地方。但是目前来说还是对sde面试最有帮助的书之一
了。 |
|
