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.

.