Re: [algogeeks] Pointers Usage
http://geeksquiz.com/c-pointers-question-12/ On Sat, Jan 12, 2013 at 9:18 PM, Piyush Raman piyush2011...@gmail.comwrote: For simple reasons according to me: 1- It reduces overhead drastically,thus more efficient execution time is achieved. Consider a recursive function call having array parameters - func (int a[100][100], int b[100][100]).. Now instead if we use pointers- func(int **a, int **b), the overhead on the stack of the language decreases drastically and thus further reducing the execution time of the code!! 2- It allows dynamic memory storage. If you do not know the amount of memory needed, then using dynamic allocaton using pointer is the best way. Consider we have an array - arr[1000], but we actually need to use only 10,5, or even 2 sized array! This will lead to huge memory wastage.. instead we can do size_type *arr= new size_type[size]. thus this leads to more space efficient code and avoid chances of memory overflow. 3- Access to an entity via pointer is faster!! :P Hope this helps! On Thu, Jan 3, 2013 at 7:49 PM, Debabrata Das debabrata.barunhal...@gmail.com wrote: @ arun... 8 byte may be for 64 bit application or far pointer ... On Thu, Jan 3, 2013 at 6:29 PM, Arun Vishwanathan aaron.nar...@gmail.com wrote: @atul/shady: why is it that pointer takes 8 bytes ? So the takes a memory location whose value is the address of the element it points to. Why does the pointer value have to take 8 bytes? I am sorry if I am missing something silly here. -- -- -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Matrix Minimum Path Sum
http://www.geeksforgeeks.org/archives/14943 On Mon, Jun 4, 2012 at 7:57 PM, Decipher ankurseth...@gmail.com wrote: @Victor - Someone had asked this question from me !! He told me its from Project Euler Q-83. @Hassan - I think you are right. This question can be solved by Dijikstra's algo, if we consider the matrix elements as weights. On Monday, 4 June 2012 16:28:31 UTC+5:30, Hassan Monfared wrote: moving must be done in A* style On Mon, Jun 4, 2012 at 1:17 PM, atul anand atul.87fri...@gmail.comwrote: i dont think so dijistra will worh here..bcozz we cannot move diagonally ...but according to matrix this path can be considered. On Mon, Jun 4, 2012 at 1:39 PM, Hassan Monfared hmonfa...@gmail.comwrote: for non-negative values Dijkstra will solve the problem in ( O(N^2) ) and Floyd-Warshal is the solution for negative cells. ( O(N^3) ) On Mon, Jun 4, 2012 at 11:20 AM, atul anand atul.87fri...@gmail.comwrote: this recurrence wont work..ignore On Mon, Jun 4, 2012 at 8:55 AM, atul anand atul.87fri...@gmail.comwrote: find cumulative sum row[0] find cumulative sum of col[0] after this following recurrence will solve the problem. start from mat[1][1] mat[i][j]=mat[i][j]+min( mat[i][j-1] , mat[i-1][j] ) On Sun, Jun 3, 2012 at 7:30 PM, Decipher ankurseth...@gmail.comwrote: Q) In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297. *131* 673 *234* *103* *18* *201* *96* *342* 965 *150* 630 803 746 *422* *111* 537 699 497 *121* 956 805 732 524 *37* *331* Write an algorithm to find the same. Also, write an algorithm if the same matrix contains negative numbers (maybe negative cycle) and compare the space and time complexity of both. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/**msg/algogeeks/-/3JeyGNqWbs8Jhttps://groups.google.com/d/msg/algogeeks/-/3JeyGNqWbs8J . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@ **googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=enhttp://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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/l9UCuzmoZRMJ. To post to this group, send email to algogeeks@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 algogeeks@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: Dynamic programming question
http://www.geeksforgeeks.org/archives/14943 is a very similar problem. On Thu, Dec 15, 2011 at 1:12 PM, WgpShashank shashank7andr...@gmail.comwrote: @Azhar , also for 1st question u r trying Array DS will suffices. Its Standard Coin Change Problem , u need to solve subproblem 1st , store it in extra array to avoid recalculation , if u are able to produce the sum less given sum then u can use same approach to reach desired sum . it uses the memozation (DP) approach solve efficiently . hope it help. Thanks Shashank Mani CSE, BIT Mesra http://shashank7s.blogspot.com/ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/N3nEi3dNwR0J. To post to this group, send email to algogeeks@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 algogeeks@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] structure padding query
http://www.geeksforgeeks.org/archives/9705 On Fri, Nov 25, 2011 at 12:36 AM, rahul sharma rahul23111...@gmail.comwrote: struct abc { int g; float f; double gj; }; like in this int takes 4 bytes and we want align in 8 bytes so i wana know that whether the float should put with int as 4 bytes are there to complete 8 or float should be int+4 bytes padding and then store the float.. acc to o/p float is stores after int -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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: An Array Problem
It's a variation of next greater element problem ( http://www.geeksforgeeks.org/archives/8405). Instead of next greater element, this problem asks about next smaller element. On Wed, Nov 23, 2011 at 5:29 PM, Gene gene.ress...@gmail.com wrote: Thanks. Maybe I'm not reading correctly, but tech coder's algorithm doesn't mention anything about pairs, which are necessary to obtain O(n). This is what I meant by almost. In reverse order, you don't need the pairs. Its simpler. In a subroutine like yours, void find_smaller_to_right(int *a, int n) { int i, in, p, stk[n]; // C99 var length array for (i = n - 1; i = 0; i--) { in = a[i]; while (p 0 stk[p - 1] = in) p--; // pop a[i] = (p 0) ? stk[p - 1] : 0; stk[p++] = in; // push } } On Nov 23, 5:13 am, Ankur Garg ankurga...@gmail.com wrote: Solution given by tech coder is fine and is working .. I coded it and its working perfectly using stack On Wed, Nov 23, 2011 at 2:50 PM, Gene gene.ress...@gmail.com wrote: It's a nice problem, and this solution is almost right. Process the input in _reverse_ order, which means we'll also generate output in reverse order. The invariant is that the stack is a sorted list - highest value on top - of the strictly descending subsequence of elements seen so far in reverse. So when we get a new input, we want to search backward through the stack to find the first smaller element. This is handy however, because the new input also means that when we search past an element, it's too big to maintain the invariant, so it must be popped! We can both find the output value and update the stack at the same time: stack = empty for next input I in _reverse order_ while stack not empty and top of stack is = I pop and throw away top of stack if stack is empty, output is zero else output top of stack push I end Since each item is pushed and popped no more than once, this is O(n). Here's your example: #include stdio.h int main(void) { int in[] = { 1, 5, 7, 6, 3, 16, 29, 2, 7 }; int n = sizeof in / sizeof *in - 1; int out[100], stk[100], p = 0, i; for (i = n - 1; i = 0; i--) { while (p stk[p - 1] = in[i]) p--; out[i] = (p 0) ? stk[p - 1] : 0; stk[p++] = in[i]; } for (i = 0; i n; i++) printf( %d, out[i]); printf(\n); return 0; } On Nov 22, 2:20 pm, Aamir Khan ak4u2...@gmail.com wrote: On Tue, Nov 22, 2011 at 11:50 PM, tech coder techcoderonw...@gmail.com wrote: here is an O(n) approach using a stack. problem can be stated as find the 1st smaller element on the right. put the first element in stack. take next element suppose num if this number is less than elements stored in stack, pop those elements , for these pooped elements num will be the required number. put the the element (num) in stack. repeat this. at last the elements which are in next , they will have 0 (valaue) @techcoder : If the numbers are not in sorted order, What benefit the stack would provide ? So, are you storing the numbers in sorted order inside the stack ? I can think of this solution : Maintain a stack in which the elements will be stored in sorted order. Get a new element from array and lets call this number as m. Push m into the stack. Now, find all elements which are = (m-1) using binary search. Pop out all these elements and assign the value m in the output array. Elements remaining at the end will have the value 0. I am not sure about the complexity of this algorithm... On Wed, Nov 23, 2011 at 12:02 AM, Anup Ghatage ghat...@gmail.com wrote: I can't think of a better than O(n^2) solution for this.. Any one got anything better? On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta ankuj2...@gmail.com wrote: Input: A unsorted array of size n. Output: An array of size n. Relationship: elements of input array and output array have 1:1 correspondence. output[i] is equal to the input[j] (ji) which is smaller than input[i] and jth is nearest to ith ( i.e. first element which is smaller). If no such element exists for Input[i] then output[i]=0. Eg. Input: 1 5 7 6 3 16 29 2 7 Output: 0 3 6 3 2 2 2 0 0 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Anup Ghatage -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group,
Re: [algogeeks] Re: deep vs shallow copy
http://geeksforgeeks.org/forum/topic/deep-copy-vs-shallow-copy On Fri, Nov 18, 2011 at 12:58 PM, Gene gene.ress...@gmail.com wrote: The most extreme shallow copy is just copying a pointer to a large data structure like a graph or tree. Deep copy is copying the entire data structure and returning a new pointer. Here is a more common example: typedef struct list { struct list *next; void *data; } LIST_NODE; In practice you'd want to code these as loops instead of recursion. But this gives the idea. LIST_NODE *shallow_copy(LIST_NODE *lst) { return lst ? new_list_node(shallow_copy(lst-next), data) : NULL; } LIST_NODE *deep_copy(LIST_NODE *lst) { return lst ? new_list_node(deep_copy(lst-next), data_copy(data)) : NULL; } Where data_copy is assumed to copy its argument into fresh memory and return a poionter and new_list_node returns a freshly allocated node with given fields. On Nov 18, 6:33 am, rahul sharma rahul23111...@gmail.com wrote: plz give me xample of these two .as per from book m not able to get thesw clearly,...i have reda from wiki and got it but cant relate with these...plz differ b/w these two with xample..thnx in advance a shallow copy of an object copies all the member field values.this works well if the fields are values,but may not be what we want for fields that point to dynamically allocsted value.The pointer will be copied.But memory it point will not be copied. a deep cpy copies all fields,and makes copies of dynamically allocated memory pointed to by the fields.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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] Placement
http://geeksforgeeks.org/ On Tue, Nov 16, 2010 at 8:23 PM, Mukesh Kumar thakur mukeshraj8...@gmail.com wrote: try website:-.www.placementpapers.com indiabix.com On 11/15/10, Bittu B bittu.bitt...@gmail.com wrote: Plz suggest some links for placement aptitude and technical For companies like Microsoft , Amdocs, Infosys, Accenture etc -- 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. -- 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: Excellent Compilation of Interview Questions
http://geeksforgeeks.org/ On Sat, Sep 11, 2010 at 11:52 AM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: Thanks man for the site.Anybody having such info/any material please post it here.Thanks in advance On Sat, Sep 11, 2010 at 1:53 PM, bittu shashank7andr...@gmail.com wrote: thanks keep posting such type of material... regards Shashank -- 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 Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- 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.
Re: [algogeeks] Re: isbst
@Raj N It won't work for the tree like. your method would return true for the following tree. 13 / 12 \ 14 On Sat, Jul 3, 2010 at 3:45 AM, Raj N rajn...@gmail.com wrote: According to me perform inorder traversal and at every point store the current element in a temporary variable and check if the next element obtained is greater than temp otherwise return false int temp=-; int flag=1; void isBst(NODE *tree) { if (tree!=NULL) { isBst(tree-left); if (temptree-info) temp=tree-info; else { flag=0; return; } isBst(tree-right); } } Please correct me if I'm wrong On Fri, Jul 2, 2010 at 6:43 PM, sharad kumar sharad20073...@gmail.comwrote: i read that link ,i dont think that is very efficient,someone plzzz look at that soln n comment bcoz i m really confused in this isbst ques so plzzz -- 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. -- 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: rotation
Have you guys seen following? http://geeksforgeeks.org/?p=2838 http://geeksforgeeks.org/?p=2398 http://geeksforgeeks.org/?p=2878 On Sat, Jul 3, 2010 at 12:12 PM, Pramod Negi negi.1...@gmail.com wrote: I guess you want the following juggling algorithm http://www.cs.bell-labs.com/cm/cs/pearls/s02b.pdf On Fri, Jul 2, 2010 at 11:16 PM, Dave dave_and_da...@juno.com wrote: @Jalaj. The original poster said, P.S---do not give block reversal method for array rotation Dave On Jul 2, 10:54 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: reverse full array first then, reverse last k elemnts and initial n-k elements seperately this will do On Fri, Jul 2, 2010 at 8:34 PM, Ratnesh Thakur ratneshthaku...@gmail.comwrote: correction.. a[j]=a[j-1] instead of a[i]=a[i-1] On Fri, Jul 2, 2010 at 7:30 PM, Ratnesh Thakur ratneshthaku...@gmail.comwrote: i think this should work. for(i=1;i=k;i++) { var=a[n-1] for(j=n-1;j=1;j--) a[i]=a[i-1] a[0]=var } On Fri, Jul 2, 2010 at 5:36 PM, Saurabh Ahuja nsit.saur...@gmail.comwrote: a[0] = a[2] a[1] = a[3] a[2] = a[4] a[0] and a[1] has been changed a[3] = a[0] a[4] = a[1] so this solution would not work. On Fri, Jul 2, 2010 at 5:14 PM, Akash Gangil akashg1...@gmail.com wrote: wouldn't this work: for i in range(0,len) a[i] = a[(i+2)%5]; where len is the length of array On Sat, Jun 26, 2010 at 3:37 PM, sharad kumar sharad20073...@gmail.com wrote: i have to right rotate an array by k positions 1 2 3 4 5 for k=2 o/p shud be 3 4 5 1 2 P.S---do not give block reversal method for array rotation and soln must be inplace.plzz write ur logic also along with d code -- 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 algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Best Regards Akash Gangil -- 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 algogeeks%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 algogeeks%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 algogeeks%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- Hide quoted text - - Show quoted text - -- 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. -- 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: sort 0's 1's and 2's
http://geeksforgeeks.org/?p=8133 has the complete solution On Thu, Jul 1, 2010 at 5:33 AM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: in this case counting sort is inplace as how long the input array be ..the auxilary array will be of soze 3 only.. and counting sort is stable too On Thu, Jul 1, 2010 at 7:43 AM, Gene gene.ress...@gmail.com wrote: On Jun 30, 12:21 am, Sathaiah Dontula don.sat...@gmail.com wroe: @Gene, Your logic is specific to 0, 1 and 2. Let me change the problem, there are three different symbols in an array, separate them in O(n) with O(1) space. Thanks, Sathaiah Well, your problem was specific to 0, 1, and 2. Arbitrary symbols are no different. You just create a lookup table that maps the symbols to 0,1,2 and look them up as needed. In the code below I made the lookup table s myself, but you could easily do it with a O(n) preprocessing pass. #include stdio.h #define M 3 int idx(int *s, int ai) { int i = 0; for (i = 0; i M; i++) if (s[i] == ai) return i; return -1; } void sort(int *s, int *a, int n) { int i, j, c[M]; for (j = 0; j M; j++) c[j] = 0; for (i = 0; i n; i++) ++c[idx(s, a[i])]; for (i = j = 0; j M; j++) while (c[j]--) a[i++] = s[j]; } int main(void) { int i, s[] = {'a','b','c'}, a[] = { 'c','c','a','b','a','b','c','a','c'}; sort(s, a, sizeof a / sizeof a[0]); for (i = 0; i sizeof a / sizeof a[0]; i++) printf(%c , a[i]); printf(\n); return 0; } -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: isbst
http://geeksforgeeks.org/?p=3042 has all the approaches (right and wrong) for solving this. On Thu, Jul 1, 2010 at 4:43 AM, divya jain sweetdivya@gmail.com wrote: @ above here u r comparing node value with min and max only for eg if ur tree is 45 / \ 65 85 / 25 ur code will say that this is bst. bt it is not plzz correct me if i m wrong.. On 1 July 2010 16:17, CM Saikanth Varma saikanthva...@gmail.com wrote: Hi, The idea is like this: Isbst(node *t){ if(t==NULL){ return true; } if ( Isbst(t-left) Isbst(t-right) (maxValue(t-left) =(t-data) ) (minValue(t-right) = (t-data) ) return true; else return false; } I hope it makes sense :D On Thu, Jul 1, 2010 at 3:37 PM, vicky mehta...@gmail.com wrote: just do one thing print inorder. if sorted it is a BST On Jun 19, 2:57 pm, divya sweetdivya@gmail.com wrote: i have found the following code on net to check if the binarytreeis bst or not /* Returns true if a binarytreeis a binary searchtree. */ int isBST(struct node* node) { if (node==NULL) return(true); // false if the min of the left is than us if (node-left!=NULL minValue(node-left) node-data) return(false); // false if the max of the right is = than us if (node-right!=NULL maxValue(node-right) = node-data) return(false); // false if, recursively, the left or right is not a BST if (!isBST(node-left) || !isBST(node-right)) return(false); // passing all that, it's a BST return(true); } int minValue(struct node* node) { struct node* current = node; // loop down to find the leftmost leaf while (current-left != NULL) { current = current-left;} return(current-data); } and maxvalue also similarly returns right most vaslue oftree.. now i have a doubt that here v r comparing the node-data with only the min node nd max node.. shd nt we compare the node data with its left node and right node only. as it can b a case that node value is greater than min but less than its left node.. nd here we r nt checking that... plzz correct me if i m wrong... and is there any other efficient method to find isbst? -- 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. -- 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.
Re: [algogeeks] request
A collection of links: http://geeksforgeeks.org/?page_id=6028cat=Data+Structures+%26+Algorithms On Thu, Jun 17, 2010 at 8:33 AM, chinna thirupathi.thu...@gmail.com wrote: plz can u provide material -reg:design and analysis of algorithms. basics of algorithms and psudocode notation,time and space complexity's ..etc thank u -- 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.
Re: [algogeeks] max sum
See http://geeksforgeeks.org/?p=3133 for solution. On Fri, Jun 11, 2010 at 8:41 AM, divya sweetdivya@gmail.com wrote: Given an array all of whose elements are positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. Eg. i) 3 2 7 10 should return 13 (sum of 3 and 10) ii) 3 2 5 10 7 should return 15 (sum of 3, 5 and 7) -- 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.
Re: [algogeeks] Re: array question
The link http://geeksforgeeks.org/?p=1488 has many different solutions and implementation of hashing method. On Mon, Jun 7, 2010 at 12:59 AM, Raj N rajn...@gmail.com wrote: @Anand :Your approach will turn out very crude if elements are something like 1000, 2000 keeping an array i.e count[1000] is not feasible. I think souravsain's approach is better. On Mon, Jun 7, 2010 at 3:57 AM, Anand anandut2...@gmail.com wrote: Here is my approch which runs in O(n). http://codepad.org/d3pzYQtW http://codepad.org/d3pzYQtW On Sun, Jun 6, 2010 at 7:47 AM, divya jain sweetdivya@gmail.comwrote: output willl be 12 12 5 6 6 On 6 June 2010 18:27, souravsain souravs...@gmail.com wrote: @divya: Does your problem require the output to be sorted also? What will be the output required if inout is 12,5,6,12,6? Will it be 12,12,6,6,5 or 12,12,5,6,6,? Sain On Jun 6, 12:01 am, divya sweetdivya@gmail.com wrote: Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. So cant use a dictionary -- 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. -- 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. -- 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] k the smallest in BST without using static variable
@satwik See http://geeksforgeeks.org/?p=6358 for Morris Inorder traversal On Sat, May 15, 2010 at 9:44 PM, satwik krishna sathi...@gmail.com wrote: @Rohit Can u pass on thje link of morris inorder On 5/15/10, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: there is something called morris inorder traversal. credits to donald knuth On 5/15/10, kaushik sur kaushik@gmail.com wrote: Hi Friends I have encountered the question in sites - Given a Binary Search Tree, write a program to print the kth smallest element without using any static/global variable. You can't pass the value k to any function also. I have tried my hands using explicit stack for inorder and keeping a non-static count variable. I welcome any better solution, time and space efficient. Best Regards Kaushik Sur -- 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. -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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. -- 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] data structure and algorithm implementation
http://geeksforgeeks.org/ can be helpful. You can also find links to tutorials/articles http://geeksforgeeks.org/?page_id=6028 On Fri, May 21, 2010 at 3:57 AM, sharad kumar aryansmit3...@gmail.comwrote: @venky pls c www.topcoder.com/tc its gt tutorials,srm matches etc. On Fri, May 21, 2010 at 2:55 PM, venkat kumar svenkatkuma...@gmail.comwrote: i'm new to coding.it is difficult to implement algorithms and even standard data structures is there a sort of lab manual available and are there solutions to problems in uva,sphere etc etc websites kindly reply. 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- 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.
Re: [algogeeks] Finding the mode in a set of integers
Here are 3-4 methods to solve http://geeksforgeeks.org/?p=503 On Sat, Apr 17, 2010 at 5:45 AM, Ashim Kapoor ashimkap...@gmail.com wrote: are you referring to the lectures by Dr Naveen Garg ? Or are these lectures different? Please clarify. Thank you, Ashim. On Sat, Apr 17, 2010 at 5:43 AM, rahul rai raikra...@gmail.com wrote: On 4/16/10, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Just got another O(n) solution. Find the n/2 th largest element in the array using the Median of Medians Selection algorithm. =? takes O(n) That's It ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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. Work out the CDEEP Algorithms course lectures . It will give all basics -- 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. -- 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: Implement a queue using a stack
Here is code and explanation http://geeksforgeeks.org/?p=5009 On Sat, Apr 10, 2010 at 10:18 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: hmm... that can always be done ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Wed, Mar 24, 2010 at 6:24 PM, Dave dave_and_da...@juno.com wrote: Please post your results. I'd like to study your algorithm. On Mar 23, 11:15 pm, chitta koushik koushik.infin...@gmail.com wrote: yeah i understand that . still wanted to attempt writing a recursive reverse() stack operation. On Wed, Mar 24, 2010 at 9:21 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: Even when you are writing a recursive function.. you are not using one stack. One stack is yours. Other used for recursion. Making queue from a single stack = Making turing machine from CFG. -Rohit On Wed, Mar 24, 2010 at 9:18 AM, chitta koushik koushik.infin...@gmail.com wrote: Can we implement it using a single stack by writing a recursive reverse stack operation ? On Tue, Mar 23, 2010 at 10:18 AM, Sundeep Singh singh.sund...@gmail.comwrote: Thanks Dave, I didn't think about this... definitely better! Sundeep. On Mon, Mar 22, 2010 at 9:08 PM, Dave dave_and_da...@juno.com wrote: Better still. To enqueue: push onto stack A. For dequeuing: If stack B is empty, pop all items from stack A and push onto stack B. Then pop stack B. There is no need to push remaining items back to stack A. As every item passes through the queue, it is pushed onto stack A, then popped from stack A and pushed onto stack B, and finally popped from stack B. The time is roughly twice the time required for a direct implementation of a queue. There is room for a little optimization if both stacks are empty when enquing, as you can push the item directly onto stack B. Furthermore, when popping from stack A and pushing onto stack B, you don't need to push the last item popped, as it is the return value. Dave On Mar 22, 9:29 am, Sundeep Singh singh.sund...@gmail.com wrote: Hey Brian, Better still, for inserting in queue, just keep pushing onto the stack A. You need stack B only for dequeuing: for dequeuing, push all items into stack B, pop as many as you want from stack B and then push back all remaining items in stack A. Regards, Sundeep. On Mon, Mar 22, 2010 at 6:56 PM, Brian brianfo...@gmail.com wrote: How is it possible to implement a queue using a stack only? Interesting, but tricky... You need two stacks as Prakhar stated... In general, if you have Stack A and Stack B, you should keep all the items in stack A and then use stack B for processing. For example to insert an item: 1. Pop all the items from A and then push them into B (this should push the items into Stack B in reverse order) 2. Insert the new item into A 3. Pop all the items in B and push them back into A (again this will push them back into Stack B in reverse order) Running time should be O(1)+O(2n), which is O(n) for larger values of n - which is not good... To retrieve an item, pop the first item in stack A Hope this helps - Regards B On 3/22/2010 4:55 AM, Prakhar Jain wrote: By a do u mean a single stack ? Otherwise if you use 2 its v simple Best, Prakhar Jain http://web.iiit.ac.in/~prakharjain/http://web.iiit.ac.in/%7Eprakharjain/ http://web.iiit.ac.in/%7Eprakharjain/ http://web.iiit.ac.in/%7Eprakharjain/ On Mon, Mar 22, 2010 at 12:56 AM, Pushpesh Gupta pushpes...@gmail.comwrote: How is it possible to implement a queue using a stack only? -- 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 algogeeks%2bunsubscr...@googlegroups.com algogeeks%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 algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this
Re: [algogeeks] Coding Problems
Please go through the site http://geeksforgeeks.org/ I recently found the site. This is a great site as this provides well organized and well coded solutions for generally asked interview/programming questions Enjoy!! Dheeraj On Tue, Feb 2, 2010 at 9:11 AM, Ashudeep Sharma ashu00.sp...@gmail.comwrote: u can also try stackoverflow.com On Tue, Feb 2, 2010 at 9:38 PM, gaurav gupta 1989.gau...@googlemail.comwrote: try uva online judge On Tue, Feb 2, 2010 at 8:56 PM, vikas mehta mehta...@gmail.com wrote: i will recommend u usaco training gateway. it is awesome On Tue, Feb 2, 2010 at 2:54 AM, Neeraj Singh 17.neera...@gmail.comwrote: Hey fellas, I need to seek some advice from you all. I have recently developed strong interest in programming problems. So, What is the best place I should start practicing my skills. It would be great if the effort is rewarding as well. Thanks in advance. TY -- Neeraj Ted Turnerhttp://www.brainyquote.com/quotes/authors/t/ted_turner.html - Sports is like a war without the killing. -- 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. -- GAURAV GUPTA B.Tech IV Yr. , Department of Computer Science Engineering IT BHU , Varanasi Contacts Phone No: +91-99569-49491 e-mail : gaurav.gu...@acm.org gaurav.gupta.cs...@itbhu.ac.in -- 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. -- Ashudeep Sharma http://www.itbhu.ac.in/codefest/ -- 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.