Microsoft Interview Question Software Engineer / Developers
I think we should use "insertion sort" for inserting elements in array and use Binary Search
Complexity: O(N^2)
I think, we can do it in 0(log n) time,
1. take the recent element, which is inserted into arry,
Case 1, recent is greater than the search-key.
Apply Binary search on the existing array.
Case 2, recent is less than the search key,
then wait, upto the arraival of search key through stream.
I think, we can do it in 0(log n) time,
1. take the recent element, which is inserted into arry,
Case 1, recent is greater than the search-key.
Apply Binary search on the existing array. --time comp: 0(log m), m==> number of elements in array.
Case 2, recent is less than the search key,
then wait, upto the arraival of search key through
stream. --its time complexity: 0(k) ===> search key found after k elements.
Time complexity; 0(log m + k)
please correct me...If any thing wrong :P
I am not sure if you have access to the internals of the sorted, unbounded array. All you have is a way to get the ith element. Something like this:
// Third Party Class.
// You don't have access to internals.
class UnBoundedSortedArray {
// No idea of implementation.
}
// Your Method.
void SearchForElement(UnBoundedSortedArray array, Element x) {
// All you can do is
// Element tmp = array[i];
// Implement this method to check if Element x
// Is part of the array.
}
There is yet another O(log n) solution.
This is with assumptions that we dont know how many elements are existing in the array currently and hence binary search is ruled out.
start with 1st(2^0) element, compare and proceed with 2^1 element and so on like . When the searched_for element is less than the array[2^n) element, do binary search for limits between 2^(n-1) and 2^n.
Ofcourse the boundary conditions of array count must be compared with 2^n and handled.
i think first we have to maintain searching and insertion mutually exclusive (like consumer and produce) when we search element should store in buffer and when search complete we can search ..
suppose at instant no key value not found i have n element and more element can come .
if we enter in search insertion is lock ..
in search
check 2^0 and 2^1 2^2 ... untill either array ends or at 2^i > search key if second one work .. now we know that at this instan search key is in between 2^(i-1) / 2^i now do binary search if element is present then return ;
now open lock ..means now we can insert element ...after this new element came .... again if we enter in search then we have to look only from previous 2^(i-1) because
search key when ever comes will be placed furthur from previous 2^(i-1) in array
keep this continuing untill we find array
If the index of the last element that is recently introduced into the array is unkown, then we do not know high and we cannot apply binary search just like that. So two solutions are there depending on what we have at our disposal.
1.Index of last element is known - in other words the size of array is known.
Check if a[lastIndex] > key
a. If so apply binary search b/w 0 to lastIndex-1.
2.Index of the last element is unknown. Then we would have to search at 2, 4, 8, 16 locations and see if we either find an index where the element is found or an index whose value is greater than the element to be found. In the former, we have the index to return. In the latter case, we would have to do binary search between last index which we checked and the current index where the number is higher than the element to be searched.
keep inspecting the incoming values. Till you have o or 1 value in the array stay at the first index of the array. When second value comes , if this 2nd value is smaller than the current value present jump to the new value ( assuming array is sort in ascending manner). This way keep inspecting new incoming values, if all values are greater than the value to be found try to point to the 1st value. if all values in array are smaller than the value to be found, stay at the last value.
- Anonymous February 12, 2009If some values are lesser than the value to be found and some greater than the value to be found , stay at the largest value smaller than the value to be found