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 <
[email protected]> wrote:
> Also please do provide some test cases to comprehend this problem better
>
>
> On Sun, Mar 27, 2011 at 10:34 PM, Raunak Agrawal
> <[email protected]>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
>> <[email protected]>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 <[email protected]>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
>>>> <[email protected]>wrote:
>>>>
>>>>> kul man...wud appreciate if u cud post your question
>>>>>
>>>>> On Wed, Mar 23, 2011 at 11:28 PM, balaji a
>>>>> <[email protected]>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
>>>>>> <[email protected]>wrote:
>>>>>>
>>>>>>> Thnx :-) I am from SSN College of Engineering,Chennai....
>>>>>>>
>>>>>>>
>>>>>>> On Tue, Mar 22, 2011 at 12:28 PM, Akash Mukherjee <
>>>>>>> [email protected]> wrote:
>>>>>>>
>>>>>>>> u r welcome :), nd all the best for ur test.....btw, which clg??
>>>>>>>>
>>>>>>>>
>>>>>>>> On Tue, Mar 22, 2011 at 11:45 AM, guru <[email protected]>wrote:
>>>>>>>>
>>>>>>>>> Thank you very much for the info friend....And sure will give u a
>>>>>>>>> treat :-)
>>>>>>>>>
>>>>>>>>> On Mar 22, 11:02 am, Akash Mukherjee <[email protected]> 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 <[email protected]>
>>>>>>>>> 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
>>>>>>>>> [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.
>>>>>>>>>
>>>>>>>>>
>>>>>>>> --
>>>>>>>> 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.
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> 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 [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.
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> 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 [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.
>>>
>>
>> --
>> 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.
>>
>
>
>
> --
> 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 [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.
