Re: [algogeeks] pointer and array
@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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] pallindrome
take a look at this: www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/ -- 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: You can see it like this. When we create an array then 'a' points to the whole array not just the first element so it returns the size of the whole array. when you pass the array though by default in c it is pass by value but as you are passing the address of the array so it acts like pass by reference. So the formal parameter acts as a pointer when you pass the address of the array to it. And you know that the size of a pointer is always equal to the size of int. On Sun, Jul 25, 2010 at 12:31 AM, tarak mehta wrote: > void hell(int arr[]); > main() > { >int arr[]={1,2,3,4,5}; > > >hell(arr); > } > void hell(int arr[]) > { > printf("%d",sizeof(arr)/sizeof(*arr)); > } > even this gives 1 !! > @manjunath ur idea seems correct..but could u plz elaborate a bit > > > > On Sat, Jul 24, 2010 at 10:51 PM, Manjunath Manohar < > manjunath.n...@gmail.com> wrote: > >> >> >> when arrays are passed as arguments to a function,the starting address of >> the array is passed like a pointer, >> thus sizeof(arr)=2..thus 2/2=1..this is the precise reason for always >> specifying the column length in the definition of function when functions >> have arrays as one of the arguments.. >> >> Hope i made any sense.. :) >> >> -- >> 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. >> > > -- > 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. > -- regards Apoorve Mohan -- 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] pallindrome
Its a repeated question. Please check the archives for your answer. Anurag Sharma On Sat, Jul 24, 2010 at 11:34 PM, dreamer < igolalal...@gmail.com> wrote: > please tell me how to find longest pallindrome in a string in linear > time > > -- > 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. > > -- 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
@Rahil: you are correctthanks On 24 July 2010 18:33, rahul patil wrote: > 1> convert the BST into a sorted doubly linklist.(increasing order) It > will take O(n) time. > > 2> Now find two nodes in a link list whose sum is k(given no) > > to find sum in linklist. take two pointers ptr1= head ptr2=tail of > linlist. > > now find sum of ptr1->data + ptr2-> data > > while(ptr1->data < ptr2-> data){ > if ((ptr1->data + ptr2-> data )>k) > ptr2= ptr2->prev; >else if ((ptr1->data + ptr2-> data ) ptr1= ptr1->next; > else if ((ptr1->data + ptr2-> data ) == k){ > print_data_of_ptr1_and_ptr2; > ptr2= ptr2->prev; > ptr1= ptr1->next; >} > } > > > the 2nd step will take O(n) time.No added space complexity > > > > > > > > On Jul 24, 9:29 am, Priyanka Chatterjee 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 > > > India > > >http://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. > > -- Thanks & Regards, Priyanka Chatterjee Final Year Undergraduate Student, Computer Science & Engineering, National Institute Of Technology,Durgapur India http://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.
[algogeeks] algorithm
You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream (in sorted order) in O(1) time. Eg: 0 1 2 3 4 Right FIND MEDIAN returns 2 as median Now input is -2 -4 So Stream = 0 1 2 3 -2 -2 -4 Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1 -- 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] 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
hmm. thnxx for the case On Sat, Jul 24, 2010 at 3:17 PM, Algoose chase wrote: > > @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 > 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 (i> if((num<=a[i])||(num<=a[j])||num<(a[i]+b[j])) >> return 0; >> if(num==(a[i]+b[j])) >> return 1; >> if(num>a[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 wrote: >> >>> 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 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.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.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. >> > > -- > 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. > -- 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: Abstract computer
I assume that loop(0) skips the body of the loop. 1. If given m > 0, this code sets m = m - 1. If given m = 0, it leaves m = 0. k = 0; loop(m) { m = k; k++; } 2. If given m >= n, this code sets m = m - n. If given m < n, it sets m = 0. loop(n) { k = 0; loop(m) { m = k; k++; } } This is algorithm 1 as the body of a loop(n) statement. 3. I'm still working on division. Back to you later. Dave On Jul 24, 11:45 am, BALARUKESH wrote: > You have an abstract computer, so just forget everything you know > about computers, this one only does what I'm about to tell you it > does. You can use as many variables as you need, there are no > negative > numbers, all numbers are integers. You do not know the size of the > integers, they could be infinitely large, so you can't count on > truncating at any point. There are NO comparisons allowed, no if > statements or anything like that. There are only four operations you > can do on a variable. > 1) You can set a variable to 0. > 2) You can set a variable = another variable. > 3) You can increment a variable (only by 1), and it's a post > increment. > 4) You can loop. So, if you were to say loop(v1) and v1 = 10, your > loop would execute 10 times, but the value in v1 wouldn't change so > the first line in the loop can change value of v1 without changing > the > number of times you loop. > You need to do 3 things. > 1) Write a function that decrements by 1. > 2) Write a function that subtracts one variable from another. > 3) Write a function that divides one variable by another. > 4) See if you can implement all 3 using at most 4 variables. Meaning, > you're not making function calls now, you're making macros. And at > most you can have 4 variables. The restriction really only applies to > divide, the other 2 are easy to do with 4 vars or less. Division on > the other hand is dependent on the other 2 functions, so, if subtract > requires 3 variables, then divide only has 1 variable left unchanged > after a call to subtract. Basically, just make your function calls to > decrement and subtract so you pass your vars in by reference, and you > can't declare any new variables in a function, what you pass in is > all > it gets. -- 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
void hell(int arr[]); main() { int arr[]={1,2,3,4,5}; hell(arr); } void hell(int arr[]) { printf("%d",sizeof(arr)/sizeof(*arr)); } even this gives 1 !! @manjunath ur idea seems correct..but could u plz elaborate a bit On Sat, Jul 24, 2010 at 10:51 PM, Manjunath Manohar < manjunath.n...@gmail.com> wrote: > > > when arrays are passed as arguments to a function,the starting address of > the array is passed like a pointer, > thus sizeof(arr)=2..thus 2/2=1..this is the precise reason for always > specifying the column length in the definition of function when functions > have arrays as one of the arguments.. > > Hope i made any sense.. :) > > -- > 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. > -- 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] sort
You are given a doubly link list and out of some nodes of this doubly linked list, some other doubly link list emerge and from some of these emerging doubly linked list, more doubly link list emerge. You have to write a quick algo that merges all these doubly linked list into a singly linked list -- 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] memory allocation
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.
[algogeeks] pallindrome
please tell me how to find longest pallindrome in a string in linear time -- 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
when arrays are passed as arguments to a function,the starting address of the array is passed like a pointer, thus sizeof(arr)=2..thus 2/2=1..this is the precise reason for always specifying the column length in the definition of function when functions have arrays as one of the arguments.. Hope i made any sense.. :) -- 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] Abstract computer
You have an abstract computer, so just forget everything you know about computers, this one only does what I'm about to tell you it does. You can use as many variables as you need, there are no negative numbers, all numbers are integers. You do not know the size of the integers, they could be infinitely large, so you can't count on truncating at any point. There are NO comparisons allowed, no if statements or anything like that. There are only four operations you can do on a variable. 1) You can set a variable to 0. 2) You can set a variable = another variable. 3) You can increment a variable (only by 1), and it's a post increment. 4) You can loop. So, if you were to say loop(v1) and v1 = 10, your loop would execute 10 times, but the value in v1 wouldn't change so the first line in the loop can change value of v1 without changing the number of times you loop. You need to do 3 things. 1) Write a function that decrements by 1. 2) Write a function that subtracts one variable from another. 3) Write a function that divides one variable by another. 4) See if you can implement all 3 using at most 4 variables. Meaning, you're not making function calls now, you're making macros. And at most you can have 4 variables. The restriction really only applies to divide, the other 2 are easy to do with 4 vars or less. Division on the other hand is dependent on the other 2 functions, so, if subtract requires 3 variables, then divide only has 1 variable left unchanged after a call to subtract. Basically, just make your function calls to decrement and subtract so you pass your vars in by reference, and you can't declare any new variables in a function, what you pass in is all it gets. -- 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
int ClearHighestBitSet (unsigned int n) { double x; int exp; x = frexp((double)n, &exp); return n ^ (1 << (exp-1)) } To see how it works, look up the standard C++ function frexp. Dave On Jul 23, 10:15 am, Tech Id wrote: > Write a C function that unsets the leftmost set bit of an integer in > less than order (n) > n here is 32 (bit-length of an integer) > Hint: do some bit-tricks -- 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: interview microsoft............
this is a recursive problem, the moment it says that there are n lists, it becomes recursive, the solution i have given can be made generic even though the sample is for 3 if total number of elements in a list is m i.e. 2 power k //function to merge two lists L1S//represents start of list 1 L2S//represents start of list 2 L1E//end of list 1(may not be needed) L2E//endof List L1C//number of elements treated as single element in list 1 L2C//number of elements treated as single element in list 2 for (int pass=1; pass<=k;pass++) { passS1= L1E-pass*L1C; passS2=L2S; for (int swapCount=1;swapCount<=pass;swapCount++) { swap(a[passS1], L1C, a[passS2],L2C); passS1 +=L1C; passS2 +=L2C; } } this is generic for two lists //function to merge n lists for (int merge=1; merge<=n;merge++) { bstart=m*merge; bend= bstart+m; b=&a[bstart]; mergeTwo(a, astart, aend, aele,b, bstart, bend, bele); aele++; } this can be improved to merge two lists in parallel Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Thu, Jul 22, 2010 at 10:37 PM, Tech Id wrote: > > In the final position, element at > arr[0] remains at arr[0] > arr[1] comes at arr[3] > arr[2] comes at arr[6] > arr[n] comes at arr[3n-3] position > So element at k goes at 3k, if 1 <= k < n > > arr[n] comes at arr[1] > arr[n+1] comes at arr[4] > arr[n+2] comes ar arr[7] > arr[2n-1] comes ar arr[3n-2] > So element at k goes at (k-n)*3+1, if n <= k < 2n > > arr[2n] comes at arr[2] > arr[2n+1] comes at arr[5] > arr[2n+2] comes at arr[8] > arr[3n-1] remains at arr[3n-1] > So element at k goes at (k-2n)*3+2, if 2n <= k < 3n-1 > > So, we can have a function req_pos which will return the required > position for a number if its current position is given. > int req_pos (int k, int n) { >if (k < n) { >return 3*k; >} >if (k < 2n) { >return (k-n)*3+1; >} >return (k-2n)*3+2; > } > > int k=1; > for (int i=0; i<3n-1;i++) { >int new_k = req_pos (k); >swap (arr, k , new_k); >k = new_k; > } > > The above loop runs 3n times, which is sufficient to cover all the > numbers. > Only problem is that if k becomes equal to any previous value already > covered, then it will fall into a loop and swap already swapped > integers. > If someone can prove that this will not happen, then we have an O(n) > in-place solution. > > For n=10, k will have values like: > 1, 3, 9, 27, 23, 11, 4, 12, 7, 21, 5, 15, > > Yoo-hoo... seems like it works! > Please comment. > > > > On Jul 22, 7:02 pm, Ashish Goel wrote: > > 123456789 > > then interchange middle one of 123 and 456 > > 12 43 56 789 > > now exchange in pairs except first and last i.e. 24 ->42, 35->53 > > 1 42 53 6 789 > > now treat 14 as single number, 25 as single number ans 36 as single > number > > and again apply this logic > > 14257 36 89 > > 14 725 836 9 > > > > need time to program this, a bit busy... > > > > done :) > > > > Best Regards > > Ashish Goel > > "Think positive and find fuel in failure" > > +919985813081 > > +919966006652 > > > > On Thu, Jul 22, 2010 at 5:58 PM, UMESH KUMAR >wrote: > > > > > > > > > Qn:-in the given array elements > > > a1a2a3a4..anb1b2b3b4...bnc1c2c3c4cn > > > without take a extra memory how to merge just like? > > > > > a1b1c1a2b2c2a3b3c3anbncn > > > > > -- > > > 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. > > -- > 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. > > -- 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
@jalaj your code will not work for list having negative numbers. A: 8, 9, 12, 14 (Sorted) B: -5, -4, 1, 10 (Sorted) num=3 Regards, Shafi On Sat, Jul 24, 2010 at 3:17 PM, Algoose chase wrote: > > @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 > 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 (i> if((num<=a[i])||(num<=a[j])||num<(a[i]+b[j])) >> return 0; >> if(num==(a[i]+b[j])) >> return 1; >> if(num>a[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 >> wrote: >>> >>> 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 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.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.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. > > -- > 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. > -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: BST
1> convert the BST into a sorted doubly linklist.(increasing order) It will take O(n) time. 2> Now find two nodes in a link list whose sum is k(given no) to find sum in linklist. take two pointers ptr1= head ptr2=tail of linlist. now find sum of ptr1->data + ptr2-> data while(ptr1->data < ptr2-> data){ if ((ptr1->data + ptr2-> data )>k) ptr2= ptr2->prev; else if ((ptr1->data + ptr2-> data )next; else if ((ptr1->data + ptr2-> data ) == k){ print_data_of_ptr1_and_ptr2; ptr2= ptr2->prev; ptr1= ptr1->next; } } the 2nd step will take O(n) time.No added space complexity On Jul 24, 9:29 am, Priyanka Chatterjee 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 > > India > >http://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
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.
Re: [algogeeks] pointer and array
sizeof(arr) is 4.. o.e the number of elements in the array size of *arr is the size of any normal pointer i.e 4(in case of 32-bit compilers) so the answer is 1 On Sat, Jul 24, 2010 at 9:52 AM, ravi gupta wrote: > > > On Sat, Jul 24, 2010 at 9:40 AM, tarak mehta wrote: > >> int arr[]={1,2,3,4}; >> k=sizeof(arr)/sizeof(*arr); >> value of k=4; >> >> however >> >> >> void hell(int arr[]); >> main() >> { >>int arr[]={1,2,3,4}; >>hell(arr); >> } >> void hell(int arr[]) >> { >> printf("%d",sizeof(arr)/sizeof(*arr)); >> } >> >> >> output of hell() is 1. why??? >> >> -- >> 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. >> >> When array is passed as an argument, only a pointer to the first element > of the array is passed. Therefore the parameter int arr[] in void hell(int > arr[]) is just a pointer, hence the result . > I hope it answers your query. > > -- > 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. > -- 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] 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
@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 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 (i if((num<=a[i])||(num<=a[j])||num<(a[i]+b[j])) > return 0; > if(num==(a[i]+b[j])) > return 1; > if(num>a[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 wrote: > >> 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 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.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.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. > -- 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: random clicks
the problem statement doesn't seem to be true. there's no surety that you can see all the questions within a certain no. of clicks.. it all depends on the randomness of the algorithm that picks the random question. somebody correct me if i'm wrong. On Jul 22, 5:39 pm, akash wrote: > A website has n questions. If you're shown one random question per > click, prove that it takes O(n log n) clicks on avg to see all > questions. > > How should I approach this problem. This sounds easy but till now I am > not able to get any headway. Any help is appreciated. 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.
[algogeeks] Re: unset leftmost bit
#include ; main() { int input,output; int temp; int counter=0; printf("\nEnter the number: "); scanf("%d", &input); temp=input; while(temp) { counter++; temp>>=1; } printf("\n[debug] the length of the binary no. is : %d", counter); output = input^(1<<(counter-1)); printf("\nThe number after unsetting the leftmost bit: %d", output); printf("\n"); } On Jul 23, 8:15 pm, Tech Id wrote: > Write a C function that unsets the leftmost set bit of an integer in > less than order (n) > n here is 32 (bit-length of an integer) > Hint: do some bit-tricks -- 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
this algo sets all bits to zero Debajyoti refer http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Sat, Jul 24, 2010 at 10:20 AM, Debajyoti Sarma wrote: > for(i=sizeof(int)*8-1;i>=0;i--) > { > if((number>>i)&1) > { > number=number^(1< break; > } > } > > -- > 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. > > -- 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.