Viva Questions

1. What is an algorithm?
Answer: An algorithm is a step-by-step procedure for solving a problem or accomplishing a task.

2. What are the characteristics of a good algorithm?

Answer: A good algorithm should be correct, efficient, and easy to understand.

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

Answer: An algorithm is a step-by-step procedure for solving a problem, while a program is an
implementation of an algorithm in a particular programming language.

4. What is the time complexity of an algorithm?

Answer: The time complexity of an algorithm is a measure of the amount of time it takes to
run as a function of the size of the input data.

5. What is the space complexity of an algorithm?

Answer: The space complexity of an algorithm is a measure of the amount of memory it requires
as a function of the size of the input data.

6. What is the Big O notation?

Answer: The Big O notation is used to describe the upper bound on the time complexity of an
algorithm.

7. What is the worst-case time complexity of an algorithm?

Answer: The worst-case time complexity of an algorithm is the maximum amount of time it
takes to run over all possible inputs of a given size.

8. What is the best-case time complexity of an algorithm?

Answer: The best-case time complexity of an algorithm is the minimum amount of time it takes
to run over all possible inputs of a given size.

9. What is the average-case time complexity of an algorithm?

Answer: The average-case time complexity of an algorithm is the expected amount of time it
takes to run over all possible inputs of a given size.

10. What is the difference between the best-case and worst-case time complexity of an
algorithm?
Answer: The best-case time complexity is the minimum amount of time an algorithm can take
to run, while the worst-case time complexity is the maximum amount of time an algorithm can take
to run.

11. What is the difference between the average-case and worst-case time complexity of
an algorithm?
Answer: The worst-case time complexity is the maximum amount of time an algorithm can take
to run, while the average-case time complexity is the expected amount of time an algorithm will
take to run.

12. What is the difference between time complexity and space complexity?
Answer: Time complexity measures the amount of time an algorithm takes to run, while space
complexity measures the amount of memory an algorithm requires.

13. What is a sorting algorithm?

Answer: A sorting algorithm is an algorithm that puts a collection of data items into a specific
order, such as alphabetical or numerical order.

14. What is memoization in dynamic programming?

Answer: Memoization is a technique of storing the results of solved subproblems in a table to
avoid their repeated calculation in future recursive calls.
15. What is the difference between dynamic programming and divide-and-conquer
algorithms?
Answer: Dynamic programming involves solving subproblems and reusing their solutions to
solve the main problem, while divide-and-conquer algorithms divide the problem into independent
subproblems and solve them separately.

16. What is the time complexity of the brute-force approach?

Answer: The time complexity of the brute-force approach is typically O(n^n) or O(2^n), where n
is the size of the input.

17. What is the difference between stable and unstable sorting algorithms?
Answer: Stable sorting algorithms preserve the relative order of equal elements in the input,
while unstable sorting algorithms may not.

18. What is the time complexity of the quicksort algorithm?

Answer: The average-case time complexity of the quicksort algorithm is O(n*log*n), where n is
the size of the input.

19. What is the difference between in-place and out-of-place sorting algorithms?
Answer: In-place sorting algorithms sort the input array in place without using additional memory,
while out-of-place sorting algorithms require additional memory to store the sorted output.

20. What is the time complexity of the mergesort algorithm?

Answer: The time complexity of the mergesort algorithm is O(n*log*n), where n is the size of
the input.

21. What is the difference between breadth-first search and depth-first search
algorithms?
Answer: Breadth-first search explores the nodes in the graph in a breadth-first order, while
depth-first search explores the nodes in a depth-first order.

22. What is the difference between a graph and a tree data structure?
Answer: A tree is a special case of a graph, where there are no cycles, and every pair of nodes is
connected by a unique path.

23. What is the time complexity of the Dijkstra’s algorithm?

Answer: The time complexity of Dijkstra’s algorithm is O(E*log*V), where E is the number of
edges and V is the number of vertices in the graph.

24. What is the difference between a directed graph and an undirected graph?
Answer: A directed graph has directed edges, where each edge points from one vertex to
another, while an undirected graph has undirected edges, where each edge connects two vertices
without any direction.

25. What is the difference between a complete graph and a sparse graph?
Answer: A complete graph has all possible edges between every pair of vertices, while a sparse graph
has relatively fewer edges.

