|
c****p
发帖数: 32 | 2 一个简单方法是把原来的int[]变成circular linked list，每次删除一个node后，下
一个node成为head，然后delete head->next->next直到最后，但是这样space是O(n)...
或者用bitmap来记录删掉的，但是time就成了...呃，这个time complexity是O(n2)？？
或者...这个删除的顺序能用数学公司总结吗？我折腾了半天也推不出一个genenral
formula |
|
H*M
发帖数: 1268 | 3 最后谁survive有个数学公式的。
...
？？ |
|
|
g*******y
发帖数: 1930 | 5 这个题目不在于考推导一个数学公式，或者我变一下题目，m不是固定的值，m等于每次
删去的那个数的值
提示一下，用树来做搜索。 |
|
w********p
发帖数: 948 | 6 过年了。 我偷偷懒，等答案。
你的GOOGLE面试怎么样了？ 我只闯到第二轮。那天头发昏，加上确实很没准备充分。 |
|
c****p
发帖数: 32 | 7 ...败了，我去topcoder翻答案算了。
没想明白。关键问题是对每个i%M，都要判断是否已经被删除了，否则就往后一个个移
直到碰到还没被删掉的为止，也就是CLRS里面hash table collision的第二种处理方法
，复杂度应该是O(N*M）吧。用tree就不用判断了？？ |
|
|
g*******y
发帖数: 1930 | 9 常规的搜索是一个一个的往下找，找到第M个
而用树的搜索，找下一个要打印的数，可以提高到O(logN) |
|
g*******y
发帖数: 1930 | 10 呵呵，新年的开头就想想题目多好啊～
要是没人发答案的话，我一会儿晚上来贴吧
我的面试还没schedule具体的时间，一直在等消息 |
|
|
c****p
发帖数: 32 | 12 “找下一个要打印的数”？这又回到我开始问的问题：是否有算法可以直接算出“下一
个”，而无需比较该数已经被删除？
post一个我用linked list实现的土法:D
void RingDelete(int* values, unsigned int size, int M)
{
if (size==0) return;
printf("step: %d\n", M);
struct Node
{
int value;
Node* next;
};
Node head;
head.next = NULL;
Node* pLastNode = NULL;
// costruct a circular linked list
for(int i=0; i
{
Node* pNode = new Node();
pNode->value=values[i];
if (i==0)
{
|
|
h***r
发帖数: 726 | 13 当是抛砖引玉了
red-black tree储存所有的数字。
删除的数就从tree中也删掉。
下次要删除的数字需要在red-black tree中search.
en, 需要augment tree for order information to make sure search the ith
element can be done in o(logn) |
|
g*******y
发帖数: 1930 | 14 嗯，差不多是这个思路了。不过不需要非得是红黑树。
呵呵，其实这个就是CLRS上面augment data structure那部分后面的思考题 |
|
m*****f
发帖数: 1243 | 15 survive 那个是 F(n,k) = (F(n-1, k) + k)%n （n个人， 隔k个杀一人)
原理就是多杀一个人， 就往安全的地方退k步， 这样不死我死前面那个 |
|
H*M
发帖数: 1268 | 16 或者AVL tree?总之any balanced tree..
先build好这个augmented的tree,
第一个去死的是order(M)，删除掉
然后第二个去死的是，剩下来的order(M+M-1)，删除
第三个去死的是，剩下来的order(M+M+M-1-1),删除
其实要做个module，如果大于这个tree里面的元素个数的话。
我的天，这个用tree的方法真比那个推公式什么的清晰多了
sigh... |
|
H*M
发帖数: 1268 | 17 对了，我有个问题
如果，面试中要用augmented red black tree/avl TREE咋办啊
难道还写个RB tree/AVL tree不成
我RB tree insert/delete那些function都没记，太多了
应该怎么弄呢？assume有个现成的？ |
|
|
g*******y
发帖数: 1930 | 19 这个题不需要用RBT,AVL
想想heap是怎么用数组实现树结构的
我感觉面试不太可能让code实现RBT,AVL，有些太刁难人了。 |
|
m*****f
发帖数: 1243 | 20 面试的时候实现Red Black Tree太难了吧， 也没那么多时间写啊 |
|
H*M
发帖数: 1268 | 21 那一般关于augmented data structure的题，就只能嘴上说说了
反正我不记哪些RBTree的functions. |
|
|
H*M
发帖数: 1268 | 23 大概就是用吧，和一些特性
不是 augmented data structures被烤果好几回了 |
|
m*****f
发帖数: 1243 | 24 我觉得没, 我所听说的几个面试也就是问问linklist, queue stack之类的东西
如果被问到红黑树, 可能是因为表现的实在太强了 |
|
|
H*M
发帖数: 1268 | 26 这个跟wiki上递推公式有点像，
不过没看懂。。 |
|
g*******y
发帖数: 1930 | 27 是这样的
m=3：
1 2 3 4 5最后survive的那个是第4个数
考虑1 2 3 4 5 6:
第一个删除的是3，删除3后：
1 2 4 5 6，从4开始接着往后面计数/删，因为是循环的，相当于 4 5 6 1 2，从头开
始计数/删；
又因为删了一个，所以现在只剩5个数了，这样问题就递归到5个数的情况了
不过这个公式是找最后一个数，我这个题是让你打印所有删除的数的顺序，嘿嘿，如果你还是用这个思路做，貌似还是O(N^2)的 |
|
g*******y
发帖数: 1930 | 28 贴答案了：
思路是：
(以n=16举例，array[16]={1,2,...,16})
array的每个位置(index)写成二进制就是0000 ... 1111
可以构造一棵树，根节点统计总共还有多少个数剩下没有删。根下面，往左边走，代表bit=0，往右边走代表bit=1。这样，从根到某个节点的path，就构成了一个二进制的prefix：
比如，根的左孩子的右孩子，prefix就是01，那么该节点就用来统计array中所有包含01前缀的位置中，还有多少个数剩下还没有删。
这样，我们还可以很简便的用数组来表示这个树，只需要规定root = 1, 左孩子=root<<1, 右孩子=左孩子+1(就像书上实现heap那样)。
这个数据结构写出来后，剩下的工作就好办了。
贴一个程序：
https://webfiles.uci.edu/siyangx/public/Josephus.cpp |
|
a********a
发帖数: 219 | 29 你这个太强大了。现在面试太可怕了。
表bit=0，往右
边走代表bit=1。这样，从根到某个节点的path，就构成了一个二进制的prefix：
含01前缀的位
置中，还有多少个数剩下还没有删。
root<<1, 右孩
子=左孩子+1(就像书上实现heap那样)。 |
|
|
|
|
|
|
w*******4
发帖数: 1931 | 35 各个银行的时间不同
邮局可以直接查usps的网站
包子
plz
嘿嘿 |
|
p*t
发帖数: 671 | 36 爸妈要在小娃3个月回国，老公是在小娃3个半月的时候回国出差，接下来的3个星期，
刚好是冰天雪地的圣诞节、元旦节和寒假，完全就我一个人照顾了。看了版上的经验，
实在是拿不定主意：我一个人能否搞定小人儿？
这几天为这个事情，头疼的很。现在有几个方案，请版上有经验的妈妈们给出出主意，
看哪个更好一些。
时间：小娃3个半月-4个月零一个星期，
性格：天使与否，现在不知道。待定。
人物：就我一个当妈的。
方案一：最简单。我一个人在家白天晚上全天候的照看小娃。我不知道自己能不能撑得
住？3个月的小人是否要打疫苗之类的？打完之后会不会容易发烧？
方案二：公婆签证、提前过来。原定他们是明年春天过来，这个寒假可以趁老公回国出
差的时候，带他们去北京玩玩的。如果提前过来，一是这个游玩计划要取消，二是他们
是南方人，我们这里是美国最冷的地方，怕他们不习惯。三是老公可能心里不太想让公
婆这个时候过来，更想让公婆去旅游（原因不知道，我看老公的态度猜得。）
方案三：爸妈回去休息一个月，再过来一趟。签证有效，二次入境。但这样，一、我担
心我爸妈身体能否吃得消，比如飞机长途旅行、需要调整时差，还有刚被小娃折腾3个
月 |
|
p*t
发帖数: 671 | 37 呵呵，刚好是圣诞节、元旦节这个假期，我怕到时候不好找人。
买菜啥的，倒还好说。就怕小娃病了，或者我病了，那就出不了门了。 |
|
m*a
发帖数: 4927 | 38 不想底下有门槛就买了个木头的，还改装了半天，元旦节就都浪费在做木工上了 orz |
|
K********5
发帖数: 1986 | 39 或者说哪一个时间打折力度更大？不知圣诞节会不会开门啊 |
|
n****g
发帖数: 14743 | 40 元旦节怎么办
妇女节怎么办？
劳动节怎么办？
铲子建党怎么办？
铲子建国怎么办？ |
|
D*******o
发帖数: 3229 | 41 废公元纪年，改元庆丰；废星期，改初一十五休沐。最难办的是历法，因为农历也是当
年洋鬼子帮忙修订的。要不也废了，大家看候鸟迁徙估摸节气算了。
：元旦节怎么办
： |
|
W*****e
发帖数: 7759 | 42 【 以下文字转载自 Military 讨论区 】
发信人: Warfare (German==Arschloch), 信区: Military
标 题: 远洋一方北润园大幅降价 业主集体散步维权
发信站: BBS 未名空间站 (Sat Mar 5 12:17:46 2011, 美东)
http://finance.ifeng.com/news/house/20110305/3573933.shtml
提要：【财新网】(记者 兰方)2011年3月5日，北京东五环外通惠河畔的“远洋一方”
北润园第三次开盘。因而，业主们所提出的补偿贷款利息及保证首付比例不变的要求，
“我公司认为缺乏法律法规或者合同约定的依据，因此无法满足”。
【财新网】(记者 兰方)2011年3月5日，北京东五环外通惠河畔的“远洋一方”北润园
第三次开盘。在接待近百名购房者的同时，售楼处也迎来了一群不速之客。
早上8点左右，一群衣着普通的“抗议者”便三三两两聚集在售楼处周围，几辆警车则
悄悄静候一旁。
“我们是一群有着‘刚需’的购房者。”参与“抗议”的，是去年4月北润园首次开盘
时已以每平方米2.5万元左右高价购房的数... 阅读全帖 |
|
g**********2
发帖数: 2408 | 43 文件显示,阿里巴巴集团按美国通用会计准则2012年财年营收为40.8亿美元，毛利润为
27.64亿美元，运营利润为6.88亿美元，净利润为5.36亿美元，归属于阿里巴巴集团的
净利润为4.84亿美元。阿里巴巴集团的营收较上年增长74%，归属于阿里巴巴集团的净
利润较上年增长81%。应当说阿里巴巴集团交上了一份稍显满意的答卷。
但为什么不是满意，而只是稍显满意呢？如果把阿里巴巴2012年财年营收数据按季度
列示，可以看到以下一组数据。
查看原图
从上表中可以看出，尽管归属阿里巴巴集团全年净利润(Net Income attributable
to Alibaba)4.8亿美元，但是2012年第四财季（即2012年7月至9月），归属阿里巴巴集
团的净利润却是亏损的。而且不仅是归属阿里巴巴集团的净利润，运营利润(Income
from operations)及公司净利润(Net income)均为亏损。如上表所示，2012年第四财季
，公司营业亏损1.74亿美元，公司净亏损2.45亿美元而归属阿里巴巴集团净亏损2.45亿
美元。这是阿里巴巴集团自2010年第二财季（即2010年第一季... 阅读全帖 |
|
c*******r
发帖数: 2012 | 44 我觉得圣诞节元旦节大家欢乐完了再买可能更好,这段时间应该还会拖一阵.
我就是买早了TZA,SPXS和SLV现在还亏着,主要怕错过熊市行情,不过现在看来年底前不
会熊. |
|
|
v******y
发帖数: 4134 | 46 从现在开始到一月八号，圣诞元旦一起庆祝，各种图片帖子都将有奖哦！吃喝玩乐，旅
行购物的内容都可以 |
|
|
d******s
发帖数: 674 | 48 求legoland 成人票9张，儿童票3张。要求圣诞节至元旦节之间有效。
请短信联系4084757518 或者站内短信。 |
|
d******s
发帖数: 674 | 49 求legoland 成人票9张，儿童票3张。要求圣诞节至元旦节之间有效。
请短信联系4084757518 或者站内短信。 |
|
x*u
发帖数: 6170 | 50 求legoland 成人票2张，$25。要求圣诞节至元旦节之间有效。 |
|
