CareerCup

We need to take care of the zero inside the loop.

void change(arr &A,arr &B){
    int zero=find(A.begin(),A.end(),0)-A.begin();
    if(zero==B.size())
        return ;
    for(int i=0;i<A.size();i++){
            if(A[i]!=B[i]){

                int j=find(A.begin(),A.end(),B[i])-A.begin();
                if(B[i]==0){
                    swap(A[i],A[j]);
                    zero=i;
                    continue;
                }//end if
                swap(A[i],A[zero]);
                swap(A[i],A[j]);
                swap(A[zero],A[j]);
            }//end if
    }//end for
}//end change

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <climits>
#include <queue>
#include <algorithm>
#include <cassert>
#define INF INT_MAX
#define NIL -1
#define PR(A) cout<<endl<<#A<<" = "<<A;
#define INF INT_MAX
using namespace std;
typedef vector<vector<int> > matrix;
typedef vector<int> arr;
typedef unsigned int ui;
vector<vector<int> > & make_matrix(int m,int n,int r=0){
    vector<vector<int> >&q=*(new vector<vector<int> >);
    q.resize(m);
    for(vector<vector<int> >::iterator i=q.begin();i!=q.end();i++){
        (*i).resize(n);
        fill(i->begin(),i->end(),r);
    }//edn fr
    return q;
}//end vector
void printarr(arr &a,int low=0,int high=INT_MAX){
    if(high==INT_MAX){
        high=a.size()-1;
    }//END IF
    cout<<endl;
    for(int i=low;i<=high;i++){
        cout<<a[i]<<' ';
    }//end for
}//end [rint
void printmatrix(matrix &a){
    for(vector<vector<int> >::iterator i=a.begin();i!=a.end();i++){
        cout<<endl;
        for(vector<int> ::iterator j=i->begin();j!=i->end();j++){
            cout<<*j<<" ";
        }//end for
    }//end for
}//end [rint
bool isvalid(vector<vector<char>>&q,int i,int j){
    if(i>=0 && j>=0){
        if(i<q.size() && j<q[0].size())
            return true;
    }
    return false;
}//end isvalid
void dfs(vector<vector<char>>&q,vector<vector<int>>&dp,vector<vector<bool>>&visited,int i,int j,vector<pair<int,int>>&moves){
    int count=0;
    if(dp[i][j]!=-1 || visited[i][j])
    return ;
    visited[i][j]=true;
    for(int k=0;k<moves.size();k++){
        int x=i+moves[k].first;
        int y=j+moves[k].second;
        if(!isvalid(q,x,y))
            continue;
        if(q[x][y]==1+q[i][j]){
           // if(dp[x][y]==-1){
                if(!visited[x][y])
                dfs(q,dp,visited,x,y,moves);
            //}//end if
                count=max(count,dp[x][y]);
        }//en
    }//end for
    dp[i][j]=1+count;
}//end dfs

int main(){
vector<pair<int,int>>moves{{0,-1},{0,1},{-1,0},{1,0},{-1,-1},{1,1},{1,-1},{-1,1}};
vector<vector<char>>q{
		{'a','b','e','d'},{'b','c','f','e'},{'a','b','d','d'}
	};
	vector<vector<bool>>visited(q.size());
	for(auto &i:visited){
        i.resize(q[0].size());
        fill(i.begin(),i.end(),false);
	}//end for
	matrix dp=make_matrix(q.size(),q[0].size(),-1);
	for(int i=0;i<q.size();i++){
        for(int j=0;j<q[0].size();j++){
        if(q[i][j]=='d'){
                dfs(q,dp,visited,i,j,moves);
                cout<<endl<<i<<" "<<j<<" = "<<dp[i][j];
        }//end if
    }//end for
}//end fpr
   return 0;
}

10001 is sparse.But as per your algo, 100000 should be next sparse number , but I think 10101 is also a sparse and next one.

1,1,7,7,3,3,19,19,4,10,10,11,11
It can be easily done by binary search
mid=6,so, arr[mid]=19,we see that 19 is not an answer, but one copy of 19 lies in right subarray, so right subarray must be of odd length, otherwise it contains the single element, so we go to left.(19,19,4,10,10,11,11)
Again notice that mid=9, arr[mid]=10.
but the array to the left contains 10 and is of odd length, so we go to left, i.e.
(19,19,4) becuase [19,19,4](arr[mid]=10)[10,11,11].
again arr[mid]=19, and array to the left is of odd length and contain 19 , so we go to right and eventually end up at 4.

This method uses bitwise operators .It works for all inputs except when the said element is present in multiple of 3.

int func(vector<int>&a){
//Assuming 32-bit integers
    int result=0;
    for(int i=0;i<31;i++){
        int mask=1<<i;
        int count=0;
        for(int k=0;k<a.size();k++){
            if(a[k]&mask){
                count++;
            }//end if
        }//end for
        if(count%3){
            result|=mask;
        }//end if
    }//end for
    return result;
}//end func

Also in linked list, "next" pointers increases the space required.

I think its a trie , and not a suffix tree.

