<repo_name>akashkumar916/Bobble_internship_answer<file_sep>/Solution_2.cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long 

//Number of alphabet
const int alpha=26;

//Structure for my tree 
struct trie{
	trie* children[alpha];
	bool is_leaf;
};

//Making the new node 
trie* new_node(){
	trie* temp=new trie();
	for(int i=0;i<alpha;i++){
		temp->children[i]=NULL;
	}
	temp->is_leaf=false;
}

//Inserting each character of string in a tree
void insert(trie*  root,string m){
	trie* temp=root;
	for(int i=0;i<m.size();i++){
		int index=m[i]-'a';
		if(!temp->children[index]){
			temp->children[index]=new trie();
		}
		temp=temp->children[index];
	}
	temp->is_leaf=true;
}

//Traversing the tree
void traverse(trie* root,string s,vector<string>&ouput){

	if(root->is_leaf==true){
		
		//s[index]='\0';
		ouput.push_back(s);
	}
	for(int i=0;i<alpha;i++){
		if(root->children[i]){
			s.push_back(i+'a');		
		traverse(root->children[i],s,ouput);}

	}
}

//creating the tree through this function
vector<string> create(vector<string>&v){

	trie* root=new_node();
	for(int i=0;i<v.size();i++){
		insert(root,v[i]);
	}
	vector<string>ouput;
	string s;
	traverse(root,s,ouput);
	sort(v.begin(),v.end());
	ouput=v;
	return v;
}

//traversing the tree this function
void load(vector<string>&v){
	vector<string>output=create(v);
	for(int i=0;output.size();i++){
		cout<<output[i]<<endl;
	}
	
}
//Main Driven function
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);

	fstream fin, fout; 
  	fin.open("input.csv", ios::in); //Reading the input.csv file 

 
  	vector<string>output;  //storing the ouput string 

  	cout<<"1. create"<<endl<<"2. load"<<endl;
  	int choice;

  	vector<string>v; //stroing the string input from input.csv
  	string line,word;
  	while( getline(fin, line)){
  			        stringstream s(line); 
  			        while (getline(s, word, ',')) { 
  			   			v.push_back(word); 
        											}

  								}
  	cin>>choice;
  	if(choice==1){
  		
  		//Creating the character tree
  			output=create(v); 

  			//storing the output string in output.csv
  	
			fout.open("output.csv",ios::out);//output.csv file

			for(int i=0;i<output.size();i++){
				fout<<output[i]<<", "; //every string into ouput
			}
  				
  	}
  	
  	else {
			// loading and recreate the tree and print it.  		
  		load(v);
  		}







	return 0;
}<file_sep>/Solution_3.cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long 



//Number of alphabet
const int alpha=26;

//Structure for my tree 
struct trie{
	trie* children[alpha];
	bool is_leaf;
};

//Making the new node 
trie* new_node(){
	trie* temp=new trie();
	for(int i=0;i<alpha;i++){
		temp->children[i]=NULL;
	}
	temp->is_leaf=false;
}

//Inserting each character of string in a tree
void insert(trie*  root,string m){
	trie* temp=root;
	for(int i=0;i<m.size();i++){
		int index=m[i]-'a';
		if(!temp->children[index]){
			temp->children[index]=new trie();
		}
		temp=temp->children[index];
	}
	temp->is_leaf=true;
}


// Returns 0 if current node has a child 
// If all children are NULL, return 1. 
bool isLastNode(trie* root) 
{ 
	for (int i = 0; i < alpha; i++) 
		if (root->children[i]) 
			return 0; 
	return 1; 
}


//suggestions
void bobblesugg(trie* root, string curr,std::vector<string>& output) 
{ 
	// found a string in Tree with the given prefix 
	if (root->is_leaf) 
	{ 
		if(output.size()==5)return;//only 5 word sugesstion
		output.push_back(curr);
	} 

	// All children struct node pointers are NULL 
	if (isLastNode(root)) 
		return; 

	for (int i = 0; i < alpha; i++) 
	{ 
		if (root->children[i]) 
		{ 
			// append current character to currPrefix string 
			curr.push_back(97 + i); 

			// recur over the rest 
			bobblesugg(root->children[i], curr,output);
			
			// remove last character 
			curr.pop_back(); 
		} 
	} 
} 


