Din
BAN USER
Comments (3)
Reputation 10
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Identify the max-diff from the back and iterate till front. It roughly looks like below
int maxdiff;
int smallest = arr[n-1];
int largest = arr[n-1];
for(int i=n-2; i>=0; i--)
{
int currentMaxDiff = Max(abs(arr[i]-smallest), abs(arr[i]-largest));
if(currentMaxDiff>maxdiff)
{
maxdiff=currentMaxdiff;
}
if(arr[i]<smallest)
{
arr[i] = smallest;
}
if(arr[i]>largest)
{
arr[i] = largest;
}
}
MaxDiff should have the maximum difference at the end.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Here is an o(n) solution.
- Din March 07, 2015The idea is to iterate through the array and update the buckets the array value could go in to. arr[i] could go in to two buckets primarily - one whose minValue is arr[i] itself and the other whose minValue is arr[i]-1 (to ensure the differences between elements in a bucket do not differ by 1).
int FindLongestSubset(int[] arr)
{
Dictionary<int, int> dictionary = new Dictionary<int, int>();
//Key - minimum value of a set
//Value - count of occurrences of min value and the minvalue+1
int longestSubsetSequence;
for(int i=0; i<arr.length; i++)
{
//arr[i] value can go in to dictionary whose min value is arr[i] or arr[i]-1, so we update both the dictionary entries
int result1;
if(!dictionary.KeyExists(arr[i]))
{
dictionary.Add(arr[i], 1);
result1=1;
}
else
{
dictionary[arr[i]] = dictionary[arr[i]] + 1;
result1 = dictionary[arr[i]];
}
int result2;
if(!dictionary.KeyExists(arr[i]-1))
{
result2 = 1;
dictionary.Add(arr[i]-1, 1);
}
else
{
dictionary[arr[i]-1] = dictionary[arr[i]-1] + 1;
result2 = dictionary[arr[i]-1];
}
int maxLocalResult = max(result1, result2);
if(maxLocalResult > longestSubsetSequence)
{ longestSubsetSequence = maxLocalResult; }
}
return longestSubsetSequence;
}