__Exam 2:__

**This exam contains two problems, each asking **__four__** questions****. Please answer each question in detail with clear explanation. 🙂**

** Problem 1.** Find the index of the smallest number in a sorted array where the first k numbers were shifted to the end.

An example of a sorted array where the first k numbers were shifted to the end:

** **

* Example 1*:

*: a = [2, 5, 8, 10, 12, 0, 1] ➔*

__Input__*: 5*

__Output__* Example 2*:

*: a = [1, 6, 9, 10] ➔*

__Input__*: 0*

__Output__* Example 3*:

*: a = [20, 30, 40, 1, 5, 10] ➔*

__Input__*: 3*

__Output__** **

** **

- How would you find the index of the smallest number? (
**Note**: If you have multiple answers in mind, break them apart and explain each one separately.) Explain each solution/algorithm in a few lines.

- Write the pseudocode for the best algorithm you came up with.

- Implement your answer using any programming language you want to.

- What is the time complexity of your answer?
**Explain in detail and show all the work**. (**Note**: If possible, break your code/pseudocode to different parts, calculate the runtime for each step and then try to calculate the total running time based on that.)

** **

** Problem 2.** You are given

*k*sorted arrays in descending order of size

*n*. Develop an algorithm to merge them into a single sorted array of size

*kn*.

(**Hint 1**:

- Can you find the largest number in each array? (This step will give you
numbers)*k* - How would you find the max value among these
numbers? What is the best algorithm you can come up with?*k*

- Do you know from which array the max value came from? iv. Now, how would you find the 2
^{nd}largest element?

**Hint 2**: “The root has the largest value in a __max heap__”. Can you guess where knowing this statement might help you?

* *

* Example*:

a1 = [8, 4, 2, 0], a2 = [20, 15, 5, 3], a3 = [10, 7, 6, 1],

* Output*: Merged array: [ 20 15 10 8 7 6 5 3 2 1 0]

- How would you merge these k arrays into a single sorted array? (
**Note**: If you have multiple answers in mind, break them apart and explain each one separately.) Explain each solution/algorithm in a few lines.

- Write the pseudocode for the best algorithm you came up with.

- Implement your answer using any programming language you want to.

- What is the time complexity of your answer?
**Explain in detail and show all the work**. (**Note**: If possible, break your code/pseudocode to different parts, calculate the runtime for each step and then try to calculate the total running time based on that.)

## Reviews

There are no reviews yet.