持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
相关阅读
EB1A I-140 NSC direct pp approvedEB1A 140 Approved @TSC direct PPEB1A 真。纠结无双 忍不住PP了，NSC，求祝福！求助： 夫妻一方在国内，如何申请绿卡想找12月的RD的盖楼贴，怎么找？H1b工作，使用AP上周五入境infopass完全没用EB1a求推荐律师【2017年3月第17绿?】TSC交了485之后就可以出境了吗西北大学办的出生证和J1 wavier请问大家的SR一般是多久之后回复的呢？i-485 需要注册USCIS Online Account吗Visa Stamps485 EAD vs H4 EAD【2017年3月第6，7绿】我也来报个绿（TSC）回复under active examination是什么意思？guest editor needed求问：O1 和NIW 的推荐信的区别EB1A (DIY)-NSC-RFE Approve