Misc Algorithm
##### convert an array

Given an array:

\$[a_1, a_2, ..., a_N, b_1, b_2, ..., b_N, c_1, c_2, ..., c_N ]\$

convert it to:

\$[a_1, b_1, c_1, a_2, b_2, c_2, ..., a_N, b_N, c_N]\$

in-place using constant extra space.

```def getIndex(currentIndex, N):
return (currentIndex%3)*N + (currentIndex/3)

def convertArray(arr):
N=len(arr)/3
for currentIndex in range(len(arr)):
swapIndex=getIndex(currentIndex, N)
while swapIndex<currentIndex:
swapIndex=getIndex(swapIndex, N)
arr[currentIndex], arr[swapIndex] = arr[swapIndex], arr[currentIndex]
```

#### sliding window

http://www.leetcode.com/2011/01/sliding-window-maximum.html

Input: A long array A[], and a window width w
Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1]
Requirement: Find a good optimal way to get B[i]

``````void slidingwindow(int a[], int size, int w, int b[]) {
Queue queue = new Queue();
for (int i=0; i<w; i++) {
while(!queue.empty() && a[i] >= a[queue.back()]) {
queue.popBack();
}
queue.pushBack(i);
}

for (int i=w; i<size; i++) {
b[i-w] = a[queue.front()];

while(!queue.empty() && a[i] >= a[queue.back()]) {
queue.popBack();
}

while(!queue.empty() && queue.front() <= i-w ] {
queue.popFront();
}

queue.push(i);
}

b[n-w] = a[queue.front()];

}```
```

``````void reverse(Node* & head) {
Node* pre = NULL;
Node* current = p;

while(current) {
next = current->next;
current->next = pre;

pre = current;
current = next;
}

}```
```
``````void reverse(Node*& p) {
if (!p) return;
Node* rest = p->next;

if (!rest) return;
reverse(rest);

rest->next = p;
p->next = NULL;

p=rest;
}```
```