## NVIDIA Interview Question

• 0

Country: India

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

Sorting would do it in O(nlogn + n) which is O(nlogn)

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

Subarray. Not sub-sequence.

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

BTW whats the difference between subarray and subsequence

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

According to the example given, it's neither. If you look at the example it seems the poster meant "subset"

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

So Manan is right.

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

O(n) time with hashtable.

``````def get_consecutive_sequence(list):
# key = element in list;
# value[0] = the number of elements in the left side of the key
# value[1] = the number of elements in the right side of the key
d = {}
for x in list:
if x not in d:
d[x] = [0,0]
if x - 1 in d:
d[x][0] = d[x-1][0] + 1
if x + 1 in d:
d[x][1] = d[x+1][1] + 1
# get the element who has maximum of value[0] + value[1]
max_x = max(d, key=lambda x : d[x][0] + d[x][1])

# construct the result
result = [i for i in range(max_x - d[max_x][0], max_x)] \
+ [i for i in range(max_x, max_x + d[max_x][1] + 1)]
return result``````

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

I've seen this code many a times for this problem, but it doesn't return a subarray with consecutive numbers, it returns a permutation of the original array with consecutive numbers. Take for example the array
[1,7,12,3,9,18,4,25,-6,2]
there is no continuously increasing subarray here but your program will return [1,2,3,4] not the right answer.

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

Use hashtable to achieve O(n) complexity. Please let me know if there is any mistake.

``````public static int[] find(int[] array)
{
// Contains the number of elements of each subarray
ArrayList<Integer> list = new ArrayList<Integer>();

// Key: the element in the int array, e.g. array[i].
// Value: the index of the element in "list" that saves
// the number of elements of the subarray that array[i] belongs in.
Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>();

int seqIndex = 0; // The number of subarrays so far.

for(int i = 0; i < array.length; ++i)
{
if(table.containsKey(array[i]-1))
{
table.put(array[i], table.get(array[i]-1)); // array[i] and array[i-1] belong to the same subarray
list.set(table.get(array[i]-1),list.get(table.get(array[i]-1))+1); // Increase the number of elements of the subarray by 1
}
else if(table.containsKey(array[i]+1))
{
table.put(array[i], table.get(array[i]+1));
list.set(table.get(array[i]+1),list.get(table.get(array[i]+1))+1);
}
else if(table.containsKey(array[i]))
{
list.set(table.get(array[i]),list.get(table.get(array[i]))+1);
}
else
{
table.put(array[i], seqIndex++); // array[i] does not belong to any subarray.
list.add(1); // The new array contains only array[i], so it has only 1 element.
}
}

// Find the subarray that contains maximum number of elements.
int max = 0;
for(int i = 0; i < list.size(); ++i)
{
if(max < list.get(i))
{
max = list.get(i);
}
}

int[] result = new int[max];
int resultIndex = 0;
for(int i = 0; i < array.length; ++i)
{
if(list.get(table.get(array[i])) == max)
{
result[resultIndex++] = array[i];
}
}
return result;
}``````

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

can you explain what you're trying to do here, reading an explanation is 100 times easy and better than reading raw code.

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

actully it is like first we have to sort the array .. then apply some logic to get the longest consequitive sequence of integers from the array

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

So we can use ArrayList list to store the number of elements in each subarray (here by subarray I mean the subarray that contains consecutive numbers).

Also, we can use Hashtable table to store each element in array. The KEY is array[i], while VALUE is the index of subarray it belongs in.

Then, we traverse the array. For example: {4,5,34,33,32,11,10,31}

1. Put <4, 0> in table, and let list[0] = 1; (4 belongs to the 0-th subarray, so the 0-th subarray has 1 element)
2. Put<5, 0> in the table, and let list[0] = 2; (we know 5 belongs to the 0-th subarray because we check if array[i]-1 or array[i]+1 has been put into the table)
3. Put<34, 1> in the table, and let list[1] = 1; (this is because neither 33 nor 35 has been put int the table, so we think 34 belongs to a new subarray).
4. We keep this procedure until the last element in array.
5. Then list.size represents the number of subarray, while list[m] represents the number of elements in the m-th subarray.

===============
I just found this method cannot correctly deal with the array {4, 5, 8, 7, 6}. The above method will build two subarrays: {4, 5}, {8, 7, 6}. I think can be revised as follows:
For array[i] (say array[4] = 6), we check array[i]-1 AND array[i]+1. If both are in the table but with different subarray index (say {4, 5} is the 0-th subarray, {8, 7} is the 1st subarray), we merge them by changing the subarray index of {8, 7} to 0, and put<6, 0> into the table. Of course list[0] += list[1] and list.remove(1) should be done.

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

#include<stdio.h>
#include<conio.h>
int arr[] = {5,2,7,9,3,6,8,1};
int max=0, max_in,count;
int longest(int);
int main()
{
int i;
for(i=0;i<8;i++)
{
count = 1;
longest(arr[i]);}
for(i=0;i<max;i++)
{
printf("%d\t",max_in);
max_in++;
}
getch();
return 0;
}

