问一道facebook的面试题 - 未名空间MITBBS历史存档

r*62012-02-14 08:02

1 楼

有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
大值。
例如，
有数组 2，3，4，2，6，7，8，2，4，1，2，3
k = 3
输出
4，4，6，7，8，8，8，4，4，4
有什么好一点的解法吗。

b*e2012-02-14 08:02

2 楼

use heap?

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

: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。

n*42012-02-14 08:02

3 楼

use a queue
keep the biggest value at the head of the queue

P*A2012-02-14 08:02

4 楼

Maintain a Binary Search Tree,
with a pointer to the max node,
Every time you insert a new element, update the pointer if necessary.

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

: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。

g*y2012-02-14 08:02

5 楼

public int[] getWindowMax(int[] a, int w) {
int[] b = new int[a.length - w + 1];

ArrayDeque q = new ArrayDeque();
for (int i=0; iwhile (!q.isEmpty() && a[q.peekLast()]<=a[i]) q.removeLast();
q.addLast(i);
}

b[0] = a[q.peekFirst()];
for (int i=w; iwhile (!q.isEmpty() && q.peekFirst()<=i-w) q.pop();
while (!q.isEmpty() && a[q.peekLast()]<=a[i]) q.removeLast();
q.addLast(i);
b[i-w+1] = a[q.peekFirst()];
}

return b;
}
如果有问题，去读ihasleetcode的网站。

b*v2012-02-14 08:02

6 楼

时间复杂性是什么？

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

