Labels

Saturday, January 21, 2017

check connectivity of 2 nodes in a Graph

Here is the algorithm to see the connectivity of 2 nodes in a graph using BFS.
To see how the graph is constructed see : http://iwriteanything.blogspot.in/2017/01/represent-graph-adjacency-list-using.html


int connected (int a, int b, vector<vector<int>> & v) {
    queue<int> q;
    vector<int> v1(v.size(), 0);
    for (int i = 0; i< v[a].size(); i++) {
        q.push(v[a][i]);
    }
    v1[a] = 1;
    while(!q.empty()) {
        if (q.front() == b) return 1;
        if (v1[q.front()] == 0) {
            for (int i = 0; i< v[q.front()].size(); i++) {
                    q.push(v[q.front()][i]);
            }
        }
        v1[q.front()] = 1;
        q.pop();
    }
    return 0;
}

Represent graph (adjacency list) using STL c++

As we know graph can be represented using either adjacency matrix or adjacency list.
Below is how we can save graph using adjacenct list using STL vectors.

N is the number of nodes in the graph.
I is the number of edges in the graph.
a,b are the nodes connected.
Also note that the graph is un-directed graph with edge weight "1".   

 vector<vector<int> > pairs(N);
    for (int i = 0; i < I; ++i) {
        int a, b;
        cin >> a >> b;
        pairs[a].push_back(b);
        pairs[b].push_back(a);
    }


Monday, January 16, 2017

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

Friday, January 13, 2017

Check if a binary tree is s 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;

Geeksforgeeks as PDF offline.


Here are the  pdf files containing Algorithm and Data Structures questions listed on geeksforgeeks website.
Algorithm.pdf ( all questions from the page Algorithms - GeeksforGeeks )
DS.pdf ( all questions from the page Data Structures - GeeksforGeeks )

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.
  • Google is your friend.
  • Feel free to inbox me if you have any other doubt.