四川女子花62万买彩票仅中奖一注（因为工作人员打错号码） - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

四川女子花62万买彩票仅中奖一注（因为工作人员打错号码）

四川女子花62万买彩票仅中奖一注（因为工作人员打错号码）# Joke - 肚皮舞运动

j*22013-12-26 08:12

1 楼

1. Print all paths of a binary tree
How to do it iteratively? 用一个stack实现preorder来做？
2. Given an array of integers, find any 3 numbers in array such that they
sum to zero. eg:
[1, 2, -3, 4, 0]
1) 1 , 2, -3
2) 0, 0, 0
这个是不是三重循环？还有更快的吗？
3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了
4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
有什么好思路？
5.多层链表压扁及还原
我用stack写了一下，面试写起来太麻烦。哪位大牛给个简洁的recursion版本？
谢谢！

n*12013-12-26 08:12

2 楼

拿了I-140但没到485，不幸项目中止我们这块都被裁。
能否跟公司商量，无薪但延迟terminate时间以寻找下家？
另外，如果有新offer重新做perm,是否能用旧的PD？
谢谢

D*r2013-12-26 08:12

3 楼

失去理智买彩票一买就是800余张
家住渠县城区的李先生称，12日妻子出门买菜，直到中午都没有回家，突然接到亲
戚打来的电话后，他才得知妻子借了几十万的事。总觉得不对劲的李先生，随后立即在
城区寻找妻子陈女士，终于在一家体育彩票投注站找到了妻子。
找到妻子后，看见妻子面色苍白、几近崩溃，还一心想跳河结束生命，李先生怎么
也没有想到妻子整整2个小时，一直在投注站狂买彩票。李先生向投注站的老板要了总
票，一看见62万后，顿时傻了眼。
据陈女士回忆，12日上午去买菜，路过体彩投注站，当时仅仅只是想碰碰运气，没
想到一下子就停不下来了。从上午9点至11点，一直呆在投注站。其中购买第一张彩票
加注99倍，支付了792元。陈女士一直狂买彩票，而且投注的都是同一号码，一买就是
800多张。
豪掷62万只中一张向亲戚借款40万
买了一沓彩票，最后只中了一张，而且还是打错投注号码的……“当时老板说彩票
有新玩法“任三复四”，投资大，回报高，其实我也没有怎么搞懂玩法。”陈女士一听
到老板介绍后，打算试一试，碰碰运气，加上该老板说“41期”就要出来，便又去买，
不一会儿就花掉5400元。“说不定还会把钱赚回来。”陈女士接着去银行取了12万多，
继续购买彩票，钱不够了，又继续打电话向姐姐借钱，一借就是40万。
“专注只投注一个号码，赚得更多。所以才只买一个号码。”随着陈女士越投越多
，792元的彩票有600多张，760元的有28张，400多元的几十张，总共是800多张，花费
了622800余元。此外，陈女士还向投注站老板打了5万元的欠条。
得到的中奖金额与62万比起来简直就是小巫见大巫，“搞半天，只中了一张彩票。
”陈女士拿着中了的那张彩票，但仅兑换了3371元钱的奖金，中奖这张还是投注站的老
板打错了号码。

y*n2013-12-26 08:12

4 楼

你是要 Code 还是思路？

t*r2013-12-26 08:12

5 楼

pd 保留,没问题.
让公司不要withdraw 140 或者180天后再动, 这样你的140可以用于以后h1b无限次延期.
h1b有60天grace period. 抓紧找工作.
无薪延期事实上会violate h1b的规定,短时间还行,太长时间恐怕不行. 在你转下家h1b
时很可能要近期的pay stub, 倒时给不出会出问题.

n*g2013-12-26 08:12

6 楼

奇怪，这样的通稿也能发出来？一定有问题

【在 D***r 的大作中提到】

