CareerCup

what I can think of is there should be separate table of department having id->department.
So we can use id instead of the name(which occupies more space)

this can be done in nlogn.
1.Store the position of each element for that we can use an object with
{
val: value
position: array_index
}

for each element in the array
2.Then sort the object array created above with value.
3.Subtract the old position from the new position for each element. i.e (old position - new position) remember don't take absolute value .
and the maximum of this is the maximum surpasser of the array

this is pretty easy if you think in terms of Dp approach.
Lets say we have String as "1" so our output will be 1 because we only form 'A'
but if we add 2 to the existing string "12" then output is "AB" and "L" so if you see
the logic is when you add a character to an existing string the number of combinations increase by combining last 2 digits
in dp it can be formulized As
d[i]=dp[i-1]+dp[i-2](if the last 2 digits combined is smaller than 27)
else dp[i]=dp[i-1];
code is as below

void getMappingDp(String str)
	{
		int arr[]=new int[str.length()];
		long Dp[]=new long[str.length()];
		
		for(int i=0;i<arr.length;i++)
		{
			arr[i]=Integer.parseInt(""+str.charAt(i));
		}
	
		Dp[0]=1;
		if(arr[0]*10+arr[1]<27)
			Dp[1]=2;
		else
			Dp[1]=1;
		
		for(int i=2;i<arr.length;i++)
		{
			long combinedLast2didgits=0;
			if(arr[i-1]*10+arr[i]<27)
				combinedLast2didgits=Dp[i-2];
			Dp[i]=Dp[i-1]+combinedLast2didgits;	
		}
		System.out.println("Total mapping are:"+Dp[Dp.length-1]);
	}

see anonymous for your case the answer will be AB

guys in order to solve this u just need to remove all i mean all the even length palindromes from the string.

for eg:- in above case ABCCBCBA remove BCCB as it is even length paliondrome.
for eg:-ABBBBADD need to remove ABBBA and then DD and return -1

Algo:-
let the array be arr
1.Create An array sum as below
sum[i]=arr[0]+arr[1]+...arr[i];

2.Now see for duplicate values in sum array.
for eg:-
the array is 1,2,3,-2,-1,4,-5,1
sum array 1,3,6, 4, 3,7,2,3
so after finding duplicate values you will see the all the elements between their indices will sum upto zero and you can print it.

It will also work for over lapping intervals

geeksforgeeksdotorg slash median-of-stream-of-integers-running-integers

a good explanation

public class CombinationofCoins {


int numberoways(int den,int array[],int pos)
{

if(den<0||pos==array.length)
return 0;

if(den==0)
return 1;

int numways=0;


for(int i=pos;i<array.length;i++)
{
numways+=numberoways(den-array[i],array,i);
}

return numways;
}


public static void main(String args[])
{

int arr[]={2,3,4,5};

CombinationofCoins obj=new CombinationofCoins();

System.out.println(obj.numberoways(9, arr, 0));

}

}

u see your code only does a trivial check it will fail for many test cases

for eg:- let's say A="AAA" and B="AAB" and interlevead string be C="AABAAA"

so your statement
if (*ptrA++ != *ptrC++) {
break;
}
will give true for first 2 A's but after that your logic will fail as C will now point to "B" A is pointing to 'A' and B is also pointing to "A"..And you will come out of the loop.

because of these test cases you need to come with a dynamic programming.
Which is there in my post below you.

Construct a (n1+1)*(n2+1) table, A[0 .. n1][0 .. n2], where n1 and n2 is the length of s1 and s2, respectively.
A[i][j] = true, i.e. s3[0 .. i+j-1] is an interleaving of s1[0 .. i-1] and s2[0 .. j-1].
Thus, A[n1][n2] represents whether s3 is a interleaving of s1 and s2.
To build up such a table,
1.Set A[0][0] = true. Period.
2.Initialize the first row. The first row means whether s1[0 .. (n1-1)] matches s3[0 .. (n1-1)], correspondingly.
3.Similarly, initialize the first column which means whether s2[0 .. (n2-1)] matches s3[0 .. (n2-1)], correspondingly.
Now we fill up the table. For A[i][j], s3[0 .. (i+j-1)] match? s1[0 .. i-1] weaving s2[0 .. j-1]
4.Note that A[i-1][j] comes from s1[0 .. i-2] weaving s2[0 .. j-1]. Thus, if it is true, we need to compare s1[i-1] with s3[i+j-1].
Similarly, A[i][j-1] comes from s1[0 .. i-1] weaving s2[0 .. j-2]. Thus, if it is true, compare s2[j-1] with s3[i+j-1].

