Data structure

1. What is a data structure?

A way to organize and store data for efficient access and modification.

2. What are algorithms?

Step-by-step procedures for solving problems or performing tasks.

3. What is the importance of data structures?

They optimize data storage, retrieval, and manipulation, leading to efficient programs.

4. What is time complexity?

A measure of the time an algorithm takes to complete based on the input size.

5. What is space complexity?

A measure of the memory an algorithm uses based on the input size.

6. What is Big O notation?

A mathematical representation of the upper bound of an algorithm's time complexity.

7. What is the difference between best, average, and worst case?

Best case is the minimum time required; average case is expected time; worst case is the maximum time.

8. What is a constant time complexity?

O(1), meaning the algorithm's runtime does not change with input size.

9. What is linear time complexity?

O(n), meaning the runtime increases linearly with input size.

10. What is logarithmic time complexity?

O(log n), meaning the runtime increases logarithmically with input size.

11. What is an array?

A collection of elements identified by index or key.

12. What is a linked list?

A data structure consisting of nodes, where each node contains data and a reference to the next node.

13. What is a stack?

A last-in, first-out (LIFO) data structure where the last element added is the first to be removed.

14. What is a queue?

A first-in, first-out (FIFO) data structure where the first element added is the first to be removed.

15. What is a hash table?

A data structure that stores key-value pairs for fast data retrieval.

16. What is a binary tree?

A tree data structure where each node has at most two children.

17. What is a binary search tree (BST)?

A binary tree where the left child has a lesser value and the right child has a greater value than the parent node.

18. What is tree traversal?

The process of visiting all nodes in a tree (e.g., inorder, preorder, postorder).

19. What is a balanced tree?

A tree where the height difference between left and right subtrees is minimal.

20. What is a graph?

A collection of nodes (vertices) connected by edges.

21. What is linear search?

A simple search algorithm that checks each element sequentially until the target is found.

22. What is binary search?

A search algorithm that divides a sorted array in half to find a target value efficiently.

23. What is bubble sort?

A simple sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order.

24. What is selection sort?

A sorting algorithm that repeatedly selects the minimum element from the unsorted portion and moves it to the sorted portion.

25. What is insertion sort?

A sorting algorithm that builds a sorted array by repeatedly inserting the next element into the correct position.

26. What is merge sort?

A divide-and-conquer sorting algorithm that divides the array into halves, sorts them, and merges them.

27. What is quicksort?

A sorting algorithm that selects a pivot and partitions the array into elements less than and greater than the pivot.

28. What is Dijkstra's algorithm?

An algorithm for finding the shortest path between nodes in a graph.

29. What is the Floyd-Warshall algorithm?

An algorithm for finding shortest paths in a weighted graph with positive or negative edge weights.

30. What is a depth-first search (DFS)?

A traversal algorithm that explores as far down a branch as possible before backtracking.

31. What is a heap?

A specialized tree-based data structure that satisfies the heap property (max-heap or min-heap).

32. What is a priority queue?

An abstract data type similar to a queue, where each element has a priority and elements with higher priority are dequeued first.

33. What is recursion?

A programming technique where a function calls itself to solve a problem.

34. What are the advantages of recursion?

Simplifies code for problems that can be broken down into smaller subproblems.

35. What are the disadvantages of recursion?

Can lead to high memory usage and stack overflow for deep recursions.

36. What is a base case?

The condition under which a recursive function stops calling itself.

37. What is the difference between tail recursion and non-tail recursion?

In tail recursion, the recursive call is the last operation, allowing optimization by the compiler.

38. What is a dynamic array?

An array that can resize itself when elements are added or removed.

39. What is a circular queue?

A queue where the last position is connected to the first position, forming a circle.

40. What is a graph traversal?

The process of visiting all nodes in a graph, commonly using DFS or BFS.

41. What is greedy algorithm?

An algorithm that makes the locally optimal choice at each step with the hope of finding a global optimum.

42. What is a hash function?

A function that converts input data into a fixed-size value (hash code).

43. What is a collision in hashing?

Occurs when two different inputs produce the same hash value.

44. What is open addressing in hashing?

A collision resolution technique where a new slot is found within the hash table.

45. What is chaining in hashing?

A collision resolution method that uses linked lists to store multiple values at the same hash index.

46. What are hash tables used for?

Efficient data retrieval, implementing associative arrays, and caches.

47. What is a leaf node?

A node that does not have any children.

48. What is a full binary tree?

A binary tree where every node has either 0 or 2 children.

49. What is a complete binary tree?

A binary tree where all levels are fully filled except possibly the last level.

50. What is a binary search tree (BST)?

A binary tree where the left subtree has nodes with lesser values, and the right subtree has nodes with greater values.

51. What is height of a tree?

The length of the longest path from the root to a leaf node.

52. What is an undirected graph?

A graph where edges have no direction; the connection is bidirectional.

53. What is a directed graph?

A graph where edges have a direction, indicating a one-way relationship.

54. What is a weighted graph?

A graph where edges have associated weights or costs.

55. What is a bipartite graph?

A graph whose nodes can be divided into two disjoint sets, with edges only between nodes of different sets.

56. What is a cycle in a graph?

A path that starts and ends at the same vertex without retracing edges.

57. What is divide and conquer?

A problem-solving strategy that divides a problem into smaller subproblems, solves them independently, and combines their results.

58. What is dynamic programming?

A method for solving complex problems by breaking them down into simpler subproblems and storing their solutions.

59. What is the difference between dynamic programming and recursion?

Dynamic programming stores results of subproblems to avoid redundant computations, while recursion may recompute results.

60. What is a brute force algorithm?

A straightforward approach that checks all possible solutions until the correct one is found.

61. What is radix sort?

A non-comparative integer sorting algorithm that sorts numbers digit by digit.

62. What is counting sort?

A non-comparative sorting algorithm that counts the occurrences of each distinct element.

63. What is bucket sort?

A sorting algorithm that distributes elements into several "buckets," sorts them individually, and then concatenates the buckets.

64. What is interpolation search?

An improved variant of binary search that works on uniformly distributed data.

65. What is exponential search?

A search algorithm that finds the range of a potential element and then uses binary search within that range.

66. What is the difference between an algorithm and a program?

An algorithm is a step-by-step procedure; a program is the implementation of an algorithm in a programming language.

67. What are the advantages of linked lists over arrays?

Dynamic size, ease of insertion/deletion, and no need for contiguous memory.

68. What are the disadvantages of linked lists?

Extra memory for pointers, no random access, and traversal time.

69. What is a sparse array?

An array in which most of its elements are zero or have no value.

70. What is a circular linked list?

A linked list where the last node points back to the first node.