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):
    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


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()]) {

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

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

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


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


reverse a linked list

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

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

    pre = current;
    current = next;

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

   if (!rest) return;

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

Add a New Comment
or Sign in as Wikidot user
(will not be published)
- +
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License