CareerCup

I didn't check your code, but some optimizations are possible like somehow, keep track of solved sub-problems as they'll surely be repeated in future recursions. Also, perhaps its not necessary to actually populate whole graph, instead just recurse through one path until we get final score and then, during unwinding store results in some map of pair(score) and a string(possible path). Then, during backtracking, we don't have to recurse again for a sub-problem for which a solution is already saved in that map. Also, we don't again recurse for a sub-problem whose reverse pair is already saved in map as key but we'll take care while printing the value(string).

//Solution with Dynamic programming, although, haven't even compiled, idea is like, if replacing one character results into a valid word in dictionary then its a similar sub-problem like what's the minimum iterations required from that point onwards.
findMinWays(string str)
{
	if (str == endWord) {
		return 0;
	}
	int min=MAX_INT, num=0;
	for (int i=0; i<str.length-1; i++) {
		if ( dict.exists( str.replace(i, endWord[i]) ) ) {
			
			num = findMinWays(str.replace(i, endWord[i]));
			if (num < min)
				min = num;
		}
	}
	if (min==MAX_INT)
		return 0;
	return min;
}

Ooops, If the method wasn't virtual, you could've simply called : obj->func() and it would've surely invoked Base's version. :-)

I couldn't understand the problem, why the answer to given input is 100207 ? Please explain if someone read this.

#include <iostream>
#include <vector>

using namespace std;

struct Node {
	int data;
	Node* left, *right;
};

void findFirstnLastOfLevel(Node* root, vector<pair<unsigned int, unsigned int>>& result, unsigned int level ) {

	if (result[level].first == -1)//left for this level not yet found
		result[level].first = root->data;
	else
		result[level].second = root->data;//always overwrite the rightest node

	if (root->left != NULL)
		findFirstnLastOfLevel(root->left, result, level+1);
	if (root->right != NULL)
		findFirstnLastOfLevel(root->right, result, level+1);

}

Just wanted to add that (n & (~n+1) ) == n, looks more clear & intuitive.

Its very difficult to understand to your logic considering the code, you've provided. Lets say we've 5 stored at 0th index
so arr[0] will give us 5
lets say, we've 10 stored at 5th index
so, temp = arr[arr[temp]] = 10
then, you are setting -1 as :-
arr[arr[temp]] = -1 , which will write -1 at index by two more levels of indirection, which doesn't help in anyway, I guess.
But I somewhat understood what you were trying to say, but actually couldn't come up with right algo using that approach,
Can you repost the correct version of what you were trying to do in first place?

Perfect answer, just wanted to add, considering self-balancing BST (AVL-tree) approach, Time-complexity would be nlogn.

Dijkstra would be inefficient in comparison to Dynamic programming unless it is tweaked a little bit to find SINGLE-PAIR shortest path because generally Dijkstra is applied for SINGLE-SOURCE shortest path situations.

Indeed :-) But one should apply relevant 'SINGLE-PAIR' shortest path algo by assuming two dummy nodes at bottom and top of stairs.

This approach is like being greedy at each step and not taking into account minCostThusFar at each step. Hence, it will not give optimal answer all the time.
You can modify your algo by NOT just comparing 'move up' or 'move up and cross'; instead you should compare 'cost of move up + minCostThusFar for same side' and 'cost of move up(other side) + minCostThusFar on other side + cost of crossing'. This will give you optimal result. Applying this technique, you are actually doing Dynamic Programming from Bottom-up approach.

@Klaus : If someone plans to use single linked list for purchases then, using a Heap needs some more care in order to do Increase-key operation efficiently because to perform Increase-key, one has to know the index of that node. But it can be done, I guess, efficiently by using some map-like data-structure.
Moreover, [ having many linked lists(each for a product) & not having main linked list ] or [ having a single list ] almost takes same space. So, we are not gaining much out of it.

Not that simple though. 'All stops in a cluster should be at a distance not greater than D' - is difficult to implement by using algorithm of connected components.
Instead, I think, one has to calculate shortest paths of 'all pairs' first and need to keep only those nodes in a cluster which can be accessible via all other nodes(in that cluster) with a distance <= D and spare other nodes for other clusters probably.

I think, this code doesn't take care of overlapping and covering entire grid. Moreover, I'm not able to find DP here.

bool customFindSubSeq(string ipStr)
{
	vector<unsigned int> followedBy(26,0);
	unsigned int toCheck = 0;

	transform(ipStr.begin(), ipStr.end(), ipStr.begin(), ::tolower);

	for (int i=0; i<ipStr.size(); i++) {
		int index=(ipStr[i] - 'a');
		unsigned int tmp = (1<<index);

		if (toCheck != 0) {
			for (int b=0; (b<32 && ((1<<b)<=toCheck)); b++)
			{
				if ( (1<<b) & toCheck) {
					if ( followedBy[b] & tmp) {
						return true;
					}
				}
			}
		}
		for (int j=0; j<followedBy.size(); j++) {
			if (followedBy[j] != 0)
				followedBy[j] |= tmp;
		}
		if (followedBy[index] == 0)
			followedBy[index] |= (1 << 31);
		else
			toCheck |= tmp;
	}
	return false;
}