[algogeeks] Re: Openings in Amazon
Sir, I have sent you my CV on vivekr...@gmail.com. Hope you got that On Friday, November 23, 2012 9:29:29 PM UTC+5:30, Vivek Ramamurthy wrote: > > Hi, > Amazon is hiring people for software development projects undergoing at > Blore, Hyd and Chennai divisions.There are openings for Software > Development Engineer, Software Development Engineer in Test, Application > Engineer and for Quality Assurance Engineer positions .Send me your resume > if you are interested. > > > > -- > *Vivek Ramamoorthy, > *SDE, > Amazon, > Chennai. > --
[algogeeks] Re: Largest contigious subarray with average greather than k
Define the deficit of a subarray S to be k*size(S)-sum(S), or how much
its sum falls short of averaging k.
If the deficit of the entire array is negative, the result is the
entire array.
Otherwise, the result is the subarray created by removing the smallest
possible subarray from the front and back such that the sum of the
deficits of the two subarrays is greater than the deficit of the
entire array.
If you create an array containing the max leading deficit of the array
up to that point:
Deficit = MaxFromleft[0] = k – A[0];
BestLen = 0;
BestStart = 0;
For(I = 1; I < N; ++I)
{
Deficit += k – A[i];
MaxFromLeft[i] = max(Deficit, MaxFromLeft[i-1]);
if (Deficit < 0) BestLen = i+1;
}
Now Deficit is the deficit of the entire array, and MaxFromLeft[i] is
the largest deficit of a leading subarray including elements up to i.
Finally we can step across the array from the right computing the
deficit of the trailing subarray and then doing a binary search to
find the smallest leading subarray which gives a total deficit
reduction greater than the deficit of the entire array.
RightDeficit = MaxRightDeficit = 0;
for(j = N-1; j > BestLen; --j)
{
RightDeficit += k - A[j];
if (RightDeficit > MaxRightDeficit)
{
MaxRightDeficit = RightDeficit;
int min = 0;
int max = j - bestLen;
if (RightDeficit+MaxFromLeft[max] > Deficit)
{
while(max > min)
{
int mid = (min+max)/2;
if (RightDeficit+MaxFromLeft[mid] > deficit) max =
mid;
else min = mid+1;
}
if ((j-max-1) > BestLen)
{
BestLen = j-max-1;
BestStart = max+1;
}
}
}
}
BestLen now is the length of the longest subarray averaging more than
k, and BestStart is the index of the first element in the input array
which is a part of that subarray. Note that there may be more than one
valid value of BestStart. This program just identifies one of them.
This algorithm is technically O(N*logN). However, testing on a wide
variety of data indicates that the inner loop usually executes about N
times or fewer.
Don
On Nov 20, 12:13 pm, Koup wrote:
> Consider an array of N integers. Find the longest contiguous subarray
> so that the average of its elements is greater than a given number k
>
> I know the general brute force solution in O(N^2). Is there any
> efficient solution using extra space?
--
[algogeeks] Re: Largest contigious subarray with average greather than k
Define the deficit of a subarray S to be k*size(S)-sum(S), or how much
its sum falls short of averaging k.
If the deficit of the entire array is negative, the result is the
entire array.
Otherwise, the result is the subarray created by removing the smallest
possible subarray from the front and back such that the sum of the
deficits of the two subarrays is greater than the deficit of the
entire array.
If you create an array containing the max leading deficit of the array
up to that point:
Deficit = MaxFromleft[0] = k – A[0];
BestLen = 0;
BestStart = 0;
For(I = 1; I < N; ++I)
{
Deficit += k – A[i];
MaxFromLeft[i] = max(Deficit, MaxFromLeft[i-1]);
if (Deficit < 0) BestLen = i+1;
}
Now Deficit is the deficit of the entire array, and MaxFromLeft[i] is
the largest deficit of a leading subarray including elements up to i.
Finally we can step across the array from the right computing the
deficit of the trailing subarray and then doing a binary search to
find the smallest leading subarray which gives a total deficit
reduction greater than the deficit of the entire array.
RightDeficit = MaxRightDeficit = 0;
for(j = N-1; j > BestLen; --j)
{
RightDeficit += k - A[j];
int min = 0;
int max = j - bestLen;
if (RightDeficit+MaxFromLeft[max] > Deficit)
{
while(max > min)
{
int mid = (min+max)/2;
if (RightDeficit+MaxFromLeft[mid] > deficit) max = mid;
else min = mid+1;
}
if ((j-max-1) > BestLen)
{
BestLen = j-max-1;
BestStart = max+1;
}
}
}
BestLen now is the length of the longest subarray averaging more than
k, and BestStart is the index of the first element in the input array
which is a part of that subarray. Note that there may be more than one
valid value of BestStart. This program just identifies one of them.
This algorithm is technically O(N*logN). However, testing on a wide
variety of data indicates that the inner loop usually executes about N
times or fewer.
Don
On Nov 20, 12:13 pm, Koup wrote:
> Consider an array of N integers. Find the longest contiguous subarray
> so that the average of its elements is greater than a given number k
>
> I know the general brute force solution in O(N^2). Is there any
> efficient solution using extra space?
--
[algogeeks] Re: Largest contigious subarray with average greather than k
Define the deficit of a subarray S to be k*size(S)-sum(S), or how much
its sum falls short of averaging k.
If the deficit of the entire array is negative, the result is the
entire array.
Otherwise, the result is the subarray created by removing the smallest
possible subarray from the front and back such that the sum of the
deficits of the two subarrays is greater than the deficit of the
entire array.
If you create an array containing the max leading deficit of the array
up to that point:
Deficit = MaxFromleft[0] = k – A[0];
BestLen = 0;
BestStart = 0;
For(I = 1; I < N; ++I)
{
Deficit += k – A[i];
MaxFromLeft[i] = max(Deficit, MaxFromLeft[i-1]);
if (Deficit < 0) BestLen = i+1;
}
Now Deficit is the deficit of the entire array, and MaxFromLeft[i] is
the largest deficit of a leading subarray including elements up to i.
Finally we can step across the array from the right computing the
deficit of the trailing subarray and then doing a binary search to
find the smallest leading subarray which gives a total deficit
reduction greater than the deficit of the entire array.
RightDeficit = MaxRightDeficit = 0;
for(j = N-1; j > BestLen; --j)
{
RightDeficit += k - A[j];
int min = 0;
int max = j - bestLen;
if (RightDeficit+MaxFromLeft[max] > Deficit)
{
while(max > min)
{
int mid = (min+max)/2;
if (RightDeficit+MaxFromLeft[mid] > deficit) max = mid;
else min = mid+1;
}
BestLen = j-max-1;
BestStart = max+1;
}
}
BestLen now is the length of the longest subarray averaging more than
k, and BestStart is the index of the first element in the input array
which is a part of that subarray. Note that there may be more than one
valid value of BestStart. This program just identifies one of them.
Don
On Nov 20, 12:13 pm, Koup wrote:
> Consider an array of N integers. Find the longest contiguous subarray
> so that the average of its elements is greater than a given number k
>
> I know the general brute force solution in O(N^2). Is there any
> efficient solution using extra space?
--
Re: [algogeeks] Re: reverse a string efficiently
i guess it should be swap(str[i++], str[j--]); because we already subtracted 1 On Tue, Nov 27, 2012 at 8:58 PM, Don wrote: > swap(str[i++], str[--j]); --
[algogeeks] Re: reverse a string efficiently
Reversing a string should be linear time.
void reverse(char *str)
{
int i = 0;
int j = strlen(str)-1;
while(i < j)
swap(str[i++], str[--j]);
}
On Nov 27, 12:47 am, shady wrote:
> what is the time complexity of this?
>
> str_reverse(str){
> if(isempty(str)) return str;
> else if(length(str) = even) then split str into str_1 and str_2; (of
> equal length)
> return str_reverse(str_2)+str_reverse(str_1);
> else split str into str_1, str_2, str_3; //if str is odd length, e.g.
> len = 7, split by 1-3 | 4 | 5-7
> return str_reverse(str_3)+str_2+str_reverse(str_1);
>
>
>
>
>
>
>
> }
--
Re: [algogeeks] reverse a string efficiently
Technically linear!
On Mon, Nov 26, 2012 at 9:47 PM, shady wrote:
> what is the time complexity of this?
>
> str_reverse(str){
> if(isempty(str)) return str;
> else if(length(str) = even) then split str into str_1 and str_2; (of
> equal length) (Calculate mid =O(1), then extract(0,mid) ,
> extract(mid+1,end)
>return str_reverse(str_2)+str_reverse(str_1); Reversals again
> have linear dependence on length.
> else split str into str_1, str_2, str_3; //if str is odd length, e.g.
> len = 7, split by 1-3 | 4 | 5-7
> return str_reverse(str_3)+str_2+str_reverse(str_1);
}
Similar argument for the odd length stuff. So the net complexity is in fact
linear.
>
>
>
>
--
Re: [algogeeks] reverse a string efficiently
Yes, my bad. I din notice the recursion at all! Thot it to be a flat
mid-split followed by a reverse followed by a concat. Thanks.
On Mon, Nov 26, 2012 at 11:18 PM, atul anand wrote:
> considering '+' , here will take Cn time . Here '+' is for concatenate ,
> now this concatenation taking place in constant time?? , i dont think
> so..internally it will be adding elements to new m/m space and for that it
> need to traverse each character...so it will take cn time.
> so T(n) =T(n/2) + cn = nlogn
>
>
> On Tue, Nov 27, 2012 at 11:17 AM, shady wrote:
>
>> what is the time complexity of this?
>>
>> str_reverse(str){
>> if(isempty(str)) return str;
>> else if(length(str) = even) then split str into str_1 and str_2; (of
>> equal length)
>>return str_reverse(str_2)+str_reverse(str_1);
>> else split str into str_1, str_2, str_3; //if str is odd length, e.g.
>> len = 7, split by 1-3 | 4 | 5-7
>> return str_reverse(str_3)+str_2+str_reverse(str_1);
>> }
>>
>> --
>>
>>
>>
>
> --
>
>
>
--
Re: [algogeeks] reverse a string efficiently
if it is constant i.e T(n)=2*T(n/2) + O(1) = O(n)
so simple non-recursive approach is better...
On Tue, Nov 27, 2012 at 1:29 PM, shady wrote:
> oh, understood, i thought it takes constant time suppose if it takes,
> then is there any benefit of this recursion compared to
> reverse(str) = str[lastcharacter] + reverse(str(0, last-1))
>
> it will reduce the recursion depth right ? No gain on time complexity
> though
>
>
> a small correction, btw, T(n) = 2*T(n/2) + cn
>
> On Tue, Nov 27, 2012 at 12:48 PM, atul anand wrote:
>
>> considering '+' , here will take Cn time . Here '+' is for concatenate ,
>> now this concatenation taking place in constant time?? , i dont think
>> so..internally it will be adding elements to new m/m space and for that it
>> need to traverse each character...so it will take cn time.
>> so T(n) =T(n/2) + cn = nlogn
>>
>> On Tue, Nov 27, 2012 at 11:17 AM, shady wrote:
>>
>>> what is the time complexity of this?
>>>
>>> str_reverse(str){
>>> if(isempty(str)) return str;
>>> else if(length(str) = even) then split str into str_1 and str_2; (of
>>> equal length)
>>>return str_reverse(str_2)+str_reverse(str_1);
>>> else split str into str_1, str_2, str_3; //if str is odd length,
>>> e.g. len = 7, split by 1-3 | 4 | 5-7
>>> return str_reverse(str_3)+str_2+str_reverse(str_1);
>>> }
>>>
>>> --
>>>
>>>
>>>
>>
>> --
>>
>>
>>
>
> --
>
>
>
--
