Amazon Interview Question
Country: United States
Well this is a Design question ..So My Algo is as follows.
1> Use Structure with n children, on parent pointer , one data field and one name field.
2> Use this Structure to make N ary Tree with parent Child relationship. We can use inheritance feature of OOPs here.
3> Now we can use this structure to make Files/Folder accourdingly.
if Files that it parent pointer points to the Folder where it belongs with all its child pointer pointing to NULL and struct->data is the File Content.
else if Folder . point it parent point to it Parent Folder while Child still pointing to NULL but its Struct->data as NULL.
that way we can differentiate between file /folder and maintain its relationship.
Here we can optimise the use of child pointers
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;
}
};
- Anonymous May 18, 2012