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

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

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

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

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

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.

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

Trie is also another option!

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

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

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

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.

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

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

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

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(",");
}
}
}``````

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

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

Can characters repeat?

Like aaabbcc?

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

no characters cant repeat .. : )

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

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

}
}

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

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;
cout<<"{";
{
cout<<s[pos];
pos--;
}
cout<<"} , ";
}
return 0;
}``````

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

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

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

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

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( " ");
}
}
}``````

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

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

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

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

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

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.