Search In Rotated Sorted Array
Aahad and Harshit always have fun by solving problems. Harshit took a sorted array consisting of distinct integers and rotated it clockwise by an unknown amount. For example, he took a sorted array = [1, 2, 3, 4, 5] and if he rotates it by 2, then the array becomes: [4, 5, 1, 2, 3].

After rotating a sorted array, Aahad needs to answer Q queries asked by Harshit, each of them is described by one integer Q[i]. which Harshit wanted him to search in the array. For each query, if he found it, he had to shout the index of the number, otherwise, he had to shout -1.

For each query, you have to complete the given method where 'key' denotes Q[i]. If the key exists in the array, return the index of the 'key', otherwise, return -1.

Note:

Can you solve each query in O(logN) ?

Input Format:

The first line of input contains the size of the array: N The second line contains N single space-separated integers: A[i]. The third line of input contains the number of queries: Q The next Q lines of input contain: the number which Harshit wants Aahad to search: Q[i]

Output Format:

For each test case, print the index of the number if found, otherwise -1. Output for every test case will be printed in a separate line.

Note:

You are not required to explicitly print the expected output, just return it and printing has already been taken care of.

Constraints:

1

Question

Search In Rotated Sorted Array

Aahad and Harshit always have fun by solving problems. Harshit took a sorted array consisting of distinct integers and rotated it clockwise by an unknown amount. For example, he took a sorted array = [1, 2, 3, 4, 5] and if he rotates it by 2, then the array becomes: [4, 5, 1, 2, 3].

After rotating a sorted array, Aahad needs to answer Q queries asked by Harshit, each of them is described by one integer Q[i]. which Harshit wanted him to search in the array. For each query, if he found it, he had to shout the index of the number, otherwise, he had to shout -1.

For each query, you have to complete the given method where 'key' denotes Q[i]. If the key exists in the array, return the index of the 'key', otherwise, return -1.

Note:

Can you solve each query in O(logN) ?

Input Format:

The first line of input contains the size of the array: N

The second line contains N single space-separated integers: A[i].

The third line of input contains the number of queries: Q

The next Q lines of input contain: the number which Harshit wants Aahad to search: Q[i]

Output Format:

For each test case, print the index of the number if found, otherwise -1.

Output for every test case will be printed in a separate line.

Note:

You are not required to explicitly print the expected output, just return it and printing has already been taken care of.

Constraints:

1 <= N <= 10^6
-10^9 <= A[i] <= 10^9
1 <= Q <= 10^5
-10^9 <= Q[i] <= 10^9

Time Limit: 1sec

Accepted Answer

Finding a pivot and then performing binary search. keep repeating this until the element is found

Accepted Answer

Brute Force Approach

The idea here is to do a linear approach which apparently is a brute force way to do this.

Visit every element one by one.
Check if the current element that you are looking at is the key value that needs to be searched. If the element is found, return the index at which you find it.
Once all the elements are visited and you don't find the key-value, return -1.

Space Complexity: O(1)Explanation:

O(1)

Since a constant amount of space is used. Hence the overall space complexity is O(1).

Time Complexity: O(n)Explanation:

O(N), where N is the total number of elements in the array.

In the worst case, we have to visit every element. Hence the overall time complexity is O(N).

Accepted Answer

Binary Search Approach

Before we discuss the algorithm, there's an interesting property about sorted and rotated arrays that must be noted.

If we divide the array into two halves, at least one of the two halves will always be sorted.

Let's consider the array: [5, 6, 7, 1, 2, 3, 4]

5	6	7	1	2	3	4

Mid-index is calculated as (startIndex + endIndex) / 2 or start + (endIndex - startIndex) / 2.

The mid-index for the above-depicted list/array will be 3.

The value at the mid-index is 1. If we have a closer look at three values, that are, value at start, end, and mid then we can deduce which the subarray is sorted or not.

Since the value at the mid-index is less than the value at the start index, we clearly can say that the left subarray is not sorted or violates the property of a sorted array.

Similarly, we can deduce if the right subarray is sorted or not by comparing the values at mi-index and end index.

Now, once we know what part of the array is sorted, we can compare the value(key) to be searched in reference to the sorted subarray.

Finally, to put everything in points:

Find the mid index.
If the value(key) being searched for is at the mid index, then return the mid index.
Compare values at start index, end index, and mid-index:
- If the left subarray is sorted, check if the value(key) to be searched lies in the range:
  - If it does, then search space reduces between [start, (mid-1)].
  - Otherwise, the search space reduces between [(mid + 1), end]
- If the right subarray is sorted, check if the value(key) to be searched lies in the range:
  - If it does, then search space reduces between [(mid + 1), end].
  - Otherwise, the search space reduces between [start, (mid -1)]
Repeat from step-1 until the key is found.
Return -1 if never found.

Space Complexity: O(1)Explanation:

O(1)

Since we are using constant space. Hence the overall space complexity is O(1).

Time Complexity: O(logn)Explanation:

O(log(N)), Where N is the total number of elements in the array.

Every time we split the array into halves. Hence the overall time complexity is O(log(N)).

Top Paytm Senior Software Engineer interview questions & answers

Popular interview questions of Senior Software Engineer

Top HR questions asked in Paytm Senior Software Engineer