int longest(int in)
{
int i,in_1=in;
for(i=0;i<8;i++)
{
if(arr[i]==in+1)
{
longest(in+1);
count=count+1;
break;
}
}
if(count>max)
{
max=count;
max_in = in_1;
}
return 0;
}

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

Using arraylist or hash table would use another O(n) space.

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

According to the input length and range, choose a proper sort algorithm.
Then find out longest ascending "subset" as below.
(If there are 2+ longest subset, the first will be displayed)

main()
{
int list[]={1,2,3,6,7,9,10,11,12,14,15,16,17,45,46,48};
int i,j,start,longest;
longest = 1;
start =0;
int length = sizeof(list)/sizeof(int);
for (i = 0 ;i<length ;i=j+1 ){
j= i ;
while( (list[j+1]-list[j]) == 1) j++;
if( (j-i+1) > longest ) {
longest = j-i+1;
start = i;
}
}
printf("Longest length is %d.\n ",longest);
for(i = start;i<longest+start ;i++ ) printf("%d, ",list[i]);
}

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

#include<stdio.h>
#include<conio.h>

void goFun(int arr[],int n)
{
int i,arr1[10][10],print=0,count=0,max=0,k2=0,k=0,j,z=1,flag=1,k1=0;
printf("array is : ");
for(i=0;i<n;i++)
printf("%d\t",arr[i]);

for(i=0;i<10;i++)
for(j=0;j<10;j++)
arr1[i][j]=0;

for(i=0;i<n;i++)
{
//i=0;
//flag=1;
z=1;
k1=0;
for(j=i;j<n;j++)
{
if((arr[i] == arr[j+1]+z) || (arr[i] == arr[j+1]-z) )
{
if(k1==0)
{
arr1[k2][k]=arr[i];
k++;
}
arr1[k2][k]=arr[j+1];
//flag=1;
z++;
k++;
k1=1;
count++;
}

//else
// continue;
}
if(count > max)
{
max = count;
print = k2;

}
count = 0;
k2++;

}

printf("\nLongest consecutive nos are : ");
for(i=0;i<k2;i++)
{
if(i == print)
{
//printf("\n");
for(j=0;j<k;j++)
printf("%d\t",arr1[i][j]);
}
}
}

int main()
{
int arr[10];
int i,n;

printf("how many elements you want to insert ?? ");
scanf("%d",&n);
printf("\nEnter elements : ");
for(i=0;i<n;i++)
scanf("%d",&arr[i]);

goFun(arr,n);
getch();
return 0;
}

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

I think sorting and find consecutive numbers would be the best way.

``````public class JE15 {
public static void main(String[] args) {
// Find the longest consecutive numbers from input array
int[] input = {4, 5, 13, 33, 32, 10, 11, 34, 12, 31, 14};

int[] res = findLongestConsecNum(input);

System.out.println(Arrays.toString(res));
}

static int[] findLongestConsecNum(int[] input) {
// sorting and find the longest consecutive num : O(nlogn) + O(n)
// scan all numbers if a number belongs to certain consecutive chain : 1+2+3+...+n-1 = O(n^2)

Arrays.sort(input);

int[] temp = new int[input.length];
int[] res = new int[input.length];
temp[0] = input[0];
int count=1, maxcount = -1;
for(int i=1; i<input.length; i++) {
if(input[i]-input[i-1] != 1) {
if(count > maxcount) {
maxcount = count;
for(int j=0; j<temp.length; j++) {
res[j] = temp[j];
}
}
count = 0;
}
temp[count++] = input[i];
}

return Arrays.copyOf(res, maxcount);
}
}``````

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

``````package nvidia;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

// import org.junit.Assert;

public class LongestConsecutiveSubarray {

static void findAndPrintMaxConsecSubArray(int[] a) {
int n = a.length;

int maxL = 1, maximizerStart = 0;
Set<Integer> s = new HashSet<Integer>();
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
if(j-i < maxL) {
continue;
}
// find min and max, check if distinct
s.clear();
int min = a[i], max = a[i];
for(int k = i; k < j; k++){
if(s.contains(a[k])) {
break;
} else {
if(a[k] < min){
min = a[k];
} else if (a[k] > max) {
max = a[k];
}
}
}

int m = j-i;
if((s.size() == m) && (max-min == m-1)) {
maxL = m;
maximizerStart = i;
}

}
}

System.out.println("max length " + maxL);
for(int i = maximizerStart; i < maximizerStart + maxL; i++){
System.out.print(a[i] + "\t");
}
System.out.println();

}

