DFT/CAD Interview Questions

1) Assume strings are streaming indefinitely. Describe the different data structures and its time complexity to perform an search operation ( if the string already received)

       Basically we have to perform two operations

         1) Find

         2) Insert ( if it is not found )

       Data Structures : Array         Linked List         Trees            Hash Tables
       Insert                :
       Find                  :

                       

       Explain the analysis (above) with an example.

2) Given sets like {A,B} {A,C} {C,B} {A,D}. Here C is the input of B and it is a dependency (not necessarily immediate input). Write an algorithm to return all the possible paths in the set. Here the paths are {A,C,B} and {A,D}.

3) Hash Tables discussion: 

          Hash Functions
          Perfect Hashing
          Rehashing
          Collision (Linked list Vs Open addressing), 

       

4) There is an Hash with two types of implementation

           a) Tree based (ADT)

           b)  Array Based (classical).

       compare the performances and applications.

5) There is an Hash implementation, if the number of inputs less than threshold then it uses an simple array to store values (i.e no hash functions). For inputs greater than threshold it uses the classical implementation (hash function and key and index). To look up the values: In the first case (array based)  we iterate the entire array. In the second case we use the standard procedure (hash function then generate index and access the value).

Give the algorithm analysis and Explain if this is an efficient way of implementation?