## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

I think one important thing to consider here is that array is sorted. We need to follow binary search approach here to have the complexity between O(logn) and O(n).
For the input given in the question, we have a sequence from a[0] to a[5]. We can find the sequence using the comparison (a[low]-a[high] == low-high)

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

There's one thing that should be mentioned.
Your solution is good and fast, but it requires uniqueness of numbers. btw I think that the original formulation of the task has this requirement. So, with this aproach, it's the best and fastest solution.

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

Out of curiosity, what if the array contains negative numbers? this approach would not work then.

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

Binary search halves the array. If the sequence straddles two of such sub-arrays, you will not find it.

E.g. [1 4 5 8]

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

A solution with binary search

``````public class FindSets {

public static void main(String[] args) {
int[] array = { 4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24,
27 };
int i = 0;
int size = array.length;

StringBuilder sb = new StringBuilder();
while (i < size - 1) {

int end = findEnd(i, size - 1, array);
if (end != i) {
sb.append("" + i + ":" + end);
i = end + 1;
} else
i++;
}
System.out.println("O/P:" + sb.toString());
}

private static int findEnd(int i, int size, int[] array) {

int low = i, high = size;
int mid;

while (low < high) {
mid = (low + high) / 2;

if (mid - low == array[mid] - array[low]) {
if (mid - low + 1 < array[mid + 1] - array[low])
return mid;
else
low = mid + 1;
} else
high = mid - 1;
}
return low;
}

}``````

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

Note that the result could be stored in a variable that could be taken as a second parameter, that will avoid the copy of the results, however, for simplicity sake, thats not the case with the following code

``````bool isConsecutive(int first, int next){
if (first >= next) return false;
int difference = next - first;
if (difference == 1)
return true;
return false;
}

vector<Range*> getRanges(const vector<int> &data){
int start, end;
vector<Range*> resutl;
start = end = 0;
size_t dataSize = data.size();
if (size < 2 ) return;//a range must contain at least 2 numbers, start and end
for (int i =0; i<dataSize -2; i++){ //0 based array with bounds check
int current = data[i];
int next = data[i+1];
if ( !isConsecutive(current, next) ) {
end = i;//end current range secuende
if (start != end ) result.pushBack( new Range(start, end) );
start = i;//reset starting point

}//if
}//for
return result;
}``````

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

``````// [4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27]
private void accumulateSeqNos(int[] data){

List<String> result = new ArrayList<String>();
for(int i=0; i<data.length; i++){
while(i+1 < data.length){
// Loop to find the range of consecutive
if((data[i] + 1 != data[++i])){
i--;
break;
}
}
}
}

for(int i=0; i<result.size(); i++){
System.out.println(result.get(i));
}
}``````

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

The above code produces the result:
{4 : 9}
{15 : 18}
{22 : 24}

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

public static void main(String[] args) {
int[] array = {4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};
int size = array.length;
boolean seq = false;
StringBuilder sb = new StringBuilder();
for(int i=0;i<size-1;i++){
if((array[i+1]- array[i])==1 && !seq){
sb.append("{"+array[i]+":");
seq = true;
}
if((array[i+1]- array[i])>1 && seq){
seq = false;
sb.append(""+array[i]+"}");
}

}
System.out.println("O/P:"+sb.toString());
}

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

O/P:{4:9}{15:18}{22:24}

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

``````public class SeqArraySet {

public static void main(String[] args) {
int[] array = {4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};
int size = array.length;
boolean seq = false;
StringBuilder sb =  new StringBuilder();
for(int i=0;i<size-1;i++){
if((array[i+1]- array[i])==1 && !seq){
sb.append("{"+array[i]+":");
seq = true;
}
if((array[i+1]- array[i])>1 &&  seq){
seq = false;
sb.append(""+array[i]+"}");
}

}
System.out.println("O/P:"+sb.toString());
}

}

O/P:{4:9}{15:18}{22:24}``````

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

I think using Skip Lists will give O(log n) time

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

I think using Skip Lists will give O(log n) time (under the assumption that the numbers in the array are unique). Skip every n/2 element and compare if the sequence has been broken

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