: 失去理智买彩票一买就是800余张
: 家住渠县城区的李先生称，12日妻子出门买菜，直到中午都没有回家，突然接到亲
: 戚打来的电话后，他才得知妻子借了几十万的事。总觉得不对劲的李先生，随后立即在
: 城区寻找妻子陈女士，终于在一家体育彩票投注站找到了妻子。
: 找到妻子后，看见妻子面色苍白、几近崩溃，还一心想跳河结束生命，李先生怎么
: 也没有想到妻子整整2个小时，一直在投注站狂买彩票。李先生向投注站的老板要了总
: 票，一看见62万后，顿时傻了眼。
: 据陈女士回忆，12日上午去买菜，路过体彩投注站，当时仅仅只是想碰碰运气，没
: 想到一下子就停不下来了。从上午9点至11点，一直呆在投注站。其中购买第一张彩票
: 加注99倍，支付了792元。陈女士一直狂买彩票，而且投注的都是同一号码，一买就是

l*a2013-12-26 08:12

7 楼

1. Print all paths of a binary tree
How to do it iteratively? 用一个stack实现preorder来做？
==>postOrder可做
2. Given an array of integers, find any 3 numbers in array such that they
sum to zero. eg:
[1, 2, -3, 4, 0]
1) 1 , 2, -3
2) 0, 0, 0
这个是不是三重循环？还有更快的吗？
==>sort O(nlogn), then n^2
3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了
==> u should know 2 sum
4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
有什么好思路？
==>懒得想
5.多层链表压扁及还原
我用stack写了一下，面试写起来太麻烦。哪位大牛给个简洁的recursion版本？
==> please see PIE

s*o2013-12-26 08:12

8 楼

"H1b有60天grace period"
严格来说 H1b应该没有grace period这个说法吧?

期.
h1b

【在 t*******r 的大作中提到】

: pd 保留,没问题.
: 让公司不要withdraw 140 或者180天后再动, 这样你的140可以用于以后h1b无限次延期.
: h1b有60天grace period. 抓紧找工作.
: 无薪延期事实上会violate h1b的规定,短时间还行,太长时间恐怕不行. 在你转下家h1b
: 时很可能要近期的pay stub, 倒时给不出会出问题.

c*m2013-12-26 08:12

9 楼

老板有意打错一张给她一点钱意思意思。这不透露出来所有获奖都在老板控制之下了么？

a*n2013-12-26 08:12

10 楼

1. Print all paths of a binary tree
How to do it iteratively? 用一个stack实现preorder来做？
DFS，每到一个叶子节点打印stack。（不过这里的path是指root到leaf？有见过题目定
义是leaf到leaf）
2. Given an array of integers, find any 3 numbers in array such that they
sum to zero. eg:
[1, 2, -3, 4, 0]
1) 1 , 2, -3
2) 0, 0, 0
这个是不是三重循环？还有更快的吗？
这个已经有数学证明了，X-sum问题最少时间开销是O(N^(X-1))
3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了
同上，应该是O(n)吧，用一个hashmap的话（重复元素可以加个counter）
4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
有什么好思路？
单机没有好思路，貌似就一边生成一边过滤。不过建议和面试官讨论多机环境下map
reduce->对字符数组中的每个元素（应该可以assume无重复），map到子问题：从字符
串生成所有不包含此元素的子串->再reduce。我觉得我要是面试官会想听到这个思路。
5.多层链表压扁及还原
leetcode原题？

【在 j********2 的大作中提到】

: 1. Print all paths of a binary tree
: How to do it iteratively? 用一个stack实现preorder来做？
: 2. Given an array of integers, find any 3 numbers in array such that they
: sum to zero. eg:
: [1, 2, -3, 4, 0]
: 1) 1 , 2, -3
: 2) 0, 0, 0
: 这个是不是三重循环？还有更快的吗？
: 3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
: hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了

w*32013-12-26 08:12

11 楼

非常确定有60天的grace period的说法。

【在 s******o 的大作中提到】