26. What is the difference between a greedy algorithm and a dynamic programming
algorithm?
Answer: A greedy algorithm makes locally optimal choices at each step, while a dynamic
programming algorithm solves subproblems and reuses their solutions to solve the main
problem.

27. What is a divide-and-conquer algorithm?

Answer: A divide-and-conquer algorithm is an algorithm that recursively divides a problem into
subproblems of smaller size, solves the subproblems, and combines the solutions to solve the
original problem.
28. What is a greedy algorithm?
Answer: A greedy algorithm is an algorithm that makes locally optimal choices at each step, hoping
to find a globally optimal solution.

29. What is dynamic programming?

Answer: Dynamic programming is an algorithmic technique that solves problems by breaking them
down into smaller subproblems and storing the solutions to these subproblems to avoid redundant
calculations.

30. What is backtracking?

Answer: Backtracking is an algorithmic technique that involves exploring all possible solutions
to a problem by systematically trying different choices, and undoing choices that lead to dead
ends.

31. What is recursion?

Answer: Recursion is a programming technique in which a function calls itself to solve a
problem.

32. What is the difference between recursion and iteration?

Answer: Recursion involves calling a function from within itself to solve a problem, while
iteration involves using loops to repeat a block of code until a condition is met.

33. What is the difference between top-down and bottom-up dynamic programming?
Answer: Top-down dynamic programming involves solving a problem by breaking it down into
subproblems, while bottom-up dynamic programming involves solving the subproblems first
and combining them to solve the original problem.

34. What is the Knapsack problem?

Answer: The Knapsack problem is a classic optimization problem in which a set of items with
different weights and values must be packed into a knapsack of a given capacity, while
maximizing the total value of the items.

35. What is the traveling salesman problem?

Answer: The traveling salesman problem is a classic optimization problem in which a salesman
must visit a set of cities, each only once, and return to his starting point, while minimizing the total
distance traveled.

36. What is the complexity of the brute-force solution to the traveling salesman
problem?
Answer: The brute-force solution to the traveling salesman problem has a time complexity of O(n!),
where n is the number of cities.

37. What is a graph?

Answer: A graph is a data structure that consists of a set of vertices (nodes) and a set of edges
that connect pairs of vertices.
38. What is a directed graph?
Answer: A directed graph is a graph in which each edge has a direction, indicating a one-way
connection between two vertices.

39. What is an undirected graph?

Answer: An undirected graph is a graph in which each edge has no direction, indicating a
bidirectional connection between two vertices.

40. What is a weighted graph?

Answer: A weighted graph is a graph in which each edge has a weight or cost assigned to it,
indicating the cost or distance between the two vertices it connects.

41. What is a cycle in a graph?

Answer: A cycle in a graph is a path that starts and ends at the same vertex, and includes at least
one edge.

42. What is a connected graph?

Answer: A connected graph is a graph in which there is a path between every pair of vertices.

43. What is a spanning tree?

Answer: A spanning tree of a graph is a subgraph that includes all the vertices of the graph
and forms a tree (a connected acyclic graph).

44. What is the minimum spanning tree of a graph?

Answer: The minimum spanning tree of a graph is the spanning tree with the minimum sum of
the weights of its edges.

45. What is Kruskal’s algorithm?

Answer: Kruskal’s algorithm is a greedy algorithm that finds the minimum spanning tree of a graph
by repeatedly adding the next lightest edge that does not form a cycle.

46. What is Prim’s algorithm?

Answer: Prim’s algorithm is a greedy algorithm that finds the minimum spanning tree of a
graph by starting at a random vertex and repeatedly adding the next lightest edge that connects
a vertex in the tree to a vertex outside the tree.

47. What is the time complexity of Kruskal’s algorithm and Prim’s algorithm?
Answer: The time complexity of Kruskal’s algorithm and Prim’s algorithm is O(E log E), where
E is the number of edges in the graph.

48. What is a topological sort?

Answer: A topological sort of a directed acyclic graph is a linear ordering of its vertices such
that for every directed edge from vertex u to vertex v, u comes before v in the ordering.

49. What is the time complexity of a topological sort?

Answer: The time complexity of a topological sort is O(V + E), where V is the number of
vertices and E is the number of edges in the graph.

