Microsoft Interview Question
Country: India
@sse : Good explanation. However it wont be that simple i think when you are performing parsing. because:
1. There might be different functions in different class hierarchy with same name and one is get called but another wont. For Ex.
class A {
fun1 ();
};
class B {
fun1 ();
};
B b;
b.fun1 (); //note fun1 is called but you need to determine b's type over here. So you have to maintain symbol table as well
2. functions called with using object but when you call it from class's another member function it wont called using any object (syntactically). For ex.
class A {
fun1 ();
};
class B {
fun1 ();
public :
fun2 () {
fun1 ()
}
};
In above scenario, you need to mark only B's fun1 as known. Also need to maintain per class functions list OR need to perform name mangling.
3. There is function declaration , definition and function call. You need to differentiate all those. It is more difficult when there is no argument. For ex.
//declaration
fun1 ();
//definition
fun1 ()
{
// do relevant stuff
}
//function call
fun1 ()
Most importantly, I think interviewer might have asked to write sudo code or algorithm instead of function/code (question says that write a function).
One approach for this is we create the map as it contains all the fucntions which encounter while scanning
starting from main(), the function(s) which is called by main simply put that function into a linked list and remove from map also at the end if map contains any item(s) then those are waste functions and the linked list contains all the used functions
1.Scan the class once to get total number of function definition..let it be n,now create a bool array[n][n],
2-start scanning the class one by one..go through each function definition and make bool value array[i][j]=1 if there is function call from ith function(may 2 function be same)
3-check the functions call from the constructor directly and used the bool array to know other called function..u will in o(n^2) will know which function is not used..and which is used..
see if this can work
for every class we do following step's :
1) first we declare a static variable say: static int is_called;
2) now say we have 32 function :
for every function set corresponding bit.
ie. for i'th function include (is_called)&(1<<i)
3) now in class destructor : u can map this variable to know all function called.
The question said “Suppose you are developing a code editor” so if this is the case then we can use following path.
Create a list of function also
Create a hashmap which will have function name and a bool parameter say reachable.
So whenever you are writing code and encounter any other function, just add that function to hashmap.
And while compiling the application, return the list of functions which are not present in hashmap.
If code files are already given, then we have to scan the entire code
Proposed solution:
- sse July 15, 20121. create a MAP as <function_name_with_signature, booleanFlag>
2. crate a set for private and protected functions.
3. create a MAP for un-known status fuctions i.e function is called or not we dont know..
UN-KNOWN MAP <fucntion_name, list of fucntions called in this function>
Algo:
1.parse every funtion, if it calls any other function, then set flag of the corresponding called function. and add the main function to un-known status fucntion set.
ex: fun1 () { fun2();}
then fun2's flag will be set to true.
and fun1 will be added to UNKNOWN map.
2. for any call to member function in the fucntion definition is found, check in unknown map first, if it is found remove it from UNKNOW.
interviewer is not happy with my answer.......
please post your comments.....I am curious abt answer.