@Viharri: You can use skip list. On Mon, Jun 4, 2012 at 3:30 PM, <[email protected]> wrote:
> Today's Topic Summary > > Group: http://groups.google.com/group/algogeeks/topics > > - MS Question: Delete a node in single linked list if it is less than > any of the successor nodes <#137b6f050d04b422_group_thread_0> [1 > Update] > - LINKED LIST QUESTION <#137b6f050d04b422_group_thread_1> [2 Updates] > - amazon interview questions <#137b6f050d04b422_group_thread_2> [6 > Updates] > - Matrix Minimum Path Sum <#137b6f050d04b422_group_thread_3> [6 > Updates] > - Simple Question ,Find Error <#137b6f050d04b422_group_thread_4> [2 > Updates] > - MS: searching problem......help me > out...<#137b6f050d04b422_group_thread_5>[8 Updates] > > MS Question: Delete a node in single linked list if it is less than any > of the successor > nodes<http://groups.google.com/group/algogeeks/t/521daf6fd96c3658> > > Amol Sharma <[email protected]> Jun 04 03:25PM +0530 > > here is the question ans solution with proper explanation > > http://www.geeksforgeeks.org/archives/11604 > > -- > > > Amol Sharma > Third Year Student > Computer Science and Engineering > MNNIT Allahabad > <http://gplus.to/amolsharma99> > <http://twitter.com/amolsharma99>< > http://in.linkedin.com/pub/amol-sharma/21/79b/507>< > http://www.simplyamol.blogspot.com/> > > > > > > > > > > LINKED LIST > QUESTION<http://groups.google.com/group/algogeeks/t/79ba6b42b42efa89> > > VIHARRI <[email protected]> Jun 04 02:30AM -0700 > > Hi we need find a node in linked list in O(logn). You can change the > list > as u like. > > > > > Amol Sharma <[email protected]> Jun 04 03:17PM +0530 > > not possible i suppose.. > -- > > > Amol Sharma > Third Year Student > Computer Science and Engineering > MNNIT Allahabad > <http://gplus.to/amolsharma99> > <http://twitter.com/amolsharma99>< > http://in.linkedin.com/pub/amol-sharma/21/79b/507>< > http://www.simplyamol.blogspot.com/> > > > > > > > > > > amazon interview > questions<http://groups.google.com/group/algogeeks/t/44a0ffd4a905543b> > > anugrah <[email protected]> Jun 03 06:06AM -0700 > > So any string with two same characters is not valid?? > > for example : > > GEEK has E followed by E. > > So GEEK is also invalid? > > > > > > Hassan Monfared <[email protected]> Jun 03 10:54PM +0430 > > yes it's not valid > > > > > > utsav sharma <[email protected]> Jun 04 09:11AM +0530 > > @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). > > > > > > > utsav sharma <[email protected]> Jun 04 09:14AM +0530 > > @jeevitesh :- yes i am also thinking of suffix tree, > but i am facing problem in implementing it. did you implement it ?? > > > > > > Hassan Monfared <[email protected]> Jun 04 10:20AM +0430 > > 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(start2<s.size()) > { > int i=0; > for(;i<len && start2+i<s.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. :) > > > > > > utsav sharma <[email protected]> Jun 04 02:50PM +0530 > > @hasan :-ohhh sorry, i didn't see the outer loop > yeah, it works but it is O(n^2), required solution is of O(n). > > > -- > Utsav Sharma, > NIT Allahabad > > > > Matrix Minimum Path > Sum<http://groups.google.com/group/algogeeks/t/49d777ef6d29fa32> > > Decipher <[email protected]> Jun 03 07:00AM -0700 > > 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. > > > > > Victor Manuel Grijalva Altamirano <[email protected]> Jun 03 > 03:46PM -0500 > > interesting problem... DP ??? where do you see this problem??? > > 2012/6/3 Decipher <[email protected]> > > > -- > Victor Manuel Grijalva Altamirano > Universidad Tecnologica de La Mixteca > > > > > atul anand <[email protected]> Jun 04 08:55AM +0530 > > 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] ) > > > > > > atul anand <[email protected]> Jun 04 12:20PM +0530 > > this recurrence wont work..ignore > > > > > > Hassan Monfared <[email protected]> Jun 04 12:39PM +0430 > > 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) ) > > > > > > > > atul anand <[email protected]> Jun 04 02:17PM +0530 > > i dont think so dijistra will worh here..bcozz we cannot move > diagonally > ...but according to matrix this path can be considered. > > > > > Simple Question ,Find > Error<http://groups.google.com/group/algogeeks/t/8179445b2b3c6fab> > > mahendra sengar <[email protected]> Jun 03 03:42PM -0700 > > 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]); > } > > > > > Hassan Monfared <[email protected]> Jun 04 09:51AM +0430 > > you can't assign value into names[i]! > > > > > MS: searching problem......help me > out...<http://groups.google.com/group/algogeeks/t/63551631d6a36f36> > > abhinav gupta <[email protected]> Jun 03 08:01AM -0700 > > 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 > **[email protected] > > > > > Abhishek Goswami <[email protected]> Jun 03 09:26PM +0530 > > 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 > > > > > > > Rahul Kumar Patle <[email protected]> Jun 03 09:25PM +0530 > > @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 > > > > > > > abhinav gupta <[email protected]> Jun 03 09:06AM -0700 > > @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 < > [email protected] > > [email protected]. > > 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 > [email protected] > > > > > abhinav gupta <[email protected]> Jun 03 09:10AM -0700 > > @ 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. > > > > Allahabad(UP)-211004 > > +919628358065 > > [email protected] > > -- > ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ > *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 > [email protected] > > > > > Abhishek Goswami <[email protected]> Jun 03 10:10PM +0530 > > 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 < > [email protected] > > > > > Gene <[email protected]> Jun 03 10:53AM -0700 > > 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. > > > > > > atul anand <[email protected]> Jun 04 08:47AM +0530 > > 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. > > > > > You received this message because you are subscribed to the Google Group > algogeeks. > You can post via email <[email protected]>. > To unsubscribe from this group, > send<[email protected]>an empty message. > For more options, visit <http://groups.google.com/group/algogeeks/topics>this > group. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