: "H1b有60天grace period"
: 严格来说 H1b应该没有grace period这个说法吧?
:
: 期.
: h1b

y*n2013-12-26 08:12

12 楼

到底什么是“多层链表压扁及还原”

n*12013-12-26 08:12

13 楼

非常感谢解答。
I-140已经快一年了。这个还好。
公司也没有马上terminate，是四个月以后，我们是被重组，因为业务还挺特别的，不
清楚未来会不会被新公司接收。预防万一，打算延长一点或者看看怎样。但还是很郁闷
啊~~~

期.
h1b

【在 t*******r 的大作中提到】

Q*F2013-12-26 08:12

14 楼

同问“多层链表压扁及还原”，原题应该是怎么样的？

h*82013-12-26 08:12

15 楼

还有四个月有什么好着急的。找下一家，或者公司内转岗即可。PD会保留的

j*22013-12-26 08:12

16 楼

Thanks! Inline ...
1. Print all paths of a binary tree
How to do it iteratively? 用一个stack实现preorder来做？
DFS，每到一个叶子节点打印stack。（不过这里的path是指root到leaf？有见过题目定
义是leaf到leaf）
==> 那就是还是用一个stack来实现preorder了？
2. Given an array of integers, find any 3 numbers in array such that they
sum to zero. eg:
[1, 2, -3, 4, 0]
1) 1 , 2, -3
2) 0, 0, 0
这个是不是三重循环？还有更快的吗？
这个已经有数学证明了，X-sum问题最少时间开销是O(N^(X-1))
===》这个怎么用n^2解？注意这里一个数可以被选多次
3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了
同上，应该是O(n)吧，用一个hashmap的话（重复元素可以加个counter）
===》要是k=0, 所有数都相等呢？把解输出就已经是n^2了吧。另外，是把a[i]和-a[i]
都放到hashtable里？
4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
有什么好思路？
单机没有好思路，貌似就一边生成一边过滤。不过建议和面试官讨论多机环境下map
reduce->对字符数组中的每个元素（应该可以assume无重复），map到子问题：从字符
串生成所有不包含此元素的子串->再reduce。我觉得我要是面试官会想听到这个思路。
===》makes sense. 单机没有好办法了？

t*r2013-12-26 08:12

17 楼

2017 new policy

【在 s******o 的大作中提到】

: "H1b有60天grace period"
: 严格来说 H1b应该没有grace period这个说法吧?
:
: 期.
: h1b

j*22013-12-26 08:12

18 楼

Thanks! 但是这里一个数可以被选好几次，怎么n^2搞？
2. Given an array of integers, find any 3 numbers in array such that they
sum to zero. eg:
[1, 2, -3, 4, 0]
1) 1 , 2, -3
2) 0, 0, 0
这个是不是三重循环？还有更快的吗？
==>sort O(nlogn), then n^2

n*12013-12-26 08:12

19 楼

未雨绸缪啊，万一找不到呢。。。

【在 h**********8 的大作中提到】

: 还有四个月有什么好着急的。找下一家，或者公司内转岗即可。PD会保留的

j*22013-12-26 08:12

20 楼

Sorry. It is like this:
Given a doubly linked list, besides the next and previous pointers, each
element has a child pointer, which may or may not point to a separate doubly
linked list. These child lists may have one or more children of their own.
Now do the following:
a. Flattern this multilevel data structure
b. Restore the original structure from the flatterned structure
e.g.
L1 --> L2 --> L3 --> L7 --> L8
|
v
L4 --> L5-->L6
WIll be flattened to
L1 --> L2 --> L3 -->L4 -->L5-->L6-->L7-->L8
有大牛发一个working的简洁code吗？

【在 y***n 的大作中提到】

: 到底什么是“多层链表压扁及还原”

r*z2013-12-26 08:12

21 楼

什么行业？不至于这么差吧？
你打算绸缪什么？EB之外的选择吗？除了EB外，还可以婚姻。。。

