NVIDIA Interview Question
Country: India
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.
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( " ");
}
}
}
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 {}
}
}
}
#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");
}
}
}
}
#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++;
}
}
#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;
}
#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;
}
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;
}
#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;
}
//
// 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;
}
}
- Aalok August 31, 2012