## igor grudenic

BAN USER<pre lang="" line="1" title="CodeMonkey10275" class="run-this">Simple brute force would be to keep all the previous solutions and then iterate over

them to find the minimal one that multiplied by 2 or 5 gives the number greater

then the current element. History search should start at the latest number and continue by decreasing solutions until the first one found and multiplied by 5 is lesser then current element. Complexity is linear space, ant time is certainly better than O(n^2) but one should prove that limited history search is better than O(n) (and it is).

void GetElementsSimple(int n){

list<int> solutions;

int curSolution;

int bestNext;

solutions.push_back(1);

while(n){

curSolution=solutions.back();

cout<<solutions.back()<<" ";

bestNext=curSolution*2;

for(list<int>::reverse_iterator i=solutions.rbegin();

i!=solutions.rend()&& (*i)*5>curSolution;

i++){

if(((*i)*5>curSolution)&&((*i)*5<bestNext)) bestNext=(*i)*5;

if(((*i)*2>curSolution)&&((*i)*2<bestNext)) bestNext=(*i)*2;

}

solutions.push_back(bestNext);

n--;

}

}

Additionally one may try to exercise O(n) solution that takes a numeber 2^i*5^j

and tries to create 2 exchanges. First is to convert a subset of 2^i to 2^(i-n)*5^n. The second is to convert 5^j to 2^m*5^(j-m). Conversion that gets smaller solution must be used.

Optimal conversion for all parameters i and j can be precomputed. This leads to provable O(n) time after precomputation.

</pre><pre title="CodeMonkey10275" input="yes">

</pre>

<pre lang="" line="1" title="CodeMonkey59148" class="run-this">char* LongestPrefix(char **strings,int n){

int i,prefixLength,zeroLength;

char *result;

zeroLength=strlen(strings[0]);

for(prefixLength=0;prefixLength<zeroLength;prefixLength++){

for(i=1;i<n;i++){

if((strings[i][prefixLength]==0)||

(strings[i][prefixLength]!=strings[0][prefixLength]))

break;

}

if(i<n) break;

};

result=(char *)malloc(sizeof(*result)*(prefixLength+1));

strncpy(result,strings[0],prefixLength);

result[prefixLength]=0;

return result;

}</pre><pre title="CodeMonkey59148" input="yes">

</pre>

<pre lang="" line="1" title="CodeMonkey85370" class="run-this">I think this one can be somewhere between linear and n^2. Algorithm goes recursively and it looks into 2 pointers t1 and t2. Suppose t1->data < t2->data. If that holds then children of t1 and t2 point to data that belong to following subsets:

t1->left [-MAXINT,t1->data]

t1->right [t1->data+1,t2->data] U <t2->data,MAXINT]

t2->left [-MAXINT,t1->data] U <t1->data,t2->data]

t2->right <t2->data,MAXINT>

So basically we have to make following recursive calls

...

function(t1->left,t2->left) but limited to print numbers from [-MAXINT,t1->data]

cout<<t1->data;

function(t1->right,t2->left) but limited to print numbers from <a,t2->data]

cout<<t2->data;

function(t1->right,t2->right) but limited to print numbers from <t2->data,MAXINT]

What is the complexity of the solution? Well, for pair of nodes on the top level we create 3 recursive calls on topLevel+1. This leads to 3^level complexity. Since level is log2(n) we have 3^(log2(n))=n^(log2(3))=n^1.5849.

This can be improved by preventing recursive calls on subtrees than do not meet limits requirements, but analysis of this would be much more complicated then I am willing to do at the moment :-).

The entire code for the routine is here:

static void printSorted2TreesInternalNew(

TreeNode *t1,

TreeNode *t2,

int min,

int max){

if((t1==NULL)&&(t2==NULL)) return;

if(t1==NULL)

swapTreePointers(t1,t2);

if(t2==NULL){

printSorted2TreesInternalNew(t1->left_,t2,min,max);

std::cout<<t1->data_<<" ";

printSorted2TreesInternalNew(t1->right_,t2,min,max);

return;

}

if(t2->data_<t1->data_)

swapTreePointers(t1,t2);

printSorted2TreesInternalNew( t1->left_,

t2->left_,

min,

std::min(max,t1->data_));

if((t1->data_>min)&&(t1->data_<=max))

std::cout<<t1->data_<<" ";

printSorted2TreesInternalNew( t1->right_,

t2->left_,

std::max(min,t1->data_),

std::min(max,t2->data_));

if((t2->data_>=min)&&(t2->data_<=max))

std::cout<<t2->data_<<" ";

printSorted2TreesInternalNew( t1->right_,

t2->right_,

std::max(min,t2->data_),

max);

}

Of course you have to call it with min and max set to int range.

</pre><pre title="CodeMonkey85370" input="yes">

</pre>

Rep**evelynleary0**, Consultant at Arista NetworksHi, I am Evelyn from Los Angeles, USA. I have been a Marketing Manager in Veramons Digital Company from last ...

RepJe suis Kirsten. Je travaille dans un magasin en tant que responsables de la chaîne d'approvisionnement pour promouvoir la ...

Rep**clarasbarr**, Korean Air Change Flight at Adap.tvI am ClaraBarr from California USA. Writes and records various different genres for television, film and other artists.Wrote several ...

Rep**sharoneruther**, AT&T Customer service email at ABC TECH SUPPORTI am Sharon, from Bethlehem USA. I am working as a Park naturalist in Sammy's Record Shack company. I ...

Rep**gradyjvierra**, Animator at Alliance Global ServiesJe suis Grady de Phoenix USA. Je travaille en tant que technicien de laboratoire clinique dans la société Samuels Men ...

Rep**LizzieGibson**, Cloud Support Associate at Aspire SystemsI'm an engineering student from Huntsville, AL USA. Have more interest in management and stuff related to business. Promptly ...

RepSoccer lover, coffee addict, guitarist, International Swiss style practitioner and TDC honorary member. Acting at the nexus of simplicity and ...

Rep**ShirleyMHansen**, Project Leader at Chelsio CommunicationsI am Physical Therapy Aide with 3 years experience in hospital. I like to build up my knowledge of various ...

Rep**shirleygause93**, Analyst at Absolute Softech LtdHi, I am Shirley from taxes, Conducted a re-profiling project which enabled our customers to receive orders more efficiently.Planning ...

Rep**melissamewingm**, abc at ABC TECH SUPPORTI am Melissa from Springdale. I function as an Auditing assistant in Bountiful Harvest Health Food Store. My solid interest ...

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

There is a recursive way to find all the solutions:

TrieNode is a node in a prefix tree. Node has a wordMark field that denotes whether set of

- igor grudenic December 08, 2011characters formed by visiting all the parent nodes in a tree constitute a valid word.

Method call newNode=oldNode.moveForward(c) returns new trie node reachable from oldNode

using character c.

Complexity of finding one solution is by O(N*C) (N-sentence length, C-lenght of the longest

dictionary word). Complexity of moveForward(c) is O(1).

Number of solutions may vary greatly depending on a sentence length and size of the

dictionary. For instance if one uses Morse alphabet the number of valid sentences may easily

become exponential.