Monthly Archives: June 2016

c++ STL map

dictionary data structure.

 

example with question answer :

Problem
Given names and phone numbers, assemble a phone book that maps names to their respective phone numbers.

After this dictionary is created you will then be given an unknown number of names to query your phone book for; for each queried, print the associated entry from your phone book (in the form name=PhoneNumber ) or  ( Not Found) if there is no entry for .

Input Format

The first line contains an integer,N , denoting the number of entries in the phone book.
Each of the subsequent lines describes an entry in the form of space-separated values on a single line. The first value is a friend’s , and the second value is an -digit .

After the lines of phone book entries, there are an unknown number of lines of queries. Each line (query) contains a to look up, and you must continue reading lines until there is no more input.

 

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int N;
cin>>N;
map<string,int> dict;
for(int i = 0; i < N; i++){
string name;
int number;
cin>>name;
cin>>number;
dict[name] = number;
}
string line;
vector<string> inp;
//remove top new line
getline(std::cin, line);
while (getline(std::cin, line)){
inp.push_back(line);
}
for(int i = 0; i < inp.size(); i++){
if(dict.find(inp[i]) != dict.end()){
cout<<inp[i]<<"="<<dict[inp[i]]<<endl;
}
else{
cout<<"Not found"<<endl;
}
}
return 0;
}

ffmpeg: libavformat, libavcodec and x264

ffmpeg is great tool for almost all your video processing playing need. For general purpose it has everything given as command line. Most of the time you only need to find the correct command for your specific requirement.
Rarely you need more control on your video like encoding in different library and then muxing using ffmpeg. Or say you are streaming on network and it is not of any particular format. You don’t want the overhead of coding to make it of some format and then stream and decode via ffmpeg. In those scenario you have to get away with ffmpeg wrapper and just want to do it in your own way by using core API’s.

ffmpeg is easy in that way also once you get the feel of it. There are just couple of functionality which you need to achieve all this. Sometime you don’t even need all ffmpeg and just getaway with libavcodec swscale etc.

If you have the input file for processing you can just check out the sample code provided. You just have to set the input file for reading and you are done. If your requirement is providing your own input and also getting output in code and not in a file or stream.
I wrote my own wrapper on ffmpeg for windows to get acess to core API I needed.

Once you have the wrapper say ffmpeg_wrapper.c just compile it like

gcc -I. -c -o ffmpeg_wrapper.o ffmpeg_wrapper.c
gcc -shared -o ffmpeg_wrapper.dll ffmpeg_wrapper.o -L. -lavformat -lavcodec -lavutil -lWs2_32 -liconv

any other library you need.

Include are done like this:

#include "libavformat/avformat.h"
#include "libavutil/opt.h"
#include "libavutil/mathematics.h"
#include "libavutil/timestamp.h"
#include "libswscale/swscale.h"
#include "libswresample/swresample.h"

#define DLLEXPORT __declspec(dllexport)
#define CDECL __cdecl

I faced a problem while I was doing encoding via separate h264 dll and then passing the input for muxing via ffmpeg. The problem was with timing I know there are some option in h264 to set the timing info but it was not working out. So I generated the timing using ffmpeg itself.

static int write_frame(AVFormatContext *fmt_ctx, const AVRational *time_base, AVStream *st, AVPacket *pkt)
{
/* rescale output packet timestamp values from codec to stream timebase */
pkt->pts = av_rescale_q_rnd(pkt->pts, *time_base, st->time_base, AV_ROUND_NEAR_INF|AV_ROUND_PASS_MINMAX);
pkt->dts = av_rescale_q_rnd(pkt->dts, *time_base, st->time_base, AV_ROUND_NEAR_INF|AV_ROUND_PASS_MINMAX);
pkt->duration = av_rescale_q(pkt->duration, *time_base, st->time_base);
pkt->stream_index = st->index;</code>

/* Write the compressed frame to the media file. */
log_packet(fmt_ctx, pkt);
return av_interleaved_write_frame(fmt_ctx, pkt);
}

 

Heap in cpp stl

make_heap: rearrange elements in a range such that they form a heap

 

make_heap(begin,end, comparator)

comparator is a boolean function optional

pop_heap

push_heap

if v is a vector then

std::make_heap (v.begin(),v.end());

v.front() will give you maximum [default is maxheap without comparator]

You can pass the comparator function to each operation to maintain the heap property.

get the element by v.front()

Now pop the element using

pop_heap (v.begin(),v.end()); // can also pass comparator here 
Pop element from heap and rearranges the elements in the heap range [first,last) in such a way that the part considered a heap is shortened by one: The element with the highest value is moved to (last-1).
While the element with the highest value is moved from first to (last-1) (which now is out of the heap), the other elements are reorganized in such a way that the range [first,last-1) preserves the properties of a heap.
Now to actually remove the element from the vector you can use:

v.pop_back();

