quikr Interview Question Java Developers
Country: India
Interview Type: Phone Interview
compute maxDiff first, then check the min:
for (int num: nums) {
maxDiff = Math.max(maxDiff, num-min);
min = Math.min(min, num);
}
It will work either way.
Before seeing the answers, I wrote something similar with one additional variable:
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
int main() {
vector<int> a = {10,345,4545,454,542,23,1356,5565,0};
int min=10000, max=-10000, maxDiff = -1;
for (int i=0; i<a.size(); ++i) {
if (min > a[i]) {
min = a[i];
max = a[i];
}
if (max < a[i]) {
max = a[i];
}
if (maxDiff < max - min) {
maxDiff = max - min;
}
}
cout << maxDiff << endl;
return 0;
}
There is a simple O(n) solution. We go through the array, left to right, and keep track of:
a) min number found so far
b) max difference so far
For each number we find:
- if it is less than the minimum found so far, we change our minimum.
- if it is not, we check if the difference between it and our minimum is larger than the max difference. If so, we store it
The algorithm would look something like:
int minFound = inf
int maxDiff = 0
for(int i : array){
if(i < minfound) minFound = i;
else if((i - minFound) > maxDiff) maxDiff - i-minFound
}
return maxDiff.
I will not provide a 'proof' of correctness, because I think this is trivially correct. There can be no bigger difference, because the biggest difference will always involve the smallest number found so far, and would be caught in our algorithm.
what if the min number would be at the very end? How do you fall back to prev. max difference with Highest number index>Lowest number index?
First, a small correction. "maxDiff - i-minFound" should read "maxDiff = i-minFound". Sorry if that is confusing.
Secondly, I don't understand your concern? If the min is at the end, then it is irrelevant, because there are no elements after it so no difference between it and an element with a higher index exists. Our max difference will remain the same, because it only relies on the minFound up to the point we obtain it.
Not written any code for it. Just tried some examples with pen and paper. Here is the solution.
1. Consider an array. origArr={1,10,15,7,19,4,0}
2. Create a new array. newArr={}
3. Get first element from origArr. Insert it into newArr. So newArr={1}.
4. Get second element from origArr. Is it greater than element in newArr. (is 10 > 1). Insert it into newArr. So newArr = {1,10}. This a sorted Array. maxSum = 10-1 = 9
5. Get next element from origArr(15). Is 15 > last element of newArr (15>10).
6. If so simply replace this last element with this number. So newArr = {1,15}. maxSum = 15-1=14
7. Get next element of origArr(7). Is 7 > last element of newArr? No, so Discard 7.
8. Get next element of origArr(19). Is 19 > lastelement of newArr. Yes. So as before replace last element of newArr with 19. So newArr = {1,19} and maxSum = 19-1 = 18.
9. Get next element of orgiArr(4). Is 4 > last element of newArr. No. Discard 4.
10. Get next element of origArr(0). Is 0 > last element of newArr. No.
11. For all the comparisons where origArr[element] < newArr[lastElement] next step should be executed. (For simplicity i did not mention it in previous steps as it would have made the logic difficult to understand).
12. Is 0 < first element of newArr (1). Yes, so clear the newArr and add this element. So newArr = {0}.
13. Go to step 3 and continue the process to get maxSum.
I have tried it in 2-3 scenarios(again on paper) and logic holds good. Not sure about the complexity of the solution though. Please do comment on any flaws or problems you find in the solution provided.
#include<stdio.h>
#include<conio.h>
int sort(int arr[],int size);
void main()
{
int arr[50],arr1[50];
int n,i,j,max,result;
clrscr();
printf("Enter the numberof elements in array:");
scanf("%d",&n);
printf("Enter the elements:");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
for(i=0;i<n;i++)
arr1[i]=0;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(arr[j]>arr[i])
{
arr[j]=arr[j]-arr[i];
}
}
max=sort(arr,n);
arr1[i]=max;
}
result=sort(arr1,n);
printf("Answer is %d",result);
}
int sort(int arr[],int size)
{
int i,j;
int max,swap;
for(i=0;i<size;i++)
{
max=i;
for(j=i+1;j<size;j++)
{
if(arr[j]>arr[max])
max=j;
}
if(max!=i)
{
swap=arr[i];
arr[i]=arr[max];
arr[max]=swap;
}
}
return arr[0];
}
#include<stdio.h>
#include<conio.h>
int sort(int arr[],int size);
void main()
{
int arr[50],arr1[50];
int n,i,j,max,result;
clrscr();
printf("Enter the numberof elements in array:");
scanf("%d",&n);
printf("Enter the elements:");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
for(i=0;i<n;i++)
arr1[i]=0;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(arr[j]>arr[i])
{
arr[j]=arr[j]-arr[i];
}
}
max=sort(arr,n);
arr1[i]=max;
}
result=sort(arr1,n);
printf("Answer is %d",result);
}
int sort(int arr[],int size)
{
int i,j;
int max,swap;
for(i=0;i<size;i++)
{
max=i;
for(j=i+1;j<size;j++)
{
if(arr[j]>arr[max])
max=j;
}
if(max!=i)
{
swap=arr[i];
arr[i]=arr[max];
arr[max]=swap;
}
}
return arr[0];
}
public static int[] getLargestDifference(int[] values){
if(values == null || values.length < 2){
return null;
}
int[] best = new int{
values[0], values[1]
};
if(best[0] > best[1]){
int temp = best[0];
best[0] = best[1];
best[1] = temp;
}
int[] bestDifference = best[1] - best[0];
int lo = best[0], hi = best[1];
outer:
for(int i = 2; i < values.length; i++){
int val = values[i];
if(val > hi ){
hi = val;
int diff = hi - lo;
if(diff > bestDifference){
bestDifference = diff;
best[0] = lo;
best[1] = hi;
}
}
if(val < lo){
while(val < lo){
lo = val;
i++;
if(i >= values.length){
break outer;
}
val = values[i];
}
hi = val;
int diff = hi - lo;
if(diff > bestDifference){
bestDifference = diff;
best[0] = lo;
best[1] = hi;
}
}
}
return best;
}
#include<iostream>
using namespace std;
int main()
{
int const size=8;
int array[8]={8,2,20,4,5,31,32,35};
int max=(array[0]-array[1]);
for(int i=0,j=i+1;i<size-1,j<size;i++,j++)
{
if(max<(array[j]-array[i]))
{
max=(array[j]-array[i]);
}
else
{
for(int a=size,b=0;a>=size/2,b<size-1;a--,b++)
{
if(max<(array[a]-array[b]))
{
max=array[a]-array[b];
}
}
}
}
cout<<max;
system("pause");
}
// As i assumed the question it will return the differnce of largest pair in the array and it will subtract smaller from largest index
#include<iostream>
using namespace std;
int main()
{
int const size=8;
int array[8]={8,2,20,4,5,31,32,35};
int max=(array[0]-array[1]);
for(int i=0,j=i+1;i<size-1,j<size;i++,j++)
{
if(max<(array[j]-array[i]))
{
max=(array[j]-array[i]);
}
else
{
for(int a=size,b=0;a>=size/2,b<size-1;a--,b++)
{
if(max<(array[a]-array[b]))
{
max=array[a]-array[b];
}
}
}
}
cout<<max;
system("pause");
}
I'd like to look at O(n) solution, however here is the O(nlogn) solution:
1. Create a copy and sort the array asc.
2. Use 2 pointers: start, end.
3. Move 2 pointers to get the max difference, until max pair number have higher index, than min pair number.
copy of string (n) + sort (nlogn) + move pointers (n/2) = O(nlogn)
The third time I submit this.
- Yilong March 31, 2015public int maxDiff(int[] nums) { int min = Integer.MAX_VALUE; int maxDiff = 0; for (int num: nums) { min = Math.min(min, num); maxDiff = Math.max(maxDiff, num-min); } return maxDiff; }