50. What is the difference between breadth-first search and topological sort?
Answer: Breadth-first search is a graph traversal algorithm that visits all the vertices in the
graph at a given distance (level) from a starting vertex before moving on to vertices at a greater
distance. Topological sort, on the other hand, is a way of ordering the vertices of a directed
acyclic graph such that for every directed edge u->v, u comes before v in the ordering.

51. What is Dijkstra’s algorithm?

Answer: Dijkstra’s algorithm is a greedy algorithm that finds the shortest path between a
starting vertex and all other vertices in a graph with non-negative edge weights. It works by
maintaining a set of vertices for which the shortest path is known, and repeatedly selecting the
vertex with the shortest path and updating the shortest paths to its neighbors.

52. What is the time complexity of Dijkstra’s algorithm?

Answer: The time complexity of Dijkstra’s algorithm is O((V+E)log V) using a binary heap,
where V is the number of vertices and E is the number of edges in the graph.

53. What is the Floyd-Warshall algorithm?

Answer: The Floyd-Warshall algorithm is a dynamic programming algorithm that finds the shortest
path between all pairs of vertices in a graph with possibly negative edge weights. It works by
maintaining a table of shortest path estimates for all pairs of vertices, and repeatedly updating these
estimates based on intermediate vertices.

54. What is the time complexity of the Floyd-Warshall algorithm?

Answer: The time complexity of the Floyd-Warshall algorithm is O(V^3), where V is the number
of vertices in the graph.

55. What is the difference between dynamic programming and greedy algorithms?
Answer: Both dynamic programming and greedy algorithms are techniques for solving
optimization problems, but they differ in their approach. Dynamic programming involves
breaking a problem down into smaller subproblems and solving each subproblem only once,
storing the solution in a table to avoid re-computation. Greedy algorithms, on the other hand,
make the locally optimal choice at each step, without considering the global optimal solution.
Dynamic programming is generally more computationally expensive than greedy algorithms,
but can handle more complex optimization problems.

56. What is the principle of optimality?

Answer: The principle of optimality is a key concept in dynamic programming that states that
an optimal solution to a problem can be constructed from optimal solutions to its subproblems.

57. What is quicksort algorithm?

Answer: Quicksort is a popular sorting algorithm that uses a divide-and-conquer strategy to
sort an array of elements. It works by selecting a pivot element from the array, partitioning the array
into two subarrays based on the pivot, and recursively sorting the subarrays. Quicksort has an
average case time complexity of O(n log n), making it one of the fastest sorting algorithms in
practice.

58. What is merge sort algorithm?

Answer: Merge sort is a popular sorting algorithm that uses a divide-and-conquer strategy to
sort an array of elements. It works by dividing the array into two halves, recursively sorting
each half, and then merging the two sorted halves together. Merge sort has a worst-case time
complexity of O(n log n), making it a good choice for sorting large datasets.

59. What is the difference between quicksort and mergesort?

Answer: Quicksort and mergesort are both popular sorting algorithms that use the divide-and-
conquer strategy, but they differ in their approach. Quicksort uses a pivot element to partition
the array and sort the subarrays recursively, while mergesort divides the array into two halves
and sorts them recursively before merging the sorted halves together. In general, quicksort is
faster than mergesort in practice, but mergesort has a more predictable worst-case time
complexity.

60. What is dynamic programming used for?

Answer: Dynamic programming is a technique used to solve optimization problems that can be
broken down into smaller subproblems. It is often used in problems involving sequence
alignment, shortest path finding, knapsack problems, and other optimization problems.

61. What is the time complexity of bubble sort?

Answer: The time complexity of bubble sort is O(n^2), where n is the size of the array being
sorted. Bubble sort works by repeatedly swapping adjacent elements that are out of order, so it
needs to make O(n^2) comparisons and swaps in the worst case.

62. What is the time complexity of insertion sort?

Answer: The time complexity of insertion sort is O(n^2), where n is the size of the array being
sorted. Insertion sort works by iteratively inserting each element in the proper position in a
sorted subarray, so it needs to make O(n^2) comparisons and swaps in the worst case.

63. What is the time complexity of selection sort?

Answer: The time complexity of selection sort is O(n^2), where n is the size of the array being
sorted. Selection sort works by repeatedly finding the smallest element in the unsorted portion
of the array and swapping it with the first unsorted element, so it needs to make O(n^2)
comparisons and swaps in the worst case.