【在 n*********1 的大作中提到】

: 未雨绸缪啊，万一找不到呢。。。

j*22013-12-26 08:12

22 楼

up

【在 j********2 的大作中提到】

: Thanks! Inline ...
: 1. Print all paths of a binary tree
: How to do it iteratively? 用一个stack实现preorder来做？
: DFS，每到一个叶子节点打印stack。（不过这里的path是指root到leaf？有见过题目定
: 义是leaf到leaf）
: ==> 那就是还是用一个stack来实现preorder了？
: 2. Given an array of integers, find any 3 numbers in array such that they
: sum to zero. eg:
: [1, 2, -3, 4, 0]
: 1) 1 , 2, -3

n*12013-12-26 08:12

23 楼

需要公民的居多。。。所以先做好比较坏的打算

【在 r*****z 的大作中提到】

: 什么行业？不至于这么差吧？
: 你打算绸缪什么？EB之外的选择吗？除了EB外，还可以婚姻。。。

n*g2013-12-26 08:12

24 楼

4. 双重循环？

【在 j********2 的大作中提到】

a*r2013-12-26 08:12

25 楼

先说说手里的H1B什么时候到期。

【在 n*********1 的大作中提到】

: 非常感谢解答。
: I-140已经快一年了。这个还好。
: 公司也没有马上terminate，是四个月以后，我们是被重组，因为业务还挺特别的，不
: 清楚未来会不会被新公司接收。预防万一，打算延长一点或者看看怎样。但还是很郁闷
: 啊~~~
:
: 期.
: h1b

y*n2013-12-26 08:12

26 楼

如果一个number可以重复选的话，就不是3-Sum 问题了吧。。

【在 j********2 的大作中提到】

: Thanks! 但是这里一个数可以被选好几次，怎么n^2搞？
: 2. Given an array of integers, find any 3 numbers in array such that they
: sum to zero. eg:
: [1, 2, -3, 4, 0]
: 1) 1 , 2, -3
: 2) 0, 0, 0
: 这个是不是三重循环？还有更快的吗？
: ==>sort O(nlogn), then n^2

n*12013-12-26 08:12

27 楼

2020年12月。。。

【在 a****r 的大作中提到】

: 先说说手里的H1B什么时候到期。

l*a2013-12-26 08:12

28 楼

你怎么写preOrder
preOrder上来不就把root打印扔掉了吗？
最后怎么生成path呢

【在 j********2 的大作中提到】

a*r2013-12-26 08:12

29 楼

You will have 60-day grace period from the termination date.
Based on the information above, you will have ~6 months (4 months from the
termination date and 60-day grace period) to find a same or similar job.
Good luck.

【在 n*********1 的大作中提到】

: 2020年12月。。。

y*e2013-12-26 08:12

30 楼

if extra storage allowed - think of a tree as a graph, store the parent of
each node as you traverse through the tree

【在 l*****a 的大作中提到】

: 你怎么写preOrder
: preOrder上来不就把root打印扔掉了吗？
: 最后怎么生成path呢

n*12013-12-26 08:12

31 楼

Yes. 谢谢：）
时间还比较富裕。就是可惜不能继续这个绿卡progress，还要重新做perm

【在 a****r 的大作中提到】

: You will have 60-day grace period from the termination date.
: Based on the information above, you will have ~6 months (4 months from the
: termination date and 60-day grace period) to find a same or similar job.
: Good luck.

l*a2013-12-26 08:12

32 楼

你上code吧

【在 y*e 的大作中提到】

: if extra storage allowed - think of a tree as a graph, store the parent of
: each node as you traverse through the tree

j*32013-12-26 08:12

33 楼

第2个，不是2重循环么？

y*n2013-12-26 08:12

34 楼

用个String来Concatenate, 今天有时间写一些。
楼主这几个题都不错，谢谢。。

【在 l*****a 的大作中提到】