``````/**
*
* @author alikatkar
*/
public class RangeInArray {

public class Range {

private int begin;
private int end;

public Range(int begin, int end) {
this.begin = begin;
this.end = end;
}

@Override
public String toString() {
return "{" + begin + "," + end + '}';
}
}

public List<Range> findRanges(int[] array) {

List<Range> rangeList = new ArrayList<Range>();
int i, j;
for (i = 0; i < array.length; i = j + 1) {
for (j = i; j < array.length - 1; j++) {
if (array[j + 1] - array[j] == 1) {
continue;
} else {
break;
}
}
if (j == array.length - 1) {
break;
}
}
return rangeList;
}

public static void main(String[] args) {

int[] array = {4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};

RangeInArray rangeInArray = new RangeInArray();
List<Range> ranges = rangeInArray.findRanges(array);
System.out.println(ranges);

}
}``````

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

in Objective-C

``````- (void)viewDidLoad {
NSArray *holder = @[@4, @5, @6, @7, @8, @9, @12, @15, @16, @17, @18, @20, @22, @23, @24, @27];
[self getConNum:holder];
}

-(void)getConNum:(NSArray*)givenArray{
BOOL isStart = YES;
int start = 0;
for(int i = 0; i < givenArray.count-1;i++){
if([givenArray[i]intValue]==[givenArray[i+1]intValue]-1){
if(isStart == YES ){
start = [givenArray[i]intValue];
isStart = NO;
}

}else if(isStart == NO){
NSLog(@"Start:%d End:%d",start,[givenArray[i]intValue]);
isStart = YES;
}
}
}``````

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

``````/**
*/
public class ConsecNumbs {

public static  void main (String[] args){
int [] ar = {4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};
consecNumbs(ar);

}

public static void consecNumbs( int [] ar){
int indx = 0;

for (int i=0; i <ar.length-1; i ++){
if(ar[i+1] - ar[i] == 1 && indx == 0){
System.out.print("{ " + ar[i]);
indx ++;
}

else if (ar[i+1]- ar[i] > 1 && indx != 0){
System.out.print(" : " + ar[i] + "}");
indx = 0;
}
}
}
}``````

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

This will break if {1, 3, 4, 5}

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

I think only one more "if" statement to check if it's a single element is fine.
the code is very clean, thanks!

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

Out Put : { 4 : 9}{ 15 : 18}{ 22 : 24}

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

I could do it with O(N). Woundering if anyone could handle it within O(log N)
private final static int[] SEQUENCE = {4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};

public static void printSequenceList(int[] input) {
int start = input[0];
int end = -1;
int j = 1;
for( int i = 1; i < input.length; ++i) {
if( start == input[i] - j) {
j++;
} else {
if( j > 1) {
System.out.print(String.format("{%s:%s}", start, input[i-1]));
}
j = 1;
start = input[i];
}
}
System.out.println();
}

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

You can no do this in O(log(N)).

Why? Becouse for (a,a+1,b,b+1 ...) input you need to return output with size of N/2. No algorithm of O(log(N)) can produce this.

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

public class SequenceArray
{
static int[] arr={1,2,3,4,9,10,11,12,16,17,19,21,22,23};

public static void main(String[] args)
{
for(int i=0;i<arr.length;i++)
{
int k=checkSequence(i);
if(k!=0)
{
System.out.println(arr[i] +"-" +arr[i+k]);
i=i+k;
}
}

}

public static int checkSequence(int k)
{
int count=0;
for(int m=k;m<arr.length-1;m++)
{
if(arr[m+1]==arr[m]+1)
{
count++;
}
else
break;
}
return count;
}
}

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

#include <stdio.h>
int main(void){
int a[]={5,8,9,10,12,13,14,15,16,17,19,20,21};
int start[7];
int end[7];
int i,j,k,m,n;
i = j = k = m = n=0;

for (i=0;i<7;i++){
start[i] = 0;
end[i] = 0;
}
for (i=0;i<13;i++){
printf("%d ", a[i]);
}
i=0;
for (k=0; k < 13;k++) {
while ((a[k+1] - a[k]) == 1){
n++;
k++;
}
if (n > 0){
printf("n=%d k=%d a[k]=%d a[k-n]=%d and m=%d\n",n, k, a[k],a[k-n],m);
start[m]=k-n;
end[m]=k;
n = 0;
m++;
}
}
return 0;
}

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

``````public class SortedIndex {
public static void main(String[] args) {
int[] a = {4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};
List output = new ArrayList(), temp;
int start = 0;
int end = 0;
int curr, prev;
for(int i=1;i<a.length;i++){
curr = a[i];
prev = a[i-1];
if((curr-prev) == 1){
end = i;
}else{
temp = new ArrayList();
start = (i+1);
end = (i+1);
}
//System.out.println(a[i]);
}
System.out.println(output);

}
}``````

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

