g phone interv--有没有o(n) 解法 - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - g phone interv--有没有o(n) 解法

相关主题
● 请教一个题目
● amazon phone interview
● T problem
● 问个题目，找不在区间内的所有数
● 讨论一道L的validate binary tree和求深度的问题
● Google电话面试题目
● 问个算法题，关于区间 overlap的
● merge k个数组怎样的方法好？
● 问个微软面试题
● 问个Facebook 电面题

相关话题的讨论汇总
话题: test话题: case话题: int话题: oddpos话题: array

进入JobHunting版参与讨论

(共1页)

t**r
发帖数: 3428

google-interview-questions
0
of 0 votes
10
Answers
Given an array Of integers build a new array of integers such that every 2nd
element of the array is greater than its left and right element.
eg:
[1,4,5,2,3]
o/p:
[1,4,2,5,3]
so, 3 > 2 > 1, and 5 > 4
有没有o(n) 解法

k****p
发帖数: 9

用quick sort的partition方法找最小的(n+1)/2数, random种子，O(n)吧。
然后把这(n+1)/2放在偶数坐标，剩下放奇数坐标。O(n) space或in place都行。

2nd

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

: google-interview-questions
: 0
: of 0 votes
: 10
: Answers
: Given an array Of integers build a new array of integers such that every 2nd
: element of the array is greater than its left and right element.
: eg:
: [1,4,5,2,3]
: o/p:

t********5
发帖数: 522

好像是cc150还是lc原题吧
记得有o(n)解走一遍把不符合条件的左右swap就好了忘记题目叫什么了。。。
if less:
if a[left] > a[right]:
a[left], a[right] = a[right], a[left]
less = False
else:
if a[right] < a[left]:
a[left], a[right] = a[right], a[left]
less = True

t**r
发帖数: 3428

你题目没完全理解。

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

: 好像是cc150还是lc原题吧
: 记得有o(n)解走一遍把不符合条件的左右swap就好了忘记题目叫什么了。。。
: if less:
: if a[left] > a[right]:
: a[left], a[right] = a[right], a[left]
: less = False
: else:
: if a[right] < a[left]:
: a[left], a[right] = a[right], a[left]
: less = True

i*********7
发帖数: 348

这个好像不是很难吧？
for(int i = 0; i < arr.length; i += 2){
int index = findMaxIndex(arr, i, i + 1, i + 2);
if(index != i + 1)
swap(arr[i + 1], arr[index]);
}
这样不就好了么？

y******g
发帖数: 4

#include
#include
using namespace std;
void print(const vector &A) {
int count = 0;
cout << "[";
for(auto &i : A) {
if (count++) {
cout << ", ";
}
cout << i;
}
cout << "]" << endl;
};
void zigzag(vector &A) {
if (A.empty()) return;
for (size_t i = 1; i < A.size(); ++i) {
if (i&0x01) { // odd position element should be a local maximum
if (A[i] <= A[i-1]) {
swap(A[i-1], A[i]);
}
} else { // even position element should be a local minimum
if (A[i] > A[i-1]) {
swap(A[i-1], A[i]);
}
}
}
};
int main() {
// your code goes here
vector a1{1, 4, 5, 2, 3};
cout << "Before: ";
print(a1);
zigzag(a1);
cout << "After: ";
print(a1);
return 0;
}

i****7
发帖数: 26

这个题叫Wiggle Sort

l***i
发帖数: 1309

kkkppp already gave a solution.
A special case is to put the top n/2 elements in even position and bottom n/
2 elements in odd position, 1-based index. Now the problem reduces to find
median of this array, which can be done in worse case O(n) time using median
of median's algorithm, almost every algorithm book has the algorithm.

e**y
发帖数: 784

直接从左到右扫行不行，求指正
假设A[0], A[1], ... A[i-1] 已经sort好
A[i-1] A[i] A[i+1] 值顺序m1 分配A[i-1]=m1, A[i]=m3, A[i+1]=m2
用这种分配方式，在保证A[i]>A[i-1], A[i]>A[i+1]的同时，仍然保证A[i-1] 然后继续处理 A[i+1] A[i+2] A[i+3]，以此类推
这种思路有错吗？还是我理解题目有问题？

r**h
发帖数: 1288

