Wednesday, December 27, 2017

Data structures - 1

This is an old one which was lying into my pile of drafts...Seems still valuable. Thought of discussing about data structure and touch upon key points of interest,,

1. When should we use BFS and DFS .. what is the data  structure used in BFS and DFS.
2. Which technique is used by quick sort
3. How do we analyze the complexity  of algorithms
4. Which procedure uses more memory - iteration or recursion
5. How is time complexity measured. Explain with example.
6. How is space complexity measured ?
7. Which data structure is used for evaluation of expressions ?
8. What is the maximum number of nodes in a binary tree at level 5 ?
9. What is the basic concept behind bubble sort ?
10. What is the difference  between B tree and B+ tree.
11. What is the difference between full binary tree and complete tree
12. What is trinode restructuring and when is it used
13. What are the use cases of heap data structure
14. What is the time complexity in case elements  are already sorted in case of quick sort
15. What is the time complexity of search in hashing
16. In which scenario will you use in-order traversal
17. What is use of avl tree
18. What are the different types of hashing
19. How will you reduce collision in hashing
20. What is the  concept behind priority queue.
21. What is heap property ?
22. What are the types of heap and where are they used
23. In which end will element be added in case of queue and in case of stack
24. From which end the element will be deleted in case of queue and in case of stack
25. Explain selection sort
26. What is the maximum height of an avl tree with 7 nodes
27. Tower of hanoi is based on which data structure
28. The maximum number of nodes in a binary tree of height h is
29. What is input-restricted deque
30. What is Dijkstra algorithm. Where is it used
31. What is vertex, edge in graph. What id the use of adjacency matrix
32. What is directed graph and undirected graph. Share an example usecase for them
33. How  do you determine the number of edges
34. What is height balancing property
35. What is binary search tree and where is it used
36. What is 2,4 tree
37. How do you resolve underflow scenario in case of deletion in 2,4 tree
38. What is the time consumed in restructuring in avl tree
39. What is the time complexity for search, insert, delete in avl tree with and without restructuring
40. What is m-way search tree . How many keys will be stored in d node
41. What is topological sort.
42. What is a spanning tree. What is a minimum spanning tree..
43. What is heap sort and where is it used
44. What is difference between mege sort and heap sort
45. Consider a ticket reservation system. What kind of data structures shall be used for various use cases.
46. Which sorting algo shall give better results in case the input is already sorted partially
47. What is prim-jarniks algorithm. When is it used ?
48. What is the difference between kruskals algorithm and prims algorithm
49. What is the use of priority queue in prims algo and in kruskals algo. Can it be avoided
50. What is the stop criteria in kruskals algorithm.
51. What is safe edge in spanning tree algos ?
52. What is called depth of a tree, height of a tree, level in tree ?
53. What are the real life application of graph
54. What is bellman ford algorithm and difference with dijkstra algo
55. What is edge relaxation and where is it used
56. What is collision resolution by chaining
57. What is a hash table. When is hash table used.
58. What is direct addressing scheme.
59. What is hash function. Explain any hash function
60. What is division method and mad method in hashing.
61. What is separate chaining and open addressing. When are the used.
62. What is probing and basic types of probing.
63. What is the disadvantage of linear probing
64. How can stack be used for implementing queue
65. What is greedy algorithm. Give example and illustrate use  cases.
66. What is the difference between avl tree and red black tree
67. What rules / property applicable for red black tree
68. What is a skewed binary tree . What shall result in such a tree
69. What is black height of a red black tree
70. What is segment tree and where is it used
71. Which has better time complexity among sorting algos selection, merge, quick and heap sort algorithms for worst case.
72. Why is heap sort considered as unstable sort
73. Which sorting algo gives worse performance in case elements are already sorted. Why.
74. What is introsort ?
75. Give an example for non-comparison based sort.
76. What is the property of BST
77. What is AVL rotation and what are the types of it. Explain any one with an example.
78. What are the general properties for a spanning tree
79. Can a graph have more than one spanning tree
80. What are asymptotic notations
81. What is the difference between linear search and binary search
82. What is the difference between insertion sort and selection sort
83. All BSTs are binary trees. All binary trees are BSTs. Which of these statements is true.
84. Which sorting algorithms follow divide and conquer strategy
85. What is double hashing and when is it used
86. What is the time complexity of DFS algo
87. What is an adaptive sorting algorithm. Give an example.
87. How to construct a tree from a given in-order and pre-order traversal. Explain with your own example.
88. In preorder traversal, which location of output represents the root of the tree
89. List pros, cons of BST vs hash table
90. What techniques can be used to determine cycle or loop in linked list. Which is efficient
91. What techniques can be used for finding the middle of linked list.
92. How will you convert a BST to min-heap
93. What is the difference between Floyd-warshall algorithm and Dijkstra algorithm
94. What is Ford Fulkerson algorithm. Where is it used.
95. What is the difference between fulkerson algorithm and push relabel algorithm
96. What is trie data structure and where is it used

No comments:

Post a Comment