Knowlarity Communications

[1.] Given N numbers , [N< =10^5] we need to count the total pairs of numbers that have a difference of K. [K>0]

Input Format:
1st line contains N & K (integers).
2nd line contains N numbers of the set. All the N numbers are assured to be distinct.
Output Format:
One integer saying the no of pairs of numbers that have a diff K.

Sample Input #00:
5 2
1 5 3 4 2

Sample Output #00:
3

Sample Input #01:
10 1
363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635 491595254 879792181 1069262793

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

#define MIN(x, y) ((x) < (y)?(x):(y))

int findDiffK(int arr[], int n, int k){
int count = 0;
sort(arr, arr+n);
int l = 0;
int r = 0;
while(r<n){
if(arr[r] - arr[l] == k){
count++;
l++;
r++;
}
else if(arr[r]-arr[l] > k)
l++;
else
r++;
}
return count;
}


int main(int argc, char* argv[]){
int N = 0; int K =0;
cin >> N;
cin >> K;

int *arr = new int[N];

for(int i = 0; i<N; i++){
cin >> arr[i];
}

cout << findDiffK(arr, N, K);
delete arr;
arr = 0;

return 0;
}

Time Complexity: O(n log(n) )




[2.] For two strings A and B, we define similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings "abc" and "abd" is 2. While the similarity of strings "aaa" and "aaab" is 3. Calculate the sum of similarities of a string with each of its suffixes.

Input format: 
1st line                     : N (number of strings to follow)
2nd to (N+1)th line  : input strings


//C++ implementation:
//----------------------

#include <iostream>
#include <string.h>
using namespace std;

const int maxLen = 100000;


int similaritySum(const char*str){
int count = 0;

int len = strlen(str);
for(int i=0; i<len; i++){
char *suffix = (char*)str + i;
int suffixLen = len-i;

int similarity = 0;
for(int j=0; j<suffixLen; j++){
if(str[j] == suffix[j])
++similarity;
else break;
}
count += similarity;
}


return count;
}


int main(int argc, char* argv[]){
int N = 0;
cin >> N;

for(int i=0; i<N; i++){
char buff[maxLen] = {0};
cin >> buff;
cout << similaritySum(buff);
}
return 0;
}



[3.] Given an array arr[] of integers, find out the difference between any two elements such that larger element appears after the smaller in arr[].

Example: 
if arr[] = {2, 3, 10, 6, 4, 8, 1}, then the returned value should be 8 (10-2).

//C++ implementation

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;

int maxDifference(vector < int > a) {
    if(a.size() <= 1)
return -1;
    int maxDiff = a[1]-a[0];
    int minSoFar = a[0];
    
    for(vector<int>::iterator it = a.begin()+1; it != a.end(); it++){
if((*it - minSoFar) > maxDiff)
         maxDiff = *it - minSoFar;
if(*it < minSoFar){
    minSoFar = *it;
}
    }
       
    return maxDiff;
}

int main() {
    int res;

    int _a_size;
    cin >> _a_size;
    cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n');
    vector<int> _a;
    int _a_item;
    for(int _a_i=0; _a_i<_a_size; _a_i++) {
        cin >> _a_item;
        _a.push_back(_a_item);
    }

    res = maxDifference(_a);
    cout << res;

    return 0;
}



[4.] Super stack:
Design a stack that supports these 3 operations:
- push(): pushes an element to the top of the stack and prints the top element.

- pop(): removes the top element from the stack and prints the top element. If top element is not there print "EMPTY", withour quotes.

- inc(n1, n2): Increases the value of bottom n1 elements of stack by n2, and prints the top element. if top element is not present, print "EMPTY", without quotes.

// C++ Implementation

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

int main() {
    int n = 0;
    cin >> n;
    vector<long >v;
    
    for(int i=0; i<n; i++){
        char op[256] = {0};
        cin >> op;
        if(!strcmp(op, "push")){
            long pushNum = 0;
            cin >> pushNum;
            v.push_back(pushNum);
            cout << pushNum << endl;
        }
        else if(!strcmp(op, "inc")){
            long n1 = 0; 
            long n2 = 0;
            cin >> n1;
            cin >> n2;
            for(int j=0; j<n1; ++j){
                v[j] += n2;
            }
            if(v.size())
                cout << v[v.size()-1] << endl;
            else
                cout << "EMPTY" << endl;
        }
        else if(!strcmp(op, "pop")){
            v.pop_back();
            if(v.size())
                cout << v[v.size()-1] << endl;
            else
                cout << "EMPTY" << endl;
        }
    }
    return 0;
}