Word-Break Problem (DP)

Given an input string and a dictionary of words, find out if the input string can be segmented into a space-separated sequence of dictionary words.

Suppose dp[i] will be true if string(0....i) can be segmented into space separated dictionary words.

So dp[i] = true in the following two cases->
1.  If( prefix(0...i) will be present in the dictionary.
2. for each j less than i
     dp[j] is true and substr starting from j and of len i-j will be present in dictionary.

Here is the working code for the same.

 bool wordBreakDP(string s)  
 {  
      int n = s.length();  
      int dp[n+1];  
      memset(dp,false,sizeof(dp));  
      dp[0] = true;  
      for(int i=1;i<=n;i++){  
           if(isPresent(s.substr(0,i)))  
                dp[i] = true;  
           else{  
                dp[i]=false;  
                for(int j=i;j>0;j--){  
                     if(dp[j] && isPresent(s.substr(j,i-j))){  
                          dp[i]=true;  
                          break;  
                     }  
                }  
           }  
      }  
      return dp[n];  
 }  

FloydWarshall Algorithm

#include<bits/stdc++.h>
#include "iostream"
using namespace std;

#define INF 10000

#define n 4
#define m 4

void floydWarshall(int distance[][4])
{
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            int minimum = distance[i][j];
            for(int k=i+1;k<j;k++)
                    minimum = min(minimum,distance[i][k]+distance[k][j]);
            distance[i][j] = minimum;
        }

    for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            cout<<distance[i][j]<<" ";
            cout<<endl;
        }
}


int main()
{
    int graph[4][4] = { {0,   5,  INF, 10},
                    {INF,  0,  3,  INF},
                    {INF, INF, 0,   1},
                    {INF, INF, INF, 0} };

    int distance[4][4];

    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            distance[i][j] = graph[i][j];   

    floydWarshall(distance);   
}

Operating System interview prep

Note: Content is taken from various sources according to the questions asked in interviews. But you can find all at one place.

Operating System

Fork : The fork call basically makes a duplicate of the current process, identical in almost every way (not everything is copied over, for example, resource limits in some implementations but the idea is to create as close a copy as possible).                

Vfork : The basic difference between vfork and fork is that when a new process is created with vfork(), the parent process is temporarily suspended, and the child process might borrow the parent's address space. This strange state of affairs continues until the child process either exits, or calls execve(), at which point the parent process continues.                      

Exec : The exec call is a way to basically replace the entire current process with a new program. It loads the program into the current process space and runs it from the entry point. exec() replaces the current process with a the executable pointed by the function. Control never returns to the original program unless there is an exec() error.

Clone : Clone, as fork, creates a new process. Unlike fork, these calls allow the child process to share parts of its execution context with the calling process, such as the memory space, the table of file descriptors, and the table of signal handlers.

Process VS Thread:

Both processes and threads are independent sequences of execution. The typical difference is that threads (of the same process) run in a shared memory space, while processes run in separate memory spaces.

The major difference between threads and processes is:

1. Threads share the address space of the process that created it; processes have their own address space.
2. Threads have direct access to the data segment of its process; processes have their own copy of the data segment of the parent process.
3. Threads can directly communicate with other threads of its process; processes must use interprocess communication to communicate with sibling processes.
4. Threads have almost no overhead; processes have considerable overhead.
5. New threads are easily created; new processes require duplication of the parent process.
6. Threads can exercise considerable control over threads of the same process; processes can only exercise control over child processes.
7. Changes to the main thread (cancellation, priority change, etc.) may affect the behavior of the other threads of the process; changes to the parent process does not affect child processes.

.

String Evaluation

Working code:

