DATA STRUCTURE INTERVIEW QUESTION & ANSWERS
| 26. |
What is the difference between divide and conquer and dynamic programming? |
| |
| divide and conquer |
dynamic programming |
| The problem is divided into small subproblems. These subproblems are solved independentfy. Finally all the
solutions of sub problems are collected together to get the solution to the given problem. |
In dynamic programming many decision sequences are generated and all the overlapping sub instances are considered. |
| In this method duplications in sub–solutions are neglected, i.e., duplicate subsolutions
may be obtained. |
In dynamic computing duplications in solutions is avoided totally. |
| Divide and conquer is less efficient because of rework on solutions. |
Dynamic programming is efficient than divide and conquer strategy. |
| The divide and conquer uses top down approach of problem solving (recursive methods). |
Dynamic programming uses bottom up approach of problem solving (iterative method). |
| Divide and conquer splits its input at specific deterministic points usually in the
middle.
|
Dynamic programming splits its input at every possible split points rather than at a particular point. After trying all split points it determines which split point is optimal. |
|
| 27. |
State any two applications of queue? |
| |
- Queues are useful in job scheduling algorithms in the operating system.
- Queues are also useful for categorization of data.
|
| 28. |
Define tree? |
| |
A tree is a data structure that represents a hierarchical relationship between various elements.
|
| 29. |
Given two examples of non linear data structures which are widely used? |
| |
The widely used non linear data structures are :
|
| 30. |
What do you mean by worst cast time complexity? |
| |
Worst case time complexity is a time complexity measure in which the worst-case scenario for time taken to do the steps taken in the algorithm is considered. The measure considers the maximum number of computation steps required on any input size N. It considers the closest approximation of the maximum time taken. It is given by the ‘big–O’ notation.
|
