CareerCup

The time complexity will be n^2 for searching all elements. and logN to find the array pointer which needs incrementing. In all it would take n^2logn. Is there a solution to find the result in n^2.

while i understand the solution for O(nlogn) , unable to get the n^2 solution. can you explain/give clue?

@Durga, In the following program, why the assignment in fun() "temp=2000" only casues crash and not the assignment in main "b = 30"?

#include <iostream>
#include <stdio.h>
using namespace std;
class A{
	public:
		void fun(int& temp){
			cout<<"1am inside fun()"<<endl;
			temp = 2000;
			cout<<"2am inside fun()"<<endl;
			printf("in fun() temp[%p] temp val[%d]\n",&temp, temp);
		}
};

const int temp=100;
int main()
{
	A a;
	printf("in main() temp[%p] temp val[%d]\n",&temp, temp);
	int b = const_cast<int&>(temp);
	b = 30;
	cout << "b:" << b << endl;
	a.fun(const_cast<int&>(temp));
	cout<<"temp:"<<temp<<endl;
}

Suppose the dislike graph forms two disjoint sets, in this case the inverse graph is always a connected(so every node is taken into a room).

Can you explain how the program outpus kth smallest element.

There are only 4 matches possible in days 2,3,4,5,6,7 and only 2 matches possible in 8,9,10,11,12,13,14,15.

In days 2,3,4,5,6,7 there can be a maximum of 5 matchs are possible instead of 4.

So total days of 15 can be reduced to n-1(9).

the line

zigzag(nextStack, currentStack, !reverse);

should be after the while loop.

const int CatalanNos[12]={1,1,2,0};
long int catalan(int n){
if(n == 0 || n == 1)
return 1;
if(n == 2)
return 2;
if(CatalanNos[n] == 0)
{
long int sum = 0;
for (int i = 0; i < n; i++)
sum = sum + catalan(i) * catalan(n - i - 1);
return sum;
} else {
return CatalanNos[n];
}
}

The volatile keyword is a type qualifier used to declare that an object can be modified in the program by something such as the operating system, the hardware, or a concurrently executing thread.

This means every time the variable is requested inside the program, each time the value is read from the source memory location(harddrive,devices.etc). normal variables are stored in virtual memory of the processor. They are synced with source memory location only twice. Once during first read and second termination write.
This is useful when the varialbe is used as a control condition in multthreaded or RT applications applications.

Argument1:
Greedy algorithms dont work find for all the problems. It is true, that does not mean that in single-source-shortest-path-problem dijkstra's wont provide correct solution all the time.

Greedy algorithms wont work in some problems as in travelling sales man problem. There the Greedy-solution may lead to a city where all the paths are traversed and there is no untraversed way to go a next city. Thus for problem TSP it is not a 100 solution. BUT Greedy-Algorithm has a way to find single-source-shortest-path-problem correct all the time. Using dijkstra's.

Argument2:
As Problem is to find the shortest-path between two nodes where as Dijkstra's produces shortest-path tree, just run the Dijkstra's algorithm till you find the destination node. Report once you traverse the destination node instead of going for all nodes.

Hope you didnt understand the Greedy algorithm concept.
The solution which you suggested is itself a Greedy-Dijkstra algorithm.

It should be (b). The first encountered complete sub array.

let abcd -> acdb then transformations are ( 1->1, 2->4, 3->2, 4->3).
With the principle that some-position-element needs to be replaced by another-position-element there will always be loops(It can be drawn from graph theorms that if for every position(node in graph) has only 1 in and 1 exit, then they always form a loop).

so in a loop of length x nodes, after x mappings all the nodes in loop are at the same state as in the initial word. so answer for that loop alone is X.

but if there are multiple loops then the answer is LCM of all the loop lengths.