Add two numbers in string form -- FB

// Add two numbers in string.cpp : Defines the entry point for the console application.
/*
You have two numbers in string form, write a function that sums them and returns the result.
Input: 1567,789
Output: 2356
*/
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

string addtwonum (string a, string b){
int len1 = a.length();
int len2 = b.length();
int vc = 0, va = 0, vb = 0, sum = 0, i, j;
char remain ='0';
string res;

for(i= len1-1,j= len2-1;i >=0 && j>=0;--i,--j){
va = a[i]-'0';
vb = b[j]-'0';
sum = va + vb + vc;
       remain = sum %10 + '0';
       vc = sum /10;
res.insert(0,1,remain);
}
string l = i>=0? a : b;
int k = i>=0? i : j;

for(;k>=0;--k){
   sum = l[k] - '0' + vc;
       remain = sum %10 + '0';
       vc = sum /10;
res.insert(0,1,remain);
}
if(vc){
res.insert(0,1,vc+'0');
}
return res;
}

int main(){
string a,b,c;
while(1){
cin>> a;
cin>> b;
c = addtwonum (a,b);
   cout <<a<<endl<<b<<endl<<c<<endl;
}
return 0;
}

Multiply two number in array form -- FB

/*
int a[] = {1,2,3}
int b[] = {9,8}
int res[] = {1,2,0,5,4}
*/
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

vector<int> multiplytwonum(vector<int> &a, vector<int> &b){
vector<int> s, l, res(a.size()+b.size(),0);

if(a.size()>b.size()){
s=b;
l=a;
}
else{
s=a;
l=b;
}

int carryon = 0;
for(int i=s.size()-1;i>=0;--i){
for(int j=l.size()-1;j>=0;--j){
int product = s[i]*l[j];
int v = res[i+j+1] + product + carryon;
res[i+j+1] = v %10;
carryon = v /10;
}
}
if(carryon){
res[0] = carryon;
}
return res;
}

int main(){
int a[] = {1,2,3};
int b[] = {9,8};
vector<int> aa(a,a+3);
vector<int> bb(b,b+2);
vector<int> res = multiplytwonum(aa, bb);
for (int i=0;i<res.size();++i){
cout<<res[i]<<" ";
}
getchar();
return 0;
}

Add two binary number in string format -- FB

Question:
You have two numbers decomposed in binary representation, write a function that sums them and returns the result.

Input: 100011, 100100
Output: 1000111

Answer
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string>
#include <iostream>

using namespace std;

string addBinary(string a, string b){
int len1 = a.length();
int len2 = b.length();
int maxlen = max(len1,len2);
int minlen = min(len1,len2);

int vc = 0, va = 0, vb = 0;
char remain = '0';
string res;

for(int i= maxlen-1;i >=0;--i){
if(i >= maxlen - minlen){
va = len1 < len2 ? a[i-maxlen+len1]-'0'+0 : a[i]-'0'+0;
vb = len2 < len1 ? b[i-maxlen+len2]-'0'+0 : b[i]-'0'+0;
}
else{
   va = len1 > len2? a[i]-'0'+0 : 0;
vb = len2 > len1? b[i]-'0'+0 : 0;
}

int sum = va + vb + vc;
if(sum<2){
remain = sum - 0 + '0';
vc = 0;
}
else{
remain = sum -2 - 0 + '0';
   vc = 1;
}
res.insert(0,1,remain);
}
if(vc){
res.insert(0,1,'1');
}
return res;
}

int main(){
string a,b,c;
while(1){
cin>> a;
cin>> b;
c = addBinary (a,b);
   cout <<a<<endl<<b<<endl<<c<<endl;
}
return 0;
}

Binary search with duplicates & return 1st idx of duplicate element -- FB

Question:
Binary search with duplicates and return 1st occrance idx of duplicate element.

Answer:
1: Treat find 1st occrance idx of duplicate element as natural case.
//*****Better******but cost more recursive steps!!*****//
int BSHelp1(int a[], int low, int high, int val){
while( low < high){
int mid = low + (high-low)/2;
if( val > a[mid]){
low = mid + 1;             //+1, to avoid infinite loop!!!
}
else{    //if(val <= a[mid]). Note: if(val==a[mid],still recursive into the left part to search for 1st idx!!!
high = mid;
}
}
                            //low == high now.
if(val == a[low])  return low;
else return -1;
}

int BS1 (int a[],int n, int val){
return BSHelp1(a,0,n-1,val);
}

2.  Treat find 1st occrance idx of duplicate element as special case. Just add while loop.
int BSHelp2(int a[], int low, int high, int val){
while(low < high){            
int mid = low +(high-low)/2;

if(val == a[mid]) {
                                        //Just add while loop part.
int idx = mid;
while(a[idx] == a[idx-1]){
--idx;
}
return idx;                //Find the 1st idx of duplicate value.
}
else if(val < a[mid]){
high = mid;
}
else{
 low = mid + 1;
}
}
                 //edge case: low == high now!
if(val == a[low]) return low;
else return -1;             //don't exist in the array!
}

