LBaralgeen
BAN USERUse shift left and the rest fill with addition operations..
- LBaralgeen September 05, 2014--- but NOT virtual constructors
it's not true. Borland Builder C++ has virtual constructor to support Delphi VCL library
use file mapping then apply classic merge sort to pointer on this file. almost no memory will be used.
- LBaralgeen March 12, 2014API to support pear-to-pear encrypted messages
- LBaralgeen March 03, 2014if tweets will be stored with hashes for each word then such search always will be O(1)
- LBaralgeen February 25, 2014something like that:
std::string encode( int num )
{
static char alphabet[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
std::vector<char> sb;
const size_t base = sizeof(alphabet);
while ( num > 0 )
{
size_t index = num % base;
sb.push_back( alphabet[ index ] );
num /= base;
}
std::string result = alphabet;
std::reverse_copy( sb.begin(), sb.end(), result.begin() );
result[ sb.size() ] = '\0';
return result;
}
void Test6486723970203648()
{
char sym[] = {'a', 'c' , 't'};
std::set<char> chrs(sym, sym + sizeof(sym));
char* arr[] = {"cat", "act", "ac", "stop" , "cac" };
int result = 0;
for( size_t i = 0; i < _countof(arr); i++)
{
size_t length = ::strlen(arr[ i ]);
if( sizeof(sym) >= length )
{
char tst[255] = {'\0'};
for( size_t j = 0; j < length; j++ )
{
char& chr = arr[ i ][j];
if( chrs.find( chr ) == chrs.end()
|| '\0' != tst[ chr ] ) // word should not use symbol twice
{
length = 0x00;
break;
}
tst[ chr ] = chr;
}
if( 0x00 != length )
{
std::cout << arr[i] << std::endl;
result++;
}
}
}
CPPUNIT_ASSERT_EQUAL_MESSAGE( "successed", 3, result );
}
with binary tree quite easy - check all parent nodes have no more then two children and data satisfy Binary Tree criteria.
DLL is simple - parents always have one children
write recursive function which will use the chunk of dictionary, take first letter in the middle of chunk (put in the middle of alphabet), than call itself twice with left and right portion of chunk.
speed O(logn)
copy/paste ads from home page search box and then compare prices
- LBaralgeen May 25, 2013void Comparator( std::map<float, point_t*>& arr, const float data, point_t* file, const size_t k, bool op )
{
if( k > arr.size() ) // collect first k values
{
arr[ data ] = file;
return;
}
std::map<float, point_t*>::iterator iter = op ? std::prev( arr.end() ) : arr.begin();
if( op ? (*iter).first > data : data > (*iter).first )
{
arr[ data ] = file;
if( k < arr.size() ) // pull out wrong value
{
op ? arr.erase( std::prev( arr.end() ) ) : arr.erase( arr.begin() );
}
}
}
int test17900686()
{
const size_t k = 3;
point_t largeFile[] = { {1,2}, {3,4}, {5,6}, {7,8}, {9,1}, {4,5}, {3,5}, {2,6}, {2,7}, {1,4}, {7,8}, {3,7}, {8,3}, {4,9}, {4,3}, {8,3}, {2,2} };
std::map<float, point_t*> Xs, Xl, Ys, Yl; // k smallest and largest
// collect 4 * k lowest and largest coordinates
for( size_t i = 0; i < _countof( largeFile ); i++ )
{
Comparator( Ys, largeFile[i].y, &largeFile[i], k, true );
Comparator( Xs, largeFile[i].x, &largeFile[i], k, true );
Comparator( Yl, largeFile[i].y, &largeFile[i], k, false );
Comparator( Xl, largeFile[i].x, &largeFile[i], k, false );
}
Xs.insert(Xl.begin(), Xl.end()); // joint biggest and smallest X
Ys.insert(Yl.begin(), Yl.end()); // joint biggest and smallest Y
std::map<float, pare_t> dist;
// all combinations of k points
for( std::map<float, point_t*>::iterator iterX = Xs.begin(); iterX != Xs.end(); ++iterX )
{
for( std::map<float, point_t*>::iterator iterY = Ys.begin(); iterY != Ys.end(); ++iterY )
{
if( (*iterX).second == (*iterY).second ){ continue; } // skip the same points
float d1 = ::fabs((*iterX).first - (*iterY).second->x);
float d2 = ::fabs((*iterX).second->y - (*iterY).first);
float distance = d1*d1 + d2*d2;
pare_t pare;
pare.first = (*iterX).second;
pare.second = (*iterY).second;
if( k < dist.size() && (*std::prev( dist.end() )).first > distance ) // skip shortest distances
{
continue;
}
dist[ distance ] = pare;
}
}
std::map<float, pare_t>::reverse_iterator iter = dist.rbegin();
float result[k] = {0};
for( size_t i = 0; i < k && iter != dist.rend(); ++iter, i++ )
{
pare_t pare = (*iter).second;
result[i] = ::sqrt((*iter).first);
std::cout << result[i] << " XY0:" << pare.first->x << "-" << pare.first->y << " XY1:" << pare.second->x << "-" << pare.second->y << std::endl;
}
float expected[k] = {9.43398, 8.544, 7.07107}; // 9-1 : 4-9, 1-4 : 9-1, 1-4 : 8-3
return ::memcmp( expected, result, sizeof(result) );
}
// distribute task between smallest and highest
void distribute( size_t CPU[], size_t start, size_t end, bool direction )
{
for( size_t index = start; ; index++ )
{
if( index == end )
{
index = start;
}
if( direction )
{
CPU[index]++;
CPU[index+1]--;
}else
{
CPU[index]--;
CPU[index+1]++;
}
if( 1 >= ::labs( CPU[start] - CPU[end] ) )
{
return;
}
}
}
// there is a circle of N CPU's with amount of tasks loaded on each one.
// Amount of tasks can be devided at N.
// Only one task can be passed between neihgbore CPU's in the circle
void Test17252672()
{
size_t CPU[] = { 2, 9, 3, 6, 5, 1, 2 }; // sum = 28
size_t sumBefore = 0;
for( size_t i = 0; i < _countof(CPU); i++ )
{
sumBefore += CPU[i];
}
CPPUNIT_ASSERT_EQUAL_MESSAGE( "does not pass requeirements", 0, sumBefore % _countof(CPU) );
bool isChanged = true;
size_t minItem = CPU[_countof(CPU) - 1], maxItem = 0;
// neighbor's exchange: share tasks between two CPU's
for( size_t index = 0; isChanged; index++ )
{
size_t next = index + 1;
if( _countof(CPU) - 1 == index )
{
isChanged = false;
next = 0;
}
if( CPU[index] > CPU[next] + 1 )
{
while( 1 < (CPU[index] - CPU[next]) )
{
CPU[ index ]--;
CPU[ next ]++;
}
isChanged = true;
}else
if( CPU[next] > CPU[index] + 1 )
{
while( 1 < (CPU[next] - CPU[index]) )
{
CPU[ next ]--;
CPU[ index ]++;
}
isChanged = true;
}
if( CPU[minItem] >= CPU[ index ] )
{
minItem = index;
}
if( CPU[maxItem] <= CPU[ index ] )
{
maxItem = index;
}
if( _countof(CPU) - 1 == index )
{
index = 0;
}
// adjasment min..max..min or max..min..max and max-min > 1
if( !isChanged && 1 < ( CPU[maxItem] - CPU[minItem] ) )
{
// pass task throw the subchain
distribute( CPU, min(minItem, maxItem), max(minItem, maxItem), minItem < maxItem );
index = 0;
isChanged = true;
}
}
size_t sumAfter = 0;
for( size_t i = 0; i < _countof(CPU); i++ )
{
sumAfter += CPU[i];
}
CPPUNIT_ASSERT_EQUAL_MESSAGE( "does not pass requeirements", 0, sumAfter % _countof(CPU) );
CPPUNIT_ASSERT_EQUAL_MESSAGE( "sums must be the same", sumBefore, sumAfter );
}
size_t findHighBorder( const size_t value, size_t* arr, const size_t length )
{
for( size_t i = 0; i < length; i++ )
{
if( value < arr[i] )
{
return arr[i];
}
}
return value;
}
void Test16759664()
{
size_t L1[] = {4, 10, 15, 24, 26};
size_t L2[] = {0, 9, 12, 20};
size_t L3[] = {5, 18, 22, 30};
map<size_t, size_t> keyer;
keyer[ L1[0] ] = L1[ _countof(L1)-1 ];
keyer[ L2[0] ] = L2[ _countof(L2)-1 ];
keyer[ L3[0] ] = L3[ _countof(L3)-1 ];
const size_t lowerBorder = (*keyer.begin()).second;
std::set<size_t> higher;
higher.insert( findHighBorder( lowerBorder, L1, _countof(L1) ) );
higher.insert( findHighBorder( lowerBorder, L2, _countof(L2) ) );
higher.insert( findHighBorder( lowerBorder, L3, _countof(L3) ) );
size_t higherBorder = (*higher.rbegin());
for( std::set<size_t>::iterator iter = higher.begin(); iter != higher.end(); ++iter )
{
if( *iter != lowerBorder )
{
higherBorder = *iter;
break;
}
}
std::cout << "range is (" << lowerBorder << " - " << higherBorder << ")\n";
}
sorry. Did not realized it should be for Java. Also movieDiscount should be summed
- LBaralgeen June 11, 2012class TMovie
{
public:
enum eType { e2D = 0, e3D = 30, e4D = 50 };
eType m_type;
TMovie( eType type )
{
m_type = type;
}
};
class TTicket
{
public:
enum eAge { adult = 0, kid = 50, senior = 30 };
eAge m_ageDiscount;
TTicket( eAge age )
{
m_ageDiscount = age;
};
};
class TPurchase
{
public:
static float m_SinglePrice;
TMovie * m_movie;
std::vector<TTicket *> m_basket;
int m_dayOfWeek;
int GetCurrentDayOfWeek()
{
return 3;
}
void Add( TTicket::eAge age, size_t num )
{
for( size_t i = 0; i < num; i++ )
{
m_basket.push_back( new TTicket( age ) );
}
}
TPurchase( TMovie::eType type )
{
m_dayOfWeek = GetCurrentDayOfWeek();
m_movie = new TMovie( type );
};
~TPurchase()
{
for( size_t i = 0; i < m_basket.size(); i++ )
{
delete m_basket[i];
}
}
float GetTotalPrice()
{
float price = 0.0;
for( size_t i = 0; i < m_basket.size(); i++ )
{
float ageDiscount = m_basket[i]->m_ageDiscount * m_SinglePrice / 100;
float dayDiscount = ( 2 == GetCurrentDayOfWeek() ? 50 : 0 ) * m_SinglePrice / 100;
float movieDiscount = m_movie->m_type * m_SinglePrice / 100;
price += m_SinglePrice - ( dayDiscount > 0 ? dayDiscount : ageDiscount ) - movieDiscount;
}
return price;
}
};
float TPurchase::m_SinglePrice = 10.0;
void testAmazon13878774()
{
TPurchase tickets( TMovie::e2D );
tickets.Add( TTicket::eAge::adult, 2 );
tickets.Add( TTicket::eAge::kid, 3 );
tickets.Add( TTicket::eAge::senior, 1 );
cout << " Totoal price: " << tickets.GetTotalPrice() << endl;
}
void FacebookTest1()
{
const char const szInput[] = "CAE2W3A";
char tmp[26] = {0x00};
size_t sum = 0;
for( size_t i = 0; i < sizeof(szInput); i++ )
{
char chr = szInput[i];
size_t index = chr - 'A';
if( '0' <= chr && chr <= '9' )
{
sum += chr - '0';
}
else
{
if( 0x00 == tmp[index] )
{
tmp[index] = szInput[i];
}
}
}
for( size_t i = 0; i < 26; i++ )
{
if( tmp[ i ] )
{
cout << tmp[ i ];
}
}
cout << sum << endl;
}
int test20()
{
const char szTest[] = "aaaafghaksdxljwedojlzacskdjhiiuaaaaaaaa";
int maxLen = 0;
int lastIndex = -1;
char szTmp[26] = {0x00};
for( size_t i = 0; i < sizeof(szTest); i++ )
{
char chr = szTest[i];
size_t index = chr - 'a';
if( szTmp[index] == 0x00 )
{
szTmp[index] = chr;
}
else
{
if( maxLen < i - lastIndex && lastIndex > 0 )
{
maxLen = i - lastIndex;
}
lastIndex = i;
::memset( szTmp, 0x00, sizeof(szTmp) );
szTmp[index] = chr;
}
}
cout<<"max length is " << maxLen <<endl;
return(0);
}
for faster result better to use bit array instead of set
int test19()
{
size_t nArrray[] = {2,10,4,3,6,5,7,1,3,8,0};
const size_t n = _countof(nArrray);
set<int> lstTest;
int sum = 0, doubling = 0;
for( size_t i = 0; i < n; i++ )
{
if( lstTest.find( nArrray[i] ) != lstTest.end() )
{
doubling = nArrray[i];
cout << "duplicated number is " << doubling;
}
else
{
lstTest.insert( nArrray[i] );
}
sum += nArrray[i];
}
int missed = ( n * ( n - 1 ) / 2 ) - (sum - doubling);
cout << " and missing number is " << missed << endl;
return(0);
}
did your test you code? it does not work
- LBaralgeen May 21, 2012void test18()
{
int A[4][4] = { {1,5,3,8}
, {7,3,1,8}
, {8,3,5,9}
, {8,3,5,1} };
int B[4][4] = {0x00};
for( size_t i = 0; i < 4; i++ )
{
for( size_t j = 0; j < 4; j++ )
{
int left = (j > 0 ? B[i][j-1] : 0) ;
int upper = (i > 0 ? B[i-1][j] : 0);
int sum = left + upper + A[i][j];
B[i][j] = sum;
}
}
for( size_t i = 0; i < 4; i++ )
{
cout << B[i][0] << ", " << B[i][1] << ", " << B[i][2] << ", " << B[i][3] << "\n";
}
}
O(nLogn)
float power(float x, unsigned int n) {
float aux = 1.0;
while (n > 0) {
if (n & 1) { \\ odd?
aux *= x;
if (n == 1) return aux;
}
x *= x;
n /= 2;
}
return aux;
}
first approach
class TPermission
{
public:
string name;
enum {full_access, read_only, write, read};
};
enum TType { file, folder };
class TFile
{
public:
map<string, set<TPermission>> permissions;
map<string, TFile*> content;
class FSObject* node;
vector<__int64> lstCluster;
enum TAttriute{ system, hidded, archive };
TType type;
bool deleted;
wstring name;
set<TAttriute> attribute;
time_t created, modifyed, accessed;
size_t lenFile;
TFile( TType _type, wstring nameFile ) : node(0x00)
{
type = _type;
name = nameFile;
}
size_t GetFile( void* pBuffer )
{
return lenFile;
};
TFile* findFile( const string& nameFile )
{
for( map<string, TFile*>::iterator it = content.begin(); it != content.end(); ++it )
{
if( 0 == _stricmp( (*it).first.c_str(), nameFile.c_str() ) )
{
return (*it).second;
}
return NULL;
}
}
};
template<size_t N> class TCluster
{
public:
unsigned char* space;
int cylinder;
int order;
TCluster( int c, int o )
{
space = new unsigned char[N+1];
}
~TCluster()
{
delete [] space;
}
};
template<size_t N> class TFS
{
public:
typedef TCluster<N> TClstType;
char driveName;
size_t clusterSize;
typedef TTreeNode<TFile> FSObject;
map<__int64, TClstType*> lstCluster; // index and pointer to real cluster
FSObject *main, *backup;
__int64 findAvailableCluster()
{
map<__int64, TClstType*>::iterator cls = lstCluster.end();
do
{
map<__int64, TClstType*>::iterator cls = lstCluster.find( rand() );
}while( cls != lstCluster.end() );
(*cls).second = new unsigned char( N );
return (*cls).first;
}
~TFS()
{
for( map<__int64, TClstType*>::iterator iter = lstCluster.begin(); iter != lstCluster.begin(); ++iter )
{
if( (*iter).second )
{
delete [] (*iter).second;
}
}
}
TFile* CreateFile( FSObject* folder, wstring name )
{
TFile* file = new TFile(file, name);
file->node = folder->AddNode( file );
return file;
}
void ReadFile( FSObject* folder, wstring name, void* &pBuffer, size_t szBuffer )
{
}
void WriteToFile( FSObject* folder, wstring name, void* pBuffer, size_t szBuffer )
{
TFile* file = folder->data.findFile( name );
if( 0x00 == file )
{
TClstType file = CreateFile( folder, name );
}
void* ptr = pBuffer;
for( size_t i = 0; i < szBuffer / N; i++ )
{
__int64 custerId = findAvailableCluster();
TClstType* cluster = lstCluster[ custerId ];
ptr += ( i * N );
::memcpy( cluster->space, ptr, N);
lstCluster.push_back( custerId );
}
}
TFS( char disk )
{
main = new FSObject( new TFile(folder, L"SYSFILE.IO") );
backup = new FSObject( new TFile(folder, L"SYSFILE.BAK") );
driveName = disk;
clusterSize = N;
}
};
hash is cheaper
__int32 GetHash( __int8* pattern, bool direction )
{
__int8 b1 = direction ? *pattern++ : *(pattern-2);
__int8 b2 = direction ? *pattern++ : *(pattern-1);
__int8 b3 = *pattern;
__int32 result = __int32(b1 << 24) + __int32(b2 << 16) + __int32(b3 << 8);
return result;
}
// without DS
bool CheckPolinoms( char* forward, char* reverse )
{
if( 0x00 == forward || 0x00 == *forward || 0x00 == reverse || 0x00 == *reverse )
{
return false;
}
bool f = ( *forward++ == *(reverse ) );
bool m = ( *forward++ == *(reverse-1) );
bool l = ( *forward++ == *(reverse-2) );
return f && m && l;
}
void test17()
{
char test[] = "abcdefdcbnp";
for( size_t i = 0; _countof(test)-2 > i; i++ )
{
for( size_t j = _countof(test)-2; 2 < j; j-- )
{
if( CheckPolinoms( &test[i], &test[j] ) )
{
cout << i << ", " << j << "\n";
break;
}
}
}
}
static bool IsMyPalindrom( list* node )
{
list* begin = node->GetFirst();
list* end = node->GetLast();
while( begin && end && begin->data == end->data && begin != end )
{
if( begin == end || begin->next == end || begin->next == end->prev )
{
return true;
}
begin = begin->next;
end = end->prev;
}
return begin == end;
}
n^2 = 1 + 3 + ... + (2k-1) + ... + (2n-1)
- LBaralgeen September 11, 2014int square(int n)
{
int s = 0;
for(n = n+n-1; n > 0; n = n-2) s = s + n;
return s;
}