## Amazon Interview Question

Country: India

Comment hidden because of low score. Click to expand.
6
of 10 vote

Maintain a fixed size hashtable, say, of size 4. Input numbers would be keys and counts of their frequencies would be the values.

0. 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.

Comment hidden because of low score. Click to expand.
0

I got your idea, but i don't think there is any good hash function

Comment hidden because of low score. Click to expand.
0

what do u mean by there is no good has functioin?

Comment hidden because of low score. Click to expand.
0

#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;
}

Comment hidden because of low score. Click to expand.
2
of 2 vote

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;

}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

How can it be O(n)? I think it's O(n^2)???????

Comment hidden because of low score. Click to expand.
0
of 0 vote

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++){
count++;
length++;
int j=0;
for(j=i;j<in.length;j++){
if(s.size()<=3){
length++;
}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]);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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]))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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++) {
}
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);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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 {
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.
numbers.put(A[i], 1);
windowSize++;
}

// Update max
if (windowSize > max) {
max = windowSize;
}

i++;
}
return max;
}

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

1,2,3,4 are 3 unique elements ?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.