m***o
发帖数: 995 | 1 http://en.wikipedia.org/wiki/Opium
Following China's defeat in the Second Opium War in 1858, China was forced
to legalize opium and began massive domestic production. Importation of
opium peaked in 1879 at 6,700 tons, and by 1906, China was producing 85% of
the world's opium, some 35,000 tons, and 27% of its adult male population
regularly used opium —13.5 million people consuming 39,000 tons of opium
yearly.[44]From 1880 to the beginning of the Communist era, the British
attempted to discourage... 阅读全帖 |
|
w****x
发帖数: 2483 | 2 说DFS的无非就是preprocessing把字典做成图
如果字典的单词是trie tree组织, 要找可以列出所有组合, 一个个在trie中找, 代价
比较大, 可以做为第一个brute force的解答
还有一种方法是做签名
aabcda => a3b1c1d1 <=abacda
签名就是hash, 比如我给出a1b2c3, 在o(1)时间就可以找出所有同样签名的单词
对于一个给定单词, 比如damp的签名是a1b0c0d1...m1..p1...
列举所有签名 |
|
e*****e
发帖数: 1275 | 3 新鲜的狗狗面筋。
电面一，
a, b, c, d, e,
f, g, h, i, j,
k, l, m, n, o
p, q, r, s, t
u, v, w, x, y
z
Write code to give the character sequence given a word, For example, if the
word is "CON", the function will print this:
Right//now we're at B
Right//now we're at C
OK//to select C
Down
DOwn
Right
Right
OK//to select O
Left//now at N
OK//to select N
电面二，search rotate sorted array.
check binary serarch tree is valid
Onsite 1, check sting is valid UTF-8.
给一个矩阵，每个格子上有三种可能，空房，阻碍物或者是保安，阻碍物不能进，空房
四个方向都能进，要写代码给每个空房标... 阅读全帖 |
|
R******9
发帖数: 267 | 4 a1b2c3 => abc123不会。。
the |
|
|
l****i
发帖数: 2772 | 6 a1b2c3 to abc123
用cycle leader iteration algorithm当场白板？ |
|
d******s
发帖数: 274 | 7 a1b2c3 to abc123是什么意思？
隔一个重排数组还是说分离字母数字什么的？ |
|
l****f
发帖数: 88 | 8 写了几次都没写出来, 太笨了。有没有大牛贴个简单明了的版本
150上的算法感觉也不对 |
|
|
|
|
h*****a
发帖数: 1718 | 11 No additional space other than a few variables. |
|
|
|
A*****i
发帖数: 3587 | 14 不用啊，如果是数组的话，用A[i+1] = A[i]一步一步把前面的往后挪就完了啊
就是复杂度有些高不能线性了。
如果一个字符一个node放在连表里就可以线性了。 |
|
h*******t
发帖数: 2679 | 15 原题是什么？
是不是这个思路：
char x='b';
char y='1';
x=x^y;
y=x^y;
x=x^y;
result ==> x = '1'; y='b';
这样可以不用extra space实现字符对调。 |
|
d*k
发帖数: 207 | 16 好久没来贡献了，刚好有时间来，和大家交流一下。
这个题需要一个巧妙的思路，如果想不到是无法解答的。个人认为这种depend solely
on one key observation的题目不适合当面试题，而且以我的能力，除非有很好的提示
，不可能想出来。
设原来的结构为
a1a2a3...anb1b2b3...bn，需要变换为a1b1a2b2a3b3...anbn。可以把左右两个数组看
做A和B，长度分别为n。现在把A和B都划分成两个长度为n/2的数组，则输入可表示为
A1A2B1B2。这里的四个数组长度都是n/2（n是奇数也则A2和B2的长度比A1和B1的长度少
1）。有算法可以在O(n)时间内inplace地交换A2和B1得到A1B1A2B2。之后递归地处理
A1B1和A2B2。时间复杂度分析，上面的递归时间代价可以表示为
T(n) = O(n/2) + 2 * T(n / 2)
因此T(n) = O(nlogn)。
关于inplace地交换A2和B1的算法，相信大家都知道了。首先将A2B1这部分反序，设A2
长度为p，B1长度为q。反序后的部分，先将前q个元素反序，再将后面的p个... 阅读全帖 |
|
|
|
y**********a
发帖数: 824 | 19 void swap(char[]A, int i, int j) {char c=A[i];A[i]=A[j];A[j]=c;}
void shuffleString(char[]A) {
for (int n=A.length,l=1,r=n/2;l
for (int l=2,n=A.length;l
while (A[l]!='A'+l/2)swap(A, l, (A[l]-'A')*2);
} |
|
j********g
发帖数: 427 | 20 这种题，当你想据掉candidate的时候还是挺合适的
solely
A2 |
|
l****f
发帖数: 88 | 21 写了几次都没写出来, 太笨了。有没有大牛贴个简单明了的版本
150上的算法感觉也不对 |
|
|
|
h*****a
发帖数: 1718 | 24 No additional space other than a few variables. |
|
|
|
A*****i
发帖数: 3587 | 27 不用啊，如果是数组的话，用A[i+1] = A[i]一步一步把前面的往后挪就完了啊
就是复杂度有些高不能线性了。
如果一个字符一个node放在连表里就可以线性了。 |
|
h*******t
发帖数: 2679 | 28 原题是什么？
是不是这个思路：
char x='b';
char y='1';
x=x^y;
y=x^y;
x=x^y;
result ==> x = '1'; y='b';
这样可以不用extra space实现字符对调。 |
|
d*k
发帖数: 207 | 29 好久没来贡献了，刚好有时间来，和大家交流一下。
这个题需要一个巧妙的思路，如果想不到是无法解答的。个人认为这种depend solely
on one key observation的题目不适合当面试题，而且以我的能力，除非有很好的提示
，不可能想出来。
设原来的结构为
a1a2a3...anb1b2b3...bn，需要变换为a1b1a2b2a3b3...anbn。可以把左右两个数组看
做A和B，长度分别为n。现在把A和B都划分成两个长度为n/2的数组，则输入可表示为
A1A2B1B2。这里的四个数组长度都是n/2（n是奇数也则A2和B2的长度比A1和B1的长度少
1）。有算法可以在O(n)时间内inplace地交换A2和B1得到A1B1A2B2。之后递归地处理
A1B1和A2B2。时间复杂度分析，上面的递归时间代价可以表示为
T(n) = O(n/2) + 2 * T(n / 2)
因此T(n) = O(nlogn)。
关于inplace地交换A2和B1的算法，相信大家都知道了。首先将A2B1这部分反序，设A2
长度为p，B1长度为q。反序后的部分，先将前q个元素反序，再将后面的p个... 阅读全帖 |
|
|
|
y**********a
发帖数: 824 | 32 void swap(char[]A, int i, int j) {char c=A[i];A[i]=A[j];A[j]=c;}
void shuffleString(char[]A) {
for (int n=A.length,l=1,r=n/2;l
for (int l=2,n=A.length;l
while (A[l]!='A'+l/2)swap(A, l, (A[l]-'A')*2);
} |
|
j********g
发帖数: 427 | 33 这种题，当你想据掉candidate的时候还是挺合适的
solely
A2 |
|
f**********t
发帖数: 1001 | 34 void abc123_(string &s, unsigned left, unsigned right) {
int num = right - left;
if (num < 3) {
return;
}
int mid = (left + right + 1) / 2;
int ll = left + (mid - left) / 2;
int rr = mid + (ll - left);
int i = ll;
for (int k = mid; k < rr; ++i, ++k) {
swap(s[i], s[k]);
}
if (i < mid) {
char temp = s[i];
for (int z = mid; z < rr; ++z) {
s[z - 1] = s[z];
}
s[rr - 1] = temp;
--mid;
}
abc123_(s, left, mid);
abc123_(s, mid, right);
}
void a... 阅读全帖 |
|
s*********3
发帖数: 25 | 35 这个题就是一个2* 3 的矩阵转置成一个3*2的矩阵。
a b c
1 2 3
===>
a 1
b 2
c 3
如何实现矩阵的就地转置，网上搜一下就有了。 |
|
|
r****7
发帖数: 2282 | 37 你都recursive了还谈啥constant space。。。
这个就是操作index，可以算出来的，和矩阵转置差不多。
solely |
|
w****k
发帖数: 755 | 38 You cannot recurse because space should be O(1). It has to be iterative.
Also, you can only solve a1b1a2b2.. . You cannot solve a1b1c1..
Here is my iterative solution:
Say original array is M. Then ai appears in M[i] and it should finally
appear in M[3i]; also bi from M[n+i] to M[3i+1], and ci from M[2n+i] to M[3i
+2].
With these in mind, we can start from a1, find its final position and put it
there after saving the value there. Then we can figure out for that value
where its final position, an... 阅读全帖 |
|
p****a
发帖数: 447 | 39 这个不对
被换到右边的数，如果已经在合适的位置了，
继续换就错了. |
|
k******e
发帖数: 145 | 40 Very good comment
Thanks
3i
it
steps |
|
w**a
发帖数: 487 | 41 用StringBuilder算extra space么？
public static String googleABC(String test){
int len = test.length()/2;
StringBuilder res = new StringBuilder();
for(int i=0;i
res.append(test.charAt(i)).append(test.charAt(i+len));
}
return res.toString();
} |
|
S*******C
发帖数: 822 | 42 StringBuilder肯定不能算extra space，不然这道题用JAVA无解，因为答案的长度就是
O(N) |
|
h******o
发帖数: 30 | 43 这个方法很好。可以按照新的坐标来逐次更换原来数组中的每个元素。当然不用新数组
储存坐标，可以计算出来。 |
|
|