: 你怎么写preOrder
: preOrder上来不就把root打印扔掉了吗？
: 最后怎么生成path呢

y*n2013-12-26 08:12

35 楼

写了一个，看一看。。
http://ideone.com/NyqYyS

【在 y***n 的大作中提到】

: 用个String来Concatenate, 今天有时间写一些。
: 楼主这几个题都不错，谢谢。。

y*n2013-12-26 08:12

36 楼

这个题目明明说“find any 3 numbers”，原题在那里找到的？

【在 j********2 的大作中提到】

j*22013-12-26 08:12

37 楼

怎么搞？注意一个数可以被选多次

【在 j**********3 的大作中提到】

: 第2个，不是2重循环么？

n*g2013-12-26 08:12

38 楼

2重循环加一个hash map

【在 j********2 的大作中提到】

: 怎么搞？注意一个数可以被选多次

y*n2013-12-26 08:12

39 楼

写了Flattern this multilevel data structure： http://ideone.com/11xcqw
Restore 不知道如何写，感觉要存一下那里开始Flat的才行。

doubly
.

【在 j********2 的大作中提到】

: Sorry. It is like this:
: Given a doubly linked list, besides the next and previous pointers, each
: element has a child pointer, which may or may not point to a separate doubly
: linked list. These child lists may have one or more children of their own.
: Now do the following:
: a. Flattern this multilevel data structure
: b. Restore the original structure from the flatterned structure
: e.g.
: L1 --> L2 --> L3 --> L7 --> L8
: |

j*72013-12-26 08:12

40 楼

1.)
/*
* print all paths from root to leaf.
*/
public static void printPaths(TreeNode root) {
if (root == null) {
return;
}
ArrayList path = new ArrayList();
// post order tree traversal.
Stack st = new Stack();
st.add(root);
while (st.isEmpty() == false) {
TreeNode current = st.pop();
if (current == null) {
current = st.pop();
if (current.left == null && current.right == null) {
System.out.println(path.toString());
}
path.remove(path.size() - 1);
} else {
st.add(current);
st.add(null);
path.add(current.val);
if (current.right != null) {
st.add(current.right);
}
if (current.left != null) {
st.add(current.left);
}
}
}
}

j*72013-12-26 08:12

41 楼

5.多层链表压扁及还原
// 没有测试过。
public static Node flatten(Node head, Node tail) {
Node start = head;
while (head != tail.next) {
Node next = head.next;
if (head.down != null) {
Node leftMost = leftMost(head.down);
Node rightMost = rightMost(head.down);
head.down.up = null;
head.down = null;
head.next = leftMost;
leftMost.prev = head;
rightMost.next = next;
next.prev = rightMost;
next = leftMost;
}
if (head.up != null) {
Node leftMost = leftMost(head.up);
Node rightMost = rightMost(head.up);
head.up.down = null;
head.up = null;
head.next = leftMost;
leftMost.prev = head;
rightMost.next = next;
next.prev = rightMost;
next = leftMost;
}
head = next;
}
return start;
}
private static Node leftMost(Node n) {
while (n != null && n.prev != null) {
n = n.prev;
}
return n;
}
private static Node rightMost(Node n) {
while (n != null && n.next != null) {
n = n.next;
}
return n;
}
private static class Node {
private Node next;
private Node prev;
private Node up;
private Node down;
public Node() {
}
}

j*82013-12-26 08:12

42 楼