5.Return A[n1][n2]

Hi this a tested code i used using backtacking.

public class combinations {




int arr[];

int sumuptoAi(int m,int n)
{
int sum=0;
for(int i=m;i<=n;i++)
sum=sum*10+arr[i];

return sum;
}

public boolean Combinations(int start,int sum)
{



if(sum==0&&start==arr.length)
return true;

for(int i=start;i<arr.length;i++)
{


if(Combinations(i+1, sum-sumuptoAi(start, i)))
return true;

}
return false;
}






public static void main(String args[])
{


int arr[]= {2,3,7,2};
combinations obj=new combinations();
obj.arr=arr;

System.out.println(obj.Combinations(0, 239));



}





}

instead of using hash you can directly use array.It will save you lot of space.
for eg. as the number ranges from 0 to n-1
you can write this as
for(int j=0;j<arrayLngth;j++)
{
i=j;
len=0;
init(array) // this will make all entries again positive
while(array[i]>0)
{
i=array[i];
array[i]=array[i]*-1;
len++
}
System.out.println(len)

}

Consider a data structure composed of a hashtable H and an array A. The hashtable keys are the elements in the data structure, and the values are their positions in the array.

1.insert(value): append the value to array and let i be it's index in A. Set H[value]=i.
2.remove(value): We are going to replace the cell that contains value in A with the last element in A. let d be the last element in the array A at index m. let i be H[value], the index in the array of the value to be removed. Set A[i]=d, H[d]=i, decrease the size of the array by one, and remove value from H.

3.getRandomElement(): let r=random(current size of A). return A[r].

1.Sort the elements to be searched to be stored in arr[]
2.Now Start from the root of bst.
2.1 search root element in the array arr

if it's index is index>0 or (index < arr.length -1) return false

else if index is 0 then move to Tree's right and arr is from 1 to arr.length-1


or if index is arr.length-1 move to tree's left and arr is now from 0 to arr.length-2;

at the end arr should be empty.

return true

does not work for case

8 14 11 9 13 20 16 22
8 14 20 22 16 11 13 9

@guest in the heap we keeping 2 things the value of element and the array to which it belongs so when removed we will know which element to fetch

@apostle you are right the complexity will be mlogk

time complexity will be m*[log k] assuming log k << m so it can be taken as m ofcourse we need to do nk inserts in heap

Algorithm as follows
1.Create a min heap of first elements of all the arrays.
(a node of heap would be an object containg number's value and number of array it belongs to.)O(Klogk)
2.Now remove the element from the min heap
3. Add corresponding element of that array to heap to which min element belonged.
repeat steps 2 and 3
total time complexity will be ->m is total no of element i.e m=k*n

Here goes the algo

1. Find the max element in the series and that element becomes root.
2.elements which are in the series to the left of root is in left subtree and on the right belongs to right subtree
do it recursively for left and right subtree

for eg:-

Inorder traversal- 5 10 8 20 6 7 4
so 20 is the root
and left subtree {5,10,8}
right subtree {6,7,4}}

no do it recursively for (5,10,8)
here 10 becomes the root and 5 it's left child and 8 it's right child

we can use heap to perform k-way merge sort
Algo
1.create a min heap of first element of all the k array(time klogk)
2.remove the min element and enter the element of the same array to which min element belonged.
now repeat step 2
time-nklogk

did u see here overlap need to be considered.

int dictionaryContains(string word)
{
string dictionary[] = {"mobile","samsung","sam","sung","man","mango",
"icecream","and","go","i","like","ice","cream"};
int size = sizeof(dictionary)/sizeof(dictionary[0]);
for (int i = 0; i < size; i++)
if (dictionary[i].compare(word) == 0)
return true;
return false;
}

