TheGhost
BAN USERI found an approach, which has some constraints however:
1- Find an integer w such that, pow(INT_MAX, w) = c x (n-k).
2- Use, the RND() function w times, summing the results.
val = RND() + RND() + .. + RND(); (w times)
3- element_Index = val % (n-k);
4- return L' [element_Index]
Such that, L' is a list containing elements not present in the original list L.
In this approach, the probability of finding each element in L' is equal.(i.e- 1/(n-k))
@csguy:
ur approach is nice, except that, the median (assuming the constraint you've mentioned) is given by the min of the min-heap.
Moreover, the constraint should rather be:
Number of elements in Max-heap <= 1 + Number of elements in Min-heap.
Specifically, when the equality holds, the root of either Min/Max heap serves as the median.
void findOccurences(char *substr, char *str){
char *p = str;
int i, j, lenSubStr = strlen(substr), w =strlen(str);
j = 0;
while(j < w-lenSubStr+1){
printf("Starting search at:%s\n",p);
for(i=0;i<lenSubStr;i++){
if((char)p[i] != (char)substr[i]){
printf("break\n");
break;
}
}
if(i == lenSubStr)
printf("Match found at: %d\n",j);
p +=1;
++j;
}
}
O(n^2) Exhaustive search.
Prints multiple occurrences of any substring.
Okay, here's what the function for xor strings should be like:
But, it's behaving weird, I'm gonna take a break, in the meantime..if somebody can spot, the bug, well, bingo then !
char * xorStrings(char *str1, char *str2){
int i=0, n;
int lenCommon;
char *strShort, *strLong, *strXor;
strShort = (strlen(str1) > strlen(str2))?str2:str1;
strLong = (strlen(str1) > strlen(str2))?str1:str2;
i = 0;
lenCommon = strlen(strShort);
n = strlen(strLong);
strXor = (char*)malloc((size_t)sizeof(char) * (n+1));
n -= lenCommon;
while(lenCommon-- ){
strXor[i] = strLong[i] ^ strShort[i];
i++;
}
while(n--){
strXor[i] = strLong[i] ^ 0;
i++;
}
strXor[i] = '\0';
return strXor;
}
int main(){
char *p = "We";
char *w = p;
w[0] = 'H';
printf("%s", w);
return 0;
}
2,3. Run-Time error in minGW, since we are trying to modify:
char * str = "blah"; //which is equivalent to
const char * str = "blah";
However, note that:
const char * str = "blah";//is not equivalent to
const (char *) str = "blah";
Hope it helps.
@crdmp :
Shouldn't the code be:
Node* maxSubtree(Node* r) {
int max = -oo;
Node* maxNode = NULL;
f(r, &max, &maxNode);//Change
return maxNode;
}
int f(Node* r, int *max, Node** maxNode) {//Change
if(r==NULL) return 0;
int sum = f(r->left, max, maxNode) + f(r->right, max, maxNode) + r->data;
if(sum> *max) {//Change
*max = sum;//Change
*maxNode = r;
}
return sum;
}
Check the lines with the comment: "//Change"
- TheGhost February 01, 2012void printCommonNumbers(FILE* fp1,FILE* fp2){
int x,y;
fscanf(fp1,"%d",&x);
fscanf(fp2,"%d",&y);
while(!feof(fp1) || !feof(fp2)){
if(x<y)
fscanf(fp1,"%d",&x);
else if(x>y)
fscanf(fp2,"%d",&y);
else{
printf("%d ",x);
fscanf(fp1,"%d",&x);
fscanf(fp2,"%d",&y);
}
}
}
Assuming, the input files contain sorted numbers.
- TheGhost January 27, 2012The idea is imagining a Btree placed aside a real mirror.
Get the catch ?
left nodes seem right, right nodes seem left.
So, basically it's like, in the new BTree,
newTree->root = createNode(originalTreeRoot->value);
newTree->lChild = <yourMirrorTreeFunction>(originalTree->rChild);
newTree->rChild = <yourMirrorTreeFunction>(originalTree->lChild);
Now, apply this step recursively.
Hope that helps.
int count = 0;
treeNode * createNode(char val){
treeNode * node = malloc(sizeof(treeNode));
node->value = val;
node->lChild = NULL;
node->rChild = NULL;
return node;
}
//treeString is the pre-order representation of tree,i.e.-"NNLLL"
treeNode * makeTree(char * treeString, int *count){
treeNode * temp = NULL;
if(*(treeString + *count) != '\0'){
temp = createNode(*(treeString + *count));
if(*(treeString+ *count) == 'N'){
*count += 1;
temp->lChild = makeTree(treeString,count);
*count += 1;
temp->rChild = makeTree(treeString,count);
}
}
return temp;
}
So, the function is called as:
int main(){
char * treeString = "NNLLNNLLL";
treeNode * root = NULL;
root = makeTree(treeString,&count);
}
Lately I've been spending some time on designs. Here's a sample generic implementation, that develops upon standard Stack design:
Hope it helps.
- TheGhost November 10, 2013Further ideas: :)
Rather than having MinStack, derive Stack with a generic constraint.