Misc Questions

有1,2,….一直到n的无序数组,求排序算法,并且要求时间复杂度为O(n),空间复杂度O(1),使用交换,而且一次只能交换两个数.

可以这样分析,从算法中看,每次交换操作的结果就是把a[i]放到数组中第a[i]个位置,就下标来说是index=a[i]-1,这也是排序结束后a[i]所应该在的位置。那么如果a[i]
已经等于在第a[i]个位置了,那么交换操作其实就是自己跟自己交换了一下,然后if语句成立,i自增1.可以发现,对于任何一个初始元素a[i],它只要通过一次交换操作就
可以到达排序结束后它所应该在的位置,而且以后不会再变动位置。因此,for 循环中所进行的exchange操作一共不超过2*len个,于是算法复杂度是linear!

#include<iostream.h>
 
int main()
{
int a[] = {10,6,9,5,2,8,4,7,1,3};
int len = sizeof(a) / sizeof(int);
int temp;
 
for(int i = 0; i < len; )
{
temp = a[a[i] - 1];
a[a[i] - 1] = a[i];
a[i] = temp;
 
if ( a[i] == i + 1)
i++;
}
for (int j = 0; j < len; j++)
cout<<a[j]<<",";
 
return 0;
}

A little bit change in order to save the swap operations if it's already ordered. So the total swap operation will be (n-1) times at most, instead of
2*(n-1) times. In either way, it's O(n).

#include <stdio.h>
 
int main()
{
int a[] = {10,6,9,5,2,8,4,7,1,3};
int len = sizeof(a) / sizeof(int);
int temp;
int i=0;
int j;
 
while(i<len)
{
// check if it's ordered or not
if ( a[i] == i + 1) {
i++;
continue;
}
 
// swap
temp = a[a[i] - 1];
a[a[i] - 1] = a[i];
a[i] = temp;
}
 
for (j = 0; j < len; j++)
printf("%d ",a[j]);
printf("\n");
 
return 0;
}

PN, infix, RPN(Post fix)

The infix expression "5 + ((1 + 2) * 4) − 3" can be written down like this in RPN: 5 1 2 + 4 * + 3 -
PN:
http://en.wikipedia.org/wiki/Reverse_Polish_notation#Converting_from_infix_notation

You have three sorted lists of numbers. You have to pick one number from each list such that the difference betweeen the maximum of the three and the minimum of the three is minimized. How fast can you do it ? Now do this for 'k' lists.

int iListA = 0;
int iListB = 0;
int iListC = 0;

int valA = listA[0];
int valC = listB[0];
int valC = listC[0];

while ( true )
{
if ( listA[iListA] <=
min( listB[iListB], listC[iListC] )
&& iListA < listA.size() - 1 )
++iListA;
else if ( listB[iListB] <=
min( listA[iListA], listC[iListC] )
&& iListB < listB.size() - 1 )
++iListB;
else if ( iListC < listC.size() - 1 )
++iListC;
else
break;

if ( minDistance( valA, valB, valC ) >
minDistance( listA[iListA],
listB[iListB],
listC[iListC] ) )
{
valA = listA[iListA];
valB = listB[iListB];
valC = listC[iListC];
}
}

int minDistance( int a, int b, int c )
{
return max( a, max( b, c ) ) - min( a, min( b, c ) );
}
oigen
Tuesday, October 17, 2006

Deleting … Approving …

Your idea are quite similar to the way Patrick proposed above for 3-list. Since you can solve the problem without merge for 3-list, I ask myself: can I solve the k-list problem without merge?

OK, if I don't merge the k-list, then I don't need to use the T array to trace the k-color… I stare at the algo and proof again…

Suddenly I found the only crucial operation is "Dump the Min value" ! Just this one, nothing else! The proof is already given.

To solve the k-list problem, use k pointers to scan those k arrays from index 0. Keep track of the Max-Min span, and increase the Min value pointer at each step.

Simple. (after you get the solution ;-))

http://discuss.techinterview.org/default.asp?interview.11.401110.9

suffix tree

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Suffix/

here are n(n+1)/2 substrings in txt[1..n]

Given a text document in an array, txtDoc[0…n], where each item in the array stores a line in the document, and you are also given several words, words[0…m], to search for in the document.

Find the minimum sub array of txtDoc where all items in words array can be found? Also explain the complexity and performance.

we can build a suffix tree from the textDoc[1..n], and then determine the lowest common ancestor (LCA) such that all its leaves contain the words you want to search for in the document. The LCA can be determined from the Euler tour. The complexity is O(n), space is O(n).

parentheses matching

initially count is set to 0 when the function is called.
int is_valid(char str[], int count, int index)
{
if(count <0) return 0

if(str[index] == '(')
{
return(is_valid(str, count + 1, index + 1);
}
else if(str[index] == ')')
{
return(is_valid(str, count - 1, index + 1);
}
else if(str[index] == '\0')
{
if(count == 0)
return 1; //valid.
else
return 0; //invalid.
}
}

Given a stack S, write a C program to sort the stack (in the ascending order).

We are not allowed to make any assumptions about how the stack is implemented.
The only functions to be used are:
Push
Pop
Top
IsEmpty
IsFull

Space lower bound is O(n).

To sort the stack, we need to access each element in the stack at least once. To access the bottom element on the stack, all the n-1 elements on top of it must be popped and stored somewhere. Hence O(n) space needed.

In view of this, create an array of size n, pop all elements in stack into the array, sort the array and push back the sorted elements into the stack.

It can be done using just the stack operations like this:

void sort(stack)
{
    type x;
 
    if (!isEmpty(stack)) {
        x = pop(stack);
        sort(stack);
        insert(x, stack);
    }           
}
 
void insert(x, stack)
{
    type y;
 
    if (!isEmpty(stack) && top(stack) < x) {
        y = pop(stack);
        insert(x, stack);
        push(y, stack);
    } else {
        push(x, stack);
    }
}

http://discuss.techinterview.org/default.asp?interview.11.434904.12

C code for swapping least significant bit and most significant bit in an unsigned and signed integer. I dont want to swap the bytes,only the bits.

This should work for an unsigned int:

shift = 8*sizeof(int) - 1;

x = (x » shift) + (x « shift) + (x & ~((1 « shift) + 1));

http://discuss.techinterview.org/default.asp?interview.11.433793.4

find the 2nd largest number

if (x[0] > x[1]) {
        max = x[0];
        second = x[1];
    } else {
        max = x[1];
        second = x[0];
    }
 
    for (i = 2; i < n; i++) {
        if (x[i] >= max) {
            second = max;
            max = x[i];
        } else if (x[i] > second) {
            second = x[i];
        }
    }

Kadane's Algorithm is an O(n) algorithm for finding the maximum contiguous subsequence in a one-dimensional sequence.

http://www.algorithmist.com/index.php/Kadane's_Algorithm

permutation

http://www.geocities.com/permute_it/

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License