[algogeeks] Re: BST
@rahul how to convert bst ot doubly linked list. I m understanding the logic but not able to code give a pseudo code to understand. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: BST
@ above have it
node * bsttolist(node *root){
if(root==NULL) return NULL;
node *l=bsttolist(root-left);
node *r=bsttolist(root-right);
root-left=root;
root-right=root;
append(l,root);
append(l,r);
return l;
}
here append function merges two circular doubly linked lists , you can make
that on your own
On Sun, Jul 25, 2010 at 1:35 PM, Debajyoti Sarma
sarma.debajy...@gmail.comwrote:
@rahul
how to convert bst ot doubly linked list.
I m understanding the logic but not able to code
give a pseudo code to understand.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] memory allocation
for this you shld make your own malloc function and while allocating memry count++ and while freeing count-- if count!=0 then there is memory leak . On Sat, Jul 24, 2010 at 11:38 PM, dreamer igolalal...@gmail.com wrote: Write a code that will check whether the memory allotted to the program at the initial and the memory returned to the system is same or not. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST
It is simple to convert BST to sorted doubly link list
Just do inorder_traverse and add node into the linklist.
It is like following.
linklist_node *head=NULL;
mod_in_order(tree_node *root){
tree_node *temp;
temp=root;
if (root is a leaf node)
add_node_to_linklist(root); // instead of printing add
node
else {
if(root-left)
inorder(root-left);
add_node_to_linklist(root); // instead of printing add
node
if(temp-right)
inorder(root-right);
}
}
On Jul 25, 2:27 pm, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
@ above have it
node * bsttolist(node *root){
if(root==NULL) return NULL;
node *l=bsttolist(root-left);
node *r=bsttolist(root-right);
root-left=root;
root-right=root;
append(l,root);
append(l,r);
return l;
}
here append function merges two circular doubly linked lists , you can make
that on your own
On Sun, Jul 25, 2010 at 1:35 PM, Debajyoti Sarma
sarma.debajy...@gmail.comwrote:
@rahul
how to convert bst ot doubly linked list.
I m understanding the logic but not able to code
give a pseudo code to understand.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] pointer and array
@tarak mehta: if u wanna understand, try passing a char array to a function n do de same... On Sun, Jul 25, 2010 at 9:59 AM, Manjunath Manohar manjunath.n...@gmail.com wrote: @Apporve... yeah u r right :)sizeof ptr is always 2 in 16 bit compilers, i.e, the sizeof an address is 2.and the sizeof(int)=2..i.e sizeof(*arr)=2..hope u got it now.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: memory allocation
Create your own malloc() free() functions. when you allocate
memory, allocate a little bit extra memory to add a token of your
choosing. When free'ing the memory, check that the token is still
there. You are going to want to add the token to the beginning of the
memory, and not at the end for 2 reasons:
1. When free'ing, you don't know how much memory was allocated, so it
would be difficult to find the end of the memory.
2. If there was a buffer overflow error in the application, it would
likely overwrite your token if it were at the end.
The other thing to consider is that depending on your compiler flags,
memory allocations typically occur at word boundaries to help improve
speed. Therefore, it would be helpful for the token added to be a
boundary supported by your compiler.
It is still possible that if there is a buffer overflow error in your
application, the token can still be wiped out.
Below are some sample functions that could implement this algorithm.
I used the address of the memory allocated as my token. I take the
MAX between sizeof(void*) and sizeof(long long) to ensure that the
token size will be compatible with the alignment of most
architectures. However, you might want to tune this to work better
(or to work at all) for your architecture.
#define MAX(a,b) (a b ? a : b)
#define TOKEN_LEN MAX(sizeof(void*), sizeof(long long))
void *my_malloc(size_t size)
{
void *p = malloc(size + TOKEN_LEN);
if(p != NULL)
{
((void*)*p) = p;
p += TOKEN_LEN;
}
return p;
}
void *my_free(void *p)
{
if(p!=NULL)
{
p -= TOKEN_LEN;
if( ((void*)*p) != p )
// ERROR: Trying to free memory not allocated by
my_malloc() -OR- there was a buffer overflow error
else
free(p);
} else {
// ERROR: Trying to free NULL
}
}
On Jul 24, 2:08 pm, dreamer igolalal...@gmail.com
wrote:
Write a code that will check whether the memory allotted to the
program at the initial and the memory returned to the system is same
or not.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: unset leftmost bit
will this work... int x= 127; //in binary it is interpreted with MSB set to 0.. and all other bits to 1 temp=xinput; temp will have the MSB unset.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: unset leftmost bit
binary search with bitwise is excellent. It will guarantee searching in log32 = 5 lookups. Great! On Jul 24, 5:00 pm, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: we can use a binary search to search for the bit in O(logn) the search would look like this: we first compute n 0x (which is 16 1s and 16 0s) if the result is 0 then the left most 1 is in the 16 less significant bits else it is in the 16 more significant bits then we can continue this way for example if the result in the first step is zero the next step would be to compute n 0xFF00 to find whether the leftmost set bit is in the 8 less significant bits or not -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Find The Kth min in a binary search tree
int FindKthSmallest(TreePointer ptr){
int count=0;
if(ptr){
FindKthSmallest(ptr-leftchild);
count++;
FindKthSmallest(ptr-rightchild);
}
return count;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Bitwise Ternary operator
int cond (int x, int y, int z) {
return (x==0)*z + (x!=0)*y;
}
On Jul 21, 10:29 pm, BALARUKESH sbalarukesh1...@gmail.com wrote:
Ternary operator- x? y : z
Implement it in a function: int cond(int x, int y, int z); using only
~, !, ^, , +, |, , no if statements, or loops or anything else,
just those operators, and the function should correctly return y or z
based on the value of x. You may use constants, but only 8 bit
constants. You can cast all you want. You're not supposed to use extra
variables, but in the end, it won't really matter, using vars just
makes things cleaner.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Bitwise Ternary operator
This is impossible in C. The ternary operator as you've given it evaluates either y or z depending on the value of x. A C function call always evaluates all of its arguments. For example. int w, x = 1, y = 1, z = 1; w = x ? ++y : ++z; printf (%d %d %d\n, y, z); will print 1 2 1. If you subsitute, w = cond(x, ++y, ++z); for the ternary operator, you'll get 1 2 2. This may sound like a small thing, but conditional/lazy evaluation is what leads to the power of Turing completeness in a language. On Jul 21, 1:29 pm, BALARUKESH sbalarukesh1...@gmail.com wrote: Ternary operator- x? y : z Implement it in a function: int cond(int x, int y, int z); using only ~, !, ^, , +, |, , no if statements, or loops or anything else, just those operators, and the function should correctly return y or z based on the value of x. You may use constants, but only 8 bit constants. You can cast all you want. You're not supposed to use extra variables, but in the end, it won't really matter, using vars just makes things cleaner. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST
You'd know how to do this if you had a sorted array A, right? Start a
pointer at each end. Call the L and R.
L = 0;
R = length(A) - 1
while (L R) {
while (L R A[L] + A[R} k) --R;
if (A[L] + A[R} == k) return L, R;
++L;
}
return failed
Since you have a BST, just replace L and R with iterators that scan
from left to right and right to left through the tree. The ammortized
cost of an iterator call is O(1), and there are clearly O(n) calls,
where n = lengh(A).
The iterators can each contain a O(log n) stack, but you seem willing
to ignore log n stack space. You could get rid of the stacks by
threading the tree.
On Jul 24, 12:03 am, Priyanka Chatterjee dona.1...@gmail.com wrote:
Given a binary search tree of n nodes, find two nodes whose sum is equal to
a given number k in O(n) time and constant space.
(ignoring recursion stack space)
I have got O(nlogn) time , O(1) space and O(n) time, O(n) space. Please
help me out with O(n) time and O(1) space.
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
Indiahttp://priyanka-nit.blogspot.com/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: unset leftmost bit
@amir hossein... Can u pls elaborate on the binary search...i donot have that much of a knowledge about hexadecimal representation of numbers..kindly pls help me.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find The Kth min in a binary search tree
void kthsmallest(Tree *node,int k)
{
static int count=0;
if(node!=NULL count!=k)
{
kthsmallest(node-left);
printf(\nKth Smallest - - %d\n,node-data);
kthsmallest(node-right);
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Sub- Palindrome
given a string ..how to find a sub-palindrome of the maximum length in linear time...O(n)..kindly help.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] What is the size of such set?
For a full tree, I want to find a set A = {a1,a2,...,an},
for each ai(i=1,...n):
Union of every leaf nodes set of each ai is the leaf node set of the
root node.
Each leaf node set of ai and aj has no intersection.
For example:
For the following tree:
n0
/ \
n1n2
Such set would be :{n0} {n1,n2};
For such tree:
n0
/ \
n1 n2
/\ / \
n3 n4 n5 n6
Such set would be: {n0} {n1,n2},{n3,n4,n5,n6},{n1,n5,n6},{n3,n4,n2}
Therefore, I want to know how many such set would be for a full n-ary
tree.
Thanks.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] You have 2 arrays of integer. You have to write a function, which take an integer as input and returns bool. Example array 1 has {1,5,10} array 2 has {2,5,9}. Func(3) should return t
If arrays are sorted, Merge Array A and B then use the algorithm to find a
pair whose sum equals required number.
On 24 July 2010 18:49, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
hmm.
thnxx for the case
On Sat, Jul 24, 2010 at 3:17 PM, Algoose chase harishp...@gmail.comwrote:
@jalaj
TRY
A:16, 12, 10, 6 ,2
B:11, 10,7, 2, 1
num: 26
On Sat, Jul 24, 2010 at 5:13 AM, jalaj jaiswal jalaj.jaiswa...@gmail.com
wrote:
Take two pointers both at the start of each array...
i=0,j=0
let the size of sorted arrays be m and n
int func(int num,int m,int n){
int i=0,j=0;
while (imjn){
if((num=a[i])||(num=a[j])||num(a[i]+b[j]))
return 0;
if(num==(a[i]+b[j]))
return 1;
if(numa[i]+b[j]){
if(a[i]b[j]) j++;
else i++;
}
}
return 0;
}
O(m+n) complexity
Ps. i'm returning true if the number equals a[i]+b[j] and not just when
it equals a single element in any array
On Fri, Jul 23, 2010 at 9:22 AM, Shafi Ahmad shafi.ah...@gmail.comwrote:
Let argument of function Func is k.
Case 1: If at least on of the array is sorted (say array1) then.
For each number in array2, do
1. binary search for (k - array1[i]) in array1
2. if found
return true.
else
return false
case 2: Arrays are not sorted then
1. Sort one array and apply algo for case 1.
Time complexity will be sizeof(unsortedarray)log (sizeofsortedarray).
Regards,
Shafi
On Fri, Jul 23, 2010 at 12:01 AM, vijay auvija...@gmail.com wrote:
You have 2 arrays of integer. You have to write a function, which take
an integer as input and returns bool. Example array 1 has {1,5,10}
array 2 has {2,5,9}. Func(3) should return true, since 1 (from array
1) +2 (from array 2) =3 ( i.e summation of 2 numbers (1 from each
array) is equal to 3). Func(13) should return false
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Shafi Ahmad
The difficult we do immediately, the impossible takes a little
longerUS Army
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks and Regards,
N. Ravikanth
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
