Given a sorted array, with fi

Interview Question

0

of 0 votes

9
Answers
Given a sorted array, with find function that finds value in array in O(1). Suppose I rotate the sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Write new find function wiht uses of the older find to find element in the rotated array in O(1) time.
- fox mulder April 09, 2014 in United States | Report Duplicate | Flag | PURGE
Algorithm

Email me when people comment.

An error occurred in subscribing you.

Country: United States

Email me when people comment.

An error occurred in subscribing you.

Comment hidden because of low score. Click to expand.

of 2 vote

Old array = O
New array = A
// Find the pivot offset
pivot_index = O.find(A[0])

// Find the element we are actually looking for, in the old code
index = O.find(item)

// Calculate the index in the new array
new_index = (index - pivot_index) % O.len()

/*
	O = [1 2 3 4 5]
	A = [3 4 5 1 2]

	pivot_index = O.find(A[0]) // returns index of 2

	// Look for 4
	index = O.find(4)  // returns 3
	
	new_index = (3-2) % 5
	new_index = 1
*/

- rotinom April 10, 2014 | Flag Reply

Comment hidden because of low score. Click to expand.

of 0 votes

Great answer. I think you might want this, though.

new_index = (index + O.len() - pivot_index) % O.len()

- Anonymous April 10, 2014 | Flag

Comment hidden because of low score. Click to expand.

of 0 votes

great!
Just O(1) to find the pivot.
After knowing the pivot, things become easy.
+1

- ninhnnsoc April 10, 2014 | Flag

Comment hidden because of low score. Click to expand.

-1

of 1 vote

@Anonymous:

-1 % 5 = 4

Beauty of the modulus operator

- rotinom April 11, 2014 | Flag

Comment hidden because of low score. Click to expand.

of 2 vote

Which company? Phone? Onsite?

O(1) is impossible for finding element in sorted array. So your question is complete nonsense.

(second part might be interesting though, but not as an interview question).

- Anonymous April 09, 2014 | Flag Reply

Comment hidden because of low score. Click to expand.

-3

of 5 votes

Agree, it can be done in O(logn) using binary search but not O(1)

- thelineofcode April 09, 2014 | Flag

Comment hidden because of low score. Click to expand.

of 0 votes

In the problem description he said suppose that you have a find function that finds the value in O(1). So using that function you have to implement your own function. Makes sense to me.

- tphokas April 10, 2014 | Flag

Comment hidden because of low score. Click to expand.

of 0 votes

Agree with tphokas, but still something is missing.

Why won't find return the element in the rotated array too?

If not, how would we apply it? What would happen if we apply the given find to an unsorted array?

CareerCup

Interview Question

Books

Videos

Resume Review

Mock Interviews