直接swap就可以了呀
随机generate了500个test case，没有问题
import random
def ShouldSwap(test_case, i):
if i % 2 == 0 and test_case[i] > test_case[i+1]:
return True
elif i % 2 == 1 and test_case[i] < test_case[i+1]:
return True
else:
return False
def Validate(test_case):
i = 0
while i < len(test_case) - 1:
if ShouldSwap(test_case, i):
return False
i = i + 1
return True
def FuzzySort(test_case):
i = 0
while i < len(test_case) - 1:
if ShouldSwap(test_case, i):
test_case[i], test_case[i+1] = test_case[i+1], test_case[i]
i = i + 1

def Process(num_of_cases):
N = 0
while N < num_of_cases:
size = int(random.uniform(2, 20))
test_case = [int(random.uniform(1, 100)) for i in range(0, size)]
print(test_case)
FuzzySort(test_case)
print(test_case)
print(Validate(test_case))
N = N + 1
if __name__ == '__main__':
num_of_cases = 500
Process(num_of_cases)

相关主题
● 问个题目，找不在区间内的所有数
● 讨论一道L的validate binary tree和求深度的问题
● Google电话面试题目
● 问个算法题，关于区间 overlap的
进入JobHunting版参与讨论

e**y
发帖数: 784

i*********7
发帖数: 348

我的想法和你的是一样的，我觉得这一题没有那么复杂

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

: 直接从左到右扫行不行，求指正
: 假设A[0], A[1], ... A[i-1] 已经sort好
: A[i-1] A[i] A[i+1] 值顺序m1: 分配A[i-1]=m1, A[i]=m3, A[i+1]=m2
: 用这种分配方式，在保证A[i]>A[i-1], A[i]>A[i+1]的同时，仍然保证A[i-1]: 然后继续处理 A[i+1] A[i+2] A[i+3]，以此类推
: 这种思路有错吗？还是我理解题目有问题？

l*****n
发帖数: 246

我也觉得从左到右扫一遍就行了

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

: 我的想法和你的是一样的，我觉得这一题没有那么复杂

e********u
发帖数: 587

排个序不就是NlogN了么...

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

k****p
发帖数: 9

恩，想复杂了，就当发散下思路~

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

: 我的想法和你的是一样的，我觉得这一题没有那么复杂

q****o
发帖数: 6

感觉没问题，即便m1要放到中间，也是对的。

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

: 我的想法和你的是一样的，我觉得这一题没有那么复杂

Q**F
发帖数: 995

如果m1=m2=m3怎么处理？

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

Q**F
发帖数: 995

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

C*********r
发帖数: 21

how about this?
1. O(n) to find the median value of the array.
2. split the array to A{a1, a2, ....} > median, and B{b1, b2, ....} < median
3. insert b1 between a1, a2 using a separate array
any value in B > A, so any value in b will be bigger than a1, a2, ...

c*****e
发帖数: 3226

void wiggleSort(int a[]) {
if (a == null || a.length <=1) return;
boolean oddPos = true;
int i=0;
while(i <= a.length-2) {
if ((oddPos && a[i] > a[i+1]) ||
(!oddPos && a[i] < a[i+1])) {
int t = a[i+1];
a[i+1] = a[i];
a[i] = t;
}
i++;
oddPos = !oddPos;
}
}

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

e**y
发帖数: 784

没排序。。。
我说的sort好是假设已经做到第i步

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

: 排个序不就是NlogN了么...

w*****d
发帖数: 105

From your statement, it seems all the odd and even position elements in the
output array are both sorted, so I think there is no O(N) solutions.
The best way I can figure out is sort the array first(O(NlogN)), and then do
O(N) swaps in one pass:
1 2 3 4 5 6 7 ...
to
1 3 2 5 4 7 6 ...

(共1页)

进入JobHunting版参与讨论

相关主题
● 问个Facebook 电面题
● divide array into two, sum of difference is min in O(N)
● FB interview question
● JAVA里sort的algorithm time complexity是多少
● 问一道FB 的电面题
● [合集] Google电话面试题目
● 一道老题
● careercup上这道题我竟然没看懂
● 这题怎么做？
● 算法题：两列找共同元素有O(n)的算法吗？

相关话题的讨论汇总
话题: test话题: case话题: int话题: oddpos话题: array

boards