czpete425
BAN USEROK, here is a solution using BFS.
Note that I abstracted away things like dictionary representation and getting all the words that differ from the given word in just one character. There are several different ways to implement these and there's no point polluting the solution with unnecessary detail. Plus a few people before me have code snippets that could be used for that.
If you are really going read this, I'd suggest to paste the code into Visual Studio (or your favorite editor that has syntax highlighting).
#include <iostream>
#include <map>
#include <queue>
#include <string>
using namespace std;
// Hash table? Trie? BST? Your choice :-)
class Dictionary
{
public:
Dictionary(string path);
~Dictionary();
// Generate the next word that differs from s only in s[position].
// If there are no such words, s is returned.
// Repeatedly calling this function will eventually return the
// string that we started with.
// One possible implementation of this is to increment s[position]
// mod 26 until a word in the dictionary is found.
const string & GetNextWord(string s, int position) const;
};
bool FindPath(
const Dictionary * pDict,
string start,
string end,
map<string, string> & mpCP)
{
mpCP[start] = ""; // Put start in the map with empty parent
queue<string> q;
q.push(start); // Enqueue start
int length = start.size();
//
// Repeat until we found end or until no more words left
while(!q.empty())
{
// Get the next word from the queue
string word = q.front();
q.pop();
// Because of the early out below, this can only happen when start==end
if (word == end)
return true;
//
// Generate all possible children (that we have not seen before)
// and put them in the queue
for (int i = 0; i < length; ++i)
{
string s = word;
while ((s = pDict->GetNextWord(s, i)) != word)
{
// We have already seen this word, do nothing
if (mpCP.count(s) > 0)
continue;
// We have not yet seen this word, let's add it
// to the map (with its parent) and to the queue
mpCP[s] = word;
// Early out - we found our target!!!
if (s == end)
return true;
q.push(s);
}
}
}
return false;
}
// Print path (up to word end) using entries in the map
void PrintPath(const map<string, string> & mpCP, const string & end)
{
string parent = mpCP.find(end)->second;
if (parent != "")
{
PrintPath(mpCP, parent);
cout << " -> " << end;
}
}
int main()
{
string start = "CAT";
string end = "DOG";
if (start.size() != end.size())
{
cout << "String lengths don't match, exiting ..." << endl;
return 1;
}
Dictionary dict("FileWithAllWords.txt");
map<string, string> mpChildParent;
bool success = FindPath(&dict, end, -1, mpChildParent, q);
if (success)
{
cout << "Path from " << start << " to " << end << " exists!" << endl;
cout << start;
PrintPath(mpChildParent, end);
}
else
{
cout << "Path from " << start << " to " << end << " does not exist!" << endl;
}
return 0;
}
From what I can tell, there is absolutely no bactracking in your code. The test example works only because your dictionary is very small. It would not work in general case. I really cannot follow your code, but it seems that if you add "hat" to your dictionary, you will get stuck with no way of recovering.
- czpete425 November 11, 2012A few comments ...
DFS - you would run out of memory very quickly because the recursion tree can be as deep as the number of words of given length in the dictionary. Plus you'd need to remember which words you had already visited to avoid visiting them repatedly with different prefixes.
BFS - that seems to be the only reasonable solution. The difficult part is doing BFS efficiently using a reasoably clean code.
If you doing anything else, seemingly clever, make sure that your code works for the 2 examples. And please add some explanation/comments (@Sunny and others). Blasting code on the page without any explanation is not helping anybody.
@MI: InOrderModify(pRoot, NULL) is exactly how you should call this function. If you do, and assuming that pRoot != NULL, you keep calling
pPrev = InOrderModify(pNode->pLeft, pPrev);
recursively until you find a node with no left child. Then pPrev becomes that node because you call
pPrev = InOrderModify(pNode->pLeft, pNode);
I did not down-vote but there's a mistake ... The function signature needs to be
Void InorderSuccessor(node* root, node* & pre);
In which case the algorithm is identical to what I posted above only instead of returning a pointer, you set it in the in-out parameter.
- czpete425 November 10, 2012Rockstar - nice! Swathi, the code is correct and purposely from right to left.
Here is a solution without a static variable:
Node * InOrderModify(Node * pNode, Node * pPrev)
{
if (pNode == NULL)
return pPrev;
pPrev = InOrderModify(pNode->pLeft, pPrev);
if (pPrev != NULL)
pPrev->pSucc = pNode;
return InOrderModify(pNode->pRight, pNode);
}
Give me just one such instance ... Anybody can say "I have seen ...".
I proved that it's mathematically imposible. If you think the proof is not correct, show me what exactly is wrong or give me a specific counter-example. Otherwise we are wasting time here.
Man I always regret posting to this site ...
You guys are all correct in that Max Heap would work. But only if all the numbers are distinct. That details was not clear from the statement of the problem. As soon as you allow numbers to appear more than once in the 1 billion (but you only want them once in your final answer, the smalles one million) Heap would not work since it is really expensive to search for a number in the heap (it's O(n)). In that case, BST would work better.
- czpete425 November 18, 2011Not sure what you mean ...
The first part of the proof says that for string with all odd counts or all even counts we cannot get any better than (0,0,2). Why, because each reduction brings us from all even to all odd or from all odd to all even. The shortest possible string with all even is (0,0,0) but that cannot be achieved by any reduction, so the next all-even shortest string is (0,0,2). The shortest possible all-odd string is (1,1,1) but that is (a) longer than (0,0,2) and (b) can be reduced to (0,0,2) by one reduction. Note that (0,0,1) is neither all-odd nor all-even so all-odd/all-even strings cannot be reduced to that. Anyway, the first part of the proof is that we cannot do any better than (0,0,2).
The second part of the proof is trying to prove the fact that (using smart reduction) we can indeed make it all the way to (0,0,2) for all-even/all-odd strings, and all the way to (0,0,1) for all the other strings as long the string we are starting from contains 2 or 3 different kinds of characters.
Let me give you an example:
all-odd string (3,1,1): (aaabc)->aacc->abc->cc
regular string (4,1,1): (aabaac)->acaac->baac->cac->bc->a
Hopefully this made it clear :-)
OK master fuji, this looks interesting. Sadly, you don't give any supporting arguments to why this would be O(n log n) or how the algorithm actually works! For example how do you count the number of values between M(i0,j0) and M(i1,j1)? If you just go through the entire matrix, you counted n^2 elements! So, just in the 1st step, you are already over your O(n log n) time!
The trick to this problem is exactly this -- you split the matrix somewhere in the middle and you can easily eliminate about 1/2 of the elements in the fisrt step (the median has to be somewhere in the top right quadrant or bottom left quadrant). But the next step is not at all obvious.
I have something that should work but I agree that it's kind of messy. I do a normal linked list reversal, and once in a while (every k elements) I connect the rigth pieces together instead of the normal reversal.
Node * K_ReverseList(Node *pHead, int k)
{
if (pHead == null || pHead->pNext == null || k <= 1) return pHead;
Node *pPrev = null;
Node *pCurr = pHead;
Node *pNext;
Node *pTail1 = null;
Node *pTail2 = null;
int i = 0;
pHead = null;
while (pCurr != null)
{
pNext = pCurr->pNext;
if (i == k-1 && pHead == null) pHead = pCurr;
if (i == 0)
{
// Tricky case when you are not supposed to reverse
if (pTail1 != null) pTail1->pNext = pPrev;
pTail1 = pTail2;
pTail2 = pCurr;
}
else
{
// Regular reversal
pCurr->pNext = pPrev;
}
// Move to the next node
pPrev = pCurr;
pCurr = pNext;
i = (i+1)%k;
}
// Tie any loose ends
if (pTail1 != null) pTail1->pNext = pPrev;
if (pTail2 != null) pTail2->pNext = null;
if (pHead == null) pHead = pPrev;
return pHead;
}
Ishant, you are correct (though there's still something missing ...). So let me list all possible cases:
(1) String contains only one kind of characters, or more precisely, the string contains k identical characters and nothing else. Clearly, no reduction is poosible and the minimum length is k.
(2) String contains 2 or 3 kinds of characters. Then if all the counts are even or all the counts are odd, the minimum string possible has length 2, otherwise we can reduce it to 1.
Proof (of 2):
With every reduction, the count of 2 characters decreases by 1, and the count of the third character increases by 1. So if all counts are even before reduction, all counts will be odd after reduction, and if allcounts are odd before, they will all be even after. So, for such strings, the shortest possible string we can get is (0, 0, 2) or (cc) or (bb) or (aa). All even counts. This proves that we can't do any better than (0, 0, 2).
Now, are we guaranteed that we can always get to (0,0,2) for the all-odd, all-even strings and to (0,0,1) for the other strings? YES! We just have to be smart about which pairs we reduce. For example, if our string is aaaaaaabc we can either reduce ab or bc. Reducing bc would mean no more reduction so we don't want to do that! So the algorithm to reach minimum string is this -- always reduce a pair that contains a character with maximum count. It does not matter which pair, just that the max count character be reduced. This will eventually result in a string of length 1 or 2 depending on the initial counts.
@Anonymous: pPrev is the in-order predecessor not the parent. And you are absolutely correct - if you start at the root and keep going to left childrent only, the current node is the smallest thing you have seen so far, hence no in-order predecessor. Once you backtrack or go to right child, you're no longer the smallest, hence pPrev is not NULL.
@shallysahi: Try stepping through the code one line at a time and write down all the variables. At the same time remember where you are for each recursion. Something like this:
Hopefully this will make things more clear ... Also, you can try running the code in a debugger ...
- czpete425 December 04, 2012