So a range can be organized into a heap by calling make_heap. After that, its heap properties are preserved if elements are added and removed from it using push_heap and pop_heap, respectively.


pop_heap (v.begin(),v.end()); v.pop_back();
  std::cout << "max heap after pop : " << v.front() << '\n';

 

push_heap (v.begin(),v.end());

Given a heap in the range [first,last-1), this function extends the range considered a heap to [first,last) by placing the value in (last-1) into its corresponding location within it.

 v.push_back(99); std::push_heap (v.begin(),v.end()); std::cout << "max heap after push: " << v.front() << '\n'; 

Git: Server setup

git best guide
http://rogerdudler.github.io/git-guide/

 

How to setup a git server

git clone –bare my_project my_project.git
Cloning into bare repository ‘my_project.git’… done.
The output for this command is a little confusing. Since clone is basically a git init then a git fetch, we see some output from the git init part, which creates an empty directory. The actual object transfer gives no output, but it does happen. You should now have a copy of the Git directory data in your my_project.git directory.
cp -Rf my_project/.git my_project.git

Putting the Bare Repository on a Server

Now that you have a bare copy of your repository, all you need to do is put it on a server and set up your protocols. Let’s say you’ve set up a server called git.example.com that you have SSH access to, and you want to store all your Git repositories under the /opt/git directory. You can set up your new repository by copying your bare repository over:

$ scp -r my_project.git user@git.example.com:/opt/git

At this point, other users who have SSH access to the same server which has read-access to the /opt/git  directory can clone your repository by running

$ git clone user@git.example.com:/opt/git/my_project.git

Examples

Clone from upstream:

$ git clone git://git.kernel.org/pub/scm/.../linux.git my-linux
$ cd my-linux

Make a local clone that borrows from the current directory, without checking things out:

$ git clone -l -s -n . ../copy
$ cd ../copy
$ git show-branch

Clone from upstream while borrowing from an existing local directory:


$ git clone --reference /git/linux.git \
git://git.kernel.org/pub/scm/.../linux.git \
my-linux
$ cd my-linux

Create a bare repository to publish your changes to the public:

$ git clone --bare -l /home/proj/.git /pub/scm/proj.git

created a user for linux called git
everyone just install git on their machine
configure git with below command:


git config --global user.email "nandan.dubey@abcde.com"
git config --global user.name "Nandan Dubey"
git status
git add .
git commit -m "first commit"
$ git remote -v
origin ssh://git@10.0.0.31:/home/git/hello_world.git (fetch)
origin ssh://git@10.0.0.31:/home/git/hello_world.git (push)

now there are two ways for any project. either it is a brand new project. Correct for all project right now as git server repository is brand new so no projects exists right now.
So for brand new project first you need to create

git init hello_world

git remote remove origin

Instead of removing and re-adding, you can do this:

git remote set-url origin git://new.url.here

git clone –bare hello_world hello_world.git
scp -r hello_world.git git@10.0.0.31:/home/git
To copy an exisiting project use
git clone ssh://git@10.0.0.31:/home/git/hello_world.git
make changes do git add and git commit
finally do git push
git push origin master
folder files:
git init
git add .
git commit -m “first commit”
git remote add origin ssh://git@10.0.0.31:/home/git/test.git

Now, you can set up an empty repository for them by running git init with the –bare option, which initializes the repository without a working directory:

$ cd /opt/git
$ mkdir project.git
$ cd project.git
$ git --bare init

Then, John, Josie, or Jessica can push the first version of their project into that repository by adding it as a remote and pushing up a branch. Note that someone must shell onto the machine and create a bare repository every time you want to add a project. Let’s use git server as the hostname of the server on which you’ve set up your ‘git’ user and repository. If you’re running it internally, and you set up DNS for git server to point to that server, then you can use the commands pretty much as is:

# on Johns computer
$ cd myproject
$ git init
$ git add .
$ git commit -m 'initial commit'
$ git remote add origin ssh://git@10.0.0.31:/home/git/test.git
$ git push origin master

At this point, the others can clone it down and push changes back up just as easily:


$ git clone git@gitserver:/opt/git/project.git
$ cd project
$ vim README
$ git commit -am 'fix for the README file'
$ git push origin master

cd ~/.sshls -al# Lists the files in your .ssh directory

ssh-keygen -t rsa -C “your_email@example.com”# Creates a new ssh key, using the provided email as a label# Generating public/private rsa key pair.# Enter file in which to save the key (/c/Users/you/.ssh/id_rsa): [Press enter]

Enter passphrase (empty for no passphrase): [Type a passphrase]# Enter same passphrase again: [Type passphrase again]

Which should give you something like this:

# Your identification has been saved in /c/Users/you/.ssh/id_rsa.# Your public key has been saved in /c/Users/you/.ssh/id_rsa.pub.# The key fingerprint is:# 01:0f:f4:3b:ca:85:d6:17:a1:7d:f0:68:9d:f0:a2:db your_email@example.com