64. What is the time complexity of a linear search?

Answer: The time complexity of a linear search is O(n), where n is the size of the array being
searched. Linear search works by iterating through each element in the array until it finds the
target element, so it needs to make O(n) comparisons in the worst case.

65. What is the difference between the Dynamic programming and Greedy method?
Answer:
Characteristic Dynamic Programming Greedy Method
Bottom-up approach (start Top-down approach (start from
Approach from subproblems and build the main problem and make
up to solve the main locally optimal choices)
problem)
Optimal solution not always
Solution quality Optimal solution guaranteed
guaranteed
Subproblems are solved only Subproblems are not
Subproblem
once and their solutions are revisited, and the locally
reuse
stored in a table optimal choice is made at each
step
Considers only the locally
Solution space Considers all possible solutions
optimal solution
Can have a higher time Can have a lower time
Time complexity
complexity than Greedy complexity than Dynamic
Method Programming
Suitable for problems that Suitable for problems where
Suitable
exhibit optimal substructure and making locally optimal choices
problems
overlapping subproblems leads to a global optimal
solution
Fibonacci sequence, Coin changing problem,
Examples
Knapsack Huffman coding
problem

66. List the advantage of Huffman’s encoding?

Answer: Huffman’s encoding is a crucial file compression technique that provides the following
benefits:
Easy to use
Flexible
Implements optimal and minimum length encoding
67. List the advantage of Huffman’s encoding?
Answer: Huffman’s encoding is a crucial file compression technique that provides the following
benefits:
Easy to use
Flexible
Implements optimal and minimum length encoding

68. What is the Algorithm’s Time Complexity?

Answer: The time complexity of an algorithm refers to the total amount of time required for the
program to run until it finishes.
It is typically expressed using the big O notation.
The algorithm’s time complexity indicates the length of time needed for the program to
run entirely.
Algorithm's Time Complexity

69. What is a Greedy method in DAA?

Answer: Greedy algorithms solve optimization problems by constructing a solution piece by
piece. At each step, they select the next component that provides an immediate benefit without
taking prior decisions into account. This method is primarily employed for addressing
optimization problems.

70. What is a Greedy method in DAA?

Answer: Greedy algorithms solve optimization problems by constructing a solution piece by
piece. At each step, they select the next component that provides an immediate benefit without
taking prior decisions into account. This method is primarily employed for addressing
optimization problems.

71. Can you explain Asymptotic Notation?

Answer: Asymptotic Notation is a mathematical technique used to analyze and describe the
behavior of functions as their input size approaches infinity. This notation involves methods
whose domains are the set of natural numbers and is useful for defining the worst-case running
time function T(n). It can also be extended to the domain of the real numbers.

72. Can you explain the concept of Huffman code?

Answer: Huffman code refers to a variable-length encoding technique that involves constructing
an optimal prefix tree to assign bit strings to characters based on their frequency in a given text.

73. Can you provide an overview of how Merge sort works, and can you give an example
of its implementation?
Answer: Merge sort is a sorting algorithm that involves dividing the original list into two smaller
sub-lists until only one item is left in each sub-list. These sub-lists are then sorted, and the
sorted sub-lists are merged to form a sorted parent list. This process is repeated recursively until
the original list is completely sorted.

For example, suppose we have an unsorted list of numbers: [5, 2, 8, 4, 7, 1, 3, 6]. The Merge
sort algorithm will first divide the list into two sub-lists: [5, 2, 8, 4] and [7, 1, 3, 6]. Each sub-
list will then be recursively divided until only one item is left in each sub-list: [5], [2], [8], [4],
[7], [1], [3], [6]. These single-item sub-lists are then sorted and merged pairwise to form new
sub-lists: [2, 5], [4, 8], [1, 7], [3, 6]. The process continues recursively until the final sorted list
is obtained: [1, 2, 3, 4, 5, 6, 7, 8].
74. Can you describe dynamic Huffman coding?
Answer: Dynamic Huffman coding involves updating the coding tree every time a new character
is read from the source text. It is an improved version of the simplest Huffman coding technique
and is used to overcome its limitations.

75. Can you define the n-queen problem?

Answer: The n-queen problem involves placing n queens on an n-by-n chessboard in a way that
none of the queens attack each other by being in the same row, column, or diagonal.