NVIDIA Interview Question


Country: India




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

It can be simply done by  using backtracking.
---------------------------------------------------------
#include <stdio.h>
void printAllSet(char *arr, char *aux, int start, int depth, int length)
{
	int j;
	if(start< length)
	{
		aux[depth]='\0';
		printf("%s",aux);
		printf("\n");
	}
	for(j=start; j<length; j++)
	{
			aux[depth] = arr[j];
			printAllSet(arr, aux, j+1, depth+1, length);
	}
}
int main()
{
char arr[]="ABC";
int length=sizeof(arr)/sizeof(arr[0]);
char aux[length];
printAllSet(arr, aux, 0, 0,  length);
return 0;
}
o/p-http://ideone.com/qc4RD

- Aalok August 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

great approach... what will be its complexiety ..???

- hk August 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this method does take care about same strings produce by permutations like if aaab could produce a,aa,aaa,aaab,aab,ab,b but this method gives many repetitions

- Anonymous August 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

It is easy to do with two for loops. I certainly believe this is not what is expected in interview. This is simple O(n^2) solution. Rather I would think of using "suffix tree" for any sub string or dictionary kind of problem.

Brute Force solution:

static void PrintAllSubStrings(char[] array)
        {
            for (int i = 0; i < array.Length; i++)
            {
                string aux = string.Empty;
                for (int j = i; j < array.Length; j++)
                {
                    aux += array[j];
                    Console.WriteLine(aux);
                }
            }
        }

Take a look at suffix tree which should optimize our solution.

- seesharpconcepts August 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Trie is also another option!

- seesharpconcepts August 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

is there any solution better than o(n^2) (ie in case with, two for loops).

- hk August 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This method is incorrect, will print ac which is not a correct output. Can be varified by looking at output link provided by the code author.

- Ankit November 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

there is no need of recursion it can easily done by loops :)

void printall(char arr[], int size)
{
int i=0;
int j=0;
int k=0;

for (i=0;i<size;i++)
{
for (j=i;j<size;j++)
{
for(k=i;k<j;k++)
System.out.print(arr[k]);
System.out.println( " ");
}
}
}

- Roopam Saxena September 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

use the following java code

public static void permutate(String str, int pos,int len)
  {
	  
	  if(pos>len )
		  return;
	 for(int i=pos;i<len ;i++)
	 {
		 System.out.println(str.substring(pos,i+1));
		 
	 }
	 permutate(str, pos+1,len);
  }
}

- nix September 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

The most elegant way I could do.

#include <stdio.h>
#include <string.h>

void main() {
	char string[10] = "abc";
	
	int i,j,k;
	for(i=0;i<strlen(string);i++) {
		for(j=0;j<(strlen(string)-i);j++) {
			for(k=0;k<=j;k++) 
				printf("%c", string[i+k]);
			printf(",");
		}
	}
}

- asbelsare March 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

as the given string can be any length long so we have to o this using BST to have a sorted order and unique permutations , to save space we will only save poinrter. here is pseudo code
void make_sub_string(char*st,struct node** root)
{
	char*s;
	char*e;
	int i,j,len;
	len =strlen(st);
	for(i=0;i<len;++i)
	{
		for(j=i;j<len;++j)
		{
			s=st+i;
			e=st+j;
			printf("y%cx%cy",*s,*e);
			insert(s,e,root);
		}
	}
}
void insert(char*s,char*e,struct node**root)
{
	if(*root==NULL)
	{	
		struct node*temp4;
		temp4=malloc(sizeof(struct node));
		temp4->s_start=s;
		temp4->s_end=e;
		temp4->left=NULL;
		temp4->right=NULL;
		*root=temp4;
	}
	else
	{
		struct node* temp=*root;
		struct node* prev=NULL;
		while(temp)
		{
			int check=compare(temp->s_start,temp->s_end,s,e);
			if(check>0)
			{
			prev=temp;
			temp=temp->right;
			}
			else if(check<0)
			{
			prev=temp;
			temp=temp->left;
			}
			else{break;}
		}
		if(temp==NULL)
		{
		int check=compare(prev->s_start,prev->s_end,s,e);
		if(check==0)
		return;
		struct node*temp1=malloc(sizeof(struct node));
		temp1->s_start=s;
		temp1->s_end=e;
		temp1->left=NULL;
		temp1->right=NULL;
		prev->right=temp1;
		if(check>0)
		prev->right=temp1;
		else if(check<0)
		prev->left=temp1;
		else {}
		}
	}
}

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

Can characters repeat?

Like aaabbcc?

- Anonymous August 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

no characters cant repeat .. : )

- hk August 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

