CareerCup

Here is the logic behind the question:
The given input has size 7 so you have to fill each position by picking one element from array [1,2,3,4,5,6,7]. Now the given height array of array is [6,3,0,2,2,0,0]. Here first height is 6 it means that 6 elements must be greater than the picking element. So we every time pick the (A[i]+1)th greatest element from the remaining array of [1,2,3,4,5,6,7].

For 1st position A[i] is 6. So pick 7th greatest element that is 1. Remaining array [2,3,4,5,6,7].
For 2nd position A[i] is 3. So pick 4th greatest element that is 4. remaining array [2,3,5,6,7].
For 3rd position A[i] is 0 so pick 1st greatest element that is 7. remaining array [2,3,5,6].
Similar process will run until we fill the all position.

If you use an array, it's O(n^2) time due to the remove operation that copies n/2 elements worst case average.
If you use a tree, (sorted map, red black tree etc) you can get away with O(n*lg(n)) time.

#include <bits/stdc++.h>
using namespace std;
vector<int> generate(const vector<int> &in) {

	int s = in.size();
	vector<int> out(s+1);
	vector<int> inserted;

	for(int i = 1; i <= s; i++)
		inserted.push_back(i);

    int curRemain = s-1;
	for(int i = 1; i <= s; i++)
	{
	    int small = curRemain - in[i-1];
	    out[i]=inserted[small];
	    inserted.erase(inserted.begin()+small);
	    curRemain--;
	}
	out.erase(out.begin());
	return out;
}
int main(){
    vector <int> cool={6,3,0,2,2,0,0};
    vector<int> str_vec = generate(cool);
     for(auto it = str_vec.begin(); it != str_vec.end(); it++) {
         cout << *it << " ";
     }
    return 0;
}

/*
You have given height array of array. Generate the original array.

Input: [6,3,0,2,2,0,0]
Output : [1,4,7,3,2,6,5]

A[i] value in input array is the number of greater element on right side.
November 20, 2017
*/

/*
Here is the logic behind the question:
The given input has size 7 so you have to fill each position by picking one element from array [1,2,3,4,5,6,7]. Now the given height array of array is [6,3,0,2,2,0,0]. Here first height is 6 it means that 6 elements must be greater than the picking element. So we every time pick the (A[i]+1)th greatest element from the remaining array of [1,2,3,4,5,6,7].

For 1st position A[i] is 6. So pick 7th greatest element that is 1. Remaining array [2,3,4,5,6,7].
For 2nd position A[i] is 3. So pick 4th greatest element that is 4. remaining array [2,3,5,6,7].
For 3rd position A[i] is 0 so pick 1st greatest element that is 7. remaining array [2,3,5,6].
Similar process will run until we fill the all position.

If you use an array, it's O(n^2) time due to the remove operation that copies n/2 elements worst case average.
If you use a tree, (sorted map, red black tree etc) you can get away with O(n*lg(n)) time.
*/
#include <bits/stdc++.h>
using namespace std;
vector<int> generate(const vector<int> &in) {

	int s = in.size();
	vector<int> out(s+1);
	vector<int> inserted;

	for(int i = 1; i <= s; i++)
		inserted.push_back(i);

    int curRemain = s-1;
	for(int i = 1; i <= s; i++)
	{
	    int small = curRemain - in[i-1];
	    out[i]=inserted[small];
	    inserted.erase(inserted.begin()+small);
	    curRemain--;
	}
	out.erase(out.begin());
	return out;
}
int main(){
    vector <int> cool={6,3,0,2,2,0,0};
    vector<int> str_vec = generate(cool);
     for(auto it = str_vec.begin(); it != str_vec.end(); it++) {
         cout << *it << " ";
     }
    return 0;
}

