p*****2
发帖数: 21240 | 1 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 | f*******t
发帖数: 7549 | | p*****2
发帖数: 21240 | 3
不是我的。是别人onsite的。
【在 f*******t 的大作中提到】
: onsite？
| c******a
发帖数: 789 | 4 第一题如果没理解错，就是一个很specific的parser。主要考coding bug free？
第二题我只能想到O(n^2)解，唉 | P*******r
发帖数: 210 | 5 我能想到的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)解，唉
| x*********w
发帖数: 533 | 6 第二题只能想到类似冒泡的O(n^2)的实现，
能用flip实现swap就可以快速排序啦 | r**h
发帖数: 1288 | 7 第一题转成后序直接计算就可以了吧，不过没练熟要写出来不容易
第二题。。。求n log n的解法 | x***y
发帖数: 633 | 8 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). | R***Z
发帖数: 1167 | 9 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)
| w**********0
发帖数: 214 | | | | R***Z
发帖数: 1167 | 11 看到左括号递归调用自己，看到右括号return
【在 w**********0 的大作中提到】
: 第一题括号有什么比较简洁的处理方式吗？
| w**********0
发帖数: 214 | 12 这个跟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)
| w**********0
发帖数: 214 | 13 好方法，多谢啦
【在 R***Z 的大作中提到】
: 看到左括号递归调用自己，看到右括号return
| r*********n
发帖数: 4553 | 14 我怎么觉得用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)
| r*******e
发帖数: 7583 | 15 你说的操作都没错，不过找出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
| w**********o
发帖数: 140 | | D****6
发帖数: 278 | | r*********n
发帖数: 4553 | 18 对的，我忘记了...
【在 r*******e 的大作中提到】
: 你说的操作都没错，不过找出j这个位置最快也需要O(lgn)把
:
: an
: 6
: it'
| Y********f
发帖数: 410 | 19 思路很好啊，不过感觉你具体操作的时候弄复杂了
以你的例子, 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
发帖数: 410 | 20 第一题分别对左右两边用递归弄成如下形式
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
发帖数: 485 | 21 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 } | e*******i
发帖数: 56 | 22 Any bull can post solution for problem 1? Many thanks.
I have a working solution. But I do not think it is good enough. | s*********t
发帖数: 52 | 23 第一题用一个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
|
|
