NVIDIA Interview Question
Country: India
According to the example given, it's neither. If you look at the example it seems the poster meant "subset"
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
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.
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;
}
can you explain what you're trying to do here, reading an explanation is 100 times easy and better than reading raw code.
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
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.
#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;
}
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]);
}
#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;
}
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);
}
}
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 {
s.add(a[k]);
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);
}
}
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 {
s.add(a[k]);
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);
}
}
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
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]);
}
Sorting would do it in O(nlogn + n) which is O(nlogn)
- loveCoding August 30, 2012