shyamal.pandya
BAN USER1]Take the string as an input
2] split it into odd and even numbered characters
3] create a even char string half of count of even characters(this would help in generating a smaller permutation subset)
4] Generate all possible permutations of an even number subset(using dynamic programming)
5] use this list to generate the pallindrome by reversing each string and appending at the end(use odd number characters in the middle of the string).
Below is the implemented code for the same.
#include "stdafx.h"
#include <string>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
void FindEvenAndOddNumberedCharacters(const string &strInput,string& strEvenCharString,string& strOddCharString);
typedef vector<string> stringVect;
stringVect GenerateSubSets(string setVals,int nIdx);
void GeneratePallindromes(string strEvenCharString,string strOddCharString);
int _tmain(int argc, _TCHAR* argv[])
{
string strInput = "abfdRacecaRAbAorTITabcdef";
string strEvenCharString, strOddCharString;
FindEvenAndOddNumberedCharacters(strInput,strEvenCharString,strOddCharString);
cout << "Odd Characters: " <<strOddCharString <<endl <<"Even Characters : "<<strEvenCharString << endl;
cout << "Max Len Pallindrome : "<< strEvenCharString.length()*2 +1 << endl;
GeneratePallindromes(strEvenCharString,strOddCharString);
std::getchar();
return 0;
}
/*
spit out the pallindromes
*/
void GeneratePallindromes(string strEvenCharString,string strOddCharString)
{
int nTotPallinCount=0;
stringVect vOnesidePallindromes = GenerateSubSets(strEvenCharString,0);
for(auto strOneSidePallin:vOnesidePallindromes)
{
string strReversePallin(strOneSidePallin);
std::reverse(strReversePallin.begin(), strReversePallin.end());
cout << strOneSidePallin<<strReversePallin<<endl;
nTotPallinCount++;
// take into condsideration the odd characaters use them at the center of the string to pivot around the same.
for(auto iter= strOddCharString.begin();iter != strOddCharString.end();iter++)
{
cout << strOneSidePallin<<*iter<<strReversePallin<<endl;
nTotPallinCount++;
}
}
cout << "Total Pallin Drome Count : " <<nTotPallinCount<< endl;
}
/*
Find out all the odd and even characaters so that they can be used to generate a pallin drome
*/
void FindEvenAndOddNumberedCharacters(const string &strInput,string& strEvenCharString,string& strOddCharString){
map<char,int> charNoMap;
// get to each character and get a count of each of the characters
for(auto iter= strInput.begin();iter != strInput.end();iter++)
{
charNoMap[*iter]++;
}
// count the characters if they are odd or even if even pick the even stream and push to pallindrome list
// if odd then just pick 1 character in odd list and push the rest into the even list.
for (auto iter : charNoMap)
{
int nCount = iter.second ;
if(nCount % 2 != 0) // if odd count
{
strOddCharString+=iter.first;
nCount--;
}
if(nCount>0)
{
// just spit out half of the even characters to help create pallindromes
for(auto i=0 ;i<nCount/2;i++) strEvenCharString+=iter.first;
}
}
}
/*
Use dynamic programming to generate the string subsets which can then be used to generate pallindromes
*/
stringVect GenerateSubSets(string setVals,int nIdx){
stringVect retStringVect;
if(setVals.length() == nIdx){
retStringVect.push_back(string()); // pushing empty vector
}
else{
retStringVect = GenerateSubSets(setVals,nIdx+1);
auto nItem = setVals[nIdx];
stringVect tempvect;
for(auto vect:retStringVect)
tempvect.push_back(vect);
for(auto iter = tempvect.begin();iter != tempvect.end();iter++){
iter->push_back(nItem);
}
for(auto vect:tempvect)
retStringVect.push_back(std::move(vect));
}
return retStringVect;
}
Look up : O(n)
Insertion: O(n)
Deletion: O(n2)
Space conserved as any digit at any level would only be stored once. With 1 million numbers there is a likely hood that a particular sequence is repeated more often for example say could be numbers in a particular series :
65423444444
65423444445
...
65423444449
Please find below the code that implements the idea.
#include "stdafx.h"
#include <iostream>
#include <memory>
struct All_0_to_9_Node;
typedef All_0_to_9_Node* AllDigitPtr ;
typedef std::unique_ptr<All_0_to_9_Node> AllDigitUniquePtr;
/*
Representing a number something like this :
If there are million number there is a likely hood that each number is going to be closer to the other one
in which case lot of these entities would get reused and further memory would only be allocated if there number in that
direction else it would be an empty pointer.
For example for a number like : 6043.......1 The representation would look something like below
[0]-> nullptr
[1]-> nullptr
[2]-> nullptr [0]-> nullptr
[3]-> nullptr [1]-> nullptr [0]-> nullptr
[4]-> nullptr [2]-> nullptr [1]-> nullptr
[5]-> nullptr [3]-> nullptr [2]-> nullptr [0]-> nullptr
[6]------------>[0]------------>[4]----------> [3]---------> .................... [1]-> nullptr
[7]-> nullptr [1]-> nullptr [5]-> nullptr [4]-> nullptr [2]-> nullptr
[8]-> nullptr [2]-> nullptr [6]-> nullptr [5]-> nullptr [3]-> nullptr
[9]-> nullptr [3]-> nullptr [7]-> nullptr [6]-> nullptr [4]-> nullptr
[4]-> nullptr [8]-> nullptr [7]-> nullptr [5]-> nullptr
[5]-> nullptr [9]-> nullptr [8]-> nullptr [6]-> nullptr
[6]-> nullptr [9]-> nullptr [7]-> nullptr
[7]-> nullptr [8]-> nullptr
[8]-> nullptr [9]-> nullptr
[9]-> nullptr
*/
typedef struct NoNode{
AllDigitPtr pNextDigitList;
short nNo;
NoNode():nNo(0),pNextDigitList(nullptr){}
NoNode(short no,AllDigitPtr pNextDigit):nNo(no),pNextDigitList(pNextDigit){}
~NoNode(){
if(nullptr != pNextDigitList)
{
delete pNextDigitList;
pNextDigitList= nullptr;
}
}
}NoNode;
typedef NoNode* NoNodePtr ;
typedef struct All_0_to_9_Node {
NoNodePtr m_NoPtrs[10];
All_0_to_9_Node(){
for(int i=0;i<10;i++)
{
m_NoPtrs[i]=nullptr;
}
}
~All_0_to_9_Node(){
for(int i=0;i<10;i++)
{
if(nullptr != m_NoPtrs[i])
{
delete m_NoPtrs[i];
m_NoPtrs[i]=nullptr;
}
}
}
bool IsValidDigit(short nNo){return (nNo >= 0 && nNo <= 9) ? true : false;}
/*
Checks if the digit is already present in current node
*/
bool IsDigitPresent(short nNo){
if( IsValidDigit(nNo) && (nullptr != m_NoPtrs[nNo])) return true;
return false;
}
/*
returns true if already present and if not present would add it.
would return false if the number is not already present.
*/
bool AddDigit(short nNo, bool bIsLastDigit= false){
if(!IsValidDigit(nNo)) { return false;}
if(IsDigitPresent(nNo)) {return true;}
m_NoPtrs[nNo]= CreateDigitNode(nNo,bIsLastDigit);
return true;
}
/*
Creates a node for the particular digit in question
*/
NoNodePtr CreateDigitNode(short nNo, bool bIsLastDigit){
AllDigitPtr pNextNoPtr = bIsLastDigit? nullptr:new All_0_to_9_Node();
return new NoNode(nNo,pNextNoPtr);
}
/*
Node insertion works very simple. It picks up the current digit and tries adding the same.
If it's already present then it won't add the same else a new one would get created.
Else it would chip of the number just added and the pass the remianing number to the corresponding
digits child node to get added. If would stop adding any further then the length of the number reduces to 1
return true if able to add the number and false otherwise.
*/
bool InsertNo(const std::string& strMobileNo){
short nNo = strMobileNo.at(0) - 48;
if(AddDigit(nNo,strMobileNo.length()==1? true : false))
{
if(strMobileNo.length() > 1)
{
std::string strRemainingNo(strMobileNo.substr(1));
m_NoPtrs[nNo]->pNextDigitList->InsertNo(strRemainingNo);
}
return true; // done adding the mobile number;
}
return false;
}
/*
Looks up for the number one digit at a time. It would keep pivoting into the appropriate hive for he remaining part of the
number.
*/
bool FindNumber(const std::string& strMobileNo){
short nNo = strMobileNo.at(0) - 48;
if(IsDigitPresent(nNo))
{
if(strMobileNo.length() == 1) return true;
std::string strRemainingNo(strMobileNo.substr(1));
return m_NoPtrs[nNo]->pNextDigitList->FindNumber(strRemainingNo);
}
return false;
}
}All_0_to_9_Node;
int _tmain(int argc, _TCHAR* argv[])
{
AllDigitUniquePtr pRootNode(new All_0_to_9_Node());
pRootNode->InsertNo("23412233355");
pRootNode->InsertNo("23435523343");
bool bRetVal = pRootNode->FindNumber("23435523341");
std::cout << "23435523341 : Found =" << std::boolalpha<< bRetVal<<std::endl;
bRetVal =pRootNode->FindNumber("23412233355");
std::cout << "23412233355 : Found =" << std::boolalpha<< bRetVal<<std::endl;
return 0;
}
I believe I misinterpreted the question and hence, ended up posting a wrong answer. Will work around building a better fix.
- shyamal.pandya July 02, 2013How about this :
int FindGreatestCommonInteger(std::list<int> lista,std::list<int> listb){
int nGCI = numeric_limits<int>::min();
int nMax = numeric_limits<int>::min();
int nUpperBound = min(lista.size(),listb.size());
for(int idx=0;i<nUpperBound;idx++)
{
nMax = max(lista[idx],listb[idx]);
nGCI = max(nGCI,nMax);
}
int nNewUpperBound = max(lista.size(),listb.size());
for( ;nIdx < nNewUpperBound;nIdx++){
int nVal = (lista.size() == nNewUpperBound) ?lista[nIdx]:listb[nidx];
nGCI = max(nGCI,nVal);
}
return nGCI;
}
This would perform the operation in O(m) time which is equivalent to the size of the largest array.
- shyamal.pandya June 26, 2013We could use a Rabin-Karp Algorithm(Check on Wiki) to search the number that you are looking for :
You could follow the steps mentioned below :
1] Generate the hash of the number that you are looking for
2] Keep generating the rolling hash of the input stream as it keeps coming in.
Rolling hash : s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]
3]Whenever the hash of the number you are looking for matches the hash of the numbers from the stream you have found the number.
public class ConvertNoToColHeader {
public static void ConvAndPrint(int n){
System.out.println(ConverNoToColHdr(n));
}
public static String ConverNoToColHdr(int n){
if(n < 26){
char mChar = (char)(65 + n);
return Character.toString(mChar);
}
else
{
String strHeader = ConverNoToColHdr(n/26 - 1);
strHeader += ConverNoToColHdr(n%26);
return strHeader;
}
}
}
public static void main(String[] args) {
String strColHeader;
ConvertNoToColHeader.ConvAndPrint(10);
ConvertNoToColHeader.ConvAndPrint(20);
ConvertNoToColHeader.ConvAndPrint(25);
ConvertNoToColHeader.ConvAndPrint(26);
ConvertNoToColHeader.ConvAndPrint(27);
ConvertNoToColHeader.ConvAndPrint(52);
ConvertNoToColHeader.ConvAndPrint(53);
ConvertNoToColHeader.ConvAndPrint(100);
ConvertNoToColHeader.ConvAndPrint(700);
ConvertNoToColHeader.ConvAndPrint(750);
ConvertNoToColHeader.ConvAndPrint(800);
ConvertNoToColHeader.ConvAndPrint(1000);
ConvertNoToColHeader.ConvAndPrint(100000);
}
Repjudydschultz1234, Android test engineer at Eterno Infotech Pvt Ltd
Spent a weekend researching weebles in Nigeria. My current pet project is developing strategies for how to break someone's ...
Simple : on Cube 1 : 0,1,2,3,4,5
- shyamal.pandya September 29, 2013On Cube 2 : 0,1,2,6,7,8
Now 6 can be interchangeably used as 9 that does the trick.