: public int[] getWindowMax(int[] a, int w) {
: int[] b = new int[a.length - w + 1];
:
: ArrayDeque q = new ArrayDeque();
: for (int i=0; i: while (!q.isEmpty() && a[q.peekLast()]<=a[i]) q.removeLast();
: q.addLast(i);
: }
:
: b[0] = a[q.peekFirst()];

y*z2012-02-14 08:02

7 楼

ST 算法 + RMQ

R*92012-02-14 08:02

8 楼

#include
#include
#include
using namespace std;
void PrintMaxInWindow(int a[], int n, int k){
set s;
int i=0;
for(;is.insert(a[i]);
set::reverse_iterator rit;
for(;i<=n;i++){
rit = s.rbegin();
cout<s.erase(a[i-k]);
s.insert(a[i]);
}
}

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

: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。

h*r2012-02-14 08:02

9 楼

单调队列吧~

b*z2012-02-14 08:02

10 楼

Use max-heap.

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

: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。

P*P2012-02-14 08:02

11 楼

这题o(n)
就是implement a queue with getMax().
有点像crack150里面的stack with getMax()
public void addLast(T data) {
// insert data to the data queue.
dataQ.add(data);
// adjust the auxiliary queue.
while (!auxiQ.isEmpty() && auxiQ.getLast().compareTo(data) < 0) {
auxiQ.removeLast();
}
auxiQ.add(data); //append to the end.
}
public T getMax() {
return auxiQ.getFirst();
}
public T removeFirst() {
T data = dataQ.removeFirst();
// adjust the auxiliary queue. Because the previous max is removed, the
// head (which is the current max) should be removed too.
if (data == auxiQ.getFirst()) {
auxiQ.removeFirst();
}
return data;
}

b*u2012-02-14 08:02

12 楼

可以用c++的map，每次存 reverse iterator的第一个，删find i-2
不过好像挺作弊。

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

: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。

b*u2012-02-14 08:02

13 楼

heap找arr[i-3]不是很容易吧。

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

: use heap?

b*u2012-02-14 08:02

14 楼

set好像不是sorted的吧？要用map

【在 R******9 的大作中提到】

: #include
: #include
: #include
: using namespace std;
: void PrintMaxInWindow(int a[], int n, int k){
: set s;
: int i=0;
: for(;i: s.insert(a[i]);
: set::reverse_iterator rit;

z*t2012-02-14 08:02

15 楼

Share a blog with two solutions of this problem:
http://codercareer.blogspot.com/2012/02/no-33-maximums-in-slidi
Enjoy it:)

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

: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。

r*62012-02-14 08:02

16 楼

有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
大值。
例如，
有数组 2，3，4，2，6，7，8，2，4，1，2，3
k = 3
输出
4，4，6，7，8，8，8，4，4，4
有什么好一点的解法吗。

b*e2012-02-14 08:02

17 楼

use heap?

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

: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。

n*42012-02-14 08:02

18 楼

use a queue
keep the biggest value at the head of the queue

P*A2012-02-14 08:02

19 楼

Maintain a Binary Search Tree,
with a pointer to the max node,
Every time you insert a new element, update the pointer if necessary.

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

: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。

g*y2012-02-14 08:02

20 楼

public int[] getWindowMax(int[] a, int w) {
int[] b = new int[a.length - w + 1];

ArrayDeque q = new ArrayDeque();
for (int i=0; iwhile (!q.isEmpty() && a[q.peekLast()]<=a[i]) q.removeLast();
q.addLast(i);
}

b[0] = a[q.peekFirst()];
for (int i=w; iwhile (!q.isEmpty() && q.peekFirst()<=i-w) q.pop();
while (!q.isEmpty() && a[q.peekLast()]<=a[i]) q.removeLast();
q.addLast(i);
b[i-w+1] = a[q.peekFirst()];
}

return b;
}
如果有问题，去读ihasleetcode的网站。

b*v2012-02-14 08:02

21 楼

时间复杂性是什么？

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

: public int[] getWindowMax(int[] a, int w) {
: int[] b = new int[a.length - w + 1];
:
: ArrayDeque q = new ArrayDeque();
: for (int i=0; i: while (!q.isEmpty() && a[q.peekLast()]<=a[i]) q.removeLast();
: q.addLast(i);
: }
:
: b[0] = a[q.peekFirst()];

y*z2012-02-14 08:02

22 楼

ST 算法 + RMQ

R*92012-02-14 08:02

23 楼

#include
#include
#include
using namespace std;
void PrintMaxInWindow(int a[], int n, int k){
set s;
int i=0;
for(;is.insert(a[i]);
set::reverse_iterator rit;
for(;i<=n;i++){
rit = s.rbegin();
cout<s.erase(a[i-k]);
s.insert(a[i]);
}
}

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

: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。

h*r2012-02-14 08:02

24 楼

单调队列吧~

b*z2012-02-14 08:02

25 楼

Use max-heap.

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

: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。

P*P2012-02-14 08:02

26 楼

这题o(n)
就是implement a queue with getMax().
有点像crack150里面的stack with getMax()
public void addLast(T data) {
// insert data to the data queue.
dataQ.add(data);
// adjust the auxiliary queue.
while (!auxiQ.isEmpty() && auxiQ.getLast().compareTo(data) < 0) {
auxiQ.removeLast();
}
auxiQ.add(data); //append to the end.
}
public T getMax() {
return auxiQ.getFirst();
}
public T removeFirst() {
T data = dataQ.removeFirst();
// adjust the auxiliary queue. Because the previous max is removed, the
// head (which is the current max) should be removed too.
if (data == auxiQ.getFirst()) {
auxiQ.removeFirst();
}
return data;
}

b*u2012-02-14 08:02

27 楼

可以用c++的map，每次存 reverse iterator的第一个，删find i-2
不过好像挺作弊。

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

: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。

b*u2012-02-14 08:02

28 楼

heap找arr[i-3]不是很容易吧。

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

: use heap?

b*u2012-02-14 08:02

29 楼

set好像不是sorted的吧？要用map

【在 R******9 的大作中提到】

: #include
: #include
: #include
: using namespace std;
: void PrintMaxInWindow(int a[], int n, int k){
: set s;
: int i=0;
: for(;i: s.insert(a[i]);
: set::reverse_iterator rit;

z*t2012-02-14 08:02

30 楼

Share a blog with two solutions of this problem:
http://codercareer.blogspot.com/2012/02/no-33-maximums-in-slidi
Enjoy it:)

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

: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。

t*j2012-02-14 08:02

31 楼

用数组实现的Q...
当然咯，用vector可以省去很多code。
void subMost(int* parentArray, int parentSize, int childSize)
{
int* valueArray = new int[childSize];
int* positionArray = new int[childSize];
int actualSize = 0;
int childFrontIndex = 0;
int childEndIndex = -1;
for(int i=0; i< parentSize+childSize-1; i++)
{
if(i>=childSize)
{
if(positionArray[childFrontIndex] == i-childSize)
{
childFrontIndex = (childFrontIndex++)%childSize;
actualSize --;
}
}
if(i < parentSize)
{
while((valueArray[childEndIndex] < parentArray[i]) && (
actualSize >0))
{
childEndIndex --;
actualSize --;
if((childEndIndex < 0) && (actualSize > 0) )
{
childEndIndex = childSize-1;
}
}
childEndIndex = (childEndIndex ++)%childSize;
valueArray[childEndIndex] = parentArray[i];
positionArray[childEndIndex] = i;
actualSize = actualSize++;
}
cout << valueArray[childFrontIndex] << endl;
}
delete valueArray;
delete positionArray;
}
test过了...

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

: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。

g*e2012-02-14 08:02

32 楼

leetcode上有这道题，貌似是两个queue

p*22012-02-14 08:02

33 楼

我前几天做了，好像一个就可以了。

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

: leetcode上有这道题，貌似是两个queue

M*t2012-02-14 08:02

34 楼

你看2月16号的帖子，何海涛本人给了他的解

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

:
: 我前几天做了，好像一个就可以了。