RE: [algogeeks] MS Question: WAP to find files in a
directory/subdirectories MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit The question is to implement without use of any library Sent from my Windows Phone From: atul anand Sent: 03-06-2012 11:19 To: algogeeks@googlegroups.com Subject: Re: [algogeeks] MS Question: WAP to find files in a directory/subdirectories i wrote this program in college labbut used shell script to simulate ls -r functionality. now to do in c or java .. we only need to knw about the libraries to use. On 6/3/12, Ashish Goel ashg...@gmail.com wrote: ls-r implementation needed... Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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] amazon interview questions
can be done with O(n^2) time complexity.. can it be done with O(n) complexity ??? On 6/3/12, utsav sharma utsav.sharm...@gmail.com wrote: given a string tell wether it is valid or not. string is valid if there is no substring which have the same substring following it. these strings are not valid:- stringstring,geek123123rt, abcadabcad,strngstingstrngsting -- 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: Rectangle area
@payel : you have mentioned sum of square of diagonal of rectangle.. but as you can see that 29 can't be the sum of square of diagonal of any rectangle.. because for a rectangle both diagonal would be equal... so sum shoud be 2 * diagonal^2... please explain your que.. On Sun, Jun 3, 2012 at 1:28 AM, Dave dave_and_da...@juno.com wrote: @Payel: Fermat's theorem on the sum of two squares applies. It says that an odd prime p can be written as the sum of two perfect squares if and only if p is congruent to 1 (mod 4). See http://en.wikipedia.org/wiki/Proofs_of_Fermat's_theorem_on_sums_of_two_squares. Thus, since 29 is congruent to 1 (mod 4), it can be written as the sum of two squares, as you have demonstrated. But, e.g., 7, 11, and 19 cannot be written as the sum of two perfect squares. Code follows: int PrimeIsSumOfTwoSquares(int p) { return (p 3) == 1; } Dave On Saturday, June 2, 2012 2:31:43 PM UTC-5, payel roy wrote: How do you verify whether sides of rectangular area are integer number If square of diagonal of a rectangular area is prime? Ex : Let's say square of a diagonal is : 2 2 = 1^2 + 1^2 [where 1,1 are the sides of the rectangular area] square of a diagonal is : 29 29 = 5^2 + 2^2. -- 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/-/wVxBh-kN-LoJ. 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 and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, India Mobile No: +91-8798049298, +91-9424738542 patlerahulku...@gmail.com rahulkumarpa...@yahoo.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: Rectangle area
sorry got the que... ignore my last reply.. thanks On Sun, Jun 3, 2012 at 9:49 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @payel : you have mentioned sum of square of diagonal of rectangle.. but as you can see that 29 can't be the sum of square of diagonal of any rectangle.. because for a rectangle both diagonal would be equal... so sum shoud be 2 * diagonal^2... please explain your que.. On Sun, Jun 3, 2012 at 1:28 AM, Dave dave_and_da...@juno.com wrote: @Payel: Fermat's theorem on the sum of two squares applies. It says that an odd prime p can be written as the sum of two perfect squares if and only if p is congruent to 1 (mod 4). See http://en.wikipedia.org/wiki/Proofs_of_Fermat's_theorem_on_sums_of_two_squares. Thus, since 29 is congruent to 1 (mod 4), it can be written as the sum of two squares, as you have demonstrated. But, e.g., 7, 11, and 19 cannot be written as the sum of two perfect squares. Code follows: int PrimeIsSumOfTwoSquares(int p) { return (p 3) == 1; } Dave On Saturday, June 2, 2012 2:31:43 PM UTC-5, payel roy wrote: How do you verify whether sides of rectangular area are integer number If square of diagonal of a rectangular area is prime? Ex : Let's say square of a diagonal is : 2 2 = 1^2 + 1^2 [where 1,1 are the sides of the rectangular area] square of a diagonal is : 29 29 = 5^2 + 2^2. -- 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/-/wVxBh-kN-LoJ. 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 and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, India Mobile No: +91-8798049298, +91-9424738542 patlerahulku...@gmail.com rahulkumarpa...@yahoo.com -- Thanks and Regards: Rahul Kumar Patle M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, India Mobile No: +91-8798049298, +91-9424738542 patlerahulku...@gmail.com rahulkumarpa...@yahoo.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.
[algogeeks] Matrix Minimum Path Sum
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/-/3JeyGNqWbs8J. 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] MS: searching problem......help me out...
We have given a list 14 6 7 15 8 9 we have to find 15 in (log n ) times. -- *Thanks and Regards,* Abhinav Kumar Gupta **abhinav@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] MS: searching problem......help me out...
Hi, I have found two url which contain answer of your question some extent. 42bits.wordpress.com/2010/04/17/find-kth-minimum-in-a-unsorted-array/ http://www.medwelljournals.com/fulltext/?doi=rjasci.2011.70.75 On Sun, Jun 3, 2012 at 8:31 PM, abhinav gupta abhinav@gmail.com wrote: We have given a list 14 6 7 15 8 9 we have to find 15 in (log n ) times. -- *Thanks and Regards,* Abhinav Kumar Gupta **abhinav@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. -- 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] Re: amazon interview questions
So any string with two same characters is not valid?? for example : GEEK has E followed by E. So GEEK is also invalid? On Jun 3, 1:49 pm, Hassan Monfared hmonfa...@gmail.com wrote: bool IsValid(string s) { for(int len=0;lens.len/2;len++) { int start1=0,start2=len+1; while(start2s.size()) { for(int i=0;ilen start2+is.size() s[start1+i]=s[start2+i];i++); if(i==len) return false; //not valid start1++; start2++; } } return true; // valid } On Sun, Jun 3, 2012 at 12:52 PM, atul anand atul.87fri...@gmail.com wrote: can be done with O(n^2) time complexity.. can it be done with O(n) complexity ??? On 6/3/12, utsav sharma utsav.sharm...@gmail.com wrote: given a string tell wether it is valid or not. string is valid if there is no substring which have the same substring following it. these strings are not valid:- stringstring,geek123123rt, abcadabcad,strngstingstrngsting -- 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] MS: searching problem......help me out...
@abhinav: if you want to search just 15 in log(n) time then you can use the concept of heap tree.. apply one round of heapification (not for all elements but just one time it will be complete in log(n) times), and you will need to swap elements but when you got element 15 you can stop.. although space complexity has increased... you will need one redundant array to use heap operation so that finally you will have original array as it is... Thanks and Regards: Rahul Kumar Patle On Sun, Jun 3, 2012 at 8:31 PM, abhinav gupta abhinav@gmail.com wrote: We have given a list 14 6 7 15 8 9 we have to find 15 in (log n ) times. -- *Thanks and Regards,* Abhinav Kumar Gupta **abhinav@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. -- 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] MS: searching problem......help me out...
@Rahul: but for heapify, i need to build heap tree first from the list. which will cost linear traversal of the elements, that will cost O(n). but i need to search it in O(log n) or polylogrithmic complexity of (log n) i.e. (log^2 n). On Sun, Jun 3, 2012 at 8:55 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @abhinav: if you want to search just 15 in log(n) time then you can use the concept of heap tree.. apply one round of heapification (not for all elements but just one time it will be complete in log(n) times), and you will need to swap elements but when you got element 15 you can stop.. although space complexity has increased... you will need one redundant array to use heap operation so that finally you will have original array as it is... Thanks and Regards: Rahul Kumar Patle On Sun, Jun 3, 2012 at 8:31 PM, abhinav gupta abhinav@gmail.comwrote: We have given a list 14 6 7 15 8 9 we have to find 15 in (log n ) times. -- *Thanks and Regards,* Abhinav Kumar Gupta **abhinav@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. -- 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. -- ++ *Technical Skill is the mastery of complexity, while Creativity is the master of presence of mind. ** * - Morihei Ueshiba ++ *Thanks and Regards,* Abhinav Kumar Gupta *M. Tech. (Software Engineering)* Motilal Nehru National Institute of Technology Allahabad(UP)-211004 +919628358065 abhinav@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] MS: searching problem......help me out...
@ Abhishek : Link that you have provided is for kth min element in the unsorted array, but here i dont know the given value is of at what min position. On Sun, Jun 3, 2012 at 9:06 AM, abhinav gupta abhinav@gmail.com wrote: @Rahul: but for heapify, i need to build heap tree first from the list. which will cost linear traversal of the elements, that will cost O(n). but i need to search it in O(log n) or polylogrithmic complexity of (log n) i.e. (log^2 n). On Sun, Jun 3, 2012 at 8:55 AM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @abhinav: if you want to search just 15 in log(n) time then you can use the concept of heap tree.. apply one round of heapification (not for all elements but just one time it will be complete in log(n) times), and you will need to swap elements but when you got element 15 you can stop.. although space complexity has increased... you will need one redundant array to use heap operation so that finally you will have original array as it is... Thanks and Regards: Rahul Kumar Patle On Sun, Jun 3, 2012 at 8:31 PM, abhinav gupta abhinav@gmail.comwrote: We have given a list 14 6 7 15 8 9 we have to find 15 in (log n ) times. -- *Thanks and Regards,* Abhinav Kumar Gupta **abhinav@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. -- 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. -- ++ *Technical Skill is the mastery of complexity, while Creativity is the master of presence of mind. ** * - Morihei Ueshiba ++ *Thanks and Regards,* Abhinav Kumar Gupta *M. Tech. (Software Engineering)* Motilal Nehru National Institute of Technology Allahabad(UP)-211004 +919628358065 abhinav@gmail.com -- ++ *Technical Skill is the mastery of complexity, while Creativity is the master of presence of mind. ** * - Morihei Ueshiba ++ *Thanks and Regards,* Abhinav Kumar Gupta *M. Tech. (Software Engineering)* Motilal Nehru National Institute of Technology Allahabad(UP)-211004 +919628358065 abhinav@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] MS: searching problem......help me out...
Hi Rahul, In the below url,They have mentioned the parallel searching. it means divide array than search element from two point. i.e number of element is {48,23,10,32,5} search 32. divide array [0-2] and [3-4] range... traverse the array from p[0] and p [3]... till half of the loop. I hope we can search element into log n ( need to look more just giving .2 cents) http://www.medwelljournals.com/fulltext/?doi=rjasci.2011.70.75 On Sun, Jun 3, 2012 at 9:25 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @abhinav: if you want to search just 15 in log(n) time then you can use the concept of heap tree.. apply one round of heapification (not for all elements but just one time it will be complete in log(n) times), and you will need to swap elements but when you got element 15 you can stop.. although space complexity has increased... you will need one redundant array to use heap operation so that finally you will have original array as it is... Thanks and Regards: Rahul Kumar Patle On Sun, Jun 3, 2012 at 8:31 PM, abhinav gupta abhinav@gmail.comwrote: We have given a list 14 6 7 15 8 9 we have to find 15 in (log n ) times. -- *Thanks and Regards,* Abhinav Kumar Gupta **abhinav@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. -- 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] Imp MAQ Softwares :
Anyone knows about the procedure for MAQ softwares when they evaluate using elitmus ?? about the written test ?? -- 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] Re: MS: searching problem......help me out...
Finding a given element in an unsorted list in less than O(n) time (with a normal RAM model of computation) is easy to prove impossible. On Jun 3, 11:01 am, abhinav gupta abhinav@gmail.com wrote: We have given a list 14 6 7 15 8 9 we have to find 15 in (log n ) times. -- *Thanks and Regards,* Abhinav Kumar Gupta **abhinav@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: amazon interview questions
yes it's not valid On Sun, Jun 3, 2012 at 5:36 PM, anugrah anugrah.agra...@gmail.com wrote: So any string with two same characters is not valid?? for example : GEEK has E followed by E. So GEEK is also invalid? On Jun 3, 1:49 pm, Hassan Monfared hmonfa...@gmail.com wrote: bool IsValid(string s) { for(int len=0;lens.len/2;len++) { int start1=0,start2=len+1; while(start2s.size()) { for(int i=0;ilen start2+is.size() s[start1+i]=s[start2+i];i++); if(i==len) return false; //not valid start1++; start2++; } } return true; // valid } On Sun, Jun 3, 2012 at 12:52 PM, atul anand atul.87fri...@gmail.com wrote: can be done with O(n^2) time complexity.. can it be done with O(n) complexity ??? On 6/3/12, utsav sharma utsav.sharm...@gmail.com wrote: given a string tell wether it is valid or not. string is valid if there is no substring which have the same substring following it. these strings are not valid:- stringstring,geek123123rt, abcadabcad,strngstingstrngsting -- 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.
[algogeeks] If any one have algorithms for interviews by adnan aziz ebook... Please mail ...
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.
[algogeeks] Simple Question ,Find Error
main() { static char names[5][20]={pascal,ada,cobol,fortran,perl}; int i; char *t; t=names[3]; names[3]=names[4]; names[4]=t; for (i=0;i=4;i++) printf(%s,names[i]); } -- 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: MS: searching problem......help me out...
finding element in an unsorted array and with no relationship b/w the elements would have lower bound - omega(n) ..boczz you need to traverse whole array atleast once to find that element. so obv it cant be done in log(n) time..think abt it. On Sun, Jun 3, 2012 at 11:23 PM, Gene gene.ress...@gmail.com wrote: Finding a given element in an unsorted list in less than O(n) time (with a normal RAM model of computation) is easy to prove impossible. On Jun 3, 11:01 am, abhinav gupta abhinav@gmail.com wrote: We have given a list 14 6 7 15 8 9 we have to find 15 in (log n ) times. -- *Thanks and Regards,* Abhinav Kumar Gupta **abhinav@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. -- 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] Matrix Minimum Path Sum
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.com wrote: 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/-/3JeyGNqWbs8J. 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: amazon interview questions
@hassan :- it will not work for many strings as you are checking from the mid of strings. try out ababcdef,aabc. @atul :- it should be done in O(n). On Sun, Jun 3, 2012 at 11:54 PM, Hassan Monfared hmonfa...@gmail.comwrote: yes it's not valid On Sun, Jun 3, 2012 at 5:36 PM, anugrah anugrah.agra...@gmail.com wrote: So any string with two same characters is not valid?? for example : GEEK has E followed by E. So GEEK is also invalid? On Jun 3, 1:49 pm, Hassan Monfared hmonfa...@gmail.com wrote: bool IsValid(string s) { for(int len=0;lens.len/2;len++) { int start1=0,start2=len+1; while(start2s.size()) { for(int i=0;ilen start2+is.size() s[start1+i]=s[start2+i];i++); if(i==len) return false; //not valid start1++; start2++; } } return true; // valid } On Sun, Jun 3, 2012 at 12:52 PM, atul anand atul.87fri...@gmail.com wrote: can be done with O(n^2) time complexity.. can it be done with O(n) complexity ??? On 6/3/12, utsav sharma utsav.sharm...@gmail.com wrote: given a string tell wether it is valid or not. string is valid if there is no substring which have the same substring following it. these strings are not valid:- stringstring,geek123123rt, abcadabcad,strngstingstrngsting -- 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] Re: amazon interview questions
@jeevitesh :- yes i am also thinking of suffix tree, but i am facing problem in implementing it. did you implement it ?? On Mon, Jun 4, 2012 at 9:11 AM, utsav sharma utsav.sharm...@gmail.comwrote: @hassan :- it will not work for many strings as you are checking from the mid of strings. try out ababcdef,aabc. @atul :- it should be done in O(n). On Sun, Jun 3, 2012 at 11:54 PM, Hassan Monfared hmonfa...@gmail.comwrote: yes it's not valid On Sun, Jun 3, 2012 at 5:36 PM, anugrah anugrah.agra...@gmail.comwrote: So any string with two same characters is not valid?? for example : GEEK has E followed by E. So GEEK is also invalid? On Jun 3, 1:49 pm, Hassan Monfared hmonfa...@gmail.com wrote: bool IsValid(string s) { for(int len=0;lens.len/2;len++) { int start1=0,start2=len+1; while(start2s.size()) { for(int i=0;ilen start2+is.size() s[start1+i]=s[start2+i];i++); if(i==len) return false; //not valid start1++; start2++; } } return true; // valid } On Sun, Jun 3, 2012 at 12:52 PM, atul anand atul.87fri...@gmail.com wrote: can be done with O(n^2) time complexity.. can it be done with O(n) complexity ??? On 6/3/12, utsav sharma utsav.sharm...@gmail.com wrote: given a string tell wether it is valid or not. string is valid if there is no substring which have the same substring following it. these strings are not valid:- stringstring,geek123123rt, abcadabcad,strngstingstrngsting -- 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] Simple Question ,Find Error
you can't assign value into names[i]! On Mon, Jun 4, 2012 at 3:12 AM, mahendra sengar sengar.m...@gmail.comwrote: main() { static char names[5][20]={pascal,ada,cobol,fortran,perl}; int i; char *t; t=names[3]; names[3]=names[4]; names[4]=t; for (i=0;i=4;i++) printf(%s,names[i]); } -- 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: amazon interview questions
utsav: It works fine, I did little bug fixing on boundaries as here goes : bool IsValid(string s) { for(int len=1;len=s.size()/2;len++) { int start1=0,start2=len; while(start2s.size()) { int i=0; for(;ilen start2+is.size() s[start1+i]==s[start2+i];i++); if(i=len) return false; //not valid start1++; start2++; } } return true; // valid } It works for both input you provided. :) On Mon, Jun 4, 2012 at 8:14 AM, utsav sharma utsav.sharm...@gmail.comwrote: @jeevitesh :- yes i am also thinking of suffix tree, but i am facing problem in implementing it. did you implement it ?? On Mon, Jun 4, 2012 at 9:11 AM, utsav sharma utsav.sharm...@gmail.comwrote: @hassan :- it will not work for many strings as you are checking from the mid of strings. try out ababcdef,aabc. @atul :- it should be done in O(n). On Sun, Jun 3, 2012 at 11:54 PM, Hassan Monfared hmonfa...@gmail.comwrote: yes it's not valid On Sun, Jun 3, 2012 at 5:36 PM, anugrah anugrah.agra...@gmail.comwrote: So any string with two same characters is not valid?? for example : GEEK has E followed by E. So GEEK is also invalid? On Jun 3, 1:49 pm, Hassan Monfared hmonfa...@gmail.com wrote: bool IsValid(string s) { for(int len=0;lens.len/2;len++) { int start1=0,start2=len+1; while(start2s.size()) { for(int i=0;ilen start2+is.size() s[start1+i]=s[start2+i];i++); if(i==len) return false; //not valid start1++; start2++; } } return true; // valid } On Sun, Jun 3, 2012 at 12:52 PM, atul anand atul.87fri...@gmail.com wrote: can be done with O(n^2) time complexity.. can it be done with O(n) complexity ??? On 6/3/12, utsav sharma utsav.sharm...@gmail.com wrote: given a string tell wether it is valid or not. string is valid if there is no substring which have the same substring following it. these strings are not valid:- stringstring,geek123123rt, abcadabcad,strngstingstrngsting -- 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. -- 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.