Re: [algogeeks] Amazon interview Question
nice algo ankit, so it will be nlogn using O (n) space only. What abt 2nd Q., which have a big online stream. On Mon, Feb 4, 2013 at 9:30 PM, kumar ankit wrote: > For 1: > i think you can use sorting, sort the array and keep the indices of the > numbers in the sorted list. > Now traverse the sorted list and in the sorted list you need to find the > unique number with the > minimum index which is easy to find. > > Eg: Array:5 3 1 2 4 1 4 > Indices: 0 1 2 3 4 5 6 > > > After sorting : Array:1 1 2 3 4 4 5 > Indices: 2 5 3 1 4 6 1 > > Now you can see the unique number with lowest index is 3(index=1). So , you > have your answer. > > > On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur > wrote: >> >> 1. Given a array,find a first unique integer. >> 2. Integers are coming as online stream,have to find a kth unique integer >> till now. >> >> For 1. >> >> Even we cannot use sorting for solving this as if we sort it than our >> first number which is non-repetitive changes. >> >> The best I am able to do is nlogn using a space of O( n ). >> >> For 2. No idea >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to algogeeks+unsubscr...@googlegroups.com. >> For more options, visit https://groups.google.com/groups/opt_out. >> >> > > > > > -- > Kumar Ankit > Senior Undergraduate > Department of Computer Engineering > Institute of Technology > Banaras Hindu University > Varanasi > Ph: +91 9473629892 > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. > > -- navneet singh gaur -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: GOOGLE Q1
In the first pass create a difference array of size n-1 where n is the size
of the input array.
D[i] = A[i+1] - A[i]
Look for for the longest consecutive no. of times an element is repeated in
the difference array.
public void longestAP(int[] a, int n) {
int[] diff = new int[n-1];
for(int i = 0; i < n-1; i++) {
diff[i] = a[i+1]-a[i];
}
int maxDiff = diff[0], maxi = 0, maxCount = 1;
int currentDiff = -1, currentCount = 0, currenti = -1;
for(int i = 1; i < n-1; i++) {
if(diff[i] == maxDiff) { maxCount++; }
else {
if(diff[i] == currentDiff) { currentCount++; if (currentCount >
maxCount) { maxDiff = currentDiff; maxCount = currentCount; maxi =
currenti;}}
else {
currentDiff = diff[i]; currenti = i; currentCount = 1;
}
}
}
System.out.print("Elements of the AP: ") ;
for(int i = maxi; i <= maxi+maxCount; i++) {
System.out.print(a[i]+" ");
}
System.out.println();
}
On Tue, Feb 5, 2013 at 5:33 PM, Ian Martin Ajzenszmidt wrote:
>
>
> On Friday, 8 July 2011 04:13:38 UTC+10, Piyush Sinha wrote:
>
>
>> Given an array of integers A, give an algorithm to find the longest
>> Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik,
>> such that
>>
>> A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the
>> largest possible.
>>
>> The sequence S1, S2, …, Sk is called an arithmetic progression if
>>
>> Sj+1 – Sj is a constant.
>>
> Click on the following links or copy and paste them into your browser.
> Many interesting possibilities.
>
> https://www.google.com.au/search?client=ubuntu&channel=fs&q=Given+an+array+of+integers+A%2C+give+an+algorithm+to+find+the+longest+Arithmetic+progression+in+it%2C+i.e+find+a+sequence+i1+%3C+i2+%3C+%E2%80%A6+%3C+ik%2C+such+that+A[i1&ie=utf-8&oe=utf-8&redir_esc=&ei=GpQRUZXnJKaeiAen7oDYAw
>
>
> http://scholar.google.com/scholar?hl=en&q=Given+an+array+of+integers+A%2C+give+an+algorithm+to+find+the+longest+Arithmetic+progression+in+it%2C+i.e+find+a+sequence+i1+%3C+i2+%3C+%E2%80%A6+%3C+ik%2C+such+that++A[i1]%2C+A[i2]%2C+%E2%80%A6%2C+A[ik]+forms+an+arithmetic+progression%2C+and+k+is+the+largest+possible.&btnG=&as_sdt=1%2C5&as_sdtp=
>
>> --
>> *Piyush Sinha*
>> *IIIT, Allahabad*
>> *+91-8792136657*
>> *+91-7483122727*
>> *https://www.facebook.com/**profile.php?id=10655377926*
>>
>> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>
>
--
Vandana Bachani
Graduate Student, MSCE
Computer Science & Engineering Department
Texas A&M University, College Station
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: GOOGLE Q1
On Friday, 8 July 2011 04:13:38 UTC+10, Piyush Sinha wrote: > Given an array of integers A, give an algorithm to find the longest > Arithmetic progression in it, i.e find a sequence i1 < i2 < … < ik, > such that > > A[i1], A[i2], …, A[ik] forms an arithmetic progression, and k is the > largest possible. > > The sequence S1, S2, …, Sk is called an arithmetic progression if > > Sj+1 – Sj is a constant. > Click on the following links or copy and paste them into your browser. Many interesting possibilities. https://www.google.com.au/search?client=ubuntu&channel=fs&q=Given+an+array+of+integers+A%2C+give+an+algorithm+to+find+the+longest+Arithmetic+progression+in+it%2C+i.e+find+a+sequence+i1+%3C+i2+%3C+%E2%80%A6+%3C+ik%2C+such+that+A[i1&ie=utf-8&oe=utf-8&redir_esc=&ei=GpQRUZXnJKaeiAen7oDYAw http://scholar.google.com/scholar?hl=en&q=Given+an+array+of+integers+A%2C+give+an+algorithm+to+find+the+longest+Arithmetic+progression+in+it%2C+i.e+find+a+sequence+i1+%3C+i2+%3C+%E2%80%A6+%3C+ik%2C+such+that++A[i1]%2C+A[i2]%2C+%E2%80%A6%2C+A[ik]+forms+an+arithmetic+progression%2C+and+k+is+the+largest+possible.&btnG=&as_sdt=1%2C5&as_sdtp= > -- > *Piyush Sinha* > *IIIT, Allahabad* > *+91-8792136657* > *+91-7483122727* > *https://www.facebook.com/profile.php?id=10655377926 * > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
For 1: i think you can use sorting, sort the array and keep the indices of the numbers in the sorted list. Now traverse the sorted list and in the sorted list you need to find the unique number with the minimum index which is easy to find. Eg: Array:5 3 1 2 4 1 4 Indices: 0 1 2 3 4 5 6 After sorting : Array:1 1 2 3 4 4 5 Indices: 2 5 3 1 4 6 1 Now you can see the unique number with lowest index is 3(index=1). So , you have your answer. On Mon, Feb 4, 2013 at 3:45 PM, navneet singh gaur < navneet.singhg...@gmail.com> wrote: > 1. Given a array,find a first unique integer. > 2. Integers are coming as online stream,have to find a kth unique integer > till now. > > For 1. > > Even we cannot use sorting for solving this as if we sort it than our > first number which is non-repetitive changes. > > The best I am able to do is nlogn using a space of O( n ). > > For 2. No idea > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- Kumar Ankit Senior Undergraduate Department of Computer Engineering Institute of Technology Banaras Hindu University Varanasi Ph: +91 9473629892 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Amazon interview Question
in above algo primary index is no of times that value is repeated till now -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