is there a typo with the return type? if the function will return char[] it'll be like [a, a, b, a, b, c, b, b, c, c] which won't be helpful, so the return type should be char*[] or char**

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

#include<stdio.h>

void main()
{
int depth=0,count=10,i,j,mdepth=0;
printf("\n Number of characters for the array to be populated \n");
scanf("%d",&count);

depth=0;

for(i=0;i<count;i++)
{ printf("%dth character : \n",i);
scanf("%c",&arr[i]);
}

for(i=0;i<count;i++);
{
printf("%dth character : %c \n",i,arr[i]);
}

printf("\n printting sub strings \n");
for(depth=1;depth <=count;depth++)
{
for(i=0;i<count;i++)
{
if(i+depth<=count)
{
j=i;
mdepth=depth;
while(mdepth)
{
printf("%c",arr[j]);
mdepth--;
j++;
}
printf("\n");
}
}

}
}

- Kunal Bansal September 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
void function(char*);
int main()
{
char arr[]="bhupendra";
function(arr);
getch();
return 0;
}
void function(char *ptr)
{
char *p = ptr;
char *t = ptr;
char *o = ptr;
int len=1, i;
while(len<=strlen(o))
{
while(*ptr != '\0')
{
p = t;
while(p<=ptr)
{
printf("%c",*p);
p++;
}
printf("\n");
ptr++;
}
t++;
ptr = t;
len++;
}
}

- Anonymous November 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<string>
using namespace std;
int main()
{
char s[]={'a','b','c'};
int size=sizeof(s)/sizeof(s[0]);
cout<<"The set is : ";
for(int i=0;i<size;i++)
cout<<s[i];
cout<<endl;
int num=1<<size;        //number of subsets
cout<<"Subsets are : "<<endl;
for(int i=0;i<num;i++)
{
    int pos=size-1;
    int bitmask=i;
    cout<<"{";
    while(bitmask>0)
    {
        if((bitmask&1)==1)
        cout<<s[pos];
        bitmask>>=1;
        pos--;
    }
    cout<<"} , ";
}
return 0;
}

- pr6989 December 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int
main(int argc, char **argv)
{
    int i=0, j=0, z;
    char arr[]="abcdefg";

    for (i=0;i<strlen(arr);i++) {
        for (j=i;j<strlen(arr);j++) {
            for (z=i;z<=j;z++) {
                printf("\ni %d j %d: %c", i, j, arr[z]);
            }
        }
        printf("\n");
    }
}

- codedamo August 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
#include <stdio.h> #include <string.h> #include <stdlib.h> int main(int argc, char* argv[]) {{{ char *s; unsigned n, i, j, a, b; if (argc < 2) printf("insufficient args!\n"); s = argv[1]; n = (unsigned) strlen(s); printf("len = %d\n", n); for (i = 0; i <= 2*(n-1); i++) {{{ a = (i/n)*(1+(i%n)); b = (i%n) > ((n-1)*(i/n)) ? (i%n) : ((n-1)*(i/n)); for (j = a; j <= b; j++) {{{ printf("%c", s[j]); }}} printf("\n"); }}} printf("\n"); return 0; }}} - silvrado August 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote
#include <stdio.h> #include <string.h> #include <stdlib.h> int main(int argc, char* argv[]) {{{ char *s; unsigned n, i, j, a, b; if (argc < 2) printf("insufficient args!\n"); s = argv[1]; n = (unsigned) strlen(s); printf("len = %d\n", n); for (i = 0; i <= 2*(n-1); i++) {{{ a = (i/n)*(1+(i%n)); b = (i%n) > ((n-1)*(i/n)) ? (i%n) : ((n-1)*(i/n)); for (j = a; j <= b; j++) {{{ printf("%c", s[j]); }}} printf("\n"); }}} printf("\n"); return 0; }}} - silvrado August 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(int argc, char* argv[]) {

    char *s;
    unsigned n, i, j, a, b;

    if (argc < 2)
        printf("insufficient args!\n");

    s = argv[1];
    n = (unsigned) strlen(s);

    printf("len = %d\n", n);
    for (i = 0; i <= 2*(n-1); i++) {
        a = (i/n)*(1+(i%n));
        b = (i%n) > ((n-1)*(i/n)) ? (i%n) : ((n-1)*(i/n));
        for (j = a; j <= b; j++) {
            printf("%c", s[j]);
        }
        printf("\n");
    }
    printf("\n");

    return 0;
}

