slfeng
BAN USER/*
Given 2 set of arrays of size N(sorted +ve integers ) find the median of the resultant array of size 2N.
(dont even think of sorting the two arrays in a third array , though u can sort them. Try something better than order NLogN
for visual c++ 2005
*/
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <iterator>
#include <math.h>
#include <numeric>
#include <sstream>
#include <stack>
#include <string>
using namespace std;
class Solution
{
public:
static int FindNLargestNumberInTwoArray( int arrA[], int nALength, int arrB[], int nBLength, int n)
{
if ( n == 1 )
return max( arrA[ nALength - 1], arrB[ nBLength - 1]);
int nRemoveNum = n / 2;
int nMinRemovedValueInA = arrA[ nALength - nRemoveNum ];
int nMinRemovedValueInB = arrB[ nBLength - nRemoveNum ];
if ( nMinRemovedValueInA > nMinRemovedValueInB )
// remove top nRemove Num in A
return FindNLargestNumberInTwoArray( arrA, nALength - nRemoveNum, arrB, nBLength, n - nRemoveNum );
else
// remove top nRemove Num in B
return FindNLargestNumberInTwoArray( arrA, nALength, arrB, nBLength - nRemoveNum, n - nRemoveNum );
}
static int FindMedian( int arrA[], int nALength, int arrB[], int nBLength)
{
return FindNLargestNumberInTwoArray(arrA, nALength, arrB, nBLength, ( nALength + nBLength + 1 ) / 2 );
}
};
int _tmain(int argc, _TCHAR* argv[])
{
int arrA[] = {1,3,5,7,8,9,17};
int arrB[] = {2,10,11,15,16,17,18};
int nResult = Solution::FindMedian( arrA, sizeof( arrA ) / sizeof( int ), arrB, sizeof( arrB ) / sizeof( int ) );
// output result
cout << "The answer is " << nResult << "." << endl;
_getch();
return 0;
}
/*
Given a NxN matrix which contains all distinct 1 to n^2 numbers, write code to print sequence of increasing adjacent sequential numbers.
ex:
1 5 9
2 3 8
4 6 7
should print
6 7 8 9
for visual c++ 2005
*/
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <iterator>
#include <math.h>
#include <numeric>
#include <sstream>
#include <stack>
#include <string>
using namespace std;
map<pair<int, int>, bool> mapIsNeighbor;
class Solution
{
public:
static void SetNeighbor( int i, int j)
{
if ( i < j )
mapIsNeighbor[ make_pair( i, j ) ] = true;
else
mapIsNeighbor[ make_pair( j, i ) ] = true;
}
static bool IsNeighbor( int i, int j)
{
if ( i < j )
return mapIsNeighbor.end() != mapIsNeighbor.find(make_pair( i, j ));
else
return mapIsNeighbor.end() != mapIsNeighbor.find(make_pair( j, i ));
}
static vector<int> FindIncNumbers(vector<vector<int>> vecInput)
{
vector<int> vecResult;
size_t N = vecInput.size();
for ( size_t i = 0; i < N; i ++)
for( size_t j = 0; j < N; j ++)
{
if ( j + 1 < N )
SetNeighbor( vecInput[i][j], vecInput[i][j + 1]);
if ( i + 1 < N )
SetNeighbor( vecInput[i][j], vecInput[i + 1][j]);
}
int nLength = 1;
vecResult.push_back(1);
int nFirstInt = 2;
while ( nFirstInt <= static_cast<int>( N * N ) )
{
int nInt = nFirstInt;
int nLenghTemp = 1;
while ( IsNeighbor( nInt - 1, nInt ) )
{
if ( nInt <= static_cast<int>( N * N ) )
nInt ++;
}
nLenghTemp = nInt - nFirstInt + 1;
if ( nLenghTemp > nLength )
{
nLength = nLenghTemp;
vecResult.clear();
for ( int i = nFirstInt - 1; i < nInt; i ++ )
vecResult.push_back( i );
}
if ( nFirstInt != nInt )
nFirstInt = nInt;
else
nFirstInt ++;
}
return vecResult;
}
};
int _tmain(int argc, _TCHAR* argv[])
{
// prepare input data
int arrLine1[] = {1,5,9};
int arrLine2[] = {2,3,8};
int arrLine3[] = {4,6,7};
vector< vector< int > > vecInput;
vecInput.push_back( vector<int>( arrLine1, arrLine1 + sizeof( arrLine1 ) / sizeof( int ) ));
vecInput.push_back( vector<int>( arrLine2, arrLine2 + sizeof( arrLine2 ) / sizeof( int ) ));
vecInput.push_back( vector<int>( arrLine3, arrLine3 + sizeof( arrLine3 ) / sizeof( int ) ));
vector<int> vecResult = Solution::FindIncNumbers( vecInput );
// output result
copy( vecResult.begin(), vecResult.end(), ostream_iterator<int>( cout, " ") );
_getch();
return 0;
}
// RePaste
/*
Output top N positive integer in string comparison order. For example, let's say N=1000, then you need to output in string comparison order as below:
1, 10, 100, 1000, 101, 102, ... 109, 11, 110, ...
*/
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <iterator>
#include <math.h>
#include <numeric>
#include <sstream>
#include <stack>
#include <string>
using namespace std;
struct Node
{
Node( int nValue )
{
this->m_nValue = nValue;
memset( this->m_SubTree, 0, sizeof( Node * ) * 10 );
}
int m_nValue;
Node * m_SubTree[10];
};
class Solution
{
public:
static void AddToTree( int nValue, Node * & pTree)
{
vector<int> vecTreePath;
int nValueCopy = nValue;
while ( nValueCopy > 0 )
{
vecTreePath.push_back( nValueCopy % 10 );
nValueCopy /= 10;
}
Node * pParent = pTree;
{
for ( size_t i = vecTreePath.size() - 1; i > 0; i -- )
pParent = pParent->m_SubTree[ vecTreePath[i] ];
}
pParent->m_SubTree[ vecTreePath[0] ] = new Node(nValue);
}
static void CreateTree( int nValue, Node * & pTree )
{
if ( nValue <= 0 )
return;
pTree = new Node( 0 );
for ( int i = 1; i <= nValue; i ++ )
AddToTree( i, pTree );
}
static void PrintTreeInDFS( Node * pTree )
{
if ( !pTree )
return;
// skip zero
if ( pTree->m_nValue )
printf( "%d ", pTree->m_nValue);
for ( int ii = 0; ii < 10; ii ++ )
{
if ( pTree->m_SubTree[ ii ])
PrintTreeInDFS( pTree->m_SubTree[ ii ] );
}
}
static void DeleteTree( Node * & pTree )
{
for ( int i = 0; i < 10; i ++ )
{
if ( pTree->m_SubTree[i] )
DeleteTree( pTree->m_SubTree[i]);
}
delete pTree;
pTree = NULL;
}
};
int _tmain(int argc, _TCHAR* argv[])
{
Node * pTree = NULL;
Solution::CreateTree( 1000, pTree );
Solution::PrintTreeInDFS( pTree );
Solution::DeleteTree( pTree );
_getch();
return 0;
}
/*
Output top N positive integer in string comparison order. For example, let's say N=1000, then you need to output in string comparison order as below:
1, 10, 100, 1000, 101, 102, ... 109, 11, 110, ...
*/
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <iterator>
#include <math.h>
#include <numeric>
#include <sstream>
#include <stack>
#include <string>
using namespace std;
struct Node
{
Node( int nValue )
{
this->m_nValue = nValue;
memset( this->m_SubTree, 0, sizeof( Node * ) * 10 );
}
int m_nValue;
Node * m_SubTree[10];
};
class Solution
{
public:
static void AddToTree( int nValue, Node * & pTree)
{
vector<int> vecTreePath;
int nValueCopy = nValue;
while ( nValueCopy > 0 )
{
vecTreePath.push_back( nValueCopy % 10 );
nValueCopy /= 10;
}
Node * pParent = pTree;
{
for ( size_t i = vecTreePath.size() - 1; i > 0; i -- )
pParent = pParent->m_SubTree[ vecTreePath[i] ];
}
pParent->m_SubTree[ vecTreePath[0] ] = new Node(nValue);
}
static void CreateTree( int nValue, Node * & pTree )
{
if ( nValue <= 0 )
return;
pTree = new Node( 0 );
for ( int i = 1; i <= nValue; i ++ )
AddToTree( i, pTree );
}
static void PrintTreeInDFS( Node * pTree )
{
if ( !pTree )
return;
// skip zero
if ( pTree->m_nValue )
printf( "%d ", pTree->m_nValue);
for ( int ii = 0; ii < 10; ii ++ )
{
if ( pTree->m_SubTree[ ii ])
PrintTreeInDFS( pTree->m_SubTree[ ii ] );
}
}
static void DeleteTree( Node * & pTree )
{
for ( int i = 0; i < 10; i ++ )
{
if ( pTree->m_SubTree[i] )
DeleteTree( pTree->m_SubTree[i]);
}
delete pTree;
pTree = NULL;
}
};
int _tmain(int argc, _TCHAR* argv[])
{
Node * pTree = NULL;
Solution::CreateTree( 1000, pTree );
Solution::PrintTreeInDFS( pTree );
Solution::DeleteTree( pTree );
_getch();
return 0;
}
/*
Write a method to return first five 10 digit prime numbers.
*/
#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <iterator>
#include <math.h>
#include <numeric> // std::accumulate
#include <sstream>
#include <stack>
#include <string>
using namespace std;
vector<int> vecPrimeTable;
int nPrimeTableMax = 0;
class Solution
{
public:
static inline bool IsPrime( int nInt )
{
int nSqrt = static_cast<int>( sqrt( nInt * 1.0 ) );
if ( nSqrt > nPrimeTableMax )
CalculatePrimeTable( static_cast<int>( nSqrt * 1.1 ) );
for ( vector<int>::iterator ii = vecPrimeTable.begin(); ii != vecPrimeTable.end(); ii ++)
{
if ( *ii > nSqrt )
break;
if ( nInt % *ii == 0 )
return false;
}
return true;
}
static void CalculatePrimeTable( int nIntMax )
{
if ( 0 == vecPrimeTable.size() )
vecPrimeTable.push_back( 2 );
int nIntMin = vecPrimeTable[ vecPrimeTable.size() - 1 ] + 1;
if ( nIntMin % 2 == 0)
nIntMin ++;
for ( int i = nIntMin; i <= nIntMax; i += 2)
{
if ( IsPrime( i ))
vecPrimeTable.push_back( i );
}
nPrimeTableMax = max( nPrimeTableMax, nIntMax );
}
static std::vector<int> OutputFirstNPrime( int nBegin, int nCount )
{
std::vector<int> vecResult;
//CalculatePrimeTable( static_cast<int>( sqrt( nBegin * 1.1 ) ) );
int nValue = nBegin;
if ( 0 == nBegin % 2 )
nValue ++;
while ( nCount >= 0 )
{
if ( IsPrime( nValue ))
{
vecResult.push_back( nValue );
nCount --;
}
nValue += 2;
}
return vecResult;
}
static void OutputArray( int A[], int n)
{
std::cout << n << std::endl;
for ( int ii = 0; ii < n; ii ++ )
if ( ii < n - 1 )
std::cout << A[ii] << ",";
else
std::cout << A[ii];
std::cout << std::endl;
}
};
int _tmain(int argc, _TCHAR* argv[])
{
std::vector<int> vecResult = Solution::OutputFirstNPrime(1000000000, 10);
copy( vecResult.begin(), vecResult.end(), ostream_iterator<int>(cout, " "));
_getch();
return 0;
}
- slfeng July 30, 2014