CareerCup

use a stack and vector and recursion

#include<iostream>
#include <vector>
#include <stack>
using namespace std;
bool printp(vector<std::pair<char, int>> s1, int s, int e)
{
	if (s > e)	return false;
	cout << s1[s].first << s1[s].second << "," << s1[e].second << ",";
	if (!printp(s1, s + 1, e - 1)) cout << "null";
	cout << s1[e].first;
	return true;
}
void Parse(string s)
{
	std::stack<char> s1;
	vector<std::pair<char, int>> t1;
	int first = 1;
	for (int i = 0; i < s.length(); i++)
	{
		t1.push_back(make_pair(s[i], i));
		if (s[i] == '[')
			s1.push('[');
		else
		{
			s1.pop(); if (s1.empty()){ if (!first) cout << ","; first = 0; printp(t1, 0, t1.size() - 1); t1.clear(); }
		}
	}
}
int main()
{
	Parse("[[]][]");
	return 0;
}

A 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;
}

the alpha beta are arranged to be alpha<beta by switching the two end points

This 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 non-decreasing 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

way too much code guys way too much code
do a simple if(a[i][j]==1) a[i][j] = max(a[i-1][j],a[i][j-1) + 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[i-1][j],a[i][j-1) + 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 ?

I 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

very 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

yes 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 j-1 results in k*(n-j)- k *j change of the value
where k = A[j]-A[j-1] this change is k*(n-2*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*(n-j) = k *(2*j-n) 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;
			}
		}

}

for O(nlogn) also you can take a number x and binary search for K-x same complexity.

@anonymous no your idea is not correct it can be middle(very likely) but not true in general..

a 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[N-i-1];
	}
	mean/=J;
	for(int i=0;i<J;i++)
	if(std::abs(a[N-i-1]-(int)mean) < near)
	{
		near = std::abs(a[N-i-1]-(int)mean);
		near_id = i;
	}
	int sum = 0;
	for(int i=0;i<J;i++)
		sum+= std::abs(a[N-i-1]-a[N-near_id-1]);
	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,N-1,K-1);
	else
		min1 = distance(a,N,N);
	if(K>1)
	for(int i=1;i<=N-K;i++)
	{
		min1 = std::min(min1,calc_distance(a,N-i,K-1)+distance(a,N,i));
	}
	return min1;
}

yeah i missed that... this dist can be calculate in O(log n) with some fancy work as the its only 1-D.. 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,k-1), F(n-1,k-1)+dist(a(n),a(n+1)), F(n-2,k-1)+dist(a(n+1),a(n),a(n-1) ...................)
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

I 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;

n1 n4 n5 are pointers what are you gonna do with shuffling some pointers.. what makes you think pointers are ordered....

you are missing something what for j==0 and also its not really random as it will be not uniform probablity for secret

i 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

should have asked then, that might be the answer :D

case1: 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

assuming 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

i 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

Segment Trees if the queries is too high.. or just do a min,max

Solution 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();

and the solution will be O(n^2).. will post a O(n) solution

@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 && non-zerochild) 
{
	swap;
	if(left-non-zero)
	preorder left;
	else
	preorder right;
}
}

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

why 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; 
};

you are assuming balanaced tree

This 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[full-len]-'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,len-1,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,len-1,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;
}

you dont need to sort the number you can just reverse the digits after the ith digit swapped

sum = Z*n*(l-1) + Z*(Z+1)*( 2*Z - 3*l -3*n +4)/6

Z=MIN( m, MIN(n,l-1) )

why not just run the code he wrote.. why write more lines of code

0,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(l-1) + Z*(Z+1)*( 2Z - 3l -3n +4)/6

Z=min(m,n,l-1)

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