I hope it is sorted because there is no benefit of imposing condition about rotation. some twist and turn in bin search should solve this in O(log n), I hope, I have not worked it till.
On Aug 22, 2:48 pm, Sachin Jain <sachinchi...@gmail.com> wrote: > If an array is rotated a number of unknown times , then how to find an > element in O(log n) > > For the above question, is the array already sorted??? > > > > > > > > On Mon, Aug 22, 2011 at 2:50 PM, vikas <vikas.rastogi2...@gmail.com> wrote: > > using interval tree/segment tree will solve this in straightforward > > fashion > > > On Aug 22, 12:41 pm, Jagannath Prasad Das <jpdasi...@gmail.com> wrote: > > > for the stick prob is the stick length required? > > > > On Mon, Aug 22, 2011 at 12:48 PM, Jagannath Prasad Das > > > <jpdasi...@gmail.com>wrote: > > > > > i think find max and min of all time-stamps respectively > > > > > On Mon, Aug 22, 2011 at 12:44 PM, saurabh agrawal < > > saurabh...@gmail.com>wrote: > > > > >> How did u solved : > > > > >> 3) There is a list containing the checkin and checkout time of every > > > >> person in a party . The checkin time is in ascending order while the > > > >> checkout is random . > > > > >> Eg: > > > > >> Check_in Check_out > > > > >> Person 1 8.00 9.00 > > > > >> Person 2 8.15 8.30 > > > > >> Person 3 8.30 9.20 > > > > >> On Mon, Aug 22, 2011 at 9:14 AM, Decipher <ankurseth...@gmail.com> > > wrote: > > > > >>> Hi, > > > > >>> This is my Adobe interview experience for freshers : > > > > >>> *Written Test:* > > > > >>> Engineering – 45 Minutes - Data Structures, Algorithms, > > > >>> Operating Systems**** > > > > >>> C/C++ – 45 Minutes - C/C++ Fundamentals & > > Coding*** > > > >>> * > > > > >>> Aptitude – 45 Minutes – Quantitative & Analytical > > > > >>> * * > > > > >>> *On clearing the Test, 3 Technical Interviews + HR discussion on the > > > >>> same day.* > > > > >>> * > > > >>> * > > > > >>> *Interview 1: * > > > > >>> 1) Insert an element in a linked list at the end , given the *start * > > > >>> pointer. > > > > >>> 2) Write a function to Swap pointers . > > > > >>> 3) There is a list containing the checkin and checkout time of every > > > >>> person in a party . The checkin time is in ascending order while the > > > >>> checkout is random . > > > > >>> Eg: > > > > >>> Check_in Check_out > > > > >>> Person 1 8.00 9.00 > > > > >>> Person 2 8.15 8.30 > > > > >>> Person 3 8.30 9.20 > > > > >>> and so on ... > > > >>> Now , give an optimized solution to find at what time the maximum > > number > > > >>> of people will be in the party . My solution - O(nlogn) time and O(n) > > space > > > >>> . He gave another O(nlogn) time and O(n) space solution . > > > > >>> and some other questions that I can't recal ...... > > > > >>> *Interview 2:* > > > >>> 1) Base class contains 2 functions and Derived class (with Private > > > >>> Inheritance from Base) also contains 2 functions (same name as those > > in Base > > > >>> cass), then he asked me the effect by changing the Inheritance type > > and > > > >>> making different functions virtual like - virtual func in Base then > > in > > > >>> Derived and then both . > > > > >>> 2) Same question appended- A derived class *A* derived from Derived > > and > > > >>> Base , now > > > > >>> A a = new A; > > > >>> Base *b = a; > > > >>> Derived *d = a; > > > > >>> b = d; > > > > >>> and b = (Base *) d; > > > > >>> then which functions can I call ? > > > > >>> 3) Convert a tree into its mirror without using extra memory - O(1) > > space > > > >>> . > > > > >>> 4) If an array is rotated a number of unknown times , then how to > > find an > > > >>> element in O(log n) > > > > >>> 5) There are 3 sticks placed at right angles to each other and a > > sphere > > > >>> is placed between the sticks . Now another sphere is placed in the > > gap > > > >>> between the sticks and Larger sphere . Find the radius of smaller > > sphere in > > > >>> terms of radius of larger sphere . > > > > >>> *This is as far I can remember so please don't ask any questions > > > >>> regarding it .* > > > > >>> -- > > > >>> 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/-/K0ws20ht-pkJ. > > > >>> 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.