static int setBit(int input, int bit)
{
int mask = 1;
mask <<= bit;
return input |= mask;
}
// assumption all characters are lower case
static vector findSubStr(string source, vector chars)
{
vector result;
// first convert chars into an integer, where bit 0-25 correspond to
a-z, o(n)
int charsBits = 0;
for (int i = 0; i < chars.size(); i++)
{
int bit = chars[i] - 'a';
charsBits = setBit(charsBits, bit);
}
// then find all the substrings of the source, o(s^2), convert
substring to integer, o(1), overall o(s^2)
for (int i = 0; i < source.length(); i++)
{
int bit = source[i] - 'a';
int currSubStrBits = setBit(0, bit);
for (int j = i; j < source.length(); j++)
{
//update currSubStrBits with the incoming character
bit = source[j] - 'a';
currSubStrBits = setBit(currSubStrBits, bit);
// then compare the currSubStrBits with charsBits, if they
equal, then its not valid, we can skip the rest of j
if (currSubStrBits == charsBits)
{
break;
}
else
{
result.push_back(source.substr(i, j - i + 1));
}
}
}
return result;

}
Test code:
string source = "abccccdef";
char mychars[] = {'a', 'b', 'c'};
std::vector chars (mychars, mychars + sizeof(mychars) / sizeof
(char) );
vector result = findSubStr(source, chars);

【在 j********2 的大作中提到】

j*22013-12-26 08:12

43 楼

这个解法很赞，谢了！

【在 y***n 的大作中提到】

: 写了一个，看一看。。
: http://ideone.com/NyqYyS

j*22013-12-26 08:12

44 楼

我也不知道restore怎么写，贴一下我的flattern. 没用recursion, 用了一个stack:
void flatternAugListWithStack(AugListNode *&node)
{
if (!node) return;
stack st;
AugListNode *p = node; // current node
AugListNode *tail = node; // current tail
while (1)
{
if (!p && st.empty()) break;
// after we go over the children, fetch it from the stack
if (!p) {p = st.top(); st.pop(); tail->next = p; continue;}
if (!p->next) tail = p;
if (!p->child) p = p->next;
else
{
if (p->next)
{
st.push(p->next); // save the next node
}
p->next = p->child; // change the next pointer
p = p->next;
}
}
}

【在 y***n 的大作中提到】

: 写了Flattern this multilevel data structure： http://ideone.com/11xcqw
: Restore 不知道如何写，感觉要存一下那里开始Flat的才行。
:
: doubly
: .

y*n2013-12-26 08:12

45 楼

感觉Restore还要一些其他条件

j*22013-12-26 08:12

46 楼

大牛觉得code应该怎么写呢

【在 y***n 的大作中提到】

: 感觉Restore还要一些其他条件

w*w2013-12-26 08:12

47 楼

mark

y*n2013-12-26 08:12

48 楼

找longway2008, 我是文科生转的。。。

【在 j********2 的大作中提到】

: 大牛觉得code应该怎么写呢

l*a2013-12-26 08:12

49 楼

PIE上有solution
自己去看好了

【在 j********2 的大作中提到】

: 大牛觉得code应该怎么写呢

t*n2013-12-26 08:12

50 楼

Thanks!
My answer in ruby:
require 'set'
def sum_3(arr, k)
check = arr.to_set
result = Set.new
arr.each do |m|
arr.each do |n|
target = k - m -n
if check.include?(target)
result.add([m, n, target].to_set)
end
end
end
result
end
def restore(my_set, k)
result = []
my_set.each do |s|
if s.length == 3
result << s.to_a
elsif s.length == 2
arr = s.to_a
arr << (k - arr[0] - arr[1])
result << arr
else
result << (s.to_a * 3)
end
end
result
end
my_set = sum_3([1, 2, -3, 4, 0], 0)
p restore(my_set, 0)
I tested it and got the correct answer.

【在 n********g 的大作中提到】

: 2重循环加一个hash map

t*n2013-12-26 08:12

51 楼

4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
My answer in Ruby:
def limited_sub(s, arr)
result = Set.new
(0..s.length - 1).each do |i|
(i..s.length - 1).each do |j|
sub = s[i..j]
if sub.split("").to_set.length < arr.length
result.add(sub)
end
end
end
result
end
p limited_sub("abbc", ['a', 'b', 'c'])
I tested and got correct answer.

t*n2013-12-26 08:12

52 楼