Then add your new key to the ssh-agent:

ssh-add ~/.ssh/id_rsa

Run the following code to copy the key to your clipboard.

clip < ~/.ssh/id_rsa.pub# Copies the contents of the id_rsa.pub file to your clipboard

ssh -T git@github.com# Attempts to ssh to github

ref: https://git-scm.com/

C++ STL std::array

A hybrid between c array and cpp vector but with lot of difference. Size has to be known at compile time. It can’t be dynamic.

Initialized as


std::array myarray;

5 is the size of the array must be known at compile time. You can access elements by [] (array) operator but this will not give in size check. For size check use at operator.


myarray.at(i)

myarray.size()

sort(myarray.begin(),myarray.end(), comparator)

Prim’s MST (Minimum Spanning Tree)

Given a graph with N nodes and M edges (Undirected) with positive weights. Find the minimum spanning tree. A tree with minimum overall weight edge. This is cover all nodes of the original graph if possible. You will be given a starting point S. Just in case the graph is not connected. Then you can find the MST which contains S.

 

Input Format

First line has two integers , denoting the number of nodes in the graph and , denoting the number of edges in the graph.

The next lines each consist of three space separated integers , first two integers are the two nodes between which the  edge exists, last/third integer is the weight of the edge.

The last line has an integer , denoting the starting node.

Nodes are numbered from 1 to N.

There can be multiple edges between same pair of nodes. Consider them as multiple edges.

 

Sample input:

3 3
1 2 2
1 3 3
3 2 6
1

Sample Output

5

 

Solution:

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

struct edge{
int begin;
int end;
int weight;
};
//minHeap
bool comp(const edge& a, const edge& b){
return (a.weight > b.weight);
}

void print(edge e){
cout<<e.begin<<" -> "<<e.end<<" w: "<<e.weight<<endl;
}
void prims(vector <vector <edge> > &adj, int start, int V){
vector <edge> minHeap;
int result = 0;
for(int i = 0; i < adj[start].size(); i++){
minHeap.push_back(adj[start][i]);
//print(adj[start][i]);
}
make_heap (minHeap.begin(),minHeap.end(), comp);
vector <bool> visited(V);
visited[start] = true;
while(!minHeap.empty()){
edge e = minHeap.front();
//cout<<"popped ";
//print(e);
pop_heap(minHeap.begin(), minHeap.end(),comp);
minHeap.pop_back();
if(!visited[e.end]){
visited[e.end] = true;
result += e.weight;
//cout<<"res: "<<result<<endl;
for(int i = 0; i < adj[e.end].size(); i++){
minHeap.push_back(adj[e.end][i]); push_heap(minHeap.begin(), minHeap.end(), comp);
//cout<<"push ";
//print(adj[e.end][i]);
}
}
}
cout<<result<<endl;
}

int main() {
int V, E, S;
cin>>V;
cin>>E;
vector <vector <edge> > adj(V);
for(int i = 0; i < E; i++){
int start, end, weight;
cin>>start;
cin>>end;
cin>>weight;
start--;end--;
edge e1;
e1.end = end;
e1.weight = weight;
e1.begin = start;
adj[start].push_back(e1);
edge e2;
e2.end = start;
e2.weight = weight;
e2.begin = end;
adj[end].push_back(e2);
}
cin>>S;
S--;
prims(adj,S, V);
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}

Max Sum

Given an array of positive numbers, find the maximum sum of a sub-sequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.

Input:

The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is N,N is the size of array.
The second line of each test case contains N input C[i].

Output:

Print the maximum sum of a sub-sequence.

 

C++ Solution


#include <iostream>
#include <vector>

using namespace std;

/*
T denotes maxsum then
T(N) = max(A[N-1] + T(N-2), T(N-1))
*/
void printMaxSum(vector <int> inp)
{
int size = inp.size();
vector <int> maxSum;
if(size <= 0)
return;
else
{
if(size == 1)
{
cout<<inp[0]<<endl;
return;
}
else
{
maxSum.push_back(inp[0]);
maxSum.push_back(max(inp[0],inp[1]));
}
}
for(int i = 2; i < size; i++)
{
int included = inp[i] + maxSum[i - 2];
int excluded = maxSum[i-1];
maxSum.push_back(max(included,excluded));
}
cout<< maxSum[size-1]<<endl;
}

int main() {
int T = 0;
//read number of test cases
cin>>T;
vector < vector <int> > allInputs;
for (int i = 0; i < T; i++)
{
int N = 0;
cin>>N;
//read all N inputs in a vector
vector <int> arr;
for(int j = 0; j < N; j++)
{
int inp = 0;
cin>>inp;
arr.push_back(inp);
}
allInputs.push_back(arr);
}

for(int i = 0; i < T; i++)
{
printMaxSum(allInputs[i]);
}

return 0;
}