``````private static Iterable<Integer> findRanges(int[] sorted) {
if (sorted.length == 0) {
return Collections.<Integer> emptyList();
}
int end = sorted.length - 1;
ArrayList<Integer> boundaries = new ArrayList<>();
findRanges(sorted, 0, end, boundaries);
return boundaries;
}

private static void findRanges(int[] sorted, int start, int end,
List<Integer> boundaries) {
if (start >= end || sorted[end] - sorted[start] == end - start) {
return;
}

int midIdx = (start + end) / 2;
findRanges(sorted, start, midIdx - 1, boundaries);

if (midIdx - 1 >= start && sorted[midIdx] - sorted[midIdx - 1] > 1) {
}

if (midIdx + 1 <= end && sorted[midIdx + 1] - sorted[midIdx] > 1) {
}

findRanges(sorted, midIdx + 1, end, boundaries);
}``````

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

Best case: O(1)
Worst case: O(N)

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

``````public List<Range> findRanges(int[] a){
List<Range> list = new ArrayList<Range>();
int start = 0;
int end = 0;
int i = 0;
while(i < a.length){
while((i < a.length-1) && (a[i]+1 == a[i+1])){
end++;
i++;
}
if(i < a.length-1){
start = i+1;
end = i+1;
}
i++;
}

return list;
}``````

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

c code

int a[] = {1,3,4,7,8,9,10,12};
void rec(int *a,int *l ,int * r)
{
int mid =0;
if((a[*r] - a[*l]) == (*r -*l))
{
printf(" complete sequence left %d to right %d\n",*l,*r);
return;
}
else
{
if( (*r - *l) == 1)
{
printf(" sequence break left index %d to right index %d left elem %d right elem %d\n",*l,*r,a[*l],a[*r]);
return;
}
mid = (*l + *r)/2;
rec(a,l,&mid);
rec(a,&mid,r);

}

}

int main(int argc, char **argv)
{
int l =0;
int r =7;
rec(a,&l,&r);
return 0;
}

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

Using the binary search approach this solution will output all the sequences in an array. I wrote it in LINQPad so it's not too elegant, but does work .. also I output the values into a Dictionary as am not sure what they mean to output in a list (since each entry would need to be start and end index):

``````void Main()
{

int[] nums=new int[]{4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};

Dictionary<int,int> dict=new Dictionary<int,int>();
FindSequence(nums,dict,0);

dict.Dump();

}

private static void FindSequence(int[] nums,Dictionary<int,int> dict,int seqStart)
{
int mid, first = seqStart, last = nums.Length - 1;

bool found = false;

int lastMatchIndex=-1;
while (!found && first<=last)
{
mid = (first + last) / 2;

if (nums[seqStart]+mid-seqStart == nums[mid])
{
first = mid + 1;
lastMatchIndex=mid;
}
else if(nums[seqStart]+mid != nums[mid])
{
last = mid - 1;
}
}

if(lastMatchIndex!=-1)
{
dict[seqStart]=lastMatchIndex;
}

if(lastMatchIndex!=-1 && lastMatchIndex<nums.Length-1)
{
FindSequence(nums,dict,lastMatchIndex+1);
}

}``````

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

here is my solution::

``````public static void printRanges(int[] arr){
int i,j;
for(i=0;i<arr.length;i=j+1){
for(j=i;j<arr.length-1;j++){
if(arr[j+1] - arr[j] == 1){
continue;
}else{

//print range from i to j
for(int k=i;k<=j;k++){
System.out.print(arr[k]);
}

System.out.println(" ");
break;

}
}

if(j == arr.length-1){
//print range from i to j
for(int k=i;k<=j;k++){
System.out.print(arr[k]);
}
break;
}
}

}``````

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

``````import java.util.ArrayList;
import java.util.List;

