Amazon Interview Question for SDE-2s


Team: Payments
Country: India
Interview Type: In-Person




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

Sorting Solution:
Time Complexity = O(nlogn)
Space Complexity = O(1)

HashSet Solution:
Time Complexity = O(n) (amortized)
Space Complexity = O(n)

There is a trade-off for both the solutions.
Implemented both of them below:

public class Main {

	public static void main(String[] args) {
		int[] array = { 1, 94, 93, 1000, 2, 92, 1001};
		System.out.println("Max continuous length = "+maxContinuousLength2(array));
	}
	
	//Using sorting.
	public static int maxContinuousLength(int[] array){
		int maxLength = 1, curLength = 1;
		Arrays.sort(array);
		int prev = array[0];
		for(int i=1; i<array.length; i++){
			if(prev == array[i]-1){
				curLength++;
			}else{
				maxLength = max(maxLength,curLength);
				curLength = 1;
			}
			prev = array[i];
		}
		return maxLength;
	}
	
	//using HashSet
	public static int maxContinuousLength2(int[] array){
		int maxLength = 0;
		HashSet<Integer> set = new HashSet<Integer>();
		for(int i=0; i<array.length; i++){
			set.add(array[i]);
		}
		for(Integer i: set){
			if(!set.contains(i-1)){
				int curLength = 0;
				while(set.contains(i)){
					i++;curLength++;
				}
				maxLength = max(maxLength, curLength);
			}
		}
		return maxLength;
	}
}

- settyblue July 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

O(n) solution

// Returns length of the longest contiguous subsequence
int findLongestConseqSubseq(int arr[], int n)
{
    unordered_set<int> S;
    int ans = 0;
 
    // Hash all the array elements
    for (int i = 0; i < n; i++)
        S.insert(arr[i]);
 
    // check each possible sequence from the start
    // then update optimal length
    for (int i=0; i<n; i++)
    {
        // if current element is the starting
        // element of a sequence
        if (S.find(arr[i]-1) == S.end())
        {
            // Then check for next elements in the
            // sequence
            int j = arr[i];
            while (S.find(j) != S.end())
                j++;
 
            // update  optimal length if this length
            // is more
            ans = max(ans, j - arr[i]);
        }
    }
    return ans;
}

- aneeshas.kollam July 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sort the array and then look for consecutive numbers

- raj mglani July 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Q6 {

	
	
	public static void main(String[] args) {
	

		int array[]={1,94,93,1000,2,92,1001};
		
		array=mergeSort(array);

		int last_ele=array[0];
		int i=1,count=1,max=1;
		
		
		while(i<array.length)
		{
			if(array[i]==last_ele+1)
			{
				count++;
			}
			else
			{
				if(max<count)
					max=count;
				count=1;
			}
			last_ele=array[i++];
		}
		
		System.out.println("max consecutive numbers : "+max);
		
	}

	private static int[] mergeSort(int[] array) {
		// TODO Auto-generated method stub
		
		if(array.length<=1)
			return array;
		
		int mid=array.length/2;
		
		
		int temp1[]=new int[mid];
		for(int i=0;i<mid;i++)
			temp1[i]=array[i];
		
		int temp2[]=new int[array.length-mid];
		for(int i=mid;i<array.length;i++)
			temp2[i-mid]=array[i];
		
		temp1=mergeSort(temp1);
		temp2=mergeSort(temp2);
		
		array=mergeArray(temp1, temp2);
		
		return array;
	}

	private static int[] mergeArray(int[] array1, int[] array2) {
		// TODO Auto-generated method stub
		
		int result[]=new int[array1.length+array2.length];
		
		int i=0,j=0;
		
		while(i<array1.length&&j<array2.length)
		{
				if(array1[i]<=array2[j])
				{
					result[i+j]=array1[i];
					++i;
				}
				else
				{
					result[i+j]=array2[j];
					++j;
				}
			
		}
		
		while(j<array2.length)
		{
			result[i+j]=array2[j];
			++j;
		}
		
		while(i<array1.length)
		{
			result[i+j]=array1[i];
			++i;
		}
		
		
		
		return result;
	}

}

- Anonymous July 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def maxConsecutive(a):
	# a = [1, 94, 93, 1000, 2, 92, 1001]
	a.sort()
	consecutive = 0
	prev = a[0]
	m = consecutive
	for each in a[1::]:
		if each == prev + 1:
			consecutive += 1
		else:
			if consecutive != 0:
				if m < consecutive + 1:
					m = consecutive + 1
			consecutive = 0
		prev = each
	return m

- mayukh July 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MaximumConsequtiveNumbers {

	public static void main(String[] args) {
		int[] a={1,94,93,1000,2,92,1001,1002,999,3,4,5,6};
		Arrays.sort(a);
		int max=0;
		int count=0;
		for(int i=1;i<a.length;i++){
			if(a[i]-a[i-1]==1){
				count++;
				if(count>max){
					max=count;
				}
			}
			else count=0;
			
		}
      System.out.println(max+1);
	}

}