Code assumes that given expression will be valid and there is single digit char only to evaluate.

 

 // Evaluating a string  
 bool isOperator(char op){  
      return ( (op=='+')||( op=='-')||(op=='*')||(op=='/'));  
 }  
 int preference(char op1,char op2){  
      if(op1=='(') return -1;  
      else if(op2=='(') return 1;  
      if(op1=='+' || op1=='-'){  
           if(op2=='+'||op2=='-')  
                return 0;  
           else  
                return -1;  
      }  
      else  
           if(op2=='+'||op2=='-')  
                return 1;  
           else  
                return 0;  
 }  
 int applyOperator(int first,char op,int second)  
 {  
      int f = first;  
      int s = second;  
      switch(op){  
           case '+':  
                return f+s;  
                break;  
           case '-':  
                return f-s;  
                break;  
           case '*':  
                return f*s;  
                break;  
           case '/':  
                return f/s;  
      }  
 }  
 int evaluatePostFix(string s){  
      stack<int> st;  
      for(int i=0;i<s.length();i++){  
           if(s[i]>='0' && s[i]<='9')  
                st.push(s[i]-'0');  
           else{  
                int a = st.top();  
                st.pop();  
                int b = st.top();  
                st.pop();   
                int ans = applyOperator(b,s[i],a);  
                //cout<<ans<<" ";  
                st.push(ans);  
           }       
      }  
      return st.top();  
 }  
 string infixToPostfixConversion(string s)  
 {  
      string postfix = ""; // Final postfix conversion of given string  
      stack<char> st;  
      for(int i=0;i<s.length();i++){  
           // If digit is 0 to 9 then directly print it to output  
           if(s[i]>='0' && s[i]<='9'){  
                postfix.push_back(s[i]);  
           }  
           else   
                if(isOperator(s[i])){  
                     if(st.empty())  
                          st.push(s[i]);  
                     else  
                          if( preference(st.top(),s[i])<0)  
                               st.push(s[i]);  
                          else  
                               if(preference(st.top(),s[i])==0){  
                                    postfix.push_back(st.top());  
                                    st.pop();  
                                    st.push(s[i]);  
                               }  
                               else{  
                                    while(!st.empty() && preference(st.top(),s[i])>0){  
                                         //cout<<"in";  
                                         postfix.push_back(st.top());  
                                         st.pop();  
                                    }  
                                    st.push(s[i]);  
                               }  
                }  
                else{  
                     if(s[i]=='(')  
                          st.push('(');  
                     else{  
                          //cout<<s[i]<<" "<<st.size()<<endl;  
                          while(!st.empty() && st.top()!='('){  
                               //cout<<st.top()<<" ";  
                               postfix.push_back(st.top());  
                               st.pop();  
                          }  
                          st.pop();  
                     }            
                }  
      }  
      while(! st.empty())  
      {  
           postfix.push_back(st.top());  
           st.pop();  
      }  
      //cout<<postfix<<endl;  
      return postfix;  
 }  
 int eval(string s){  
      string s1 = infixToPostfixConversion(s);  
      cout<<"Converted String is "<<s1<<endl;  
      return evaluatePostFix(s1);  
 }  
 int main()  
 {  
      cout<<eval("5*(2+(3*4*5)+5/6)")<<endl;;  
      cout<<eval("1+2+3*(4+5)*9+4-5*2");  
      return 0;  
 }  

Evaluation of a string

We can convert the given string to postfix string and then evaluate it.

Consider example for conversion of infix string to postfix string

A * (B + C * D) + E becomes A B C D * + * E +

	current symbol	operator stack	postfix string