/*
Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature.
[73, 74, 75, 71, 70, 76, 72] -> [1, 1, 3, 2, 1, nothing, nothing]
November 22, 2017  
*/
Solution ::
#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int> T={73, 74, 75, 71, 70, 76, 72};
    	vector<int> wait_time(T.size());

    	wait_time[wait_time.size()-1]=0;
    	for(int i=wait_time.size()-2; i>=0; i--){
        	if(T[i]<T[i+1]){
            		wait_time[i]=1;
        	}else{
            		if(wait_time[i+1]==0){
                		wait_time[i]=0;
            		}else{
                		wait_time[i]=wait_time[i+1]+1;
            		}
        	}
    	}
    	for(auto it=wait_time.begin();it!=wait_time.end();it++){
    	    cout<<*it<<" ";
    	}
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
/*
Given an array which is in ascending order till some point and then descending order till end. find peak element

*/
int peak_value(vector<int>a, int start, int end){


    if (start==end)  return a[start];
    if(start>end) return 0;
    int mid=(start+end)/2;
    if(a[mid]<a[mid+1]){

       return peak_value(a,mid+1, end);

    }else if(a[mid]>a[mid+1]){
        if((mid-1)>=0){
            if(a[mid-1]>a[mid]){
                return peak_value(a, start, mid-1);
            }else{
                return a[mid];
            }
        }else{
            return a[mid];
        }

    }

}

