Tags: , | Posted by Admin on 5/10/2012 7:37 AM | Comments (1)

A friend of mine is interviewing for a job. One of the interview questions got me thinking, just wanted some feedback.

There are 2 non-negative integers: i and j. Given the following equation, find an (optimal) solution to iterate over i and j in such a way that the output is sorted.

2^i * 5^j

So the first few rounds would look like this:

2^0 * 5^0 = 1
2^1 * 5^0 = 2
2^2 * 5^0 = 4
2^0 * 5^1 = 5
2^3 * 5^0 = 8
2^1 * 5^1 = 10
2^4 * 5^0 = 16
2^2 * 5^1 = 20
2^0 * 5^2 = 25

Try as I might, I can't see a pattern. Your thoughts?

Comments (1) -

Aron Monszpart Hungary on 1/2/2013 2:51 PM One suggestion:


#include <map>

int g( uint a, uint b )
{
   using namespace std;
  
   // ordered storage
   map< uint,pair<uint,uint> > heap;
   // insert root element (a^0*b^0 = 1)
   heap[ 1U ] = make_pair( 0U, 0U );
  
   // run iterations
   const uint N = 200U; uint n = 0U;
   while ( n++ < N )
   {
      // pop minimum element from front
      auto front = *heap.begin(); heap.erase( heap.begin() );

      // ordered insert of new neighbour 1
      uint newKey = front.first * a;
      if ( !heap.count(newKey) ) // if not inserted yet
         heap[ newKey ] = std::make_pair( front.second.first+1, front.second.second );
      
      // ordered insert of new neighbour 2
      newKey = front.first * b;
      if ( !heap.count(newKey) ) // if not inserted yet
         heap[ newKey ] = std::make_pair( front.second.first, front.second.second+1 );
      
      
      // print current
      std::cout << a << "^" << front.second.first << "*" << b << "^" << front.second.second << "=" << front.first << std::endl;
   }
  
   return 0;
}

Add comment




  Country flag
biuquote
  • Comment
  • Preview
Loading