Sample input =
Sam, Ian, technical lead, 2009 / Ian, NULL, CEO,2007/ Fred, Sam, developer, 2010
Build a hash table with key as the manager and the values as their descendents
e.g.
Ian->Sam
Sam->Fred
(Since there was no boss for Ian , we didn't added it but instead recorded it as the top person in the heirarchy).
Now, start with Ian and Print Sam and again using the key Sam we got Fred.

#include <cstdio>
#include <iostream>
#include <stack>
#include <cctype>
#include <cstdlib>
#include <vector>
#include <climits>
#include <queue>
#include <algorithm>
#include <cassert>
#define INF INT_MAX
#define NIL -1
#define PR(A) cout<<endl<<#A<<" = "<<A<<endl;
#define INF INT_MAX
using namespace std;
typedef vector<vector<int>> matrix;
typedef vector<int> arr;
typedef unsigned int ui;
vector<vector<int>> & make_matrix(int m,int n,int r=0){
    vector<vector<int>>&q=*(new vector<vector<int>>);
    q.resize(m);
    for(auto &i:q){
        i.resize(n);
        fill(i.begin(),i.end(),r);
    }//edn fr
    return q;
}//end vector
void printarr(arr &a,int low=0,int high=INT_MAX){
    if(high==INT_MAX){
        high=a.size()-1;
    }//END IF
    cout<<endl;
    for(int i=low;i<=high;i++){
        cout<<a[i]<<' ';
    }//end for
}//end [rint
void printmatrix(matrix &a){
    for(auto i:a){
        cout<<endl;
        for(auto j:i){
            cout<<j<<" ";
        }//end for
    }//end for
}//end [rint
void func(string &s){
    stack<int>q;
    q.push(1);
    int i=s.length()-1;
    vector<int>count(256,0);
    while(i>=0){
        if(s[i]=='('){
            q.pop();
            i--;
        }//end if
        else if(s[i]==' ')
                i--;
        else if(isdigit(s[i])){
                int k=1;
                int num=0;
                while(i>=0 && isdigit(s[i])){

                        num=num+(k*(s[i]-'0'));
                        i--;
                }//end while
                while(i>=0 && s[i]==' ')
                    i--;
                if(isalpha(s[i])){
                        count[s[i]]+=num*q.top();
                        i--;
                }//end if
                else{
                    q.push(num*q.top());
                    i--;
                }//end else
        }//end else if
        else if(isalpha(s[i])){
                count[s[i]]+=q.top();
                i--;
        }//end else if
    }//end while
    for(int i=0;i<count.size();i++){
            if(count[i]){
                    cout<<char(i)<<count[i];
            }//end for
    }//end for
}//end func
int main(){
string s="A2((AB3)2(C2D)4)5";
func(s);
   return 0;
}

How about this, 1c.Here the limitation is that minimum number is among the last k-1 elements.So using the windowing approach , we maintain the list of last k-1 minimum elements and then calculate profit by considering the current element as the selling point .We slide the window to the right and then recalculate the profit using the next element as the current element.

@miranda.zhang You will need to return "I" Only. becuse after that, like and hate doesn't matches.

Can't we apply KMP and find the password substring in the input.

There is no need of visited stuff.Its a tree.it doesn't have cycles

Sort the two arrays and start an imaginary merge process by keeping the index i and j at a and b respectively.Whenever we find a[i]>b[j] and i<j, find the ceil(a[i]) in b[j+1....b.size], that will give us the count of pairs corresponding to each a[i] found.Continuing in this manner, all pairs corresponding to each a[i] can be found in O((M+N)Log(M+N)).

The problem is just a variation of Matrix Chain Multiplication Dynamic Programming.Here is a working code working on all given test cases.

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <climits>
#include <queue>
#include <algorithm>
#include <cassert>
#define INF INT_MAX
#define NIL -1
#define PR(A) cout<<endl<<#A<<" = "<<A;
#define INF INT_MAX
using namespace std;
typedef vector<vector<int>> matrix;
typedef vector<int> arr;
typedef unsigned int ui;
vector<vector<int>> & make_matrix(int m,int n,int r=0){
    vector<vector<int>>&q=*(new vector<vector<int>>);
    q.resize(m);
    for(auto &i:q){
        i.resize(n);
        fill(i.begin(),i.end(),r);
    }//edn fr
    return q;
}//end vector
void printarr(arr &a,int low=0,int high=INT_MAX){
    if(high==INT_MAX){
        high=a.size()-1;
    }//END IF
    cout<<endl;
    for(int i=low;i<=high;i++){
        cout<<a[i]<<' ';
    }//end for
}//end [rint
void printmatrix(matrix &a){
    for(auto i:a){
        cout<<endl;
        for(auto j:i){
            cout<<j<<" ";
        }//end fo

    }//end for
}//end [rint
int solve(vector<int>&a){

    matrix dp=make_matrix(a.size(),a.size(),INT_MIN);
    for(int i=0;i<a.size();i++){
        dp[i][i]=a[i];
    }//end for
    for(int i=0;i<a.size()-1;i++){
        dp[i][i+1]=max(a[i]*a[i+1],a[i]+a[i-1]);
    }//end for
    for(int len=3;len<=a.size();len++){
        for(int i=0;i<=a.size()-len;i++){
            int j=i+len-1;
            for(int k=i;k<j;k++){
                dp[i][j]=max(dp[i][j],max(dp[i][k]+dp[k+1][j],dp[i][k]*dp[k+1][j]));
            }//end for
        }//end for
    }//end for
    return dp[0][a.size()-1];
}//end solve
int main(){
vector<int>a{-1,-2,-3};
cout<<endl<<solve(a);
   return 0;
}

Inorder Traversal in Iterative manner would be helpful here.

Please explain it a little

I think Mehrdad is right.Due to the restrictions imposed in the question, this seems to be an optimal solution.

I have one doubt regarding the words "Contiguous Sub arrays".Should the resultant sub arrays be located right next to each other or they can be located anywhere in the given array as soon as they are non-overlapping.

May be external Sort can help. Each of the chunk can be sorted on using threads and them merged together.

Using the Bitwise operators , you can generate the power set in iterative manner.It will help you to deal with Out of Memory error.Running Time remains the same.

Hey can't we maintain one heap and one linked list.Heap always contain top 100 purchases in recent time and Linked List has Just the purchases in which recent ones are at the head always.