Klaus
BAN USER#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;
}

Klaus
July 25, 2015 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 32bit 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

Klaus
July 21, 2015 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;
}

Klaus
July 19, 2015 How about this, 1c.Here the limitation is that minimum number is among the last k1 elements.So using the windowing approach , we maintain the list of last k1 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.
 Klaus July 19, 2015Sort 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)).
 Klaus July 15, 2015The 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[i1]);
}//end for
for(int len=3;len<=a.size();len++){
for(int i=0;i<=a.size()len;i++){
int j=i+len1;
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;
}

Klaus
July 15, 2015
We need to take care of the zero inside the loop.
 Klaus July 29, 2015