// Returns true if string can be segmented into space separated
// words, otherwise returns false
bool wordBreak(string str)
{
int size = str.size();
if (size == 0) return true;

// Create the DP table to store results of subroblems. The value wb[i]
// will be true if str[0..i-1] can be segmented into dictionary words,
// otherwise false.
bool wb[size+1];
memset(wb, 0, sizeof(wb)); // Initialize all values as false.

for (int i=1; i<=size; i++)
{
// if wb[i] is false, then check if current prefix can make it true.
// Current prefix is "str.substr(0, i)"
if (wb[i] == false && dictionaryContains( str.substr(0, i) ))
wb[i] = true;

// wb[i] is true, then check for all substrings starting from
// (i+1)th character and store their results.
if (wb[i] == true)
{
// If we reached the last prefix
if (i == size)
return true;

for (int j = i+1; j <= size; j++)
{
// Update wb[j] if it is false and can be updated
// Note the parameter passed to dictionaryContains() is
// substring starting from index 'i' and length 'j-i'
if (wb[j] == false && dictionaryContains( str.substr(i, j-i) ))
wb[j] = true;

// If we reached the last character
if (j == size && wb[j] == true)
return true;
}
}
}

/* Uncomment these lines to print DP table "wb[]"
for (int i = 1; i <= size; i++)
cout << " " << wb[i]; */

// If we have tried all prefixes and none of them worked
return false;
}

// Driver program to test above functions
int main()
{
wordBreak("ilikesamsung")? cout <<"Yes\n": cout << "No\n";
wordBreak("iiiiiiii")? cout <<"Yes\n": cout << "No\n";
wordBreak("")? cout <<"Yes\n": cout << "No\n";
wordBreak("ilikelikeimangoiii")? cout <<"Yes\n": cout << "No\n";
wordBreak("samsungandmango")? cout <<"Yes\n": cout << "No\n";
wordBreak("samsungandmangok")? cout <<"Yes\n": cout << "No\n";
return 0;
}

can be done by giving threads their sequence and when the running value equals that value then the thread is allowed to run

as below
class resource
{


private int sequence;

public resource(int i) {
this.sequence=i;
}


public int getSequence() {
return sequence;
}

public synchronized void incementSequence()
{
sequence++;
}

}

class sequence implements Runnable

{

int sequence;
resource obj;

public sequence(int i,resource obj) {

this.sequence=i;
this.obj=obj;
}

public void run() {


synchronized(obj)
{
while(obj.getSequence()!=sequence)
{
try {
obj.wait();
} catch (InterruptedException ex) {
Logger.getLogger(sequence.class.getName()).log(Level.SEVERE, null, ex);
}
}

System.out.println("my processing is done with sequence->"+sequence);
obj.incementSequence();
obj.notifyAll();
}
}



}





public class sequenceRunning {



public static void main(String args[])
{


sequence obj[]=new sequence[3];
resource objresource=new resource(1);
for(int i=0;i<3;i++)
{
obj[i]=new sequence(i+1,objresource);
Thread runThread=new Thread(obj[i]);
runThread.start();
}



}



}

It can be done in o(n) with space o(2n)

Algo as follows:-

1.create 2 arrays maxTillNow and minTillNow
where Maxtillnow[i]=max{maxTillNow[i+1],A[i]}
and MaxTillnow[n]=A[n]

MinTillNow[i]=min{MinTillNow[i-1],A[i]}

and MinTillNow[0]=A[i]


2.Now again traverse the array
if a[i]!=minTillnow[i] && a[i]!=maxtillnow[i]

print mintillnow[i] a[i] maxtillnow[i]


plus the above condition can also be written as
if a[i]>minTillnow[i] && a[i]<maxtillnow[i]

@aka u forced me to write the complete code :)
int sumUptoi=a[0];
int x[]=new int[a.length];
x[0]=sumUptoi
i=1;
while(i<a.length)
{
x[i]=a[i]+=sumUptoi;
i++;
} //(o(n) asu can see)


int y[]=new int[a.length];
int sumfromi=a[a.length-1];
y[a.length-1]=a[a.length-1];

j=a.length-2;


while(j>=0)
{
y[j]=sumfromi+a[j]


j--;
}//(o(n) asu can see)



for(int i=0;i<a.length;i++)
{


if(i==0)
s[i]=y[i+1];
else if (i==a.length-1)
s[i]=x[i-1]

s[i]=x[i-1]+y[i+1]
}//this is also o(N)

Algo
1.take 2 arrays X and Y

where X[i]={A[1]+A[2]+ _ _ _ _ +A[i]}
AND Y[i}={A[i]+A[i+1]+A[i+2]+_ _ _ _ +A[n]}

THE ABOVE can be calculated in O(n) time

Now s[i]=x[i-1]+y[i+1]
Boundry conditions needs to be handled for i=0 and i=n

It just another version of finding middle of linked listwith following modifaction
1.Storing head in a temp variable.
2.The termination condition will now be while(p2>next!=Head&&p2->next->next !=head)

this is a kind of producer consumer problem where consumer can consume only until producer has produced