Misc Questions

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

```#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;
int valC = listB;
int valC = listC;

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 > x) {
max = x;
second = x;
} else {
max = x;
second = x;
}

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