Level order traversal on binary tree

Level order traversal or BFS traversal  on binary tree:
/*
struct node
{
    int data;
    node* left;
    node* right;
}*/
#include <queue>
void LevelOrder(node * root)
{
  queue<node *>q;
  q.push(root);
   
  while (!q.empty()) {
      node * temp = q.front();
      if (temp->left)
        q.push(temp->left);
      if (temp->right)
          q.push(temp->right);
      cout<<temp->data<<" ";
      q.pop();
  }
 
}

Check if a binary tree is a binary search tree

/*   struct Node {
      int data;
      Node* left;
      Node* right;
   }
*/
bool checkBST_util(Node * root, int min, int max) {
    bool ret=true;
    if (root == NULL) return true;
    if (root->left) {
          if (root->data > root->left->data && root->left->data<max && root->left->data>min)
            ret =true;
          else
              return false;
    }
    if (root->right) {
          if (root->data < root->right->data && root->right->data < max && root->right->data > min)
            ret =true;
          else
              return false;
    }
    return (ret && checkBST_util(root->left, min, root->data < max ? root->data : max) && checkBST_util(root->right, root->data>min ? root->data:min , max));
}
bool checkBST(Node* root) {
       return checkBST_util(root, -1, 100000); 
}

Implement heap using vector STL c++

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void heapify(vector<int> &v, int t) {
    int s = v.size();
    if ( ((s> 2*t+1 ) && (v[t] > v[2*t+1])) || ((s>2*t+2) && (v[t] > v[2*t+2]))) {
        if (s>2*t+2) {
           
            int index = v[2*t+1] > v[2*t+2] ? 2*t+2 : 2*t+1;
            int temp = v[index];
            v[index] = v[t];
            v[t] = temp;
            heapify(v, index);
        } else {           
           
            int temp = v[2*t+1];
            v[2*t+1] = v[t];
            v[t] = temp;
            heapify(v, 2*t+1);
        }
    }
}

void insert_h(vector<int> &v, int t) {
   
    if (v.size() > 0) {
        v.push_back(t);
        t= v.size() -1;
        while((t-1)/2>= 0 && v[t] < v[((t-1)/2)]) {
            int temp = v[t];
            v[t] = v[(t-1)/2];
            v[(t-1)/2] = temp;
            t = (t-1)/2;
        }
    } else {
        v.push_back(t);
    }
}

void delete_h (vector<int> &v , int t) {
    for (int i = 0; i< v.size(); i++) {
        if (v[i] == t) {
            v[i] = v.back();
            v.pop_back();
            heapify(v, i);
            break;
        }
    }
}
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    vector<int> v;
    int n;
    int q;
    int t;
    cin>>n;
    for (int i =0; i<n; i++) {
        cin>>q;
        if (q == 1) {
            cin>>t;
            insert_h(v,t);
        } else if (q == 2) {
            cin>>t;
            delete_h(v,t);
        } else {
            cout<<v[0]<<endl;
        }
    }
    return 0;

Best resource to learn Android