- Ninja82 July 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MaximumConsequtiveNumbers {

	public static void main(String[] args) {
		int[] a={1,94,93,1000,2,92,1001,1002,999,3,4,5,6};
		Arrays.sort(a);
		int max=0;
		int count=0;
		for(int i=1;i<a.length;i++){
			if(a[i]-a[i-1]==1){
				count++;
				if(count>max){
					max=count;
				}
			}
			else count=0;
			
		}
      System.out.println(max+1);
	}

}

- Ninja82 July 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution (ignoring sorting)

int maxLenConsNums(vector<int>& arr){
    if(arr.size() <= 1) return arr.size();
    
    sort(arr.begin(), arr.end());
    int maxLen = 0, currLen = 0;
    int i = 1;
    while(i < arr.size()){
        int diff = arr[i] - arr[i-1];
        if(diff == 1){
            currLen++;
        }
        else if(diff != 1){
            maxLen = max(maxLen, currLen);
            currLen = 0;
        }
        i++;
    }
    return maxLen+1;
}

- swapnilsj July 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the array .using Arrays.sort(aray);
find
int count=0;
for(int j=0;j<ar.length-1j++
{
if(ar[j+1]-ar[j]==1
count++;
}
SOP(count)

- MrWayne August 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int maxConsecutiveNumCount(int A[], const int N)
	{
		int B[N] = {1};
		int maxCount = 0;
		
		for(int i = 1; i < N; i++)
		{
			for(int j = 0; j<i; j++)
			{
				if(A[j] == A[i]+1 || A[j] == A[i]-1)
				{
					B[i] = max(B[i], B[j]+1);
					maxCount = max(maxCount, B[i]);
				}
			}
		}
		return maxCount;
	}

- Anonymous August 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int maxConsecutiveLen(vector<int>& arr){
    
    map<int,int> pos;
    
    for(int i = 0; i < arr.size(); i++){
        pos[arr[i]] = i;
    }
    
    int maxcount(0), count(0);
    
    auto p = pos.begin();
    
    for(auto i = pos.begin(); i != pos.end(); i++){
        
        if(i->first - p->first == 1){
            count++;
        }
        else{
            maxcount = max(maxcount, count);
            count = 0;
        }
        
        p = i;
    }
    
    return maxcount+1;
}

- swapnilsj August 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#!python3
from heapq import *

def maxConsecutive(nums):
	if not nums:
		return 0

	heap = list(nums)
	heapify(heap)

	prev = heap[0] - 1
	acc = 0
	best = 0
	for cur in popheap(heap):
		acc = (acc รท 1) & -int(prev + 1 == cur)
		best = max(best, acc)

- Riccardo August 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#C++

#include<iostream>
using namespace std;
int main()
{
int n;int x;int ct=0;
cout<<"Enter the no of elemnts in an array";
cin>>n;
int arr[n];
for(int j=0;j<n;j++)
{
cin>>arr[j];
}
for(int i=0;i<n-1;i++)
{
x=arr[i];
if(arr[i+1]==(x+1))
{
ct++;
}
}cout<<ct;}

- Sam_31 October 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream.h>
using namespace std;
int main()
{
    int n;
    int max=1;
    cin>>n;
    int temp=0;
    int arr[n];
    for(int i=0; i<n; i++)
    {
        cin>>arr[i];
    }
    for(int j=0; j<n; j++)
    {
        for(int k=j; k<n; k++)
        {
            if(arr[j]>arr[k])
            {
                temp=arr[j];
                arr[j]=arr[k];
                arr[k]=temp;
            }
        }
    }
    int x;
    for(int l=0; l<n; l++)
    {
        int ct=1;
        x=arr[l];
        for(int m=0; m<n-1; m++)
        {
            if(arr[m+1]==(x+1))
            {
                ct++;
                x=x+1;
            }
        }
        if(ct>max)
        {
            max=ct;
        }
    }
    cout<<max<<endl;
}

- desaisamveed October 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about the following approach

def findMaximumNumberinJumbled(listOfNumbers):

    countyet = 1
    countMax = 1
    sortedList = sorted(listOfNumbers)
    print sortedList

    for index in range(1, len(sortedList)):
        if sortedList[index] - sortedList[index-1] != 1:
            countyet = 1
        elif sortedList[index] - sortedList[index-1] == 1:
            countyet = countyet +1
            if countyet > countMax:
                countMax = countyet

    print countMax


if __name__ == "__main__":
    findMaximumNumberinJumbled([1,94,93,1000,2,92,1001,1002,999,3,4,5,6])

- tusharsappal July 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

sort the array and then look out in O(nlogn)

- rajmiglani128 July 26, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More