# Practice questions – II

## Rooted trees

• Given a binary tree, print the elements in a reversed level order.
• Find the nearest match of a given value in a binary search tree.
• Write a function to check whether two binary trees are structurally identical.
• Write a function to find the size of a BST.
• Write a function to compute the sum of all the elements in a BST.

## Complexity analysis

• Write down the lower bound, upper bound, and order functions for the following timing function: `f(n) = 0.5 * n^3 + 2 * n^2 + log n`
• Solve the following recurrence equation: `T(1) = 1; T(n) = T(n-1) + n(n-1), n > 1`

• For the sorting algorithm below, compare the time complexity for partitioning in the middle vs the beginning.
``````L' = Sort (L, n)
begin
if (n == 1) L' = L;
else
Split L into two non-empty sets L1 and L2;
L1' = Sort(L1);
L2' = Sort(L2);
L' = MERGE(L1', L2');
end
end``````

## Sorting

• Discuss the sorting algorithms covered in the class. Analyze the time complexity for each sorting algorithm.
• Given an array of n numbers, design an algorithm for checking whether there are repeated elements, without any additional space overhead.
• Given an array consisting of 0’s, 1’s and 2’s, design an algorithm for efficiently sorting the array.

## Heaps

• What are the minimum and maximum number of elements in a heap of height h?
• Given a min-heap, how would you find the max element? What is the complexity of such an algorithm?
• Insert the following numbers into a heap for an inplace sort in descending order: 3, 5, 2, 9, 20.
• Given a big file containing billions of numbers, design an algorithm to find the max 10 numbers.

## Graphs

• Write an algorithm for checking whether a given graph has a simple path from a given source node to a given destination node.
• Assuming an adjacency matrix representation of a graph, count all the simple paths from a source to a destination.
• Given a directed graph, write an algorithm to detect whether there is a cycle.
• Given an undirected graph, write an algorithm to detect whether there is a cycle.
• Assuming that there are only non-negative weights, suggest an algorithm for computing the single-source shortest path.

## Hashing

• Design an efficient algorithm to find the first non-repeated character in a string.
• Design an efficient algorithm to find the first repeated character in a string.
• Given an array of n numbers, present an algorithm which displays all pairs whose sum is S.
• Given two sets A and B, and a number K, present an algorithm to find whether there exists a pair of elements, one from A and one from B that adds up to K.