Android tutorial series by  ProgrammingKnowledge (https://www.youtube.com/channel/UCs6nmQViDpUw0nuIx9c_WvA) is one of the best tutorials I found on internet.

Link to video series : https://youtu.be/EknEIzswvC0?list=PLS1QulWo1RIbb1cYyzZpLFCKvdYV_yJ-E

Here are the steps I followed to make my first app :

• Download Android studio : Android studio makes your life easier as android developer. It is far more user friendly than eclipse.
• Follow any video tutorial series : I followed this one :

• A lot of help came from Stack Overflow : There is a treasure of codes and questions and answers for android here. Feel free to ask questions if you feel that your doubt is unique.
• A lot of free high quality codes present at github are a great help too.
• Mother of all resources : https://developer.android.com/reference/classes.html
• Google is your friend.
• Feel free to inbox me if you have any other doubt.

 

Implementing 2-d array using STL vector c++

#include <iostream>
#include<vector>
using namespace std;

int main() {
    int row = 10, column = 20, initial = 0;
    cin>>row>>column>>initial;
    vector<vector<int> > v(row, vector<int>(column,initial));
    for (int i = 0;i<row;i++) {
        cout<<endl;
        for (int j = 0; j< column; j++) {
            cout<<v[i][j]<<" ";
        }
    }
   
    // your code goes here
    return 0;
}

multiply 2 strings in c++

Given two numbers as stings s1 and s2 your task is to multiply them. You are required to complete the function multiplyStrings which takes two strings s1 and s2 as its only argument and returns their product as strings.

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow . Each test case contains two strings s1 and s2 .

Output:
For each test case in a new line the output will be a string denoting the product of the two strings s1 and s2.

Constraints:
1<=T<=100
1<=length of s1 and s2 <=100

Example(To be used only for expected output) :
Input:
2
33 2
11 23
Output:
66
253

http://www.practice.geeksforgeeks.org/problem-page.php?pid=700383

string multiplyCharStr(char r, string s2) {
    int j = r - '0';
    int carry = 0;
    int val = 0;
    int len = s2.length();
    string ret;
    char cr;
    for (int i = len-1; i>=0; i--) {
        val = j*(s2[i]-'0');
        cr = '0' + (val + carry)%10;
        ret = (cr) + ret;
        if (val + carry >= 10)
            carry = (val+carry)/10;
        else
        carry = 0;
    }
    if (carry > 0)
    ret = ((char)('0' + carry)) + ret;
    return ret;
}

string addstring(string s1, string s2)
{
int len1 = s1.length() -1, len2 = s2.length() -1, carry = 0, val=0, j=0;
string s3;
while (len1 >= 0 && len2 >= 0) {
val = s1[len1] - '0' + s2[len2] - '0' + carry;
s3 = (char)(val%10 + '0') + s3;
len1--;
len2--;
carry = val/10;
}
while (len1 >= 0) {
val = s1[len1] - '0' + carry;
s3 = (char)(val%10 +'0') + s3;
len1--;
carry = val/10;
}
while (len2 >= 0) {
val = s2[len2] - '0' + carry;
s3 = (char)(val%10 +'0') + s3;
len2--;
carry = val/10;
}
if (carry>0)
s3 = (char)(carry +'0') + s3;
while (s3[j] == '0')
j++;
if (j>0 || s3[j] == '0')
s3.erase(0, j);
return s3;
}

string multiplyStrings(string s1, string s2) {
   //Your code here
   string s3,s4;
   int len1 = s1.length(), len2 = s2.length();
   if (len1>len2) {
    string temp = s1;
    int temi = len1;
    len1 = len2;
    s1=s2;
    s2=temp;
    len2 = temi;
   }
   
   s3 = multiplyCharStr(s1[len1-1], s2);
   if (len1 == 1) return s3;
   s4 = multiplyCharStr(s1[len1-2], s2);
 
   s4 = s4 + '0';
 
   s3 = addstring(s3,s4);
   if (len1 == 2) return s3;
   for (int i = len1-3; i>=0;i--) {
    s4 = multiplyCharStr(s1[i], s2);
    for (int j= 0; j < len1 - i - 1; j++)
    s4 = s4 + '0';
    s3 = addstring(s3,s4);
   }
   return s3;
}

Finding nth ugly number in C++

Ugly Numbers

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
shows the first 11 ugly numbers. By convention, 1 is included.
Write a program to find and print the 150’th ugly number.

#include <iostream>
#include <vector>
using namespace std;

int find_ugly(int n)
{
    int i2 = 0, i3 = 0, i5 = 0;
    int multiple_2, multiple_3, multiple_5;
 
    vector<int> ugly;
    vector<int> :: iterator it ;
    ugly.push_back(1);
    multiple_5 = ugly[i5]*5;
    multiple_2 = ugly[i2]*2;
    multiple_3 = ugly[i3]*3;
    for (int i=1; i<n; i++) {
        if (multiple_2 < multiple_3) {
            if (multiple_2 < multiple_5) {
                ugly.push_back(multiple_2); i2++;
            } else {
                ugly.push_back(multiple_5); i5++;
            }
        } else {
            if (multiple_3 < multiple_5) {
                ugly.push_back(multiple_3); i3++;
            } else {
                ugly.push_back(multiple_5); i5++;
            }
        }
     
        multiple_5 = ugly[i5]*5;
        while (multiple_5 == multiple_2 || multiple_5 == multiple_3) {
            i5++;
            multiple_5 = ugly[i5]*5;
        }
     
        multiple_2 = ugly[i2]*2;
        while (multiple_3 == multiple_2 || multiple_5 == multiple_2) {
            i2++;
            multiple_2 = ugly[i2]*5;
        }
     
        multiple_3 = ugly[i3]*3;
        while (multiple_3 == multiple_2 || multiple_5 == multiple_3) {
            i3++;
            multiple_3 = ugly[i3]*5;
        }
        cout<<"loop = "<<i<<" i2 = "<<i2<<" i3 = "<<i3<<" i5 = "<< i5<<" multiple_2 = "<<multiple_2<<" multiple_3 = "<<multiple_3<<" multiple_5 = "<< multiple_5<<endl;
    }
    for (it = ugly.begin(); it != ugly.end(); ++it)
        cout << *it << "\t";
    cout<<endl;  
    return ugly[n -1];
}

int main() {
// your code goes here
    cout<<find_ugly(150);
return 0;
}