int find_the_peak_value(vector<int> a){
    if(a.size()==0){
        return 0;
    }else{
        cout<<"calling first peak_value function"<<endl;
        return (peak_value(a, 0, a.size()-1) );
    }
}
int main(){
    static const int arr[] = {1,2,3,4,5,3,1}; 
    vector<int> vec (arr, arr + sizeof(arr) / sizeof(arr[0]) );
    cout<<find_the_peak_value(vec);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
/*
Given an array which is in ascending order till some point and then descending order till end. find peak element

*/
int peak_value(vector<int>a, int start, int end){


if (start==end) return a[start];
if(start>end) return 0;
int mid=(start+end)/2;
if(a[mid]<a[mid+1]){

return peak_value(a,mid+1, end);

}else if(a[mid]>a[mid+1]){
if((mid-1)>=0){
if(a[mid-1]>a[mid]){
return peak_value(a, start, mid-1);
}else{
return a[mid];
}
}else{
return a[mid];
}

}

}

int find_the_peak_value(vector<int> a){
if(a.size()==0){
return 0;
}else{
cout<<"calling first peak_value function"<<endl;
return (peak_value(a, 0, a.size()-1) );
}
}
int main(){
static const int arr[] = {1,2,3,4,5,3,1};
vector<int> vec (arr, arr + sizeof(arr) / sizeof(arr[0]) );
cout<<find_the_peak_value(vec);
return 0;
}

/*
Input : n = 2 k = 4
Output : 16
We have 4 colors and 2 posts.
Ways when both posts have same color : 4 
Ways when both posts have diff color :
4*(choices for 1st post) * 3(choices for 
2nd post) = 12

Input : n = 3 k = 2
Output : 6
*/
#include<bits/stdc++.h>
using namespace std;
 
// Returns count of ways to color k posts
// using k colors
long countWays(int n, int k)
{
    // To store results for subproblems
    long dp[n + 1];
    memset(dp, 0, sizeof(dp));
 
    // There are k ways to color first post
    dp[1] = k;
 
    // There are 0 ways for single post to
    // violate (same color_ and k ways to
    // not violate (different color)
    int same = 0, diff = k;
 
    // Fill for 2 posts onwards
    for (int i = 2; i <= n; i++)
    {
        // Current same is same as previous diff
        same = diff;
 
        // We always have k-1 choices for next post
        diff = dp[i-1] * (k-1);
 
        // Total choices till i.
        dp[i] = (same + diff);
    }
 
    return dp[n];
}
 
// Driver code
int main()
{
    int n = 3, k = 2;
    cout << countWays(n, k) << endl;
    return 0;
}

Consider a simple matrix like this one:

1 3 5
2 4 6
7 8 9


You can solve this problem in O(k log n) time by merging the rows incrementally, augmented with a heap to efficiently find the minimum element.

Basically, you put the elements of the first column into a heap and track the row they came from. At each step, you remove the minimum element from the heap and push the next element from the row it came from (if you reach the end of the row, then you don't push anything). Both removing the minimum and adding a new element cost O(log n). At the jth step, you remove the jth smallest element, so after k steps you are done for a total cost of O(k log n) operations (where n is the number of rows in the matrix).

For the matrix above, you initially start with 1,2,7 in the heap. You remove 1 and add 3 (since the first row is 1 3 5) to get 2,3,7. You remove 2 and add 4 to get 3,4,7. Remove 3 and add 5 to get 4,5,7. Remove 4 and add 6 to get 5,6,7. Note that we are removing the elements in the globally sorted order. You can see that continuing this process will yield the kth smallest element after k iterations.

(If the matrix has more rows than columns, then operate on the columns instead to reduce the running time.)

Here is a solution

#include <bits/stdc++.h>
    using namespace std;
    void Interleave(string s)
    {
    int left = 1;
    int right = s.length()/2;
    int temp;
    while (left < right)
    {
    for (int i = right; i > left; i--)
    {
    temp = s[i];
    s[i] = s[i - 1];
    s[i - 1] = temp;
    cout<<s<<endl;
    }
    left += 2;
    right += 1;
    }
    cout<<s<<endl;
    }
    int main(){
     string s="abcdefgh";
     Interleave(s);
     return 0;
    }

Output ::
abcedfgh
abecdfgh
aebcdfgh
aebcfdgh
aebfcdgh
aebfcgdh
aebfcgdh

On the one hand, using a hash table, we can dfs/bfs and find connected components on the path graph (add an edge for each adjacent elements) to solve the problem in Θ(n) expected time.

On the other hand, on the algebraic decision tree model, your problem cannot be solved in O(n) time. To see this, take an instance of the set disjointness problem (A, B) and transform it to [3A1, ..., 3An, 3B1 + 1, ..., 3Bn + 1]. Because the set disjointness problem has lower bound [1], your problem has the same bound.

[1] Ben-Or, Michael. Lower bounds for algebraic computation trees.

#include <iostream>

#include<algorithm>

using namespace std;

bool compare(int i,int j)

{

if(i<0 && j<0)

    return false;

else if(i>=0 && j>=0)

    return false;

else

    return i<j;

}

int main() {

// your code goes here

int a[5]={-1,1,3,-2,2};

for(int i=0;i<5;i++)

cout<<a[i]<<" ";

cout<<"\n";

sort(a,a+5,compare);

for(int i=0;i<5;i++)

cout<<a[i]<<" ";

return 0;

}

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

bool isOperator(char c)
{
	if(c == '+' || c == '-' || c == '*' || c == '/')		//	you may add operator here
		return true;
	return false;
}

int main()
{
	string prefix;
	cin >> prefix;
	
	stack<string> st;
	string t1, t2;
	
	int l = prefix.length();
	for (int i = l - 1; i >= 0; i--)
	{
		if (isOperator(prefix[i]))
		{
			t1 = st.top();		st.pop();
			t2 = st.top();		st.pop();
			t2 += prefix[i];
			st.push(t1 + t2);
		}
		else
		{
			t1 = "";
			t1 += prefix[i];
			st.push(t1);
		}
	}
	
	string postfix = st.top();		st.pop();
	cout << postfix << endl;
}

/*
Sample Input  :  -*+ABC*-DE+FG
Sample Output :  AB+C*DE-FG+*-
*/

//C++ Code 
for( int i = a.length()-1, j = b.length()-1; i >= 0 && j >= 0 && a[i] == b[j]; i--;j--);
if ( i < a.length()-1 ) return a.substr(i);
else
return "";

An update to the above code ::

s1.reverse();
s2.reverse();
string s;
for (int i = 0; i < s1.length()&&s2.length(); i++) {
    if (s1[i] == s2[i]) {
        s+=s1[i];
    }
    else {
        break;
    }
}
s.reverse();
cout<<s;

s1.reverse();
s2.reverse();
for (int i = 0; i < s1.length()&&s2.length(); i++) {
    if (s1[i] == s2[i]) {
        System.out.println(s1[i]);
    }
    else {
        break;
    }
}