SRB
BAN USER
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();
}
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;
}
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;
}
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;
}
#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;
}
}
}
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);
}
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).
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);
}
}
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).
- SRB September 24, 2011Above 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;
}
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.
Agree .. Q is not complete. Google never asked such silly Q.
- SRB January 30, 2013