Yes, I agree that problem seems to be incomplete. The best we can do is to make better the O(n) search. For searching a number k in array A[n]; Starting from index 0, we can skip the indexes which are within the difference between A[i] and k, ie:
i=0; while(i<n) { if(A[i]==k) return i; else i= i+ | k-A[i] |; } The order is still O(n). To see why divide and conquer wont work (in case trying a log(n) solution), see the example: Array: 4,5,4,5,4,5,4,5,4,5,4,5,4,5,4 k=6. Even if we divide array into half, we have to look into both of the halves since 6 can occur in both of them ( ie we cant discard a particular half on the basis of range of numbers a segment of array can have), hence O(n). On Sun, Mar 27, 2011 at 11:00 PM, kunal srivastav < kunal.shrivas...@gmail.com> wrote: > Also please do provide some test cases to comprehend this problem better > > > On Sun, Mar 27, 2011 at 10:34 PM, Raunak Agrawal > <raunak.ra...@gmail.com>wrote: > >> Hi Ankit, >> >> Please correct me if I am wrong: >> >> 1. There is no need of recursion and also I cant see any base >> condition....so this is basically a iterative problem. >> >> 2. Suppose the element is at last index of array...so the worst case order >> would be of O(n) >> >> 3. *|n-a[0]| >size: I am not able to get the logic...I mean is there any >> relation between n and size?* >> >> >> On Sun, Mar 27, 2011 at 10:24 PM, ankit sambyal >> <ankitsamb...@gmail.com>wrote: >> >>> For the following question : >>> There is an array and the distance between any two consequent elements >>> is one(+1 or -1) and given a number. You have to check whether the number is >>> in array or not with minimum complexity. >>> >>> Assuming the array may not be sorted, the following algo can be used: >>> Let a[] be the array of size "size" and n be the element to be searched. >>> 1. If a[0]==n >>> return yes >>> else if( |n-a[0]| >size) >>> return no >>> else >>> call this function recursively with pointer to array pointing to >>> the next element. >>> >>> >>> Any problems with this solution, Plz let me know >>> >>> >>> >>> >>> On Wed, Mar 23, 2011 at 9:07 PM, balaji a <peshwa.bal...@gmail.com>wrote: >>> >>>> First I had a paper pen coding round. The questions were: >>>> 1) There are two sorted linked lists. Write a code to return the >>>> merged linked list which is also sorted. No additional nodes must be used. >>>> >>>> 2) Design a DS that would do Push(),Pop(), and GetMax() elements at >>>> complexity O(1) >>>> 3) Do a BFS in given binary tree do find whether the given element in >>>> the tree or not. >>>> >>>> I got shortlisted and I attended three interview rounds. >>>> Round 1: >>>> It was a kind of debugging round. The questions were: >>>> 1) Consider you are given a mobile alarm application how will u >>>> test it >>>> 2) Consider ur gmail chat box is not working for a particular >>>> person alone, wht will u do to find the problem >>>> 3) I was given a program (without the code - black box testing) >>>> and asked to write the test cases for it >>>> 4) A program was given and asked to debug - was simple only >>>> >>>> Round 2: >>>> It was an algorithm designing round. >>>> 1) Consider there is an array with duplicates and u r given two >>>> numbers as input and u have to return the minimum distance between the two >>>> in the array with minimum complexity. >>>> 2) For a normal Binary tree write the code for inorder traversal >>>> without recursion >>>> 3) Given an array and an number find all the pairs in the array >>>> that would add up to the given number. This also with minimum complexity. >>>> >>>> Round 3: >>>> It was also coding round >>>> 1) There is an array and the distance between any two consequent >>>> elements is one(+1 or -1) and given a number. You have to check whether the >>>> number is in array or not with minimum complexity. >>>> >>>> >>>> >>>> On Thu, Mar 24, 2011 at 12:11 AM, Akash Mukherjee >>>> <akash...@gmail.com>wrote: >>>> >>>>> kul man...wud appreciate if u cud post your question >>>>> >>>>> On Wed, Mar 23, 2011 at 11:28 PM, balaji a >>>>> <peshwa.bal...@gmail.com>wrote: >>>>> >>>>>> hi i got till the third round of technical interview out of the four >>>>>> rounds and got eliminated in third round.....anyways thnx for ur support >>>>>> dude :-) >>>>>> >>>>>> >>>>>> On Tue, Mar 22, 2011 at 12:51 PM, balaji a >>>>>> <peshwa.bal...@gmail.com>wrote: >>>>>> >>>>>>> Thnx :-) I am from SSN College of Engineering,Chennai.... >>>>>>> >>>>>>> >>>>>>> On Tue, Mar 22, 2011 at 12:28 PM, Akash Mukherjee < >>>>>>> akash...@gmail.com> wrote: >>>>>>> >>>>>>>> u r welcome :), nd all the best for ur test.....btw, which clg?? >>>>>>>> >>>>>>>> >>>>>>>> On Tue, Mar 22, 2011 at 11:45 AM, guru <peshwa.bal...@gmail.com>wrote: >>>>>>>> >>>>>>>>> Thank you very much for the info friend....And sure will give u a >>>>>>>>> treat :-) >>>>>>>>> >>>>>>>>> On Mar 22, 11:02 am, Akash Mukherjee <akash...@gmail.com> wrote: >>>>>>>>> > hey, dis is what i was told by a friend working @ amazon - >>>>>>>>> > >>>>>>>>> > Sometimes they do go to the level of the subject basics like OS >>>>>>>>> or DS but >>>>>>>>> > you should be able to tackle these if you had studied well. No >>>>>>>>> separate prep >>>>>>>>> > is needed. >>>>>>>>> > >>>>>>>>> > Few Favs DS & Algos ( i should get treat for revealing this.;)... >>>>>>>>> ) >>>>>>>>> > 1) All Trees (Binary for sure) >>>>>>>>> > 2) Graphs >>>>>>>>> > 3) Sorting Algos >>>>>>>>> > 4) Heaps >>>>>>>>> > "Let us C" ... though clichéd gives a good insight. If you can >>>>>>>>> find time. >>>>>>>>> > >>>>>>>>> > can u tell a bit more about your profile?? fresher?? >>>>>>>>> > >>>>>>>>> > On Tue, Mar 22, 2011 at 11:20 AM, guru <peshwa.bal...@gmail.com> >>>>>>>>> wrote: >>>>>>>>> > > Hi geeks, >>>>>>>>> > > tomorrow i am having Amazon.com's Coding round followed by >>>>>>>>> > > Interview...pls suggest some tips to help me out... >>>>>>>>> > >>>>>>>>> > > -- >>>>>>>>> > > 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. >>>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> -- >>>>>>> A.Balaji >>>>>>> >>>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> A.Balaji >>>>>> >>>>>> -- >>>>>> 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. >>>>> >>>> >>>> >>>> >>>> -- >>>> A.Balaji >>>> >>>> -- >>>> 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. >> > > > > -- > thezeitgeistmovement.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.