jeetscoder
BAN USER#include <iostream>
#include <vector>
using namespace std;
void findAllPairs(int a[],
int n,
int num,
std::vector<std::pair<int,int> >& pairs);
int partition(int a[], int start, int end, int pivot);
void quicksort(int a[], int n);
void qsort(int a[], int start, int end);
void printArr(int a[], int n)
{
cout<<endl;
for(int i=0;i<n;++i)
{
cout<<a[i]<<",";
}
cout<<endl;
}
int main()
{
std::vector<std::pair<int,int> > pairs;
int a[] = {3,5,9,10,2,1,-2,-3};
int n = 6;
findAllPairs(a,sizeof(a)/sizeof(int), n, pairs);
for(int i=0;i<pairs.size();++i)
{
cout<<"pair["<<i<<"] = "<<pairs.at(i).first<<","<<pairs.at(i).second<<endl;
}
return 0;
}
void findAllPairs(int a[], int n, int num, std::vector<std::pair<int,int> >& pairs)
{
if (n <= 1)
{
return; //no pair.
}
cout<<"Array before sorting."<<endl;
printArr(a,n);
quicksort(a,n);
cout<<"Array after sorting."<<endl;
printArr(a,n);
int start = 0;
int end = n-1;
while(start < end)
{
if (a[start] + a[end] == num)
{
pairs.push_back(std::make_pair(a[start], a[end]));
++start;
--end;
}
else if (a[start] + a[end] < num)
{
++start;
}
else
{
--end;
}
}
}
void quicksort(int a[], int n)
{
if (n <= 0)
return;
int start = 0;
int end = n-1;
qsort(a, start, end);
}
void qsort(int a[], int start, int end)
{
if (start < end)
{
int pivot = start;
int j = partition(a, start, end, pivot);
int temp = a[pivot];
a[pivot] = a[j];
a[j] = temp;
qsort(a, start, j-1);
qsort(a, j+1, end);
}
}
int partition(int a[], int start, int end, int pivot)
{
while(start < end)
{
while(a[start] <= a[pivot] && start < end)
++start;
while(a[end] > a[pivot])
--end;
if (start < end)
{
int temp = a[start];
a[start] = a[end];
a[end] = temp;
}
}
return end;
}
#include <iostream>
#include <queue>
#include <fstream>
using namespace std;
void printLastNLines(const std::string& fname, int n);
int main()
{
std::string fname = "myfile.txt";
int n=10;
printLastNLines(fname, n);
return 0;
}
void printLastNLines(const std::string& fname, int n)
{
ifstream infile(fname.c_str());
if (!infile.is_open())
{
cout<<"File opening error."<<endl;
return;
}
std::queue<std::string> lines;
std::string line;
while (std::getline(infile, line))
{
if (lines.size() >= n)
{
lines.pop();
}
lines.push(line);
}
infile.close();
while(!lines.empty())
{
cout<<"line = "<<lines.front()<<endl;
lines.pop();
}
}
int findPivot(int a[], int n)
{
if (n <= 0)
return -1;
int start = 0;
int end = n-1;
while(a[start] > a[end])
{
int mid = (start+end)/2;
if (a[mid] > a[end])
start = mid+1;
else
end = mid;
}
return start;
}
Q.1b: solution: to find out the maximum loss just reverse the logic so that you take worstBuy and worstSell price, by finding non-increasing runs of array and then comparing with them with the any last found non-increasing runs of array.
Q.1c: In this case just consider the non-decreasing runs of array of length k only.
The solution is :
Try to find the non-decreasing runs of array. When such a run is found (lets say [start,end], then set currBestBuy = a[start], currBestSell = a[end].
Also if this is not the first run, then check whether (currBestSell - bestBuy) > (currBestSell- currBestBuy) and if so that update the bestSell = currBestSell.
When the entire array is iterated over entirely the bestbuy and bestSell will store the best buy price and best sell price respectively.
Assume that the penalty attached to the steps of the two stairs is given in two integer array stair_a[] and stair_b[] of the same size (n).
Iterate through the both array to find out the steps to be taken by comparing the penalty value of each index (steps) individually.
#include <iostream>
using namespace std;
int main()
{
int stair_a[] = {3,4,6,1,2};
int stair_b[] = {1,0,7,5,3};
printSteps(stair_a, stair_b, sizeof(stair_a)/sizeof(int));
return 0;
}
void printSteps(int stair_a[], int stair_b[], int n)
{
if (n <= 0)
{
return;
}
int p1 = 0;
int p2 = 0;
for(int i=0;i<n;++i)
{
if (stair_a[i] <= stair_b[i])
{
cout<<"climb step "<<i+1<<" on stair_a"<<endl;
}
else
{
cout<<"climb step "<<i+1<<" on stair_b"<<endl;
}
}
}
The question is to find out how many numbers are required to make a sum equal to a given integer N.
The array should contain at least first x natural numbers to make this sum.
The sum can be given by sum of first x natural numbers N = x*(x+1)/2.
So to know how many numbers are required in the array solve the equation to get X.
#include <iostream>
#include <math.h>
using namespace std;
//Get the element to be added by deducting
// the lenght of the given array from (-1+sqrt(1+8n))/2
int getMinNumElementsToAdd(int lengthOfArr, int n)
{
double TotalElemReqd = ceil((-1+sqrt(8*n+1))/2) - lengthOfArr;
return TotalElemReqd;
}
int main()
{
int a[] = { 1,2,9};
int num = 10;
int lengthOfArr = sizeof(a)/sizeof(int);
int n = getMinNumElementsToAdd(lengthOfArr, num);
cout<<"Number of elements to add = "<<n<<endl;
return 0;
}
Algorithm to find out the topological sorted array:
1. find out the source vertice. Let a[][2] stores the edges in the for of a pairs
a[][2] = {
(a,b)
(c,b)
(a,d)
(a,c)
(c,d)
(d,b)
}
First find out a unique id for each vertex and then for each id check whether any of those doesn't appear in 2nd place of the pair. That will be the source vertex (a vertex having only outgoing edges).
2. traverse the graph and find out the weights of all the vertices. To find out the weight add 1 to the weights of already visited vertices. Each edge will have a weight of 1. So
int calculateWeight()
{
weight(v) = 0;
for(each v1 which is predecessor vertex of v)
{
if (v1 has been visited)
{
weight(v) += (1+ weight(v1));
}
else
{
weight(v) += (1+calculateWeight(v1));
}
}
v.visited = true;
return weight(v);
}
3. traverse the graph doing a BFS and calculate weights of each vertex using calculateWeight function.
4. Sort the vertex as per their weights.
5. Print the id /name of each vertex which will print in topologically sorted order.
Here is the actual C++ code:
- jeetscoder August 10, 2015