4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
有元素.
abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
有什么好思路？
单机没有好思路，貌似就一边生成一边过滤。不过建议和面试官讨论多机环境下map
reduce->对字符数组中的每个元素（应该可以assume无重复），map到子问题：从字符
串生成所有不包含此元素的子串->再reduce。我觉得我要是面试官会想听到这个思路。
I can't figure out how to implement this to make it faster than O(n ^2)...

t*n2013-12-26 08:12

53 楼

3. 一个数组,一个target,求所有的pairs, array[i] - array[j] = k.
hash table? 要是k=0, 所有数都相等呢？怎么看都是n^2了
同上，应该是O(n)吧，用一个hashmap的话（重复元素可以加个counter）
===》要是k=0, 所有数都相等呢？把解输出就已经是n^2了吧。另外，是把a[i]和-a[i]
都放到hashtable里？
def sum_2b(arr, k)
seen = Hash.new{ |hash, key| hash[key] = [] }
result = Set.new
(0..arr.length - 1).each do |i|
if seen.include?(k+ arr[i])
seen[k+ arr[i]].each do |j|
result.add([j, i])
end
end
seen[arr[i]]<< i
end
result
end
p sum_2b([3,3,3], 0) #got [[0, 1],[0, 2],[1, 2]], O(n ^2)
If we just want the actual nums, we can use 2 sum to get linear time, but is
we want the actual index, it seems like linear time impossible?

t*n2013-12-26 08:12

54 楼

What is PIE?

【在 l*****a 的大作中提到】

: PIE上有solution
: 自己去看好了

r*k2013-12-26 08:12

55 楼

这个case可以先从头到尾访问一遍字符串
然后就可以得到好多个最小的包含abc的范围
[0,4]
然后双重循环i，j
只要不满足i<=0,j>=4
都是一个合法的子串

【在 t********n 的大作中提到】

: 4. 一个字符串,一个字符数组,求所有的子字符串,子字符串不能包括字符数组里面的所
: 有元素.
: abbc, [a,b,c] -> a, b, c, ab, abb, bbc, bb, bc
: 有什么好思路？
: 单机没有好思路，貌似就一边生成一边过滤。不过建议和面试官讨论多机环境下map
: reduce->对字符数组中的每个元素（应该可以assume无重复），map到子问题：从字符
: 串生成所有不包含此元素的子串->再reduce。我觉得我要是面试官会想听到这个思路。
: I can't figure out how to implement this to make it faster than O(n ^2)...

r*k2013-12-26 08:12

56 楼

其实好像不用遍历再判断
i的范围会决定了j的范围
可以直接生成
所以应该比n^2低点，不过还是有可能有重复的
还是要判断是否已经生成过

【在 r*******k 的大作中提到】

: 这个case可以先从头到尾访问一遍字符串
: 然后就可以得到好多个最小的包含abc的范围
: [0,4]
: 然后双重循环i，j
: 只要不满足i<=0,j>=4
: 都是一个合法的子串

l*82013-12-26 08:12

57 楼

Programming Interview Exposed.

【在 t********n 的大作中提到】

: What is PIE?

l*82013-12-26 08:12

58 楼

PIE上的跟这个不是一题。

【在 l*****a 的大作中提到】

: PIE上有solution
: 自己去看好了

l*82013-12-26 08:12

59 楼

我写一个linked list flatten和restore吧。可能还有bugs
Node * flatten(Node * curr, Node * tail = NULL, Node * parent = NULL) {
if (!curr) return tail;

if (tail)
tail->next = current;
tail = current;
Node * next = curr->next;
if (curr->child)
tail = flatten(curr->child, tail, next ? curr : parent);
else if (!next)
curr->child = parent;
return flatten(next, tail, parent);
}
void restore(Node * curr) {
while (curr) {
Node * next = curr->next;
if (curr->child) {
curr->next = NULL;
if (curr->child != next) {
curr->child->next = next;
curr->child = NULL;
}
}
curr = next;
}
}

