kkr.ashish
BAN USERA simple DP solution
int num_c1(int N1, int M1, int t1)
{
if (N1 == 0)
return 0;
if (N1 == 1 && M1 == 0)
if (t1 == 0)
return 21;
else
return 5;
if (t1 == 0)
return num_c1(N1  1, M1, 0) * 21 + num_c1(N1  1, M1, 1) * 25;
if (t1 == 1)
return num_c1(N1  1, M1  1, 1) + num_c1(N1  1, M1, 0) * 5;
if (t1 == 2)
return num_c1(N1  1, M1, 0) * 21 + num_c1(N1  1, M1, 1) * 25 + num_c1(N1  1, M1  1, 1) + num_c1(N1  1, M1, 0) * 5;
}
int main()
{
cout << num_c1(1, 1, 2) << endl;
cout << num_c1(3, 1, 2) << endl;
cout << num_c1(3, 2, 2) << endl;
cout << num_c1(4, 2, 2) << endl;
cout << num_c1(4, 3, 2) << endl;
return 0;
}

kkr.ashish
October 26, 2017 the alpha beta are arranged to be alpha<beta by switching the two end points
 kkr.ashish November 12, 2014This problem is O(n^2) solvable
take a point on the circle (0,1) say.. now for each line get the two angles formed from the two end points w.r.t x axis, say (alpha, beta) such that alpha<beta so for each line you will get these angles (a0,b0), (a1,b1), (a2,b2)....
sort them on their first index(O(nlogn) and then find the largest nondecreasing sequence on the second index..O (n^2)
you can solve this with constant space too by building from 1 > X
2,3,4,5,
you have to keep 3 pointers(for 2,3,5, multiples) pointing to 3 locations in the list and incrementing every time you use one of them.. the only thing you would need is to do the compare and use the minimum and increment the pointer
run Djikstra twice on all the nodes, once for uphill and then for downhill .... run it from source as well as destination
take minimum of sum of both values calculated above for each node and take minimum
I guess most of you guys are splitting and solving this puzzle which is completely trash way to solve it..
rather just create an array of characters b[26] = count for string s2, c[26] = count for string s3;
now iterate over s1 and whenever you encounter a character of string s3 flush out a[26]; or else keep incrementing the character index in a[26], if a[26] >= b[26] element wise add up all the count in a[26] and thats one possible solution then delete the earliest char in a[26] till it keep satisying a[26]>=b[26] and updating the minimum solution, no other substring memories no splitting nothin, its a basic one pass linear algorithm
Brilliant :D:D
 kkr.ashish March 03, 2014way too much code guys way too much code
do a simple if(a[i][j]==1) a[i][j] = max(a[i1][j],a[i][j1) + 1 if its 4 connected
if its 8 connect then you need Union find both will result in O(n^2) and will be better than brute force because checking viisted nodes repeatedly is complex
way too much code guys way too much code
do a simple if(a[i][j]==1) a[i][j] = max(a[i1][j],a[i][j1) + 1 if its 4 connected
if its 8 connect then you need Union find both will result in O(n^2) and will be better than brute force because checking viisted nodes repeatedly is complex
for size greater than long long int ?
 kkr.ashish March 03, 2014I guess there is need to DFS but we can start at all letters and see if there exist a valid suffix with that letter as the starting point if its true we can search a valid prefix attached to it.. we can mark all the suffix letters as visited but not the prefix searched ones.. this will not invalidate other possible cases
 kkr.ashish March 03, 2014very high complexity and you cannot make visited nodes unusable unless they are starting position even then there is problem try "fhdfck", there are two similar characters in the word so you need to keep visited nodes into loop
 kkr.ashish March 03, 2014yes anonymous is correct a more straight proof will be
let j be the position of the minimum and j!=mid
then if(j>mid=n/2) moving j to j1 results in k*(nj) k *j change of the value
where k = A[j]A[j1] this change is k*(n2*j) as u can see it is negative till j!=n/2
similarly for j<mid=n/2 which will result in k*j k*(nj) = k *(2*jn) which is negative till j!=n/2
this should do the work(C++)
void solve4(string z)
{
std::set<string> ssa;
for(int i=0;i<z.length();i++)
for(int j=i+1;j<z.length()+1;j++)
{
string k=z.substr(i,j);
if(ssa.find(k)==ssa.end())
{
ssa.insert(k);
cout<<k<<endl;
}
}
}
 kkr.ashish February 11, 2014for O(nlogn) also you can take a number x and binary search for Kx same complexity.
 kkr.ashish February 10, 2014@anonymous no your idea is not correct it can be middle(very likely) but not true in general..
 kkr.ashish February 05, 2014a very basic bugg ridden code using recursion :D and O(n) for dist
int distance(int a[],int N,int J)
{
double mean=0;
int near=INT_MAX,near_id;
for(int i=0;i<J;i++)
{
mean+=a[Ni1];
}
mean/=J;
for(int i=0;i<J;i++)
if(std::abs(a[Ni1](int)mean) < near)
{
near = std::abs(a[Ni1](int)mean);
near_id = i;
}
int sum = 0;
for(int i=0;i<J;i++)
sum+= std::abs(a[Ni1]a[Nnear_id1]);
return sum;
}
int calc_distance(int a[],int N,int K)
{
int min1=INT_MAX;
if(K<1)
return min1;
if(N<0)
return 0;
if(N<=K)
return 0;
if(K>1)
min1 = calc_distance(a,N1,K1);
else
min1 = distance(a,N,N);
if(K>1)
for(int i=1;i<=NK;i++)
{
min1 = std::min(min1,calc_distance(a,Ni,K1)+distance(a,N,i));
}
return min1;
}

kkr.ashish
February 02, 2014 yeah i missed that... this dist can be calculate in O(log n) with some fancy work as the its only 1D.. same thing for 2D will be O(n)
using mean and binary search for number closest to mean
where will u keep the location j or i ??
greedy will not work its just wrong:
example k=2
1 5 6 10
its a DP question
since this is one D array use DP
F(n+1,k) = min(F(n,k1), F(n1,k1)+dist(a(n),a(n+1)), F(n2,k1)+dist(a(n+1),a(n),a(n1) ...................)
also F(j,k) = 0 for j<=k
complexity.. O(k*n^2)
this code is assuming we can destroy the linked list :D there will be updation for deletion of every node in array
 kkr.ashish February 01, 2014I have already mentioned a space based solution which some1 has downgraded without giving reason
the other solution without keeping space is:
for(each node in array)
if(node>left!=NULL && node>right!=NULL)
count++
else if(node>left==NULL && node>right==NULL)
count;
else
do nothing;

kkr.ashish
February 01, 2014 n1 n4 n5 are pointers what are you gonna do with shuffling some pointers.. what makes you think pointers are ordered....
 kkr.ashish February 01, 2014you are missing something what for j==0 and also its not really random as it will be not uniform probablity for secret
 kkr.ashish January 29, 2014i guess the array of nodes is unordered or else its just a simple question
on a simple thought:
can create a bool a[n] = {false}
and then set it for every occurance in the array then rescan the bool array and we will have the count
nope not really efficient at all .. try using BFS from starting point pretty simple question
 kkr.ashish January 29, 2014should have asked then, that might be the answer :D
 kkr.ashish January 29, 2014case1: 14114111 > 14114111> 14111411> 11411411
case2: 14111411 > 14114111> 14111411> 11411411
11411411 is the solution and yes the linear algorithm works.. you haven't understood the algorithm
 kkr.ashish January 26, 2014assuming M=2..
41141111 => 1st pass (L>R)
41111411 > 11411411 => 2nd pass(R>L) so it dint fail
a dequeue can solve this problem very easily .. i think that will work out
 kkr.ashish January 26, 2014i don't know how much complexity wise it will be different as the soln i gave is anyway O(n) .. the good thing with stack is it always keep a portion of tree as required.. while in case of queue you will have to abruptly empty the queue if there are only zeros
please try the solution using queue, To keep track of zero present is a bit messy .. will be interesting
i think this was the basic starting question the interviewer start with which might be converted to basic segmented trees.. i dont think such a simple question makes any sense otherwise
 kkr.ashish January 25, 2014Segment Trees if the queries is too high.. or just do a min,max
 kkr.ashish January 25, 2014Solution O(n)
std::stack ss;
preorder Traversal{
IF(parent == zero)
{
ss.push(parent);
}
else
{
if(!ss.empty())
{
swap(ss.top(),parent)
ss.pop();
ss.push(parent);
}
}
preorder left;
preorder right;
if(ss.top()==parent)
ss.pop();

kkr.ashish
January 24, 2014 and the solution will be O(n^2).. will post a O(n) solution
 kkr.ashish January 24, 2014@anonymous
your solution is also wrong try this
0
1 2
3 4 5 6
both of your codes will not propagate 0 downwards
preorder Traversal{
preorder left;
preorder right;
IF(parent == zero && nonzerochild)
{
swap;
if(leftnonzero)
preorder left;
else
preorder right;
}
}

kkr.ashish
January 24, 2014 sorry i gave an approx for the limit the right limit is N (N/(M +1))
the results comes from if you have N objects then the min number of separators required is N/(M+1)
we can take two pointers and store the occurance count and move left to right and swapping at any occurance of more than M with the next difference number.. this will leave same digits in the end .. so you will need to move from right to left and refill them.. will have no solution if a digit occurs more than N  (N/M) times in the pattern
 kkr.ashish January 22, 2014why is
if(root.left==null&&root.right==null)
x++;
statement required just do
if(x==0) x++; at the same place
Do it this way .. Make a rectangle d covering both the rectangles.. the length and width of this new rectangle has to be less than the sum of both the rectangles for any overlap
int doesRectOverlap(rect ra, rect rb){
rect d;
d.topx = min(ra.topx,rb.topx);
d.topy = min(ra.topy,rb.topy);
d.botx = max(ra.botx, rb.botx);
d.boty = max(ra.boty,rb.boty);
if(width(d) > width(ra)+ width(rb)  length(d) > length(ra) + length(rb))
return 0;
else
return 1;
}
/* For your reference
struct rect{
int topx,topy,botx,boty;
};

kkr.ashish
January 21, 2014 you are assuming balanaced tree
 kkr.ashish January 19, 2014This should suffice
basically just a permutation generator with remembrance
#include <cstring>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<char> AA;
int coverd[9];
char a[9];
void generate(char a[],int len,int full)
{
if(len==0)
{
for(auto it=AA.begin();it!=AA.end();it++)
cout<<*it;
cout<<endl;
}
else
{
int coeff=(int)(a[fulllen]'1');
coeff = coeff*3;
if(coverd[coeff/3]==1)
{
for(int i=0;i<3;i++)
{
coverd[coeff/3] = i;
AA.push_back((char)('A'+ coeff+i));
generate(a,len1,full);
coverd[coeff/3] = 1;
AA.pop_back();
if(coeff==24&i==1)
i=3;
}
}
else
{
AA.push_back((char)('A'+ coeff+coverd[coeff/3]));
generate(a,len1,full);
AA.pop_back();
}
}
}
int main()
{
int sum =0;
int count = 0;
char a[100];
cin>>a;
for(int i=0;i<9;i++)
coverd[i] = 1;
generate(a,strlen(a),strlen(a));
return 0;
}

kkr.ashish
January 15, 2014 you dont need to sort the number you can just reverse the digits after the ith digit swapped
 kkr.ashish January 14, 2014sum = Z*n*(l1) + Z*(Z+1)*( 2*Z  3*l 3*n +4)/6
Z=MIN( m, MIN(n,l1) )
why not just run the code he wrote.. why write more lines of code
 kkr.ashish January 07, 20140,1,2,2,3,4
0,1,2
2,3,4
so no the answer is not n, the problem is pretty interesting in itself forget variation
0,1,6,5,2,4,3,7
the answer to above one is 7 not 8
the summation is
Zn(l1) + Z*(Z+1)*( 2Z  3l 3n +4)/6
Z=min(m,n,l1)
test if any doubt
you answer cannot be independent of m and n
if you still dont get it use m=10,n=1,l=20
use a stack and vector and recursion
 kkr.ashish October 29, 2017