Intel Interview Question
Software Engineer / DevelopersI hope it does not go for recursion as every header #ifndef and #defines to avoid mutiple inclusions. Here the problem generally comes with declarations : one type declaration includes other which uses the first one inside.
Eg:
// In A.h
Class A{
.....
public:
B* b;
....
};
// In B.h
Class B
{
.....
public:
A* a;
....
}
In this situation each class declaration is not complete as the other is not complete.
These kind of problems can be avoid by just declaring other type in each header.
// A.h
class B;
class A{
.....
B* b;
....};
//B.h
class A;
class B{
....
A* a;
.....
};
int f(char* fileName, size_t n)
create Stack [allFiles] out of all the include# in fileName
Have a hashtable where key is the absolute header file name.
while(!allFiles.empty())
{
File f = allFiles.pop();
if(!hashtable.key(f.full_path()))
{
hashtable.put(f.full_path(), f);
}
Add all the include# from file f if it's not in allFiles Stack
}
This problem can be easily solved by defining a Graph dependency and testing for a circular path as explained below:
- Jagga Muddasani May 28, 2011For a given set of files you can create a Graph consisting of two nodes and an edge between them if the file "B" is included in the file "A" as
A -> B
As you scan the file, collect all such pairs for a given set of files recursively and construct the graph incrementally for each such pair and thus we can easily use the graph traversal algorithms to find and detect any circular paths that may exists from a given node "X" by employing either the DFS (depth first search) or BFS (breadth first search) algorithms.
Every time a new file need to be included check for any such possible cicurlar paths and if you detect one then do not include the file otherwise continue recuversively until there is no circular path exists.