chetan.j9
BAN USERHere is the c++ code, using DP.
#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n; i++)
#define rep2(i,m,n) for(int i=m;i<(int)n; i++)
int PossibleDiceRolls(int S, int A, int N) {
vector< vector<int> > sum;
sum.resize(S+1);
rep(i,S+1)
sum[i].assign(N+1,0);
rep(i,min(A+1,S+1))
sum[i][1] = 1;
rep2(n,2,N+1)
rep2(i,1,S+1)
rep2(j,1,A+1)
if(i-j>0)
sum[i][n]+=sum[i-j][n-1];
return sum[S][N];
}
int main()
{
cout << PossibleDiceRolls(6, 6, 3) << endl;
return 0;
}
O(1) solution for every set operation and random element of the set.
- Maintain a hash-table for insertion and deletion.
- Along with the hash-table, maintain a vector of pointers to the elements in the hash-table. Lets call it vector(hashtable-element-pointers).
- For insertion, add the element to hash-table, and add a pointer to the end of the vector(hashtable-element-pointers).
- For deletion, get the index of the key of vector(hashtable-element-pointers), replace that pointer with the last element of vector(hashtable-element-pointer) and perform pop_back() on the vector.
Here is the code..
#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
using namespace std;
// Supports set of strings and random-element in the set.
class mySet {
private:
unordered_map<string,int> myMap;
vector<unordered_map<string,int>::iterator> myMapVector;
public:
mySet() {
myMap.clear();
myMapVector.clear();
}
bool IsElementPresent(string s) {
unordered_map<string,int>::iterator it = myMap.find(s);
if( it!= myMap.end() )
return true;
return false;
}
void Insert( string s ) {
if( IsElementPresent(s) )
return;
myMap[s] = myMapVector.size();
unordered_map<string,int>::iterator it = myMap.find(s);
myMapVector.push_back(it);
}
void Delete(string s) {
if( !IsElementPresent(s) )
return;
unordered_map<string,int>::iterator it = myMap.find(s);
myMapVector[it->second] = myMapVector[myMapVector.size()-1];
myMap.erase(it);
myMapVector.pop_back();
}
string GetRandomElement() {
if(myMapVector.size() == 0 )
return NULL;
int randomIndex = rand()%myMapVector.size();
return myMapVector[randomIndex]->first;
}
};
int main()
{
mySet testSet;
testSet.Insert("zero");
testSet.Insert("one");
testSet.Insert("two");
testSet.Insert("three");
testSet.Insert("four");
testSet.Insert("five");
testSet.Insert("seven");
testSet.Insert("eight");
testSet.Insert("nine");
cout << testSet.IsElementPresent("six") << endl;
cout << testSet.IsElementPresent("five") << endl;
cout << testSet.IsElementPresent("four") << endl;
testSet.Delete("four");
cout << testSet.IsElementPresent("four") << endl;
cout << testSet.GetRandomElement() << endl;
cout << testSet.GetRandomElement() << endl;
cout << testSet.GetRandomElement() << endl;
cout << testSet.GetRandomElement() << endl;
}
Well written code. Here is a cake for c++ enthusiasts, which handles multiple starting points for a given search string.
#include <iostream>
#include <deque>
#include <map>
#include <list>
#include <string>
#define rep(i,m) for(int i=0;i<(int)(m);i++)
#define rep2(i,n,m) for(int i=n;i<(int)(m);i++)
using namespace std;
void PreprocessBoard(string boggleBoard, map<char, list<int> > &prePosMap) {
rep(i,boggleBoard.size())
prePosMap[boggleBoard[i]].push_back(i);
}
void GetNeighbours(string boggleBoard,int curPosDst, map<int,bool> &neighboursMap, map<int,bool> &resultPosMap, int wd, int ht) {
neighboursMap.clear();
int posx = curPosDst/wd, posy = curPosDst%ht;
rep2(i,posx-1,posx+2)
rep2(j,posy-1,posy+2) {
if( (i>=0) && (j>=0) && (i < wd) && (j < ht) && (resultPosMap.find(i*wd+j) == resultPosMap.end()) ) {
neighboursMap[i*wd+j] = 1;
}
}
}
bool _SearchBoggle(string boggleBoard, string searchStr, map<int,bool> &resultPosMap ,deque<int> &resultPosQ, int curPosSrc, int wd, int ht )
{
if( curPosSrc == searchStr.size() )
return true;
int prevPosDst = resultPosQ.back();
map<int,bool> neighboursMap;
GetNeighbours(boggleBoard, prevPosDst, neighboursMap, resultPosMap, wd, ht);
for(map<int,bool>::iterator it = neighboursMap.begin(); it!=neighboursMap.end(); it++ ) {
if( boggleBoard[it->first] == searchStr[curPosSrc] ) {
resultPosMap[it->first] = 1;
resultPosQ.push_back(it->first);
if( _SearchBoggle(boggleBoard, searchStr, resultPosMap ,resultPosQ, curPosSrc+1, wd, ht ) ) {
return true;
}
else {
// Backtrack :)
resultPosMap.erase(it->first);
resultPosQ.pop_back();
}
}
}
return false;
}
bool SearchBoggle(string boggleBoard, map<char, list<int> > &prePosMap, string searchStr, deque<int> &resultPosQ, int wd, int ht) {
// resultPos contains the positions of the result.
if( searchStr.size() == 0 )
return false;
map<char, list<int> >::iterator it = prePosMap.find(searchStr[0]);
if( it == prePosMap.end() )
return false;
list<int> startingPositions = it->second;
for(list<int>::iterator it = startingPositions.begin(); it!=startingPositions.end(); it++ ) {
resultPosQ.clear();
map<int,bool> resultPosMap; resultPosMap.clear();
resultPosMap[*it] = 1;
resultPosQ.push_back(*it);
if( _SearchBoggle(boggleBoard, searchStr, resultPosMap, resultPosQ, 1, wd, ht) )
return true;
}
return false;
}
int main()
{
string boggleBoard = "SMEFRATDLONIKAFB";
int width = 4, height = 4;
map<char, list<int> > prePosMap;
deque<int> resultPos;
PreprocessBoard(boggleBoard, prePosMap);
bool isStringPresent;
isStringPresent = SearchBoggle(boggleBoard, prePosMap, "STAR", resultPos, width, height);
isStringPresent = SearchBoggle(boggleBoard, prePosMap, "TONE", resultPos, width, height);
isStringPresent = SearchBoggle(boggleBoard, prePosMap, "NOTE", resultPos, width, height);
isStringPresent = SearchBoggle(boggleBoard, prePosMap, "SAND", resultPos, width, height);
return 0;
}
This can be done recursively for K out of N numbers.
Assuming unique numbers here is c++ code.
// Print C(N,K) numbers in order of N^K, but not 2^N.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void PrintNcK(vector<int> &arN, int K);
void _PrintNcK(vector<int> &arN, vector<int> &arK, int cur, int start, int end);
void PrintNcK(vector<int> &arN, int K)
{
vector<int> arK;
arK.assign(K,1);
_PrintNcK(arN, arK, 0, 0, arN.size()-K+1);
}
void _PrintNcK(vector<int> &arN, vector<int> &arK, int cur, int start, int end)
{
if(cur == arK.size()) {
// Print the combination
for(int i=0;i<arK.size();i++)
cout << arK[i] << " ";
cout << endl;
return;
}
for(int i=start; i<end;i++) {
arK[cur] = arN[i];
_PrintNcK(arN, arK, cur+1, i+1, end+1); // Recurse here
}
}
int main()
{
vector<int> arN;
arN.push_back(15);
arN.push_back(5);
arN.push_back(12);
arN.push_back(6);
arN.push_back(2);
arN.push_back(4);
arN.push_back(41);
arN.push_back(49);
arN.push_back(20);
sort(arN.begin(), arN.end(), greater<int>());
int N = arN.size(), K = 3;
PrintNcK(arN,K);
return 0;
}
c++ code here.. for constructing DAG from pair of consecutive two strings. And topological sort over constructed DAG.
#include <iostream>
#include <list>
#include <vector>
#include <string>
#include <stack>
#include <deque>
#include <set>
using namespace std;
#define NO_OF_ALPHABETS 26
#define NOT_VISITED 0
#define TEMP_VISITED -1
#define VISITED 1
typedef vector < set<int> > graph_t;
// Assume all are ascii characters between 'a' and 'z' only
void AddEdge( graph_t &myGraph, char *s1, char* s2);
void PrintTopologicalOrder( graph_t &myGraph, int startNode );
int GetUnvisitedNode(char * isVisited, int size );
void AddEdge( graph_t &myGraph, char *s1, char* s2)
{
while( (*s1 != 0) && (*s2 != 0) )
{
if( *s1 == *s2 )
{
s1++;
s2++;
continue;
}
else
{
myGraph[*s1-'a'].insert(*s2-'a');
break;
}
}
}
void PrintTopologicalOrder(graph_t &myGraph)
{
char isVisited[NO_OF_ALPHABETS];
memset( isVisited, NOT_VISITED, NO_OF_ALPHABETS);
stack<int> myStack; // for DFS
deque<int> resultOrder;
set<int>::iterator it;
int startNode = GetUnvisitedNode(isVisited, NO_OF_ALPHABETS);
while( startNode!= -1 )
{
myStack.push(startNode);
while( !myStack.empty() )
{
int currNode = myStack.top();
isVisited[currNode] = TEMP_VISITED;
int countFreeNodes = 0;
for(it = myGraph[currNode].begin(); it!= myGraph[currNode].end(); it++ )
{
if(isVisited[*it] == TEMP_VISITED)
{
cout << "Loop present, Path not possible" << endl;
return;
}
else if(isVisited[*it] == NOT_VISITED)
{
isVisited[*it] = TEMP_VISITED;
myStack.push(*it);
countFreeNodes++;
break;
}
}
if(countFreeNodes == 0 )
{
isVisited[currNode] = VISITED;
myStack.pop();
resultOrder.push_front(currNode);
}
}
startNode = GetUnvisitedNode(isVisited, NO_OF_ALPHABETS);
}
cout << "Topological order" << endl;
for( deque<int>::iterator it = resultOrder.begin();it!= resultOrder.end(); it++ )
{
char c = *it+'a';
cout << c << "->";
}
cout << endl;
}
int GetUnvisitedNode(char * isVisited, int size )
{
for(int i=0;i<size;i++)
{
if( isVisited[i] == NOT_VISITED )
return i;
}
return -1;
}
int main()
{
FILE * fp = fopen("words.txt", "r");
graph_t myGraph;
myGraph.resize(NO_OF_ALPHABETS);
char * string1 = new char[1024]; char * string2 = new char[1024];
string1[0] = 0; string2[0] = 0;
while( fscanf(fp, "%s", string2 )!=EOF )
{
AddEdge( myGraph, string1, string2);
strcpy(string1, string2);
}
PrintTopologicalOrder(myGraph);
return 0;
}
I agree with your answer, but you are traversing whole tree. Why not skip a part of tree if it is either less than a OR greater than b ?
void countInsideRange(node *root, int min, int max, int* count)
{
if (root == NULL)
return;
if( (root->key < min) || (root->key > max) )
return;
if((root->key > min) && (root->key < max))
*count = *count + 1;
countInsideRange(root->left, min, max, count);
countInsideRange(root->right, min, max, count);
}
Say there are N strings.
(1) Construct a suffix tree with the first string. In each node of the suffix tree maintain a count, which will be initialized to zero.
(2) Now search all the suffix strings of each string, and while searching increment the count of the suffix-tree-node if found.
(3) Repeat step (2) for all the N-1 strings (except the first string).
(4) Do DFS on the suffix tree and return the longest-string, where node is considered valid only if its count is equal to N-1.
Here is the C++ code ...
Output:
- chetan.j9 May 10, 2013Longest common substring == ted