// print suggestions for given query string 
int print(trie* root, const string q) 
{ 
	trie* curr = root; 

	
	int level; 
	int n = q.length(); 
	for (level = 0; level < n; level++) 
	{ 
		int index = q[level]-'a'; 

		// no string in the Tree 
		if (!curr->children[index]) 
			return 0; 

		curr=curr->children[index]; 
	} 

	// If prefix is present as a word. 
	bool is_leaf = (curr->is_leaf == true); 

	bool isLast = isLastNode(curr); 
	if (is_leaf && isLast) 
	{ 
		cout << q << endl; 
    // no string found
		return -1; 
	} 

	// If there are are nodes below 
	std::vector<string> output;
	//output.push_back("-1"); //storing all output strings
	if (!isLast) 
	{ 
		string prefix = q; 
		bobblesugg(curr, prefix,output); 
		 
	} 

	while(output.size()<5){
		output.push_back(q);
	}
	//cout<<output.size();
		//printing the string array

	for(int i=0;i<5;i++){
		cout<<output[i]<<", ";
	}
} 



// Main Driver Code 
int main() 
{ 
	trie* root = new_node(); 
	
	

	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
    
    fstream fin, fout; 
 	fin.open("input.csv", ios::in); //Reading the input.csv file 

  	vector<string>v; //storing the string input from input.csv
  	
   	string line,word;
   	 
   	    //reading every line by line
   	 	while( getline(fin, line)){
  	 	        stringstream s(line); 
  	 	        //reading specefic line
         while (getline(s, word, ',')) { 
     			   if(isdigit(word[0])==false)v.push_back(word); //only string allowed

  	}
  	}


  	for(int i=0;i<v.size();i++)insert(root,v[i]);//inserting 
  
  		//string to find
  	string string_to_find;
  	cin>>string_to_find;
  		
  		
  		//printing all suggestions
    print(root,string_to_find);
        
        
	return 0; 
} 
<file_sep>/Solution1.cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long 

//recursive function to calculate all permutation
void recursive_cal(int i, string s, vector< vector<char> > v)
{
    if (i >= (int) v.size()) {
        cout << s << ", ";
        return;
    }
 	
   for (char c:v[i]) {
        s.push_back(c);
        recursive_cal(i + 1, s, v);
        s.pop_back();
    }
}
 

int main(){


	ios_base::sync_with_stdio(false);
	
    cin.tie(0);

	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);

 	vector< vector<char> >v// storing dynamic array

  	string line,word;


  	fstream fin, fout; 
 	fin.open("input.csv", ios::in); //Reading the input.csv file 

  	    //reading every line by line
 	
  	while(getline(fin, line)){
  	 	        stringstream s(line); 
  	 	        
  	 	        vector<char>temp; // will contains all character of first line of csv file
  		        
  		        int i=0;
        		while (getline(s, word, ',')) { 

     			   	if(i==0){temp.push_back(word[1]);i=1;} //if first word of line  then store 2nd character

     			   	else {temp.push_back(word[2]);} //else store 3rd character

     			}
  				v.push_back(temp);
  	}
  	
  	

  	//recursive solution to printing all permutation
   recursive_cal(0, "", v);

   return 0;
}
<file_sep>/README.md
# Booble_internship_answer
**Assignment solutios for all 3 Questions**

**Questions 1: Permutations**<br/><br/>
First I extract all words like ('a', 'b', 'c') from dynamic array in every line and store in my container 
and then use a recursive approach to calculate all permutations.<br/><br/>
1 Functions</br>
<ul>
  <li>recursive_call():  Calculate all different permutation for the dynamic array</li>
 </ul>
<br/>
<br/>
<br/>




**Question 2:Character Tree serialization**
<br/>
<br/>
Data Structure used: Tree
<br/>
4 Functions<br/>
<ul>
  <li>Insert():  Make a tree and Inserting the characters in thr tree</li>
  <li>Traverse(): Traversing the tree</li>
  <li>Create(): Read words from the CSV file, create tree of characters and then serialize it and save it to the file-path accepted after csv file name</li>
  <li>Load():  Read the serialized file, recreate the character tree and print all the words present in the tree.</li>
  </ul>
<br/>
<br/>
<br/>

**Question 3:Word suggestions**
<br/>
<br/>
first I used Trie data structure which used a very unique and efficient approach to insert all the string and then extract first 5 string which is starting from that prefix or query string .<br/><br/>
Data structure used: Trie (most efficient for information retrieval)
<br/>
4 Functions</br>
<ul>
  <li>Insert():  Make a tree and Inserting the characters in thr tree</li>
  <li>Traverse(): Traversing the tree</li>
  <li>booblesugg(): Helping function for print function</li>
  <li>Print():  Print 5 word suggestions .</li>
  </ul>
<br/>
