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++){
}
for(Integer i: set){
if(!set.contains(i-1)){
int curLength = 0;
while(set.contains(i)){
i++;curLength++;
}
maxLength = max(maxLength, curLength);
}
}
return maxLength;
}
}``````

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

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

sort the array and then look for consecutive numbers

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

}``````

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

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

}``````

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

}``````

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

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)

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

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

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

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

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

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

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

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

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

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.