【在 y***n 的大作中提到】

: 找longway2008, 我是文科生转的。。。

j*22013-12-26 08:12

60 楼

restore 部分没看懂，大牛可否解释一下？

【在 l*********8 的大作中提到】

: 我写一个linked list flatten和restore吧。可能还有bugs
: Node * flatten(Node * curr, Node * tail = NULL, Node * parent = NULL) {
: if (!curr) return tail;
:
: if (tail)
: tail->next = current;
: tail = current;
: Node * next = curr->next;
: if (curr->child)
: tail = flatten(curr->child, tail, next ? curr : parent);

l*82013-12-26 08:12

61 楼

在flatten的时候，利用没有child也没有next的节点的child pointer来指向restore时
要返回的祖先节点。
restore的时候，利用前面说的"child pointer"来返回祖先节点，并恢复指针的值。

【在 j********2 的大作中提到】

: restore 部分没看懂，大牛可否解释一下？

y*n2013-12-26 08:12

62 楼

这个有点看晕了，我可能会用一个map 存一下被Flatten的List 的头尾
节点，然后Restore 一下。

j*22013-12-26 08:12

63 楼

大牛上个code吧

【在 y***n 的大作中提到】

: 这个有点看晕了，我可能会用一个map 存一下被Flatten的List 的头尾
: 节点，然后Restore 一下。

j*22013-12-26 08:12

64 楼

照你的建议写了一个，没测过
void restore(AugListNode *head, unordered_map
&ht)
{
if (!head) return;
AugListNode *curNode, *nextNode;
curNode = head; nextNode = curNode->next;

while (1)
{
if (!curNode) break;
if (ht.find(nextNode) != ht.end()) // a child list found
{
// separate the child list
curNode->child = nextNode;
AugListNode *nextNodeAfterChildList = ht[nextNode]->next;
curNode->next = nextNodeAfterChildList;

restore(nextNode, ht); // restore the child list
// move on
curNode = nextNodeAfterChildList;
nextNode = curNode->next;
}
else
{
// move on
curNode = nextNode;
nextNode = curNode->next;
}
}
}

【在 y***n 的大作中提到】

: 这个有点看晕了，我可能会用一个map 存一下被Flatten的List 的头尾
: 节点，然后Restore 一下。

y*n2013-12-26 08:12

65 楼

我写了一个。
http://ideone.com/H1WUL0

v*o2013-12-26 08:12

66 楼

1. 递归 plus path array
Pseudo code(Pre-Order)
public void PrintAllPath( ArrayList paths, Node node)
{
System.Out.Println(paths.Tostring);
if (node ==null)
return;
paths.Add(node);
PrintAllPath(paths, node.Left);
PrintAllPath(paths, node.right);
}
不用递归的话，用个额外的stack traversal即可。

【在 j********2 的大作中提到】

p*62013-12-26 08:12

67 楼

doubly
.
if(node == null) return node;

Stack stack = new Stack();
ListNode head = new ListNode(-1);
head.next = node;

while(node!=null){
if(node.other!=null){
if(node.next!=null)
stack.add(node.next);
node.next = node.other;
node.other = null;
}else{
if(node.next == null && !stack.isEmpty()){
ListNode top = stack.pop();
node.next = top;
}
}
node = node.next;
}
return head.next;
用stack还清晰些。

【在 j********2 的大作中提到】

m*a2013-12-26 08:12

68 楼

这个不错

【在 j**7 的大作中提到】

: 1.)
: /*
: * print all paths from root to leaf.
: */
: public static void printPaths(TreeNode root) {
: if (root == null) {
: return;
: }
: ArrayList path = new ArrayList();
: // post order tree traversal.

x*B2013-12-26 08:12

69 楼

你把这个链表想像成二叉树或者带父亲节点的二叉树。然后前序遍历？

doubly
.

【在 j********2 的大作中提到】

b*r2013-12-26 08:12

70 楼

mark.谢谢！