Re: [algogeeks] I am new to CPP STL please help
strcmp is for C-style strings. Use in-built compare function of C++ strings ( http://www.cplusplus.com/reference/string/string/compare/ ), or why not simply '==' operator. -- Prakhar Jain IIIT Allahabad B.Tech IT 4th Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@gmail.com On Thu, May 9, 2013 at 9:40 PM, Nishant Pandey nishant.bits.me...@gmail.com wrote: This is my code snippet #include iostream.h #include string #include set #include map #include vector #include sstream #include cctype using namespace std; void work() { mapstring, int name_age; mapint,string index_name; mapint,string index_name_temp; std::map int, string ::iterator it; name_age[abc] = 12; name_age[pqr] = 1; name_age[stu] = 13; index_name[0] = abc; index_name[1] = pqr; index_name[2] = stu; cout name_age[abc] endl; cout index_name[1]; name_age.erase(abc); index_name_temp[0] = abc'; for ( it = index_name.begin(); it != index_name.end(); ++it ) { cout (*it).second ; } In this i have deleted key abc first from hash table name_age in the next hash table index_namei have abc as value i want to erase the abc entry from index_name table too, The idea is to first iterate on hash_map index_name when found abc delete the entry from index_name but how to compare abc in index_name map. as we cant do if (strcmp((*it).second, abc) ==0 ) in this , how do i do the comparision please help } -- 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. -- 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.
Re: [algogeeks] how does this code achieve SIGSEGV
You are initialising random memory address with 0, which OS doesn't allow. On 12/17/12, Shubham Sandeep s.shubhamsand...@gmail.com wrote: how does this code achieve SIGSEGV code: *p;main(){*p=0;} -- Regards, SHUBHAM SANDEEP IT 3rd yr. NIT ALD. -- -- -- Prakhar Jain IIIT Allahabad B.Tech IT 4th Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@gmail.com --
Re: [algogeeks] Flipkart test
Firstly, there is a written test in which there are 30 MCQs and 2 coding questions. MCQs cover all major topics such as algorithms,data structures, OS, DBMS, C. Coding questions has to be done to get place in Interviews. Otherwise, 1 coding question done correctly and efficiently, with good performance in MCQs can also give u a chance. Then, there are 2-3 round of face-to-face interviews which only concentrate on algorithm designing. No OS. No DBMS.( I mean no Technical rounds are there ) Last Interview is HR one which has few HR ques such as What is team work...?,etc. and 2-3 puzzles. On 10/9/12, Manish Patidar manishpatidar...@gmail.com wrote: NO DUDE Thank you, Have a great day !! * With Regards, * * Manish Patidar.* On Tue, Oct 9, 2012 at 9:47 AM, Avinash Mishra mishra.avinas...@gmail.comwrote: Hello any one have idea about Flipkart recruitment process for SDE1. Please guide me what to prepare. Thanks -- regard's Avinash -- 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. -- -- Prakhar Jain IIIT Allahabad B.Tech IT 4th Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@gmail.com -- 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] Inversion problem
You can use either Merge sort or BIT(refer TopCoder tutorial). -- Prakhar Jain IIIT Allahabad B.Tech IT 3rd Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@gmail.com On Sun, Jul 8, 2012 at 11:31 AM, Navin Kumar algorithm.i...@gmail.comwrote: Let A[n] be an array of n distinct number. If ij and A[i] A[j] then the pair (i , j) is called inversion of A. Give an algorithm that determines the total number of inversions in O(nlogn) time. -- 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/-/o7L4RLyUMuQJ. 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] flipkart question
Label 3 of the faces with 0 and other 3 faces with 6. -- Prakhar Jain IIIT Allahabad B.Tech IT 3rd Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@gmail.com On Sat, Jul 7, 2012 at 12:52 AM, Hraday Sharma hradaysha...@gmail.comwrote: You are given 2 dice. Both are fair. One of the dice has no numbers printed on it. You have to label the unmarked dice such that when both the dice are thrown, the sum on the faces is evenly distributed between 1 and 12 . -- 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/-/uXBWN7DSu_gJ. 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] Find peak element in log(n)
The idea behind this O(log n) Divide conquer algorithm is they assumed that element before the first element and after the last element is -infinite. So, they can they always pick the locally rising element ;since, even if the array continues to increase in that half, the last element can be the peak element. So, the peak element is always there in the array even if it is sorted in any order. -- Prakhar Jain IIIT Allahabad B.Tech IT 3rd Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@gmail.com On Sun, Jun 24, 2012 at 2:26 PM, adarsh kumar algog...@gmail.com wrote: ahh yes, as prakhar says, if the array is bitonic, my approach will work for O(log n). On Sun, Jun 24, 2012 at 1:57 AM, Prakhar Jain jprakha...@gmail.comwrote: I think it can't be done in O(log n) as per given problem constraints. It can be done in O(log n) if additional information that array is bitonic is given. -- Prakhar Jain IIIT Allahabad B.Tech IT 3rd Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@gmail.com On Sun, Jun 24, 2012 at 1:45 AM, Sourabh Singh singhsourab...@gmail.comwrote: @adarsh kumar are u sure it's worst case will be O (log n) ?? i think iff array is fully sorted O(n) will be required to say NO such element present On Sat, Jun 23, 2012 at 1:11 PM, adarsh kumar algog...@gmail.com wrote: This is a variation of binary search, the difference being that we have to search for an element that is greater than its immediate left one and lesser than its immediate right one. Just implement binary search with these additional constraints, thereby giving O(log n). In case of any difficulty/error, let me know. On Sun, Jun 24, 2012 at 1:27 AM, Hassan Monfared hmonfa...@gmail.com wrote: Given an array of integers find a peak element of array in log(n) time. for example if A={3,4,6,5,10} then peak element is 6 ( 65 64 ). Regards. -- 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/-/AQI6ahWgyOIJ. 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. -- 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. -- 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] Find peak element in log(n)
I think it can't be done in O(log n) as per given problem constraints. It can be done in O(log n) if additional information that array is bitonic is given. -- Prakhar Jain IIIT Allahabad B.Tech IT 3rd Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@gmail.com On Sun, Jun 24, 2012 at 1:45 AM, Sourabh Singh singhsourab...@gmail.comwrote: @adarsh kumar are u sure it's worst case will be O (log n) ?? i think iff array is fully sorted O(n) will be required to say NO such element present On Sat, Jun 23, 2012 at 1:11 PM, adarsh kumar algog...@gmail.com wrote: This is a variation of binary search, the difference being that we have to search for an element that is greater than its immediate left one and lesser than its immediate right one. Just implement binary search with these additional constraints, thereby giving O(log n). In case of any difficulty/error, let me know. On Sun, Jun 24, 2012 at 1:27 AM, Hassan Monfared hmonfa...@gmail.com wrote: Given an array of integers find a peak element of array in log(n) time. for example if A={3,4,6,5,10} then peak element is 6 ( 65 64 ). Regards. -- 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/-/AQI6ahWgyOIJ. 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. -- 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.
[algogeeks] Suggestion needed
Hello everyone, Please anyone suggest that what books,sites,etc. should be preffered while preparing for topics such as networking, dbms, os, aptitude for placements. Any advice would be helpful! (Sorry for posting not related to group) Thanks. -- Prakhar Jain IIIT Allahabad B.Tech IT 3rd Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@gmail.com -- 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: Power(n^n)
Typo in this problem statement. K is not less than or equal to 1000. Only N=1000. K can be as big as 1000^1000,i.e. 1000 digits. -- Prakhar Jain IIIT Allahabad B.Tech IT 3rd Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@gmail.com On Tue, Jun 12, 2012 at 12:27 PM, hary rathor harry.rat...@gmail.comwrote: there would no problem of rang if K^(1/N)==N -- 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] If any one have algorithms for interviews by adnan aziz ebook... Please mail ...
@abhishek...Plz share the link here.Thanks -- Prakhar Jain IIIT Allahabad B.Tech IT 3rd Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@gmail.com On Wed, Jun 6, 2012 at 5:32 PM, amrit harry dabbcomput...@gmail.com wrote: @abhishek pls send link me too... thanks. On Mon, Jun 4, 2012 at 5:54 PM, Abhishek Sharma abhi120...@gmail.comwrote: mailing you the link for same On Mon, Jun 4, 2012 at 1:31 AM, Dhaval Moliya moliyadha...@gmail.comwrote: If any one have algorithms for interviews by adnan aziz ebook... Please mail ... Thanks -- 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. -- Abhishek Sharma Under-Graduate Student, PEC University of Technology -- 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. -- Thanks Regards Amritpal singh -- 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.
[algogeeks] Allocating memory of size 0
Hi everyone, Someone plz explain why this C code works fine as memory allocated is of 0 size... main() { int *p=malloc(0); *p=2566; printf(%d\n,*p); getchar(); } -- Prakhar Jain IIIT Allahabad B.Tech IT 3rd Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@gmail.com -- 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] MODULUS
Why you expect it should work...? the constant you assigned to mod is not within int range declare it as long long mod = 100283LL; and it would work. On Tue, Feb 21, 2012 at 8:10 PM, Anurag Gupta anurag.gupta...@gmail.comwrote: how can we take mod by a very large number for example 100283 int mod = 100283; ans % mod is not working Please Help -- 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. -- -- Prakhar Jain IIIT Allahabad B.Tech IT 3rd Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@gmail.com -- 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] determining if frequency is greater than n/2
But in this post, we don't have prior information about what can be possible majority element. According to my question, we know that either x is the majority element or there is no majority element. Can we use that information to reduce complexity to O(log n)..??? -- 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.
[algogeeks] determining if frequency is greater than n/2
Hello everyone, suppose we have an array of size n and a number, say x, and we have to determine whether the number x is present in the array more then n/2 times or not? can we have an O(log n) algo for determining it..?..pls help...!!! -- -- Prakhar Jain IIIT Allahabad B.Tech IT 3rd Year Mob no: +91 9454992196 E-mail: rit2009...@iiita.ac.in jprakha...@gmail.com -- 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] Finding the mode in a set of integers
If m thinking right, That works if mode occurs =n/2 times in the array Best, Prakhar Jain http://web.iiit.ac.in/~prakharjain/ On Wed, Apr 14, 2010 at 8:12 PM, sharad kumar aryansmit3...@gmail.comwrote: can we make use of majority VOTE ALGORITHM? On Wed, Apr 14, 2010 at 4:14 PM, Gauri gauri...@gmail.com wrote: Say If I have an array of 1,000 32-bit integers .And one of the value is occuring 501 number of times or more in the array. Can someone help me devise an efficient algorithm for the same ? Thanks Regards Gauri -- 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] Implement a queue using a stack
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/ 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 . 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] Implement a queue using a stack
A better version exists where amortized order is (1) for both opreations Best, Prakhar Jain http://web.iiit.ac.in/~prakharjain/ 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/ 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 . 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.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] Implement a queue using a stack
on an avg... say if you insert 10 elemets n remove 10. you consume O(20) Best, Prakhar Jain http://web.iiit.ac.in/~prakharjain/ On Mon, Mar 22, 2010 at 7:39 PM, vikrant singh vikrantsing...@gmail.comwrote: Can u xplain what amortized means? On Mon, Mar 22, 2010 at 7:32 PM, Prakhar Jain prakh...@gmail.com wrote: A better version exists where amortized order is (1) for both opreations Best, Prakhar Jain http://web.iiit.ac.in/~prakharjain/http://web.iiit.ac.in/%7Eprakharjain/ 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/ 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 . 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.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. -- Vikrant Singh -- 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] Kth element in BST without static/global variable or function argument
Do an iterative inorder traversal and stop at k ? Best, Prakhar Jain http://web.iiit.ac.in/~prakharjain/ On Thu, Dec 10, 2009 at 7:38 AM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: You can maintain the size. or it can be computed in at worst linear time. In first method, the only difference is that it will make the kth smallest element the root of the tree. When in 2nd method it goes to left, in first method it will also go to left but rotate the tree right. Rohit Saraf Sophomore Computer Science and Engineering IIT Bombay On Wed, Dec 9, 2009 at 9:45 PM, Vikram Sridar vikramsridar...@gmail.comwrote: read augmenting data structures (chapter 14 i think) in Introduction in Algorithms by Corman.. if an extra attribute is added to each of the nodes storing the number of elements in the sub tree rooted at the node, this can be done easily.. the extra is neither global or static(as it is created n destroyed with each node).. -- 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.
[algogeeks] Re: Spell Checker
Its not onyl about searching for the word. How would you propose alternates ? Prakhar On Fri, Jul 31, 2009 at 9:42 AM, Arun N arunn3...@gmail.com wrote: I think we can use a trie and search, is the word there in trie but still trie eats memory . Arun, On Thu, Jul 30, 2009 at 1:45 PM, Prakhar Jain prakh...@gmail.com wrote: Hi, How would you design a dictionary so that you can make a spell checker ? You would have to suggest alternates... Best, Prakhar -- Potential is not what U have, its what U think U have!!! It is better to worn out than rust. --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Spell Checker
Alternatives as in alternate spelling suggestions Prakhar On Fri, Jul 31, 2009 at 7:03 PM, Vikram Sridar vikramsridar...@gmail.comwrote: Alternatives?? what way?? In terms of implementation or providing some other functionalities?? --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Spell Checker
Hi, How would you design a dictionary so that you can make a spell checker ? You would have to suggest alternates... Best, Prakhar --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
Re: Fwd: [algogeeks] Re: Binary search
I would call search() not binsearch() search() find any index and then iterates sequentially till the highest index. Prakhar On Wed, Mar 4, 2009 at 4:27 PM, Kapil navka...@gmail.com wrote: @Prakhar how would you ensure that this is highest index On Mar 1, 3:05 pm, Prakhar Jain prakh...@gmail.com wrote: I guess the Soln given is O(n) Much better can be achieved through binary serach O(nlogn) int binsearch(int a[],int start,int end,int key) { int mid=(start+end)/2; if(start==end a[mid]!=key) return -1; if(a[mid]key) end=mid; else if(a[mid]key) start=mid; else return mid; } int search(int a[],int key,int n) { int p=binsearch(a,0,n,key) if(p=0) while(a[p]==key) p++; return p-1; } On Sun, Mar 1, 2009 at 3:14 PM, Miroslav Balaz gpsla...@googlemail.com wrote: cout ((int)((int*)upperbound(a,a+5,k)-a))/4-1; 2009/3/1 sharad kumar aryansmit3...@gmail.com #includeiostream.h int main() { int a[5]={3,3,3,6,7}; int k; cink; int i=0,j=1,c=0; for(;i5;i++) { if(a[j-1]!=a[i] a[i]!=k) j++; else c=i; } coutc; return 0; } On Sun, Mar 1, 2009 at 9:50 AM, sharad kumar aryansmit3...@gmail.com wrote: hi, does the above solution need any time complexity and space complexity in specifific. idont understand use binary search On Sun, Mar 1, 2009 at 12:13 AM, jaanu jaanu.cher...@gmail.com wrote: Given a sorted arrays of N integers, possibly with duplicates, write a function that returns the highest index of an element X in that array if found or -1 otherwise.(use Binary search) -- Prakhar -- Prakhar --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
Re: Fwd: [algogeeks] Re: Binary search
no the order is log(n) On Wed, Mar 4, 2009 at 4:45 PM, sharad kumar aryansmit3...@gmail.com wrote: but commplexity is O(n2) rite??wat about my solution?? On Wed, Mar 4, 2009 at 4:32 PM, Prakhar Jain prakh...@gmail.com wrote: I would call search() not binsearch() search() find any index and then iterates sequentially till the highest index. Prakhar On Wed, Mar 4, 2009 at 4:27 PM, Kapil navka...@gmail.com wrote: @Prakhar how would you ensure that this is highest index On Mar 1, 3:05 pm, Prakhar Jain prakh...@gmail.com wrote: I guess the Soln given is O(n) Much better can be achieved through binary serach O(nlogn) int binsearch(int a[],int start,int end,int key) { int mid=(start+end)/2; if(start==end a[mid]!=key) return -1; if(a[mid]key) end=mid; else if(a[mid]key) start=mid; else return mid; } int search(int a[],int key,int n) { int p=binsearch(a,0,n,key) if(p=0) while(a[p]==key) p++; return p-1; } On Sun, Mar 1, 2009 at 3:14 PM, Miroslav Balaz gpsla...@googlemail.com wrote: cout ((int)((int*)upperbound(a,a+5,k)-a))/4-1; 2009/3/1 sharad kumar aryansmit3...@gmail.com #includeiostream.h int main() { int a[5]={3,3,3,6,7}; int k; cink; int i=0,j=1,c=0; for(;i5;i++) { if(a[j-1]!=a[i] a[i]!=k) j++; else c=i; } coutc; return 0; } On Sun, Mar 1, 2009 at 9:50 AM, sharad kumar aryansmit3...@gmail.com wrote: hi, does the above solution need any time complexity and space complexity in specifific. idont understand use binary search On Sun, Mar 1, 2009 at 12:13 AM, jaanu jaanu.cher...@gmail.com wrote: Given a sorted arrays of N integers, possibly with duplicates, write a function that returns the highest index of an element X in that array if found or -1 otherwise.(use Binary search) -- Prakhar -- Prakhar -- Prakhar --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Binary search
hmm.. worst case will be O(n). m not sure but i think avg case would be logn + k ( now if k approx logn ( kn) where k is the number of times an element can repeat itself the order remains same) now if k is large, no of different elements is v low, many times unsucc search will happen which is logn rigrous analysis has to be done. Anyways my second soltn is definitly O(logn) where u chk the highest number instead of mid. On Wed, Mar 4, 2009 at 7:43 PM, sharad kumar aryansmit3...@gmail.com wrote: ya boss rite.but according to asymptotic analysis the solutin shld be O(n);rite?? On Wed, Mar 4, 2009 at 6:48 PM, Prakhar Jain prakh...@gmail.com wrote: see its log(n) + k where k=the number of duplicates of the element being searched. For log(n), you can continue till your high comes on the element u desire and not low. On Wed, Mar 4, 2009 at 6:45 PM, sharad kumar aryansmit3...@gmail.com wrote: search() find any index and then iterates sequentially till the highest index how is this logn On Wed, Mar 4, 2009 at 6:44 PM, sharad kumar aryansmit3...@gmail.com wrote: ya rite On Wed, Mar 4, 2009 at 5:31 PM, Prunthaban pruntha...@gmail.com wrote: @sharad - Your solution is O(n) Miroslav's solution is O(logn). And what are you doing with the 'j' variable in your solution? Why not simply use a[i] == k then c = i. That is what eventually your solution is doing and it is O(n). On Mar 4, 4:32 pm, sharad kumar aryansmit3...@gmail.com wrote: pls tell wats difference btwn increasing and non decresing sorted array.question clearly tells n sorted array... On Wed, Mar 4, 2009 at 4:55 PM, Miroslav Balaz gpsla...@googlemail.comwrote: of course, you cannot assume that array is in ascending order, it is in non-decreasing order however not in ascending and you should swap order here :(a[mid+1] key||mid==high) 2009/3/4 Kapil navka...@gmail.com just fixing a bug what if you write bin_search as this //assumption array is in ascending order binsearch(high, low, key, a) begin if low high return -1 mid = (high+low)/2 if a[mid] = key And (a[mid+1] key||mid==high) return mid if a[mid] = key low = mid+1 else high = mid - 1 return binsearch(high,low,key,a) end On Mar 4, 3:46 pm, Kapil navka...@gmail.com wrote: what if you write bin_search as this //assumption array is in ascending order binsearch(high, low, key, a) begin if low high return -1 mid = (high+low)/2 if a[mid] = key And a[mid+1] key return mid if a[mid] = key low = mid+1 else high = mid - 1 return binsearch(high,low,key,a) end -- Prakhar -- Prakhar --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
Fwd: [algogeeks] Re: Binary search
I guess the Soln given is O(n) Much better can be achieved through binary serach O(nlogn) int binsearch(int a[],int start,int end,int key) { int mid=(start+end)/2; if(start==end a[mid]!=key) return -1; if(a[mid]key) end=mid; else if(a[mid]key) start=mid; else return mid; } int search(int a[],int key,int n) { int p=binsearch(a,0,n,key) if(p=0) while(a[p]==key) p++; return p-1; } On Sun, Mar 1, 2009 at 3:14 PM, Miroslav Balaz gpsla...@googlemail.com wrote: cout ((int)((int*)upperbound(a,a+5,k)-a))/4-1; 2009/3/1 sharad kumar aryansmit3...@gmail.com #includeiostream.h int main() { int a[5]={3,3,3,6,7}; int k; cink; int i=0,j=1,c=0; for(;i5;i++) { if(a[j-1]!=a[i] a[i]!=k) j++; else c=i; } coutc; return 0; } On Sun, Mar 1, 2009 at 9:50 AM, sharad kumar aryansmit3...@gmail.com wrote: hi, does the above solution need any time complexity and space complexity in specifific. idont understand use binary search On Sun, Mar 1, 2009 at 12:13 AM, jaanu jaanu.cher...@gmail.com wrote: Given a sorted arrays of N integers, possibly with duplicates, write a function that returns the highest index of an element X in that array if found or -1 otherwise.(use Binary search) -- Prakhar --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---