Amazon Interview Question
Country: India
#include<stdio.h>
#include<stdlib.h>
typedef struct Hash_Element
{
int key;
int value;
};
typedef struct Hash_Table
{
int size;
int capacity;
struct Hash_Element *table;
};
Hash_Table* createHashTable( int size)
{
Hash_Table* h = ( Hash_Table*)malloc( sizeof( Hash_Table ) );
h->size = size;
h->capacity = 0;
h->table = (Hash_Element*)malloc(sizeof(Hash_Element) * h->size);
int i;
for( i = 0; i < h->size; ++i )
{ h->table[i].key = NULL; h->table[j].value = NULL; }
return h;
}
int maxlen( struct Hash_Table* h, int a[] , int n)
{
int start=0;
int end=0;
int i, j=1;
int len = 0;
int max = 0;
for( i=0; i<n; i++)
{
for( j=1; j<=h->size; j++)
{
if( h->table[j].key == a[i] )
{
h->table[j].value++;
end++;
}
if( h->table[j].key == NULL )
{
h->capacity++;
int k=1;
while( h->capacity == h->size && k < h->capacity)
{
if( h->table[k].value == 1)
{
h->table[k].key = NULL;
h->capacity--;
start++;
}
h->table[k].value--;
start++; k++;
}
if( h->capacity <= 3)
{
h->table[j].key = a[i];
h->table[j].value++;
end++;
}
}
len = end - start;
}
if ( max < len)
max = len;
}
return max;
}
int main()
{
int size = 4;
Hash_Table* h = createHashTable(size);
int a[] = {1, 2, 3, 1, 4, 3, 4, 1, 2 };
int n = sizeof(a)/sizeof(a[0]);
printf("Max length contigous subarray is : %d", maxlen(h,a,n));
return 0;
}
Implementation for an algorithms adviced above:
int maxLength(int[] arr){
int left = 0;
int right = 1;
int maxLength = 1;
Map<Integer, Integer> freq = new HashMap<>();
freq.put(arr[0], 1);
while( right < arr.length ){
int val = arr[right];
if( freq.containsKey(val) ){
freq.put(val, freq.get(val) + 1);
}
else {
while( freq.size() == 3) {
int leftVal = arr[left];
++left;
int count = freq.get(leftVal);
--count;
if( count == 0 ){
freq.remove(leftVal);
}
else {
freq.put(leftVal, count);
}
}
freq.put(val, 1);
}
maxLength = Math.max(maxLength, right-left+1);
++right;
}
return maxLength;
}
Nice solution, but i have question about following code
if( count ==0 ){
freq.remove(leftVal);
}
else {
freq.put(leftVal, count);
}
Maybe you should change condition to
if( count == 1 ){
freq.remove(leftVal);
}
else {
freq.put(leftVal, count);
}
Because your map should contain only those elements, that aren't unique. If your element is unique (encountered once in map) you shouldn't store it there.
public static int getMaxLength(int[] givenIntArray) {
int maxLength = 0;
int currentLength = 0;
if (givenIntArray.length <= 3) {
maxLength = givenIntArray.length;
} else {
Map<Integer, Integer> valueToLastOccurenceMap = new HashMap<Integer, Integer>();
for (int i = 0; i < givenIntArray.length; i++) {
if (valueToLastOccurenceMap.size() < 3
|| valueToLastOccurenceMap
.containsKey(givenIntArray[i])) {
valueToLastOccurenceMap.put(givenIntArray[i], i);
currentLength++;
} else {
if (currentLength > maxLength)
maxLength = currentLength;
int earliestElement = -1;
for (Iterator<Integer> iterator = valueToLastOccurenceMap
.keySet().iterator(); iterator.hasNext();) {
int key = iterator.next();
if (earliestElement == -1)
earliestElement = key;
else if (valueToLastOccurenceMap.get(earliestElement) > valueToLastOccurenceMap
.get(key)) {
earliestElement = key;
}
}
currentLength = i
- valueToLastOccurenceMap.get(earliestElement);
valueToLastOccurenceMap.remove(earliestElement);
valueToLastOccurenceMap.put(givenIntArray[i],i);
}
if ((i == givenIntArray.length - 1)
&& (maxLength < currentLength))
maxLength = currentLength;
}
}
return maxLength;
}
int maxlength()
{
int n=0;
int elements[100]={0};
int copy[3]={0};
int startindex=0;
int maxlen=0;
int len=2;
int i,k,check;
int index;
int dummy[3]={0};
int lencheck;
printf("enter the size of array");
scanf("%d",&n);
printf("enter the array");
for(i=0;i<n;i++)
scanf("%d",&elements[i]);
if(n>=3)
{
dummy[0]=elements[0];
dummy[1]=elements[1];
dummy[2]=elements[2];
}
for(i=2;i<n;i++)
{
check=0;
if((dummy[0]==elements[i]||dummy[1]==elements[i] ||dummy[2]==elements[i]))
{
check=1;
len++;
}
if(check==1)
{
if(maxlen<len)
{
maxlen=len;
index=i;
}
// if(lencheck)
// len++;
}
else
{
len=2;
dummy[0]=elements[i];
dummy[1]=elements[i-1];
dummy[2]=elements[i-2];
}
}
return maxlen;
}
import java.util.HashSet;
import java.util.Set;
public class LongestSeq {
public static void main(String[] args) {
//int[] in = {1, 2, 3, 1, 4, 3, 4, 1, 2};
int[] in = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int[] inL = new int[in.length+1];
inL[0]=0;
int count=0;
Set<Integer> s= new HashSet<Integer>();
int length = 0;
for(int i=1;i<=in.length;i++){
s.add(in[i-1]);
count++;
length++;
int j=0;
for(j=i;j<in.length;j++){
if(s.size()<=3){
length++;
s.add(in[j]);
}else{
break;
}
}
inL[i] = Math.max(inL[i-1], length-1);
count=0;
length=0;
s = new HashSet<Integer>();
}
System.out.println(inL[inL.length-1]);
}
}
Here is one implementation in python:
time: linear
space: constant
def subarray(numbers):
start = 0
end = 0
distinct = {}
maxlen = 1
for i in range(len(numbers)):
//if number is distinct: add to table else increase count
if distinct.get(numbers[i]) == None:
distinct[numbers[i]] = 1
else:
distinct[numbers[i]] += 1
//if total distinct elements are still 3, increase max length
if len(distinct) == 3:
end = i
maxlen = end - start + 1 if end - start + 1 > maxlen else maxlen
elif len(distinct) > 3:
while(len(distinct) > 3):
if distinct[numbers[start]] == 1:
distinct.pop(numbers[start])
else:
distinct[numbers[start]] -= 1
start += 1
return maxlen
print(subarray([1,2,3,1,4,3,2,4,1,2,2,2,2,2,1,2]))
This sample is O(n) based.
public class Generico {
private static void maxDistinctElements(String[] parr,int p, int len) {
int maxDistinct=0,size=0;
Set<String> set = new HashSet<>();
for(int x=0;x<len;x++) {
for(int y=0;y<p;y++) {
set.add(parr[x+y]);
}
size=set.size(); set.clear();
maxDistinct=maxDistinct<size?size:maxDistinct;
}
System.out.println(maxDistinct);
}
/**
* A utility method to print time taken for an operation
*
* @param caption the caption to display
* @param startTime the start time of an operation. Should be result of System.nanoTime().
*/
private static void printTimeTaken(String caption, long startTime) {
long elapsedTime = System.nanoTime() - startTime;
long elapsedMillis = TimeUnit.MILLISECONDS.convert(elapsedTime, TimeUnit.NANOSECONDS);
System.out.println(String.format("%s : Time taken %,d milliseconds", caption, elapsedMillis));
}
public static void main(String[] args) {
Do_Not_Terminate.forbidExit();
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
String[] arg = s.split(" ");
int n = Integer.parseInt(arg[0]);
n=n>100000?100000:n;
int m = Integer.parseInt(arg[1]);
m=m>n?n:m;
String numbers = sc.nextLine();
String[] arp =numbers.split(" ");
int count = arp.length-m+1;
long startTime = System.nanoTime();
maxDistinctElements(arp,m,count);
printTimeTaken("Time execution: ", startTime);
}
}
This is O(n) solution
public int maxSubArrayLength(int A[], int n, int k) {
Map<Integer, Integer> numbers = new HashMap<Integer, Integer>();
Set<Integer> num = new HashSet<Integer>();
int max = 0, i = 0, count = 0, start = 0, windowSize = 0;
while (i < n) {
// Keep adding the elements in Map and set till the basic constrainst are satisfied.
if (num.size() < k || num.contains(A[i])) {
if (num.contains(A[i])) {
count = numbers.get(A[i]);
numbers.put(A[i], count + 1);
} else {
num.add(A[i]);
numbers.put(A[i], 1);
}
windowSize++;
} else {
// This while will shrink the window from left side.
while (num.size() == k && start <= windowSize) {
int temp = A[start];
count = numbers.get(temp);
if (count == 1) {
numbers.remove(temp);
num.remove(temp);
} else {
numbers.put(temp, count - 1);
}
windowSize--;
start++;
}
// Once the unique elements are < k (3 in this case) accomodate the current element.
num.add(A[i]);
numbers.put(A[i], 1);
windowSize++;
}
// Update max
if (windowSize > max) {
max = windowSize;
}
i++;
}
return max;
}
Maintain a fixed size hashtable, say, of size 4. Input numbers would be keys and counts of their frequencies would be the values.
- Murali Mohan August 05, 20130. Maintain 2 pointers to mark the start and end of the contiguous subarray we are processing. Initially they will both point to the first location.
1. When a new number is encountered, if it is not already present in the hashtable AND the size of the hashtable <=3, add the key to the hashtable, with its count value = 1 and advance the end pointer.
2. if the size of hashtable becomes equal to 4, increment the start pointer, decrement the value of the corresponding key in the hashtable and if the count =0, remove that key from the hashtable.
Repeat steps 1 and 2 keeping track of the longest contiguous subarray which satisfies the property that the elements within it are at most 3 distinct numbers(in other words, at some time during the processing we will have longest contiguous subarray, with the size of our hash table being at most 3).
Time complexity: O(n)
Space complexity: O(1) with fixed size hash table.