持H1B, 调整身份阶段，可以回国的，对吧？为什# Immigration - 落地生根
f*8
1 楼
妈的，你家地毯不是让人踩的难道是当床睡的？怕脏你铺地板纳。你嫌俺也脏，俺还嫌
你家地毯脏呢。实在看不惯的竟然有人让客人脱了鞋穿着袜子在地毯上踩，你就不怕染
上个脚气啥的。别的客人袜子上踩了地毯上的毛，还咋穿鞋？
脑子都让狗啃了
你家地毯脏呢。实在看不惯的竟然有人让客人脱了鞋穿着袜子在地毯上踩，你就不怕染
上个脚气啥的。别的客人袜子上踩了地毯上的毛，还咋穿鞋？
脑子都让狗啃了
p*2
2 楼
Round 2 45 mins
Write the following function
double solveForX(string s) { }
input will be linear equation in x with +1 or -1 coefficient.
output will be value of x.
s can be as follows
i/p x + 9 – 2 -4 + x = – x + 5 – 1 + 3 – x o/p 1.00
i/p x + 9 -1 = 0 o/p -8.00
i/p x + 4 = – 3 – x o/p -3.500
it has second part
if the i/p string can have ‘(‘ or ‘)’
x + 9 – 2 -(4 + x) = – (x + 5 – 1 + 3) – x
x + 9 + (3 + – x – ( -x + (3 – (9 – x) +x = 9 -(5 +x )
round 3
Sort an array using below operation
An operation called flip which runs in O(1) <<<<< important this is given
for an array ‘a’
a.flip(index) this operation will reverse the array from index to end of
the array
for eg:
a[]= {1,4,0,6,7};
a.flip(0) = 7,6,0,4,1 // reverse from 0 to end
a.flip(2) = 1,4,7,6,0 // reverse from 2nd index to end
a.flip(4) 1,4,0,6,7 // no change in array reverse from end to end
Write the following function
double solveForX(string s) { }
input will be linear equation in x with +1 or -1 coefficient.
output will be value of x.
s can be as follows
i/p x + 9 – 2 -4 + x = – x + 5 – 1 + 3 – x o/p 1.00
i/p x + 9 -1 = 0 o/p -8.00
i/p x + 4 = – 3 – x o/p -3.500
it has second part
if the i/p string can have ‘(‘ or ‘)’
x + 9 – 2 -(4 + x) = – (x + 5 – 1 + 3) – x
x + 9 + (3 + – x – ( -x + (3 – (9 – x) +x = 9 -(5 +x )
round 3
Sort an array using below operation
An operation called flip which runs in O(1) <<<<< important this is given
for an array ‘a’
a.flip(index) this operation will reverse the array from index to end of
the array
for eg:
a[]= {1,4,0,6,7};
a.flip(0) = 7,6,0,4,1 // reverse from 0 to end
a.flip(2) = 1,4,7,6,0 // reverse from 2nd index to end
a.flip(4) 1,4,0,6,7 // no change in array reverse from end to end
g*k
3 楼
为什么有人说要坐移民监？
F*P
4 楼
你家孩子不会坐在躺在地毯上么？
f*t
5 楼
onsite？
f*8
6 楼
洗别人的臭鞋，想想都恶心。再说客人也会交叉感染，方正我去别人家最怕人家要换拖
鞋，都不知道那鞋都什么人穿过。
我觉得鞋底比袜子干净得多
【在 F*P 的大作中提到】
: 你家孩子不会坐在躺在地毯上么？
p*2
7 楼
不是我的。是别人onsite的。
【在 f*******t 的大作中提到】
: onsite？
f*8
8 楼
绝对不会，只须在床上爬
【在 F*P 的大作中提到】
: 你家孩子不会坐在躺在地毯上么？
【在 F*P 的大作中提到】
: 你家孩子不会坐在躺在地毯上么？
c*a
9 楼
第一题如果没理解错，就是一个很specific的parser。主要考coding bug free？
第二题我只能想到O(n^2)解，唉
第二题我只能想到O(n^2)解，唉
F*P
10 楼
哦。。那还太小哦了。。
【在 f*****8 的大作中提到】
: 绝对不会，只须在床上爬
【在 f*****8 的大作中提到】
: 绝对不会，只须在床上爬
P*r
11 楼
我能想到的brute force的办法是从末尾排起，
比如 最后5个已经是排序的 4，1，2，3，5,6
到4的时候，就把4，1，2,3 copy 到新的array, 然后
newArray.O(1) 4,3,2,1
newArray.O(0) 1,2,3,4
再copy回去。
【在 c******a 的大作中提到】
: 第一题如果没理解错，就是一个很specific的parser。主要考coding bug free？
: 第二题我只能想到O(n^2)解，唉
比如 最后5个已经是排序的 4，1，2，3，5,6
到4的时候，就把4，1，2,3 copy 到新的array, 然后
newArray.O(1) 4,3,2,1
newArray.O(0) 1,2,3,4
再copy回去。
【在 c******a 的大作中提到】
: 第一题如果没理解错，就是一个很specific的parser。主要考coding bug free？
: 第二题我只能想到O(n^2)解，唉
F*P
12 楼
鞋底可能会有外面动物的大便，大便里可能会有各种细菌和病毒。。。
【在 f*****8 的大作中提到】
: 绝对不会，只须在床上爬
【在 f*****8 的大作中提到】
: 绝对不会，只须在床上爬
x*w
13 楼
第二题只能想到类似冒泡的O(n^2)的实现，
能用flip实现swap就可以快速排序啦
能用flip实现swap就可以快速排序啦
d*t
14 楼
个人习惯而已，不喜欢你就别去
r*h
15 楼
第一题转成后序直接计算就可以了吧，不过没练熟要写出来不容易
第二题。。。求n log n的解法
第二题。。。求n log n的解法
s*3
16 楼
不喜欢你就别去呗，或者想去自己带个鞋套去，一样的，楼主觉得自己的鞋子干净，别
人也觉得自己家干净，也不用那么气吧.
人也觉得自己家干净，也不用那么气吧.
x*y
17 楼
for 2nd problem, flip makes it possible to do insertion sort in O(nlogn)
time.
One nice thing about flip is that if we want to insert an element into an
ordered subarray in the head, it only takes O(logn) time.
For example, if we have an array 1 3 5 7 8 9 6 2 , and we want to insert 6
to 1
3 5 7 8 9.
First we need to know the expected position of 6(O(logn)) (assume that it's
k), then
flip(0) ---> 2 6 9 8 7 5 3 1 (0 is trivial)
flip(1) ---> 2 1 3 5 7 8 9 6 ( 1 = len(array) - ind(6)-1)
flip(4) ---> 2 1 3 5 6 9 8 7 (4 = len(array) - k)
flip(5) ---> 2 1 3 5 6 7 8 9 ( 5 = len(array) -k +1)
flip(1) ---> 2 9 8 7 6 5 3 1 ( 1 = len(array) - ind(6)-1)
flip(0) ---> 1 3 5 6 7 8 9 2 (0 is trivial)
6 flips can finish one step of insertion sort and takes O(logn) time.
So, totally should be O(nlogn).
time.
One nice thing about flip is that if we want to insert an element into an
ordered subarray in the head, it only takes O(logn) time.
For example, if we have an array 1 3 5 7 8 9 6 2 , and we want to insert 6
to 1
3 5 7 8 9.
First we need to know the expected position of 6(O(logn)) (assume that it's
k), then
flip(0) ---> 2 6 9 8 7 5 3 1 (0 is trivial)
flip(1) ---> 2 1 3 5 7 8 9 6 ( 1 = len(array) - ind(6)-1)
flip(4) ---> 2 1 3 5 6 9 8 7 (4 = len(array) - k)
flip(5) ---> 2 1 3 5 6 7 8 9 ( 5 = len(array) -k +1)
flip(1) ---> 2 9 8 7 6 5 3 1 ( 1 = len(array) - ind(6)-1)
flip(0) ---> 1 3 5 6 7 8 9 2 (0 is trivial)
6 flips can finish one step of insertion sort and takes O(logn) time.
So, totally should be O(nlogn).
f*8
18 楼
踩上狗屎的概率比中彩票的概率都低。鞋底绝对比鞋里面的袜子干净。
劝你还是别让小孩在地毯上爬了。真的不干净。
【在 F*P 的大作中提到】
: 鞋底可能会有外面动物的大便，大便里可能会有各种细菌和病毒。。。
劝你还是别让小孩在地毯上爬了。真的不干净。
【在 F*P 的大作中提到】
: 鞋底可能会有外面动物的大便，大便里可能会有各种细菌和病毒。。。
R*Z
19 楼
If you start from the back of the array, 4 flips will be enough
s
【在 x***y 的大作中提到】
: for 2nd problem, flip makes it possible to do insertion sort in O(nlogn)
: time.
: One nice thing about flip is that if we want to insert an element into an
: ordered subarray in the head, it only takes O(logn) time.
: For example, if we have an array 1 3 5 7 8 9 6 2 , and we want to insert 6
: to 1
: 3 5 7 8 9.
: First we need to know the expected position of 6(O(logn)) (assume that it's
: k), then
: flip(0) ---> 2 6 9 8 7 5 3 1 (0 is trivial)
s
【在 x***y 的大作中提到】
: for 2nd problem, flip makes it possible to do insertion sort in O(nlogn)
: time.
: One nice thing about flip is that if we want to insert an element into an
: ordered subarray in the head, it only takes O(logn) time.
: For example, if we have an array 1 3 5 7 8 9 6 2 , and we want to insert 6
: to 1
: 3 5 7 8 9.
: First we need to know the expected position of 6(O(logn)) (assume that it's
: k), then
: flip(0) ---> 2 6 9 8 7 5 3 1 (0 is trivial)
l*y
20 楼
还是挖自豪
【在 f*****8 的大作中提到】
: 踩上狗屎的概率比中彩票的概率都低。鞋底绝对比鞋里面的袜子干净。
: 劝你还是别让小孩在地毯上爬了。真的不干净。
【在 f*****8 的大作中提到】
: 踩上狗屎的概率比中彩票的概率都低。鞋底绝对比鞋里面的袜子干净。
: 劝你还是别让小孩在地毯上爬了。真的不干净。
w*0
21 楼
第一题括号有什么比较简洁的处理方式吗？
R*Z
22 楼
看到左括号递归调用自己，看到右括号return
【在 w**********0 的大作中提到】
: 第一题括号有什么比较简洁的处理方式吗？
【在 w**********0 的大作中提到】
: 第一题括号有什么比较简洁的处理方式吗？
w*0
23 楼
这个跟bubble sort没有区别啊。。
s
【在 x***y 的大作中提到】
: for 2nd problem, flip makes it possible to do insertion sort in O(nlogn)
: time.
: One nice thing about flip is that if we want to insert an element into an
: ordered subarray in the head, it only takes O(logn) time.
: For example, if we have an array 1 3 5 7 8 9 6 2 , and we want to insert 6
: to 1
: 3 5 7 8 9.
: First we need to know the expected position of 6(O(logn)) (assume that it's
: k), then
: flip(0) ---> 2 6 9 8 7 5 3 1 (0 is trivial)
s
【在 x***y 的大作中提到】
: for 2nd problem, flip makes it possible to do insertion sort in O(nlogn)
: time.
: One nice thing about flip is that if we want to insert an element into an
: ordered subarray in the head, it only takes O(logn) time.
: For example, if we have an array 1 3 5 7 8 9 6 2 , and we want to insert 6
: to 1
: 3 5 7 8 9.
: First we need to know the expected position of 6(O(logn)) (assume that it's
: k), then
: flip(0) ---> 2 6 9 8 7 5 3 1 (0 is trivial)
w*0
24 楼
好方法，多谢啦
【在 R***Z 的大作中提到】
: 看到左括号递归调用自己，看到右括号return
【在 R***Z 的大作中提到】
: 看到左括号递归调用自己，看到右括号return
r*n
25 楼
我怎么觉得用flip可以使得insertion sort变成O(n)
首先用flip做一个函数void reverse(int i, int j): reverse anything between
indices i and j, i < j.
然后insertion sort的时候，当需要把 i 放到 j 前面的时候，调用两次reverse就
可以了。
s
【在 x***y 的大作中提到】
: for 2nd problem, flip makes it possible to do insertion sort in O(nlogn)
: time.
: One nice thing about flip is that if we want to insert an element into an
: ordered subarray in the head, it only takes O(logn) time.
: For example, if we have an array 1 3 5 7 8 9 6 2 , and we want to insert 6
: to 1
: 3 5 7 8 9.
: First we need to know the expected position of 6(O(logn)) (assume that it's
: k), then
: flip(0) ---> 2 6 9 8 7 5 3 1 (0 is trivial)
首先用flip做一个函数void reverse(int i, int j): reverse anything between
indices i and j, i < j.
然后insertion sort的时候，当需要把 i 放到 j 前面的时候，调用两次reverse就
可以了。
s
【在 x***y 的大作中提到】
: for 2nd problem, flip makes it possible to do insertion sort in O(nlogn)
: time.
: One nice thing about flip is that if we want to insert an element into an
: ordered subarray in the head, it only takes O(logn) time.
: For example, if we have an array 1 3 5 7 8 9 6 2 , and we want to insert 6
: to 1
: 3 5 7 8 9.
: First we need to know the expected position of 6(O(logn)) (assume that it's
: k), then
: flip(0) ---> 2 6 9 8 7 5 3 1 (0 is trivial)
r*e
26 楼
你说的操作都没错，不过找出j这个位置最快也需要O(lgn)把
an
6
it'
【在 r*********n 的大作中提到】
: 我怎么觉得用flip可以使得insertion sort变成O(n)
: 首先用flip做一个函数void reverse(int i, int j): reverse anything between
: indices i and j, i < j.
: 然后insertion sort的时候，当需要把 i 放到 j 前面的时候，调用两次reverse就
: 可以了。
:
: s
an
6
it'
【在 r*********n 的大作中提到】
: 我怎么觉得用flip可以使得insertion sort变成O(n)
: 首先用flip做一个函数void reverse(int i, int j): reverse anything between
: indices i and j, i < j.
: 然后insertion sort的时候，当需要把 i 放到 j 前面的时候，调用两次reverse就
: 可以了。
:
: s
w*o
27 楼
No clues
D*6
28 楼
第一题有什么neat的做法？
r*n
29 楼
对的，我忘记了...
【在 r*******e 的大作中提到】
: 你说的操作都没错，不过找出j这个位置最快也需要O(lgn)把
:
: an
: 6
: it'
【在 r*******e 的大作中提到】
: 你说的操作都没错，不过找出j这个位置最快也需要O(lgn)把
:
: an
: 6
: it'
Y*f
30 楼
思路很好啊，不过感觉你具体操作的时候弄复杂了
以你的例子, 1 3 5 7 8 9 6 2
实际上3步可以做到
1 3 5 7 8 9 2 6 (reverse from 6)
1 2 5 6 2 9 8 7 (reverse from 7)
1 2 5 6 7 8 9 2 (reverse from 2)
s
【在 x***y 的大作中提到】
: for 2nd problem, flip makes it possible to do insertion sort in O(nlogn)
: time.
: One nice thing about flip is that if we want to insert an element into an
: ordered subarray in the head, it only takes O(logn) time.
: For example, if we have an array 1 3 5 7 8 9 6 2 , and we want to insert 6
: to 1
: 3 5 7 8 9.
: First we need to know the expected position of 6(O(logn)) (assume that it's
: k), then
: flip(0) ---> 2 6 9 8 7 5 3 1 (0 is trivial)
以你的例子, 1 3 5 7 8 9 6 2
实际上3步可以做到
1 3 5 7 8 9 2 6 (reverse from 6)
1 2 5 6 2 9 8 7 (reverse from 7)
1 2 5 6 7 8 9 2 (reverse from 2)
s
【在 x***y 的大作中提到】
: for 2nd problem, flip makes it possible to do insertion sort in O(nlogn)
: time.
: One nice thing about flip is that if we want to insert an element into an
: ordered subarray in the head, it only takes O(logn) time.
: For example, if we have an array 1 3 5 7 8 9 6 2 , and we want to insert 6
: to 1
: 3 5 7 8 9.
: First we need to know the expected position of 6(O(logn)) (assume that it's
: k), then
: flip(0) ---> 2 6 9 8 7 5 3 1 (0 is trivial)
Y*f
31 楼
第一题分别对左右两边用递归弄成如下形式
ax + b = a1x + b1
【在 p*****2 的大作中提到】
: Round 2 45 mins
: Write the following function
: double solveForX(string s) { }
: input will be linear equation in x with +1 or -1 coefficient.
: output will be value of x.
: s can be as follows
: i/p x + 9 – 2 -4 + x = – x + 5 – 1 + 3 – x o/p 1.00
: i/p x + 9 -1 = 0 o/p -8.00
: i/p x + 4 = – 3 – x o/p -3.500
: it has second part
ax + b = a1x + b1
【在 p*****2 的大作中提到】
: Round 2 45 mins
: Write the following function
: double solveForX(string s) { }
: input will be linear equation in x with +1 or -1 coefficient.
: output will be value of x.
: s can be as follows
: i/p x + 9 – 2 -4 + x = – x + 5 – 1 + 3 – x o/p 1.00
: i/p x + 9 -1 = 0 o/p -8.00
: i/p x + 4 = – 3 – x o/p -3.500
: it has second part
w*t
32 楼
My solution, flip 4 times per insertion
20 void _Flip(vector& a, int idx)
21 {
22 if (idx < 0 || idx >= a.size()) return;
23 int left = idx, right = a.size() - 1;
24 while (left < right) swap(a[left++], a[right--]);
25 }
26
27 void InsertByFlip(vector& a, int idx, int iPos)
28 {
29 // e.g. AB C DE --> ACB DE
30
31 _Flip(a, idx + 1); // AB C ED
32 _Flip(a, idx); // AB DE C
33
34 _Flip(a, iPos); // AC ED B
35 _Flip(a, iPos + 1); // ACB DE
36 }
37
38 int BiSearch(vector& a, int start, int end, int target)
39 {
40 while (start <= end) {
41 int mid = start + (end - start) / 2;
42 if (a[mid] < target) start = mid + 1;
43 else end = mid - 1;
44 }
45 return start;
46 }
47 void SortByFlip(vector& a)
48 {
49 for (int i = 1; i < a.size(); ++i) {
50 // find insert position (O(logN))
51 int iPos = BiSearch(a, 0, i - 1, a[i]);
52 if (iPos == i) continue;
53
54 // insert
55 InsertByFlip(a, i, iPos); // O(1)
56 }
57 }
20 void _Flip(vector
21 {
22 if (idx < 0 || idx >= a.size()) return;
23 int left = idx, right = a.size() - 1;
24 while (left < right) swap(a[left++], a[right--]);
25 }
26
27 void InsertByFlip(vector
28 {
29 // e.g. AB C DE --> ACB DE
30
31 _Flip(a, idx + 1); // AB C ED
32 _Flip(a, idx); // AB DE C
33
34 _Flip(a, iPos); // AC ED B
35 _Flip(a, iPos + 1); // ACB DE
36 }
37
38 int BiSearch(vector
39 {
40 while (start <= end) {
41 int mid = start + (end - start) / 2;
42 if (a[mid] < target) start = mid + 1;
43 else end = mid - 1;
44 }
45 return start;
46 }
47 void SortByFlip(vector
48 {
49 for (int i = 1; i < a.size(); ++i) {
50 // find insert position (O(logN))
51 int iPos = BiSearch(a, 0, i - 1, a[i]);
52 if (iPos == i) continue;
53
54 // insert
55 InsertByFlip(a, i, iPos); // O(1)
56 }
57 }
e*i
33 楼
Any bull can post solution for problem 1? Many thanks.
I have a working solution. But I do not think it is good enough.
I have a working solution. But I do not think it is good enough.
s*t
34 楼
第一题用一个stack保存当前的sign就行了，遇到left就push，遇到right就pop，
比如1+2-（3-（4-（2+1）-2））
读到第一个left的时候，因为前面的sign是负，push负号，然后3就被读成负3，第二个
（因为前面还是负号，负负得正（stack.top是负号），push正号，所以4被读成正4。
。。。。。这样follow up就能转换成前面的问题。
【在 p*****2 的大作中提到】
: Round 2 45 mins
: Write the following function
: double solveForX(string s) { }
: input will be linear equation in x with +1 or -1 coefficient.
: output will be value of x.
: s can be as follows
: i/p x + 9 – 2 -4 + x = – x + 5 – 1 + 3 – x o/p 1.00
: i/p x + 9 -1 = 0 o/p -8.00
: i/p x + 4 = – 3 – x o/p -3.500
: it has second part
比如1+2-（3-（4-（2+1）-2））
读到第一个left的时候，因为前面的sign是负，push负号，然后3就被读成负3，第二个
（因为前面还是负号，负负得正（stack.top是负号），push正号，所以4被读成正4。
。。。。。这样follow up就能转换成前面的问题。
【在 p*****2 的大作中提到】
: Round 2 45 mins
: Write the following function
: double solveForX(string s) { }
: input will be linear equation in x with +1 or -1 coefficient.
: output will be value of x.
: s can be as follows
: i/p x + 9 – 2 -4 + x = – x + 5 – 1 + 3 – x o/p 1.00
: i/p x + 9 -1 = 0 o/p -8.00
: i/p x + 4 = – 3 – x o/p -3.500
: it has second part
相关阅读
485 priority date一般收到card production的notice后多长时间会收到卡？Good news: 485 Approval Notice Received (RD 3/23/2011)国内期刊文章求LAcounty可信度效率高投资移民律师Re: 号召改变中美H1B有效期为5年多次有效签证 (转载)真心请教，有没有在准备RFE期间和律师意见不同，不用律师的？请问体检RFE递上去后，一般多久绿卡能批？Expunged or Dismissed Case需要在申请绿卡的时候Disclose吗？[已近找到2名Reviewer, 谢谢]找journal reviewer, 土木环境农业方向485申请的W-2表格131 Part 7: how you qualify for an Advance Parole document请推荐一个好的律师，急！求祝福: Just mailed out the I485 applicationEAD approved on 06/22/11. RD 04/15/11求审稿的机会-分子生物学请教独立推荐人问题移民局不能查询case status？再问一下,邮寄485的信封上需要注明485申请吗DIY Eb1A pp approved on 8th day (no RFE)