- silvrado August 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can you call it O(2n) ?

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(int argc, char* argv[]) {

    char *s, c[10];
    unsigned n, i, j, a, b;

    if (argc < 2)
        printf("insufficient args!\n");

    s = argv[1];
    n = (unsigned) strlen(s);

    printf("len = %d\n", n);
    for (i = 0; i <= 2*(n-1); i++) {
        a = (i/n)*(1+(i%n));
        b = (i%n) > ((n-1)*(i/n)) ? (i%n) : ((n-1)*(i/n));
        strncpy(c, &s[a], (b-a+1));
        c[b-a+1] = '\0';
        printf("%s\n",c);
    }
    printf("\n");

    return 0;
}

- silvrado August 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// I think this is brute force! but easier to understand for beginners.
void printsets( int arr[])
{
int i,j,k=0;
for(i=0;i<size;i++)
{	for(j=i;j<size;j++)
		{
		for(k=0;k<j;k++)
                   {cout<< arr[k]<<endl;}
		}
}
}

- technical_123 August 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void print(char arr[], int size) 
{ 
int i, j, k;

 for (i=0;i<size;i++) 
 { 
	  for (j=i;j<size;j++) 
	  { 
		     for(k=i;k<=j;k++) 
		     printf("%c", arr[k]); 
	     printf( " "); 
	  } 
 } 
}

- Shantanu May 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/* Following function is used by the library qsort() function to sort an
array of chars */
int compare (const void * a, const void * b);

/* The main function that recursively prints all repeated permutations of
the given string. It uses data[] to store all permutations one by one */
void allLexicographicRecur (char *str, char* data, int last, int index,int *count)
{
int i,len = strlen(str);

// One by one fix all characters at the given index and recur for the
// subsequent indexes

if (index > last)
{
return;
}

for(i = index;i<=last;i++)
{
data[*count] = str[i];
*count = *count + 1;
printf("%s\n", data);

if (i == last)
{
*count = 0;
memset(data,0,sizeof(*data)*len);
//return;
}

}

allLexicographicRecur (str, data, last, index+1,count);
}

/* This function sorts input string, allocate memory for data (needed for
allLexicographicRecur()) and calls allLexicographicRecur() for printing all
permutations */
void allLexicographic(char *str)
{
int len = strlen (str) ;

// Create a temp array that will be used by allLexicographicRecur()
char *data = (char *) malloc (sizeof(char) * (len + 1)) ;
data[len] = '\0';

// Sort the input string so that we get all output strings in
// lexicographically sorted order
qsort(str, len, sizeof(char), compare);

int count = 0;
// Now print all permutaions
allLexicographicRecur (str, data, len-1, 0,&count);

// Free data to avoid memory leak
free(data);
}

// Needed for library function qsort()
int compare (const void * a, const void * b)
{
return ( *(char *)a - *(char *)b );
}

// Driver program to test above functions
int main()
{
char str[] = "ABC";
printf("All permutations with repetition of %s are: \n", str);
allLexicographic(str);
getchar();
return 0;
}

- Tauqueer May 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//
// Created by Yunpeng Xu on 8/31/17.
//

#include "backtracking.h"

void backtracking(const string s, string &tmp, int start, vector<string> &ans) {
    if (!tmp.empty()) {
        ans.push_back(tmp);
    }
    unordered_set<char> set;
    for (int i = start; i < s.length(); i++) {
        if (set.find(s[i]) != set.end()) continue;
        tmp.push_back(s[i]);
        backtracking(s, tmp, i + 1, ans);
        tmp.pop_back();
    }
}

bool verifyResult(vector<string> &answers, vector<string> &expected) {
    unordered_map<string, int> map;
    for (string ans : answers) {
        map[ans]++;
    }
    for (string exp : expected) {
        if (map.find(exp) == map.end()) return false;
        map[exp]--;
        if (map[exp] < 0) return false;
    }
    for (auto item: map) {
        if (item.second != 0) return false;
    }
    return true;
}

void testBackTracking(void) {
    string s = "abc";
    vector<string> expected = {
            "a", "b", "c", "ab", "bc", "ac", "abc",
    };
    vector<string> ans;
    string tmp = "";

    backtracking(s, tmp, 0, ans);
    if (!verifyResult(ans, expected)) {
        cout << "failed backtracking test!" << endl;
    } else {
        cout << "passed backtracking test!" << endl;
    }
}

- yunpeng August 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Recursion.

def get_combinations(str):
	if len(str) == 0:
		return []
        last_result = get_combinations(str[1:])
	return sorted([str[0]] + last_result + [str[0] + x for x in last_result])

- gnahzy August 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

// I think this is brute force! but easier to understand for beginners.
void printsets( int arr[])
{
int i,j,k=0;
for(i=0;i<size;i++)
{	for(j=i;j<size;j++)
		{
		for(k=0;k<j;k++)
                   {cout<< arr[k]<<endl;}
		}
}
}

- technical_123 August 18, 2013 | Flag


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