static void findAndPrintMaxConsecSubSeq(int[] a) {
Arrays.sort(a);
int n = a.length;
// 4 , 5 , 10, 11, 31, 32, 33, 34
int maxL = 1, currL = 1, maximizerStart = 0;
for(int i = 0; i < n; i++){
if(i+1 < n && (a[i+1] == a[i] + 1)) {
currL = currL + 1;
if(currL > maxL){
maxL = currL;
maximizerStart = i - currL+2;
}
} else {
currL = 1;
}
}

System.out.println("max length " + maxL);
for(int i = maximizerStart; i < maximizerStart + maxL; i++){
System.out.print(a[i] + "\t");
}
System.out.println();
}

public static int getNOnes(int n)
{
int result = 0;
while(n>0)
{
n = n&(n-1);
result++;
}
return result;
}

public static void main(String[] args){
int[] testcase1 = {4, 5, 34, 33, 32, 11, 10, 31};
int[] testcase2 = {4, 5, 34, 32, 11, 33, 10, 31};

findAndPrintMaxConsecSubSeq(testcase1);
findAndPrintMaxConsecSubSeq(testcase2);

int[] testcase3 = { 4 , 5 , 33, 34, 32, 31, 11, 10};
findAndPrintMaxConsecSubArray(testcase3);
}
}``````

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

test

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

``````package nvidia;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

// import org.junit.Assert;

public class LongestConsecutiveSubarray {

static void findAndPrintMaxConsecSubArray(int[] a) {
int n = a.length;

int maxL = 1, maximizerStart = 0;
Set<Integer> s = new HashSet<Integer>();
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
if(j-i < maxL) {
continue;
}
// find min and max, check if distinct
s.clear();
int min = a[i], max = a[i];
for(int k = i; k < j; k++){
if(s.contains(a[k])) {
break;
} else {
if(a[k] < min){
min = a[k];
} else if (a[k] > max) {
max = a[k];
}
}
}

int m = j-i;
if((s.size() == m) && (max-min == m-1)) {
maxL = m;
maximizerStart = i;
}

}
}

System.out.println("max length " + maxL);
for(int i = maximizerStart; i < maximizerStart + maxL; i++){
System.out.print(a[i] + "\t");
}
System.out.println();

}

static void findAndPrintMaxConsecSubSeq(int[] a) {
Arrays.sort(a);
int n = a.length;
// 4 , 5 , 10, 11, 31, 32, 33, 34
int maxL = 1, currL = 1, maximizerStart = 0;
for(int i = 0; i < n; i++){
if(i+1 < n && (a[i+1] == a[i] + 1)) {
currL = currL + 1;
if(currL > maxL){
maxL = currL;
maximizerStart = i - currL+2;
}
} else {
currL = 1;
}
}

System.out.println("max length " + maxL);
for(int i = maximizerStart; i < maximizerStart + maxL; i++){
System.out.print(a[i] + "\t");
}
System.out.println();
}

public static int getNOnes(int n)
{
int result = 0;
while(n>0)
{
n = n&(n-1);
result++;
}
return result;
}

public static void main(String[] args){
int[] testcase1 = {4, 5, 34, 33, 32, 11, 10, 31};
int[] testcase2 = {4, 5, 34, 32, 11, 33, 10, 31};

findAndPrintMaxConsecSubSeq(testcase1);
findAndPrintMaxConsecSubSeq(testcase2);

int[] testcase3 = { 4 , 5 , 33, 34, 32, 31, 11, 10};
findAndPrintMaxConsecSubArray(testcase3);
}
}``````

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

``````sort the numbers then find the ranges then choose the maximum range
here is the pseudo code
main()
{
int N;
scanf("%d",&N);
int arr[N];
int arrsort[N];
int i;
for(i=0;i<N;++i)
{
scanf("%d",&arr[i]);
arrsort[i]=arr[i];
}

qsort(arrsort, N, sizeof(int), sort);
int range[N][2];
int l,h,c,d,count=0;
l=arrsort[0];c=l;h=l;
for(i=0;i<N;++i)
{
d=arrsort[i];
if(d==c+1||d==c) { h=d;c=d;}

else
{
range[count][0]=l;range[count][1]=h;count++;
l=d;c=d;h=d;
}
}
range[count][0]=l;range[count][1]=h;count++;
printf("  %d       ",count)    ;
for(i=0;i<count;++i)
{
printf("\nl %d  h %d ",range[i][0],range[i][1]);
}
form these range values have a mximum range having maximum value of range[i][1]-range[i][0] + 1``````

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

void main()
{
int temp=0,count=0,arr[100],i,j,size,arry[100];
printf("size of array : ");
scanf("%d",&size);

for(i=0;i<size;i++)
{
fflush(stdin);
scanf("%d",&arr[i]);
}

for(i=0;i<size;i++)
{
if(arr[i]==(arr[i-1]+1))
{
temp++;
}
else
temp=0;

if(temp>=count)
{
count=temp;
if((i-count)>0)
count++;
for(j=0;j<count;j++)
{
arry[j]=arr[i+j-count+1];
}
}
}
printf("\n\n");
for(j=0;j<count;j++)
printf("%d " , arry[j]);
}

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.