CareerCup

Agree .. Q is not complete. Google never asked such silly Q.

BOOL TwoNodeSum(NODE *Root, int x, NODE **N1, NODE **N2)
{
    NODE *Mn = NULL, *Mx = NULL, *List[HIGHT], *TN = NULl, *TN2 = NULl;
    int sum = 0, i = 0;

    Mn = min(Root);
    Mx = max(Root);

    while(Mn->info < Mx->info){
        sum = Mn->info + Mx->info;
        if(sum == x){
	    *N1 = Mn;
	    *N2 = Mx;
	    return TRUE;
	}else if(sum > x){//Get Predecessor of Max Node i.e. of Mx
	    TN = Root;
	    i = 0;
            while(Mx->info != TN->info){
	        List[i++] = TN;
		if(Mx->info < TN->info) TN = TN->Left;
		else TN = TN->Right;
	    }

            PN = List[--i];
            if(Mx->Left != NULL){
                Mx = max(Mx->Left);
            }else if(PN != NULL){
                if(PN->Right == Mx) Mx = PN;
                else{
	            TN2 = List[--i];
	            SWAP(TN2, PN);
	            while(PN->Left == TN2){
	                TN2 = List[--i];
		        SWAP(TN2, PN);
	        }
	        Mx = PN;
	    }
	}else{//Get Sucessor of Min Node i.e. of Mn
	    TN = Root;
	    i = 0;
            while(Mn->info != TN->info){
	        List[i++] = TN;
		if(Mx->info < TN->info) TN = TN->Left;
		else TN = TN->Right;
	    }
            PN = List[--i];
            if(Mn->Right != NULL){
                Mn = min(Mn->Right);
            }else if(PN != NULL){
                if(PN->Left == Mn) Mn = PN;
                else{
	            TN2 = List[--i];
	            SWAP(TN2, PN);
	            while(PN->Right == TN2){
	                TN2 = List[--i];
		        SWAP(TN2, PN);
	        }
	        Mn = PN;
	    }
	}
    }//while
}

Here is solution as per space complexity, but high time complexity. If any one get soln with less complexity will be better.

BOOL TwoNodeSum(NODE *Root, int x, NODE **N1, NODE **N2)
{
    NODE *Mn = NULL, *Mx = NULL, *List[HIGHT], *TN = NULl, *TN2 = NULl;
    int sum = 0, i = 0;

    Mn = min(Root);
    Mx = max(Root);

    while(Mn->info < Mx->info){
        sum = Mn->info + Mx->info;
        if(sum == x){
	    *N1 = Mn;
	    *N2 = Mx;
	    return TRUE;
	}else if(sum > x){//Get Predecessor of Max Node i.e. of Mx
	    TN = Root;
	    i = 0;
            while(Mx->info != TN->info){
	        List[i++] = TN;
		if(Mx->info < TN->info) TN = TN->Left;
		else TN = TN->Right;
	    }

            PN = List[--i];
            if(Mx->Left != NULL){
                Mx = max(Mx->Left);
            }else if(PN != NULL){
                if(PN->Right == Mx) Mx = PN;
                else{
	            TN2 = List[--i];
	            SWAP(TN2, PN);
	            while(PN->Left == TN2){
	                TN2 = List[--i];
		        SWAP(TN2, PN);
	        }
	        Mx = PN;
	    }
	}else{//Get Sucessor of Min Node i.e. of Mn
	    TN = Root;
	    i = 0;
            while(Mn->info != TN->info){
	        List[i++] = TN;
		if(Mx->info < TN->info) TN = TN->Left;
		else TN = TN->Right;
	    }
            PN = List[--i];
            if(Mn->Right != NULL){
                Mn = min(Mn->Right);
            }else if(PN != NULL){
                if(PN->Left == Mn) Mn = PN;
                else{
	            TN2 = List[--i];
	            SWAP(TN2, PN);
	            while(PN->Right == TN2){
	                TN2 = List[--i];
		        SWAP(TN2, PN);
	        }
	        Mn = PN;
	    }
	}
    }//while
}

Here is solution of multiple path & single path.

char PATH[N];//N = (Number of Node in BT)X(Max Number of Leaf in BT)
int PATH_Len=0;
int path_cunt=0
int max_sum = 0;
void main()
{
    char path[N];
    int sum = 0, l = 0;
    NODE *BT == CreateBT(4,6,1,3,9,20,56,88,21,22,15);
    path[0]='R'; l=1;

    MaxPath(BT, sum, path, l);//This will evalute one path.
    printf("\nMax Sum: %d, PATH: %s", max_sum, PATH);
    memset(PATH, 0, N);
    path[0]='R'; l=1; max_sum=0; path_cunt=0;

    Multi_MaxPath(BT, sum, path, l);//This will evalute multiple path of same max.
    for(int i=0, int temp=0; i<path_cunt; i++){
        int temp_l=strlen(PATH+temp);
	printf("Max Sum: %d, PATH: %s", max_sum, PATH+temp);
        temp += temp_l+1;
    }
}

void MaxPath(NODE *Root, int sum, char path[], int l)
{
    if(!Root) return;
    sum += Root->info;
    if(sum>max_sum){
        strcpy(PATH, path, l);
        max_sum = sum;
    }
    path[l] = 'L';
    MaxPath(Root->Left, sum, path, l+1);
    path[l] = 'R';
    MaxPath(Root->Left, sum, path, l+1);
}

void Multi_MaxPath(NODE *Root, int sum, char path[], int l)
{
    if(!Root) return;
    sum += Root->info;
    if(sum == max_sum){
        PATH[PATH_Len] = '\0'; PATH_Len++;
        strcpy(PATH+PATH_Len, path, l);//Appending multiple Path String
	PATH_Len += l;
	path_cunt++;
    } else if(sum>max_sum){
        strcpy(PATH, path, l);
        max_sum = sum;
	path_cunt=1;
	PATH_Len=l;
    }
    path[l] = 'L';
    MaxPath(Root->Left, sum, path, l+1);
    path[l] = 'R';
    MaxPath(Root->Left, sum, path, l+1);
}

T(N) = O(N)
S(N) = (Number of Node in BT)X(Max Number of Leaf in BT)

int k_smallest_combinations(int A1[], int A2[], int l1, int l2, int k){
    Min_Heap heap(l1);//l1 is size of heap
    int count=1;
    for(int i=0; i<l1; i++){
        sum = A1[i] + A2[0];
	heap.insert(sum, i, 0);
    }
    while(count<k){
        int row = heap.root.row();
        int column= heap.root.column();
        sum = A1[row] + A2[column+1];
        heap.insert(sum, row, column +1);
	count++;
    }
    return heap.root.data();
}

@dev ... the questions is not about union of two array. Its about to find k-th smallest combinations(i.e. summation) of 2 num, one from each array.

Its like sorting array contains 0's & 1's(Assume 1 means non-zero's).
Use quick-sort method to move all the non-zero to end of array and zeros to beginning of array.

@vik .. Ur logic also correct. The same thing come to me after I post this solution.

The Q is about Kth(i.e. single coordinate) closest coordinate to origin(0,0). But your solution is over k-closest(i.e. all k closet coordinate) to origin.

int OddLevelSum=0, EvenLevelSum=0;
int calcDiff(node *Root, int level){
    if(level%2){/*Odd Level*/
        OddLevelSum=OddLevelSum+Root->info;
    }else{/*Even Level*/
        EvenLevelSum=EvenLevelSum+Root->info;
    }
    calcDiff(Root->left, level+1);
    calcDiff(Root->right, level+1);
    return modDiff(OddLevelSum, EvenLevelSum);
}

Note: Assuming input stream have only alphabate, there is no special charcter or symbols.

char getUniqueCharacter(STREAM *in)
{
    int cunt=0, position;
    MinHeap MnHip; // Contains only once appeariance charcter
    int map[256] = {-1}; //This will map charcter to MeanHeap Table.
    int FLAG[256] = {0};
    char ch='\0';
    while(hasNext(in)){
        ch = getNext(in);
	if(FLAG[ch] == 0){/*Charcter comes 1st time*/
            position = MnHip.insert(ch, cunt);
	    map[ch] = position;
	    FLAG[ch] = 1;
	    cunt++;
	}else{/*Charcter comes 2nd time*/
	    position = map[ch];
	    if(position<=256){ /*This means char present in Heap else deleted because of more than once repetation*/
	        MnHip.delete(ch, position);
	        map[ch] = 300;//Max size of Heap is 256
	    }
	}
    }//while()
    if(MnHip.root) return MnHip.root;
    else return '#';
}

Data Strucure Use: Min Heap

T(N) = N*Log(256) //256 is number of unique char, N is length of input stream

For Example, suppose we are looking for M(2,4), then Max, sub_size, sub_index, index goes as follow.

-------------------------------------------------------------------------------
|(1,2) | (1,3) | (1,4) | (1,5) | (2,3) | (2,4) | (2,5) | (3,4) | (3,5) | (4,5)|
-------------------------------------------------------------------------------
|   1   |   2   |   3   |   4   |   5   |   6   |   7   |   8   |   9   |  10 |
-------------------------------------------------------------------------------

<-----------------------------Max---------------------------------------------->
                                 <-----------------------sub_size-------------->
                             ^
			     |
			  sub_index
                                            ^
			                    |
					   index

1. Create a graph G with N nodes(each set equivalent to a node in graph), where as two nodes connected if they have common integers.
2. Sort nodes(descending order) according to its degree(number of edges connected to node).
3. Delete node from beginning from sorted nodes list, till no two nodes connected to each other.
Now reaming nodes in list are mutually exclusive sets, which is maximum.

Store the Matrix in single dimensional array by removing all the elements on & above major diagonal.

E.g. Let matrix size is 5X5, then the single dimensional array will have following list
-------------------------------------------------------------------------------
|(1,2) | (1,3) | (1,4) | (1,5) | (2,3) | (2,4) | (2,5) | (3,4) | (3,5) | (4,5)|
-------------------------------------------------------------------------------

The following function will calculate the exact index position of (i,j) in single dimensional array of matrix size NXN.

int index(int i, int j, int N)
{
    int Max=0, s=0, sub_size=0, sub_index=0, index=0;
    if(i>=N || j>=N) return -1;
    if(i == j) return 0;
    if(i>j) {i = i+j; j=i-j; i=i-j;} //swap i & j
 
    Max = N*(N-1)/2;
    s = N-i;
    
    sub_size = s*(s+1)/2;
    sub_index = Max-sub_size;
    index = sub_index+j-i;
    rerurn index;
}

S(N) = O(N*(N-1)/2)
O(N) = O(1)

1. If the Ask for Duplicate Charter removal, then use a Charter MAP BIT Vector of size 256(i.e. int BIT[8]), by assuming there are only 256 charter used only.

T(N) = O(N)
S(N) = O(256)

2. If the Ask for Duplicate Word removal, then use TRIE Data Structure.

T(N) = O(N)
S(N) = O(N)

int josephus(int n, int k)
{
    printf("LL Size: %d, OffSet: %d\n", n, k);
    if (n == 1)
        return 1;
    else /* The position returned by josephus(n - 1, k) is adjusted because the
            recursive call josephus(n - 1, k) considers the original position k%n + 1 as position 1 */
        return (josephus(n - 1, k) + k-1) % n + 1;
}

void max_num(int *A, int l){
    int n1 = -1, n2 = -1, c1 = 0, c2 = 0, i;
    for(i=0; i<l; i++){
        if(-1 == n1){ n1 = A[i]; c1++; }
	else if(-1 == n2){ n2 = A[i]; c2++; }
        else if(A[i] == n1) {c1++;}
        else if(A[i] == n2) {c2++;}
	else{
	    c1--;
	    c2--;
	    if(c1 == 0) n1 = -1;
            if(c2 == 0) n2 = -1;
	}
    }//for()
    c1 = 0; c2 = 0;
    for(i=0; i<l ; i++){
        if(n1 == A[i]) c1++;
	else if(n2 == A[i]) c2++;
    }
    if(c1>(l/3)) cout << n1;
    if(c2>(l/3)) cout << n2;
}

Use Red-Black/AVL Tree.
For Lookup T(N) = O(Log(N)).
For Range Lookup T(N) = O(Log(N) + Number of keys in between Key1 & Key2).

BOOL matche(char *S1, char *S2){
    while(s2 && s1){
        if(*s2 == *s1){
	    return matche(++s1, ++s2);
	} else {
	    switch(*s2){
	        case '*':
                    while(*s2 == '*') s2++;
                    while(*s1) {if(match(++s1, s2) == TRUE) return TRUE;}
		    return FALSE;
		break;
		case '?':
		    ++s2;
                    if(match(s1, s2) == TRUE) return TRUE;
		    if(match(++s1, s2) == TRUE) return TRUE;
		break;
		default:
                     return FALSE;
		break;
	    }//switch
	}
    }//While
    if(*s2 == '*' || *s2 == '?') ++s2;
    if(*s1 == '\0')
        return TRUE;
    else return FALSE;
}

SELECT: d.name, AVG(e.salary)
FROM: DEPT d, EMP e
WHERE: d.deptno = e.deptno
GROUP By: d.name

void UniqueInt(int **A, int R, int C)
{
    int ROW[2][R], COL[2][C];
    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
            if(ROW[0][i] < A[i][j]){
	        ROW[0][i] = A[i][j];
                ROW[1][i] = j;
	    }
	    if(COL[0][j] > A[i][j]){
	        COL[0][j] = A[i][j];
		COL[1][j] = i;
	    }
	}
    }
    if(R<C){
        for(int i=0; i<R; i++){
            if(ROW[0][i] == COL[0][ROW[1][i]])
	        cout << A[i][ROW[1][i]];
        }
    } else {
        for(int i=0; i<C; i++){
            if(COL[0][i] == ROW[0][COL[1][i]])
	        cout << A[COL[1][i]][i];
    }
}

T(N) = Size of MATRIX, i.e. MXN.
S(N) = 2*M + 2*N.

Binary Tree Approach:
=====================
int MaxConnect(int **A, int R, int C)
{
    int i, j, MAX = 0, Temp_MAX = 0;
    for(i = 0; i<R; i++)
        for(j = 0; j<C; j++) {
            if(A[i][j] == 1) {
                if(i-1>=0 && j-1>=0 && A[i-1][j] == 0 && A[i][j-1] == 0) {
                    Temp_MAX = GetLength(A, i, j);
                } else if(i-1>=0 && j-1 < 0 && A[i-1][j] == 0) {
                    Temp_MAX = GetLength(A, i, j);
                } else if(i-1<0 && j-1>=0 && A[i][j-1] == 0) {
                    Temp_MAX = GetLength(A, i, j);
                } else if(i-1<0 && j-1<0) {
                    Temp_MAX = GetLength(A, i, j);
                }
                if(Temp_MAX > MAX)
                    MAX = Temp_MAX;
            }//if(A[i][j] == 1)
        }
        return MAX;
}

int GetLength(int **A, int r, int c){
    int down, right;

    if(A[r][c] == 1) {
    down = GetLength(A, r+1, c);
    right = GetLength(A, r, c+1);
    return 1+ max(down, right);
    } else {
        return 0;
    }
}

T(N) = O(N*L)
N: Size of Matrix i.e. N = Row X Culumn
L: Length of the connected 1

Dynamic Programming Approach:
=============================
int MaxConnect(int **A, int R, int C){
    int Buff[R+1][C+1], MAX = 0;
    for(int i=0; i<R+1; i++)
        for(int j=0; j<C+1; j++)
            Buff[i][j] = 0;
    for(int i=0; i<R; i++){
        for(int j=0; j<C; j++){
            if(A[i][j] == 1){
                Buff[i+1][j+1] = 1 + max(Buff[i-1][j], Buff[i][j-1]);
                if (Buff[i+1][j+1] > MAX)
                    MAX = Buff[i+1][j+1];
            }
	}
    }
    return MAX;
}

T(N) = O(N)
    N: Size of Matrix i.e. N = Row X Culumn
S(N) = Size of Matrix i.e. N = Row X Culumn

By assuming array elements are sorted in ascending order, below is the algorithm(which will take care of duplicate elements as well).

void All_Sum_Pair(int A[], int start, int end, int SUM)
{
    int temp = 0;
    if(start<end){
        temp = A[start] + A[end];
	if(temp == SUM){
	    print("(%d, %d), ",A[start], A[end]);
            All_Sum_Pair(A, start+1, end, SUM);
	    All_Sum_Pair(A, start, end-1, SUM);
	} else if(temp > SUM){
	    All_Sum_Pair(A, start, end-1, SUM);
	} else {
	    All_Sum_Pair(A, start+1, end, SUM);
	}
    }
}

I think the file can't be loaded to memory at one place because of its size, so approaches goes like as follow.

1. Break the single file into multiple files(let it be M number of files) and each files have K words/lines.
2. Call random(), whch will generate num in between 0 & 1, let it be R.
3. Multiply R by M to get file, then again multiply R by K to get the word from the file.

BOOL IsBST(Node *Root)
{
    If(NULL == Root) return TRUE;
    int min = findMin(Root);
    int max = findMax(Root);
    return IsBST(Root, min-1, max+1);
}
BOOL IsBST(Node *Root, int MIN, int MAX)
{
    If(NULL == Root) return TRUE;
    return ( (Root->info > MIN) && 
             (Root->info < MAX) && 
	     IsBST(Root->Left, MIN, Root->Info+1) && 
	     IsBST(Root->Right, Root->Info-1, MAX) );
}

Node *CommonAncestor(Node *Root, Node *N1, Node *N2){
    Node *LC = NULL, *RC = NULL;

    if(Root == NULL || N1 == NULL || N2 == NULL) return NULL;
    if(Root == N1 || Root == N2) return Root;

    LC = CommonAncestor(Root->Left, N1, N2);
    RC = CommonAncestor(Root->Riht, N1, N2);
    if(LC != NULL && RC != NULL) return Root;
    else if(LC != NULL) return LC;
    else if(RC != NULL) return RC;
    else return NULL;
}

Array merge(Array A1, Array A2) {
    int size = A1.size+A2.size, i=0, a1i=0, a2i=0;
    Array MA(size);
    A1.sort();
    A2.sort();
    whiile(a1i<A1.size && a2i<A2.size){
        if(A1[a1i]<=A2[a21])
            MA[i++] = A1[a1i++];
        else
            MA[i++] = A1[a2i++];
    }
    if(a1i<A1.size){
        while(i<size){
            MA[i++] = A1[a1i++];
        }
    } else if(a2i<A2.size){
        while(i<size){
            MA[i++] = A1[a2i++];
        }
    }
    return MA;
}

BOOL Mirror(Node *T1, Node *T2) {
    if(T1==NULL && T2==NULL) return TRUE;
    if(T1==NULL || T2==NULL) return FALSE;
    return ((T1->info == T2->info) && 
        Mirror(T1->Left, T2->Right) && 
        Mirror(T1->Right, T2->Left));
}

By assuming S1 and S2 are two Dynamic Link List. Append Tail S1 with head of S2. Which is of O(1).

Node * Union(Node *S1, Node *S2) {
    TS1 =  S1.Tail();
    TS1->Next = S2;
    S1.tail = S2.tail;
    return S1;
}

#include <stdio.h>
#define N  5


int main(char *argv[],int argc)
{
  char list[5]={'a','b','c','d','e'};
  permute(list,0,N);
  return(0);
}


void permute(char list[],int k, int m)
{
  int i;
  char temp;

  if(k==m)
  {
    /* PRINT A FROM k to m! */
    for(i=0;i<N;i++){printf("%c",list[i]);}
    printf("\n");
  }
  else
  {
     for(i=k;i<m;i++)
     {
        /* swap(a[i],a[m-1]); */ 
        temp=list[i];
        list[i]=list[m-1];
        list[m-1]=temp;

        permute(list,k,m-1);

        /* swap(a[m-1],a[i]); */ 

        temp=list[m-1];
        list[m-1]=list[i];
        list[i]=temp;
       }
  }
}

Mn1 = (a<=b)?a:b; //min(a,b)
Mn2 = (Mn1!=b)?((b<=c)?b:c):((a<=c)?a:c);
median = (Mn1>=Mn2)?Mn1:Mn2; //Max(Mn1,Mn2)

Mn1 = (a<=b)?a:b; //min(a,b)
Mn2 = (b<=c)?b:c; //min(b,c)
median = (Mn1>=Mn2)?Mn1:Mn2; //Max(Mn1,Mn2)

So According to Ur solution:
if x =6 , y=8 , z=5
then w = 8 (as Max(6,8))
then median = 5 (as Min(8, 5))
Which is wrong ...

But median here is 6.

Abstract class can not be instantiated where as in Interface class there is definition/implementation of API.

int All_common_ancestor(NODE *Tree, NODE *Node1, NODE *Node2){
    if(!Tree) return 0;
    if(!search(Tree, Node1) && !search(Tree, Node2)) return 0;
    
    if(Tree->info == Node1->info || Tree->info == Node2->info){
        if(Tree->info == Node1->info){
            if(search(Tree->left, Node2) || search(Tree->right, Node2)){
                print Tree->info;
                return 2;
            }
        } else if(Tree->info == Node2->info) {
            if(search(Tree->left, Node1) || search(Tree->right, Node1)){
                print Tree->info;
                return 2;
            }
        } else
            return 1;
    }else{
        int L = 0, R = 0;
        L = All_common_ancestor(Tree->Left, Node1, Node2);
        R = All_common_ancestor(Tree->Right, Node1, Node2);
        if(L & R){
            print Tree->info;
            return 2;
        } else if (L==2 || R==2){
            print Tree->info;
            return 2;
        } else if(L||R) {
            return 1;
        } else {
            return 0;
        }
    }
}

BOOL search(NODE *Tree, NODE *Node){
    if(!Tree) return 0;
    if(Tree->info == Node->info)
        return 1;
    else
        return search(Tree->left, Node) || search(Tree->right, Node);
}

S = 0;
E = 0;
RS = ARR[S];
while(E<ARR.length) {
	if(RS == RESULT) {
		break;
	} else if(RS>RESULT) {
		RS = RS - ARR[S];
		S++;
	} else {
		E++;
		RS = RS + ARR[E];
	}
}
if(E!=ARR.length){
	print elements of ARR[] from S to E.
} else {
	No such subarray exist.
}

The Above Approach Failed in following BST, giving 2,4, 1 as output.

T1:
     1
    / \
   /   \
 NULL  NULL
T2:
        4
       / \
      / NULL
     2
    / \
   /   \
NULL  NULL

Steps:
1. Count number of digit in the number(i.e. length of the number), Let it be N.
2. Create 10 Bit vectors(i.e. for each num "0, 1, 2, 3, 4,5 6, 7, 8, 9") of lenth N.
    BOOLEAN VECTORS[10][N] = {0};
3. For each number(i.e. "0, 1, 2, 3, 4,5 6, 7, 8, 9") in Large number, create boolean vector.
    for(int j=0; j<N; j++){
        m = MSB(LARGE_NUMBER);
		remove m from LARGE_NUMBER;
        VECTORS[m][i] = 1;
    }
4. For each number(i.e. "0, 1, 2, 3, 4,5 6, 7, 8, 9") compress the corresponding boolean vector.
    for(i = 0; i<10; i++)
        compress(VECTORS[i])
5. Now store the compressed vectors of the 10 digits of the number in HASH Table.

NOTE:
Data Structure Use Here
1. Bit Vector Representation for each number.
2. Hash Table to store all number.

Hints: Quick Sort Approach, i.e. select pivot num.
Sol:
1. Take a random pivot number from the list.
2. Put the pivot number to it's exact location in the list. T(N) = O(N)
3. If position of the pivot num is the middle of list then retun the pivot as median.
else if position of the pivot num id less than middle num position then select a random pivot number from the right group and goto setp 2(above).
else select a random pivot number from the left group and goto setp 2(above).

The complexity of above approach depends on how pivot choosen. So its comlexity will be less than (N*LogN) or it will above (N*LogN).

Do U think Ur soln is O(NLogN), which is the expection.

When carry is 0, stop the loop(Add a checkpoint in for loop for this). And for the 4th line form last .. change it to if(i == 0 && flag*carry==1) form if(flag*carry==1).

Please take care to Operator Precedence & floating points.
E.g. for arr[]={1,2,6,2,4}; its gives following outputs but none of them are correct answer.
+ + + /
+ * + /
+ / + -
- + * -
- / + -

Thanks Amit... for finding the issue with code. I have corrected the same.

Here is running C Program

#include <stdio.h>
#include <string.h>
#include <stdarg.h>
#include <stdlib.h>

void intliv_two_strings(char *str1, char *str2, char *res_str, int index);
int count = 0;
int main()
{
	char str1[] = "ABCD", str2[] = "EFGH";
	int index = strlen(str1) + strlen(str2);
	char res_str[index];
        count = 0;
	memset(res_str, 0, index);
	intliv_two_strings(str1, str2, res_str, 0);
        printf("Total number of generated string: %d\n", count);
	return 0;
}

void intliv_two_strings(char *str1, char *str2, char *res_str, int i)
{
	int l1 = strlen(str1), l2 = strlen(str2);
        char str1_t[10], str2_t[10];
        int k = strlen(res_str);
        strcpy(str1_t, str1);
        strcpy(str2_t, str2);

	if(l1 == 0 && l2 == 0) {
            return;
	} else if(l1 == 0) {
		printf("%s",str2);
                for(k; k>0; k--)
                    printf("%c", res_str[k-1]);
                printf("\n");
                count++;
		return;
	} else if (l2 == 0) {
		printf("%s",str1);
                for(k; k>0; k--)
                    printf("%c", res_str[k-1]);
                printf("\n");
                count++;
		return;
	} else {
		res_str[i] = str1[l1-1]; res_str[i+1] = '\0';
		str1_t[l1-1] = '\0';
		intliv_two_strings(str1_t, str2, res_str, i+1);

		res_str[i] = str2[l2-1]; res_str[i+1] = '\0';
		str2_t[l2-1] = '\0';
		intliv_two_strings(str1, str2_t, res_str, i+1);
	}
}

I think you are assuming "i = 1" here, else the loop will never terminate.

No merge sort needed here. To find small distancehere is algo:

List1: have position of each WORD1.
List2: have position of each WORD2.

int FindSortDist(List list1[], int m, List list2[], int n)
{
    int k, l;
    int dist = MAX;
    int l1 = 0, l2 = 0;
    while ( l1 < m && l2 < n )
    {
        dist = Min(dist, ABS(list1[l1] - list2[l2]));
        if (list1[l1] < list2[l2])
            ++l1;
        else
            ++l2;
    }
	return dist;
}

Here Time complxity: O(2N) ~ O(N).

Above program will go in infinite loop when list1[ia] equal to list2[ib], i.e. (list1[ia] == list2[ib]).

Correct code is as follow:

int FindMinDist(List<int> list1, List<int> list2)
{
    int iMinDist = int.MaxValue;
    int ia = 0;
    int ib = 0;
    while (ia<list1.Count && ib < list2.Count)
    {
        iMinDist = Math.Min(iMinDist, Math.Abs(list1[ia] - list2[ib]));
        if (list1[ia] < list2[ib])
        {
            ++ia;
        }
        else if (list1[ia] > list2[ib])
        {
            ++ib;
        }
        else return 0;
    }
    return iMinDist;
}

--> 0 < (x-q*a)*n + (y-q*b)*m < a*m + b*n = g
However, this contradicts the statement that a*m + b*n = g is the lowest such number that can be written in this form.

I cound not understand the above line .. can you please more specific ?

1. Create a B+ Tree from List1, where each leaf is different file(As the list is very large, and can't loaded to whole list to memory at once).
2. For each element in List2, seach it from B+ tree(which is of List1).

T = O(M*Log(N)(of base k) + N*Log(N)(of base k).

N: Number of elements in List1.
M: Number of elements in List2.
k: B+ Tree is k-way tree.

To make you clear stupid is called to comments and not to him.