A**u
发帖数: 2458 | 1 http://www.mitbbs.com/article_t/JobHunting/32070945.html
里面只有0,1,2
如果要求 {-1, 4, 0, -2, 1, 2} ==> {-1, -2, 0, 4, 1, 2}
怎么做的，要求O(n), inplace
还有这里
http://www.mitbbs.com/article_t/JobHunting/32072779.html
给定一个 Integer Array，只有正数和负数。
使让所有正数排在所有负数后面，所有正数间相对位置不变，所有负数间相对位置不变。
要求 In-Place，空间复杂度 O(1)
这个怎么做呢 |
|
|
c******n
发帖数: 710 | 3 disk已经存满，里面有1000个文件，每个文件有1000个数，内存里面只能存1000个数。
问题是把所有数排序后，放回这1000个文件里面，要求inplace，不能create新文件作为缓存。
我能想到的办法是从文件1读一个1000个数入内存建一个max heap，然后遍历其他999个
文件，出heap的数依次写入文件1-999，最后把最小的1000个数排序写入文件1000。重
复这个过程，把剩下的文件都过一遍。
请问有更好的办法吗？谢谢。 |
|
|
M*****e
发帖数: 568 | 5 贴一个我写的inplace merge，个人觉得还比较简明了。O(n)
void NumInterval::MergIntervals(vector & P, NumInterval Q)
{
vector::iterator open, closed;
open = closed = P.begin();
while (open != P.end())
{
if (Q.right < open->left)
{
NumInterval temp = *open;
*closed = Q;
closed++;
Q = temp;
}
else if (Q.left > open->right)
{
*closed = *open;
closed++;
}
... 阅读全帖 |
|
M*****e
发帖数: 568 | 6 贴一个我写的inplace merge，个人觉得还比较简明了。O(n)
void NumInterval::MergIntervals(vector & P, NumInterval Q)
{
vector::iterator open, closed;
open = closed = P.begin();
while (open != P.end())
{
if (Q.right < open->left)
{
NumInterval temp = *open;
*closed = Q;
closed++;
Q = temp;
}
else if (Q.left > open->right)
{
*closed = *open;
closed++;
}
... 阅读全帖 |
|
l*********8
发帖数: 4642 | 7 的确是。。。 我怎么没想到。
如果不考虑空间的话，这道题目就是一个读指针一个写指针。 如果写指针不超过读指
针，就可以inplace而且是一遍扫描完成。。 可是下面的例子怎么完成？
ababaaaaaaabbbbbbbabab
a1b1a7b7a1b1
这个例子就难以保证一遍扫描了。 |
|
i*********7
发帖数: 348 | 8 走一遍计算空间，如果要求空间大于所指定空间。
realloc一下。我觉得这也算inplace的。 |
|
A*H
发帖数: 127 | 9 how to remove A inplace at first step? |
|
s***h
发帖数: 662 | 10
BT和BST有什么区别吗? 时间都是一样的吧? BT需要hash, BST如果要
inplace好像要转换成链表吧? 题目对空间复杂度有要求吗? |
|
h****n
发帖数: 1093 | 11 来自主题: JobHunting版 - A家面试题 突然想起来了
1 million的数字不就刚好能装进2MB的内存吗？？
直接用quick sort 之类的inplace sorting搞定 |
|
f*****e
发帖数: 2992 | 12 来自主题: JobHunting版 - A家面试题 先用中位数和四分数（三个数过两遍就可以找出来）或者干脆是随机选的elements，
inplace把数组平分成4个子数组，每个子数组有2^20/2^2=2^18个数,然后对每个子数
组做radix sort。radix sort需要与原数组相同大小的额外空间，还需要buckets用来
记录落入bucket里的数的数目。如果用16位counting，要记录2^16个buckets，每个
bucket 4个字节用来记录落在这个bucket的数的数目。算一算正好够了，因为2MB内存
可以存放
buckets 2^16 x 4 =256KB，加额外空间 2^18 x 4 = 2^20 = 1MB。 |
|
|
i***e
发帖数: 452 | 14 这个可能是个问题啊， 因为你破坏原来的input。 其实这个要看要求了， inplace最
省空间但是把原来的input 的破坏了. |
|
i***e
发帖数: 452 | 15 这个可能是个问题啊， 因为你破坏原来的input。 其实这个要看要求了， inplace最
省空间但是把原来的input 的破坏了. |
|
|
p*****2
发帖数: 21240 | 17
你用什么语言面试的？
面试官有没有要求inplace？ |
|
p*****2
发帖数: 21240 | 18
这题还是可以扩展的。
比如输入的是int怎么办，inplace怎么办。
0－9和生成新的数组是最简单的。 |
|
|
l****c
发帖数: 782 | 20 我能想到的inplace可能就是用vector， 存在前面，然后resize了
不知道满足2爷的面试要求不 |
|
c********t
发帖数: 5706 | 21 青蛙没懂难点，写一个让大家笑话指正吧。是不是难点在于怎么让inplace的数组size
缩短？俺不会，全补0了。
public void delDup(int[] a) {
if (a == null || a.length == 0)
return;
int j = 0;
int[] s = new int[10];
for (int i : a) {
if (s[i] == 0) {
a[j++] = i;
s[i] = 1;
}
}
while (j < a.length)
a[j++] = 0;
} |
|
i****y
发帖数: 58 | 22 inplace 的话，我能想到是每碰到一个重复之后，要把后面的全往前移，
也就是大循环里套小循环，我不知道这算不算一个循环。。。
如果不考虑顺序 可以Swap最后一个和当前重复的那个。。。 |
|
|
w****x
发帖数: 2483 | 24 怎么inplace调整一个m*n普通矩阵成为一个Young tableau 矩阵？
能做到O(m*n)吗？ |
|
b***m
发帖数: 5987 | 25
这题其实根本不需要用queue和stack，inplace死做就行了。 |
|
b***m
发帖数: 5987 | 26 随便说说吧。今天比较tough，虽然只有4个人（包括大boss）面我。
第一个貌似是个俄罗斯人，SDE2，英语口语不错，直接考各种数据结构，这也没什么，
关键是都刨根问底，问到我说不出话为止。特别是hashtable，问了个底儿掉。然后是
分布式大系统的design，load balancing，disaster robust，redundant system……
只能根据自己的理解和经验瞎掰了。关键是后来跟第三个面试官出去吃饭时，碰到了这
位老兄，人家说今天只问了一些“极其简单”的东西……无语。
第二个是个中国人，Senior Development Lead，面试直接用中文，还是清华计算机系
的校友，不过比我低几届。闲聊一会儿之后，让我inplace mirror一个binary tree，
我用BFS解决后，又让用DFS解决，并且recursion和iterative都写一遍。
第三个是个印度人，Senior SDE，直接出去吃饭，去了附近的泰餐Bai Tong，吃得不错
。吃饭期间问了我一些基本的数据结构知识，以及原来做的项目的情况，让我列举了原
来项目中用debugging技... 阅读全帖 |
|
s********k
发帖数: 6180 | 27 inplace mirror一个binary tree,能直接换right和left的pointer吗？ |
|
|
|
|
|
|
p*****2
发帖数: 21240 | 33
Functional programming |
|
|
c******t
发帖数: 391 | 35 LZ能讲下数组旋转的detail么？ 是让inplace rotate一个array？ |
|
p*****p
发帖数: 379 | 36 左轮是打一下自动转一下么？
那样的话直接打会死的概率是只有碰到之前A射的是紧贴是子弹的那一个空腔，条件概
率 (1/6) / (4/6) = 1/4
转一下的话是重新选就是2/6 = 1/3
不知道对不对
不过第一题是要inplace么？不要就好办 |
|
s********x
发帖数: 914 | 37 这个有意思
v1理论上是 （nlog(n) + n）* T1 这个constant T1 不需要hash的operation，肯定要
小些
v1完全可以优化更多。
首先把array inplace quick sort， 这样就是ordered
然后search的时候完全不用linear time
贴一下哈（不知道v2和v3可否用这种思路）
// find longest increasing continuous sequence, better than O(n). a is
sorted already
public static int findLongestIncreasingContinuousSequence(int[] a) {
if (a == null || a.length == 0)
return 0;
int max = 1;
int end = 0;
// len = j - i + 1
int i = 0, k = 0;
... 阅读全帖 |
|
s********x
发帖数: 914 | 38 v1的bottle neck是quick sort inplace， worst case 也是nlog(n)
跟average case是一样的 |
|
x*********w
发帖数: 533 | 39 矩阵乘法，维度不一定是2的power, divided and conquer
C1 C2 A1 A2 B1 B2
= *
C3 C4 A3 A4 B3 B4
C1 = A1*B1 + A2*B3
C2 = A1*B2 + A2*B4
.........
inplace的程序感觉蛮tricky的：
===========================================
public class StrassenMatrixAlgo {
static void _inner_mul(int[][] a, int ra, int ca, int[][] b, int rb, int cb
,
int[][] c, int rc, int cc, int dim, int orgDim)
{
if (rc >= orgDim || cc >= orgDim ||
ra >= orgDim || ca >= orgDim ||
rb >= orgDim || cb >= orgDim)... 阅读全帖 |
|
l*********8
发帖数: 4642 | 40 你这个不是inplace的吧？ 也不太可能in-place吧？
这个算法时间复杂度多少？ 我感觉是O(n^3) (假如A和B都是n by n的方阵)。 这样的
话，跟直接计算比，也没有优势了？ |
|
w***y
发帖数: 6251 | 41 感觉要求是[i,i+1]两个两个一起读， 先按[i+1]的值比大小／再按[i]比大小？
如果这样的话， inplace排序方法都可以用上， 就是code起来复杂的多 |
|
g*******s
发帖数: 2963 | 42 rotate 一个 n*n的bitmap 90度。
我写的是逐行扫或者inplace的四角扫，复杂度都是n^2吧？ 也就是说至少每个元素要
遍历一次。可是面试官说有更好的方法。并提示我这是bitmap，比如每个pixel可以存
8bit的value。
最后还是没想出来有什么跟币bitmap优化的方法。。。。。大家能提示下么？
顺带求解的bug, 谁能从原理上分析下为甚下面的code会crash么？
class A
{
public:
~A(){cout<<"kill A"<
};
class B : public A
{
public:
virtual ~B(){cout<<"kill B"<
};
int main()
{
A* b = new B();
delete b;
return 0;
} |
|
g*******s
发帖数: 2963 | 43 用四角inplace方法是不用额外空间的。
我也很郁闷，跟他说再怎么每个元素也至少要visit一遍啊？ 他说不一定。并提示2d
matrix在memory里是1D的，但我还是没想出来怎么搞。。。。。 |
|
r*********n
发帖数: 4553 | 44 其实还有一个快速解法，虽然不是inplace，不用swap，而是基于copy：
A 2-D matrix can be interpreted as a 1-D array in two different ways:
the (i,j) entry is given by
arr[i*N+j] (concatenating rows)
or
arr[i+j*N] (concatenating columns)
suppose the given 2-D matrix is represented in the first form, you can
generate a rotated matrix expressed in the second form:
for(int k = N^2-1; k >= 0; k--){
arr_new[N-1-k/N+k%N] = arr[k];
}
then just copy back to the original array
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++... 阅读全帖 |
|
g*******s
发帖数: 2963 | 45 简单试了下非inplace方法用tiling和不用的，用了tiling确实快了不少，4000×4000
以上的matrix，用size 8的tiling至少快3倍左右。
void rotate1 (int ** in, int ** out, int n)
{
for(int i=0; i
for(int j=0; j
out[i][j]=in[n-j-1][i];
}
void rotate2 (int ** in, int ** out, int n, int block)
{
for (int x=0; x
for(int y=0; y
for(int i=0; i
for(int j=0; j
out[i+x][j+y]=in[n-y-j-1][i+x];
} |
|
u*****o
发帖数: 1224 | 46 很经典的一题，
Compress a given string "aabbbccc" to "a2b3c3"
constraint: inplace compression, no extra space to be used
CC150的答案是JAVA的。。而且我觉得那个方法挺麻烦的，在网上搜了半天，似乎
AMAZON, GOOGLE都出过这题啊，很希望牛牛们能给个C++的解法，关键是
abcd 我的CODE RETURN a1b1c1d1啊。。还有如果COUNT>10,也不行。。反正各种弱。。。 |
|
k*******t
发帖数: 144 | 47 CC给的答案时间和空间都是O(n). 你确实是inplace compression么？
。。 |
|
|
J****3
发帖数: 427 | 49 char *compress(char* str){
int rlen;
int len = strlen(str);
char* dest = (char*)malloc(sizeof(char)*(2*len+1));
int j = 0;
for(int i = 0; i < len; i++){
dest[j++] = str[i];
rlen = 1;
while(i+1 < len && str[i] == str[i+1]){
rlen++;
i++;
}
dest[j++] = rlen+'0';
}
dest[j] = '\0';
return dest;
}
O(n) 但是不是inplace的 你看看行不 |
|
r*********n
发帖数: 4553 | 50 那如果要输出1呢？
Compress a given string "aabbbccc" to "a2b3c3"
constraint: inplace compression, no extra space to be used
assumption : output size will not exceed input size.. ex input:"abb" -> "
a1b2" buffer overflow.. such inputs will not be given.
http://www.careercup.com/question?id=7449675 |
|