1	A		A
2	*	*	A
3	(	* (	A
4	B	* (	A B
5	+	* ( +	A B
6	C	* ( +	A B C
7	*	* ( + *	A B C
8	D	* ( + *	A B C D
9	)	*	A B C D * +
10	+	+	A B C D * + *
11	E	+	A B C D * + * E
12			A B C D * + * E +

A summary of the rules follows:
1. Print operands as they arrive.
2. If the stack is empty or contains a left parenthesis on top, push the incoming operator onto the stack.
3. If the incoming symbol is a left parenthesis, push it on the stack.
4. If the incoming symbol is a right parenthesis, pop the stack and print the operators until you see a left parenthesis. Discard the pair of parentheses.
5. If the incoming symbol has higher precedence than the top of the stack, push it on the stack.
6. If the incoming symbol has equal precedence with the top of the stack, use association. If the association is left to right, pop and print the top of the stack and then push the incoming operator. If the association is right to left, push the incoming operator.
7. If the incoming symbol has lower precedence than the symbol on the top of the stack, pop the stack and print the top operator. Then test the incoming operator against the new top of stack.
8. At the end of the expression, pop and print all operators on the stack. (No parentheses should remain.)


Evaluation of postfix string:

1. For each token  
2. {  
3.     If (token is a number)  
4.     {  
5.         Push value onto stack  
6.     }  
7.   
8.     If (token is an operator)  
9.     {  
10.         Pop 2 top values from the stack  
11.         Evaluate operator using popped values as args  
12.         Push result onto stack  
13.     }  
14. }  

Getting segmentation fault due to array size limit. Try this !

 Use static keyword:

Code:

static int i[2000][2000]; 

Without doing it, it goes to the heap, which is limited in size by the linker (can be something like 1 megabyte) and is not suitable for storing large variables.

Be aware that your function is no more reentrant after that.

or

Assign Dynamic allocation to array:
 

Code:

int **array=malloc(2000*2000*sizeof(int));

or something similar. or use the fancy "new" keyword in C++.

(for those who say malloc is not C++ enough, that may be true, but it's still functional)

Quick Sort With custom comparator function

Function Prototype:

void qsort (void* base, size_t num, size_t size,
            int (*comparator)(const void*,const void*));


The comparator function takes two pointers as arguments (both type-casted to const void*) and defines the order of the elements by returning (in a stable and transitive manner


int comparator(const void* p1, const void* p2);
Return value meaning
<0 The element pointed by p1 goes before the element pointed by p2
0  The element pointed by p1 is equivalent to the element pointed by p2
>0 The element pointed by p1 goes after the element pointed by p2.

Example:

Suppose we have to sort a given array with order defined by another array.
Given two arrays A1[] and A2[], sort A1 in such a way that the relative order among the elements will be same as those are in A2. For the elements not present in A2, append them at last in sorted order.  

 #include "iostream"   
 #include "bits/stdc++.h"  
 using namespace std;  
 
 int order[100]={2,1,8,3,4};  
 int size_orderArray;  

 int searchInOrderArray(int key){  
  for(int i=0;i<size_orderArray;i++)  
   if(order[i]==key) return i;  
  return -1;  
 }
  
 int comparator(const void* a, const void *b){  
  int index1 = searchInOrderArray(*(const int*)a);  
  int index2 = searchInOrderArray(*(const int*)b);  
  //cout<<index1<<" "<<index2<<endl;  
  if(index1!=-1 && index2!=-1)  
   return index1-index2;  
  if(index1!=-1 && index2==-1)  
   return -1;  
  if(index2!=-1 && index1==-1)  
   return 1;  
  return *(const int*)a-*(const int*)b;  
 }  

 void sortArrayByAnotherArray(int *arr,int n1){  
  qsort((void*) arr,n1,sizeof(int),comparator);  
 }  

 int main()  
 {  
   int ar1[] = {2, 1, 2, 5, 7, 1, 9, 3, 6, 8, 8, 7, 5, 6, 9, 7, 5};  
   int m = sizeof(ar1)/sizeof(ar1[0]);  
   size_orderArray = 5;  
   sortArrayByAnotherArray(ar1,m);  
   for(int i=0;i<m;i++)  
    cout<<ar1[i]<<" ";  
 }  
 

Another Example:
Given an array of words, print all anagrams together. For example, if the given array is {“cat”, “dog”, “tac”, “god”, “act”}, then output may be “cat tac act dog god”

 int comparatorForAnagram(const void* a,const void *b)  
 {  
  string s1 = *(const string*)a;  
  string s2 = *(const string*)b;  
  sort(s1.begin(),s1.end());  
  sort(s2.begin(),s2.end());  
  if(s1==s2)  
   return 0;  
  else  
   if(s1.compare(s2)>0)  
    return 1;  
   else  
    return -1;   
 }  
 void sortAccordingToAnagram(string *words,int n)  
 {  
  qsort((void*)words,n,sizeof(string),comparatorForAnagram);  
  for(int i=0;i<n;i++)  
   cout<<words[i]<<" ";  
 }  

Segment Tree (Range Maximum Query Along with Count of Maximum Element)

 #include<bits/stdc++.h>  
 #include "iostream"  
 using namespace std;  
 class node{  
 public:  
      int data;  
      int l,r;  
      int count;  
      node* left,*right;  
 };  
 node* newNode(int data,int l,int r){  
      node* newN = new node;  
      newN->data = data;  
      newN->l = l;  
      newN->r = r;  
      newN->count = 1;  
      return newN;  
 }  
 int operationOnData(int data1,int data2){  
      return max(data1,data2);  
 }  
 node* buildTree(int arr[],int l,int r)  
 {  
      if(l>r) return NULL;  
      node* nd;  
      if(l==r)  
           nd = newNode(arr[l],l,r);  
      else{  
           nd = newNode(0,l,r);  
           int mid = (l+r)/2;  
           nd->left = buildTree(arr,l,mid);  
           nd->right = buildTree(arr,mid+1,r);  
           nd->data = operationOnData(nd->left->data,nd->right->data);  
           if(nd->left->data==nd->right->data) nd->count = nd->left->count+nd->right->count;  
           else{  
                if(nd->left->data > nd->right->data) nd->count = nd->left->count;  
                else nd->count = nd->right->count;  
           }  
      }  
      return nd;  
 }  
 pair<int,int> getMax(node* root,int l, int r){  
      if(root->l>=l && root->r<=r){  
           return {root->data,root->count};  
      }  
      else  
      if(root->r<l ||root->l>r)  
           return {INT_MIN,0} ;   
      else{  
           pair<int,int> left = getMax(root->left,l,r);  
           pair<int,int> right = getMax(root->right,l,r);  
           if(left.first==right.first){  
                return {left.first,left.second+right.second};  
           }   
           else if(left.first>right.first){  
                return {left.first,left.second};  
           }  
           else   
                return{right.first,right.second};  
      }  
 }  
 int height(node* root)  
 {  
      if(root==NULL) return 0;  
      int lHeight = height(root->left);  
      int rHeight = height(root->right);  
      return lHeight>rHeight?lHeight+1:rHeight+1;  
 }  
 void printLevel(node* root,int d)  
 {  
      if(root==NULL) return;  
      if(d==1) cout<<root->data<<" "<<root->count<<" "<<root->l<<" "<<root->r<<endl;  
      printLevel(root->left,d-1);  
      printLevel(root->right,d-1);  
 }  
 void levelorder(node* root)  
 {  
      for(int d =1; d<=height(root) ;d++)  
           printLevel(root,d);  
 }  
 int main()  
 {  
       int n,m;  
       //cin>>n>>m;  
       n=5;m=1;  
       int arr[100000] = {3,1,3,2,1};  
       for(int i=0;i<n;i++);  
            //cin>>arr[i];  
       node* root = buildTree(arr,0,n-1);  
       while(m--){  
            int l,r;  
            //cin>>l>>r;  
            pair<int,int> p = getMax(root,l,r);  
            cout<<"Max Element is "<<p.first<<" and its Count in given range is ";  
            cout<<p.second<<endl;  
       }  
 }  

Segment Tree Implementation in C++

1. buildTree function creates the segment tree.
2. getSum() function return the sum.

 #include<bits/stdc++.h>  
 #include "iostream"  
 using namespace std;  
 class node{  
 public:  
      int data;  
      int l,r;  
      node* left,*right;  
 };  
 node* newNode(int data,int l,int r){  
      node* newN = new node;  
      newN->data = data;  
      newN->l = l;  
      newN->r = r; 

     newN->left = NULL;

     newN->right = NULL; 

 return newN;  
 }  
 int operationOnData(int data1,int data2){  
      return data1+data2;  
 }  
 node* buildTree(int arr[],int l,int r)  
 {  
      if(l>r) return NULL;  
      node* nd;  
      if(l==r)  
           nd = newNode(arr[l],l,r);  
      else{  
           nd = newNode(0,l,r);  
           int mid = (l+r)/2;  
           nd->left = buildTree(arr,l,mid);  
           nd->right = buildTree(arr,mid+1,r);  
           nd->data = operationOnData(nd->left->data,nd->right->data);  
      }  
      return nd;  
 }  
 int getSum(node* root,int l, int r){  
      if(root->l>=l && root->r<=r){  
           return root->data;  
      }  
      else  
      if(root->r<l ||root->l>r)  
           return 0;   
      else  
           return getSum(root->right,l,r)+getSum(root->left,l,r);  
 }  
 void update(node* root,int arr[],int index,int newValue,int l,int r)  
 {  
      if(l>r) return;  
      if(!root) return;  
      if(l==r && l == index)  
           root->data = newValue;  
      else{  
           int mid = (l+r)/2;  
           update(root->left,arr,index,newValue, l,mid);  
           update(root->right,arr,index,newValue,mid+1,r);  
           int left =0,right=0;  
           if(root->left) left = root->left->data;  
           if(root->right) right = root->right->data;  
           if(left || right)  
           root->data = operationOnData(left,right);  
      }  
 }  
 int height(node* root)  
 {  
      if(root==NULL) return 0;  
      int lHeight = height(root->left);  
      int rHeight = height(root->right);  
      return lHeight>rHeight?lHeight+1:rHeight+1;  
 }  
 void printLevel(node* root,int d)  
 {  
      if(root==NULL) return;  
      if(d==1) cout<<root->data<<" "<<root->l<<" "<<root->r<<endl;  
      printLevel(root->left,d-1);  
      printLevel(root->right,d-1);  
 }  
 void levelorder(node* root)  
 {  
      for(int d =1; d<=height(root) ;d++)  
           printLevel(root,d);  
 }  
 int main()  
 {  
       int arr[] = {1, 3, 5, 7, 9,11};  
         int n=sizeof(arr)/sizeof(int);  
         node* root = buildTree(arr,0,n-1);  
         update(root,arr,0,3,0,n-1);  
        cout<<getSum(root,0,1);  
 }  

DP For Beginners

http://www.spoj.com/problems/COINS/

 #include<bits/stdc++.h>  
 #include "iostream"  
 using namespace std;  
 map<long long,long long> dp;  
 long long coins(long long i)  
 {       
      if(i>=0 && i<12)  
      {  
           if(! dp[i])  
                dp[i] = i;  
           return dp[i];  
      }  
      else  
      {  
           if(! dp[i]){  
                dp[i] = coins(i/2)+coins(i/4)+coins(i/3);   
           }  
           return dp[i];  
      }  
 }  
 int main()  
 {  
      long long n;  
      while(cin>>n){  
           cout<<coins(n)<<endl;  
      }  
 }  

Reverse alternate levels of a perfect binary tree.

Given a Perfect Binary Tree, reverse the alternate level nodes of the binary tree.

Code:

 void reverseAlternateLevelOfPrefectBTUtil(node* left,node* right,int level,int d){  
      if(left==NULL || right==NULL) return;  
      if(level%2!=0 && level==d){  
           int a= left->data;  
           int b= right->data;  
           swap(&a,&b);  
           left->data = a;  
           right->data = b;  
      }  
      reverseAlternateLevelOfPrefectBTUtil(left->left,right->right,level+1,d);  
      reverseAlternateLevelOfPrefectBTUtil(left->right,right->left,level+1,d);  
 }  
 void reverseAlternateLevelOfPrefectBT(node* root)  
 {  
      for(int i=1; i<=height(root); i+=2)  
      reverseAlternateLevelOfPrefectBTUtil(root->left,root->right,1,i);  
      cout<<"Level Order After modification\n";  
      levelorder(root);  
 }  

Binary Tree Basic Functions

 class node  
 {  
 public:  
   int data;  
   struct node *left,*right,*random;  
   bool isThreaded ;  
 };  
 node* newNode(int data)  
 {  
   node* neNode = new node;  
   neNode->data = data;  
   neNode->left = NULL;  
   neNode->right = NULL;  
   neNode->isThreaded =false;  
   return neNode;  
 }  
 void inorder(node* root)  
 {  
   if(!root) return;  
   inorder(root->left);  
   cout<<root->data<<" ";  
   inorder(root->right);  
 }  
 int height(node* root)  
 {  
   if(root==NULL) return 0;  
   int lHeight = height(root->left);  
   int rHeight = height(root->right);  
   return lHeight>rHeight?lHeight+1:rHeight+1;  
 }  
 int main()  
 {  
    node *root = newNode(1);  
   root->left = newNode(2);  
   root->right = newNode(3);  
   //root->left->left = newNode(1);  
   //root->left->right = newNode(5);  
   root->right->left = newNode(4);  
   root->right->left->left = newNode(6);  
   root->right->left->left->left = newNode(8);  
   root->right->left->left->right = newNode(9);  
   root->right->right = newNode(5);  
   //root->right->right->left = newNode(9);  
   root->right->right->right = newNode(7);  
    root->right->right->right->left = newNode(10);  
    cout<<closestLeafDistance(root,5);  
 }  

Quick Syntax Reminder Basic Data Structure C++

Maps:

maps<int,int> m;
m[key1] = value1;
m[key2] = value2;

How to iterate
for(map<int,int>::iterator it = m.begin() ; it != m.end(); it++){
                cout<<"Key is "<<it->first<<" ";
cout<<"Value is "<<it->second<<endl;
}

List:

list<int> *adj = new list<int>[size];

adj[index1].push_back(value);

 for(list<int>::iterator i = g->adj[u].begin(); i!=g->adj[u].end(); ++i){

cout<<"->"<<*i;

}

Overload < operator for Sort() Function 

class freq
{
public:
int data;
int count;
};

inline bool operator<(const freq& a, const freq& b)
{
return a.count <= b.count;
}
 
sort(arr,arr+n);