public class FindNumberSequence {

public static void main(String[] args) {
//input number sequence
int[] nos = {4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};

//A list to hold all start and end index combination
List<Index> allIndices = new ArrayList<>();

//initialize the start and end index
int sIndex = -1, eIndex = -1;

//index points to current array element
int i = 0;

while(i < nos.length){
//index points to next array element to the current
int j = i + 1;

//Have we reached end of array?
if(j >= nos.length) {
if(sIndex > -1 && eIndex > -1){
Index aIndex = new Index(sIndex, eIndex);
sIndex = -1;
eIndex = 1;
}
break;
}

//get the current element value and + 1, them compare it with
//next element
if(nos[i] + 1 == nos[j]){

//if start index is not initialized, do it
if(sIndex == -1){
sIndex = i;
}

//update the end index
eIndex = j;
} else {
//if current and next element are not of diff 1, then create the index obj
//and store in list
if(sIndex > -1 && eIndex > -1){
Index aIndex = new Index(sIndex, eIndex);
sIndex = -1;
eIndex = 1;
}
}

i++;
}

for(Index ind: allIndices){
System.out.println(ind);
}
}

static class Index{
private int start;
private int end;
private int[] consecutiveNumbers;

Index(int s, int e){
start = s;
end = e;
}

public int getStart() {
return start;
}
public void setStart(int start) {
this.start = start;
}
public int getEnd() {
return end;
}
public void setEnd(int end) {
this.end = end;
}
public int[] getConsecutiveNumbers() {
return consecutiveNumbers;
}
public void setConsecutiveNumbers(int[] consecutiveNumbers) {
this.consecutiveNumbers = consecutiveNumbers;
}

public String toString(){
return "Sequence Starts at: " + start + " and ends at: " + end;
}
}

}``````

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

/** Given a sorted array with some consecutive numbers and some non-consecutive numbers. Write an algorithm that takes this array as an input and returns a list of {start, end} of all consecutive numbers. Consecutive numbers have difference of 1 only.
E.g. of array:
[4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27]*/

/* complexity O(n) */

#include<stdio.h>
int main(){
int a[]={4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};
//aLength = sizeof(a)/sizeof(a[0]);
int *p,*q,*r;
p=a;
q=a;
r=q+1;

while(*q){
if(*r==(*q)+1){
r++;
q++;
}
else{
if(p==q){
p=r;q++;r++;
}
else{
printf("%d------>%d\n",*p,*q);
p=r;q++;r++;
}
}
}
return 0;
}

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

``````/** Given a sorted array with some consecutive numbers and some non-consecutive numbers. Write an algorithm that takes this array as an input and returns a list of {start, end} of all consecutive numbers. Consecutive numbers have difference of 1 only.
E.g. of array:
[4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27]*/

/* complexity O(n) */

#include<stdio.h>
int main(){
int a[]={4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};
//aLength = sizeof(a)/sizeof(a[0]);
int *p,*q,*r;
p=a;
q=a;
r=q+1;

while(*q){
if(*r==(*q)+1){
r++;
q++;
}
else{
if(p==q){
p=r;q++;r++;
}
else{
printf("%d------>%d\n",*p,*q);
p=r;q++;r++;
}
}
}
return 0;
}``````

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

/** Given a sorted array with some consecutive numbers and some non-consecutive numbers. Write an algorithm that takes this array as an input and returns a list of {start, end} of all consecutive numbers. Consecutive numbers have difference of 1 only.
E.g. of array:
[4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27]*/

/* complexity O(n) */

#include<stdio.h>
int main(){
int a[]={4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};
//aLength = sizeof(a)/sizeof(a[0]);
int *p,*q,*r;
p=a;
q=a;
r=q+1;

while(*q){
if(*r==(*q)+1){
r++;
q++;
}
else{
if(p==q){
p=r;q++;r++;
}
else{
printf("%d------>%d\n",*p,*q);
p=r;q++;r++;
}
}
}
return 0;
}

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

/** Given a sorted array with some consecutive numbers and some non-consecutive numbers. Write an algorithm that takes this array as an input and returns a list of {start, end} of all consecutive numbers. Consecutive numbers have difference of 1 only.
E.g. of array:
[4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27]*/

/* complexity O(n) */

#include<stdio.h>
int main(){
int a[]={4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};
//aLength = sizeof(a)/sizeof(a[0]);
int *p,*q,*r;
p=a;
q=a;
r=q+1;

while(*q){
if(*r==(*q)+1){
r++;
q++;
}
else{
if(p==q){
p=r;q++;r++;
}
else{
printf("%d------>%d\n",*p,*q);
p=r;q++;r++;
}
}
}
return 0;
}

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

``````/** Given a sorted array with some consecutive numbers and some non-consecutive numbers. Write an algorithm that takes this array as an input and returns a list of {start, end} of all consecutive numbers. Consecutive numbers have difference of 1 only.
E.g. of array:
[4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27]*/

/* complexity O(n) */

#include<stdio.h>
int main(){
int a[]={4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27};
//aLength = sizeof(a)/sizeof(a[0]);
int *p,*q,*r;
p=a;
q=a;
r=q+1;

while(*q){
if(*r==(*q)+1){
r++;
q++;
}
else{
if(p==q){
p=r;q++;r++;
}
else{
printf("%d------>%d\n",*p,*q);
p=r;q++;r++;
}
}
}
return 0;
}``````

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.