Test function:
int main(){
int arr[] ={-100,-100,-2,-2,0,3,5,5,9,9,15,15,15,19,22,22,22,23,24,24,26,50,50,105,105,160};
int len = sizeof(arr)/sizeof(int);
 
for (int i=0; i<len;++i){
cout<< arr[i]<< ' ';
}
cout <<endl;

int value;
cout<<"Input the value you want to search:"<<endl;
int index;
while(cin>>value){
if(value == -111111) break;     //Quit!
        index = BS1(arr,len,value);
cout<<"Index is:"<<index<<endl;
cout<<"Input the value you want to search:"<<endl;
}
return 0;
}

Subsets(n,k) -- FB

Question:
eg: I/p: N = 5, K =3
O/p:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
Answer:
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <iostream>

using namespace std;

void subsetsnkHelp(int idx, int n, int k,vector<int> &subres,vector<vector<int>> &res){
   //end case!!!
if(subres.size()==k){
res.push_back(subres);
return;
}

for(int i=idx;i<=(n-(k-subres.size()-1));++i){
subres.push_back(i);
subsetsnkHelp(i+1,n,k,subres,res);
subres.pop_back();          //Backtrack!!! Important! As only maintain one vector to use as stack.
}
return;
}

vector<vector<int>> subsetsnk (int n, int k){
vector<vector<int>> res;
vector<int> subres;
if(!n || !k) return res;

subsetsnkHelp(1,n,k,subres,res);
return res;
}

int main(){
vector<vector<int>> arr = subsetsnk(5,3);
for(int i=0; i<arr.size();++i){
for(int j=0;j<arr[0].size();++j){
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
getchar();
return 0;
}

Binary tree serialization & deserialization -- FB

#include <stdio.h>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

struct BTNode{
int val;
BTNode *left;
BTNode *right;
BTNode(int v): val(v),left(NULL),right(NULL){}
};

void serialize(BTNode *root, stringstream& sstr){
int i = 0;
if(!root){
sstr<< "# ";
return;
}
sstr << root -> val << " ";
serialize(root->left, sstr);
serialize(root->right, sstr);
}

BTNode* deserialize(stringstream& sstr){
string c;
sstr >> c;
if(c == "#") return NULL;

BTNode *root = new BTNode(stoi(c));
root->left = deserialize(sstr);
root->right = deserialize(sstr);
return root;
}

int main(){
BTNode *root = new BTNode (0);
root->left = new BTNode (0);
root->right = new BTNode (0);
root->left->left = new BTNode (1);
root->left->right = new BTNode (2);
root->right->left = new BTNode (3);
root->right->right = new BTNode (4);

stringstream sstr1;
serialize(root, sstr1);
cout << sstr1.str()<<endl;

BTNode *newroot = deserialize(sstr1);
stringstream sstr2;
serialize(newroot, sstr2);
cout<< sstr2.str()<<endl;
getchar();
return 0;
}

Result:

Sink Zero -- Facebook

Question:

Sink zero in Binary tree. Swap '0' value node with non-zero value node and its descendants so that no node with value '0' could be parent of node with non-zero.

Example:

Answer:
#include <stdio.h>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

struct BTNode{
int val;
BTNode *left;
BTNode *right;
BTNode(int v): val(v),left(NULL),right(NULL){}
};

void postorder0(BTNode *);

void printTree(BTNode *root,int level){
   if(!root) return;

   printTree(root->left, level-1);

   for(int i=0; i<level; i++) {
     cout << "  ";
   }
   cout << root->val << endl;
 
   printTree(root->right, level-1);
   return;
}

void sinkZero(BTNode *root){
postorder0(root);
}

void preorder0 (BTNode *root){
if(!root) return;

if(root->val == 0){
if(root->left && root->left -> val!=0){
swap(root->val, root-> left->val);
preorder0(root->left);
}
else if(root->right && root->right->val != 0){
swap(root->val, root-> right->val);
   preorder0(root->right);
}
}
return;
}

void postorder0 (BTNode *root){
if(!root) return;

postorder0(root->left);
postorder0(root->right);

if(root->val == 0){
if(root->left && root->left->val!=0  || root->right && root->right->val!= 0){
preorder0(root);
}
}
return;
}

int main(){
BTNode *root = new BTNode (0);
root->left = new BTNode (0);
root->right = new BTNode (0);
root->left->left = new BTNode (0);
root->left->right = new BTNode (2);
root->right->left = new BTNode (3);
root->right->right = new BTNode (0);
root->left->left->left = new BTNode(0);
root->left->left->right = new BTNode(1);

printTree(root,4);
sinkZero(root);
cout<<endl<<"After sink zero elements down:"<<endl<<endl;
printTree(root,4);
getchar();
return 0;
}