Huawei Interview Question Software Engineer / Developers
B-tree does it. B-tree keeps data sorted and allows searches, sequential access, insertions, and deletions in O(log n). For the uninitiated, B-tree is a special Binary Search Tree that can have more than two children.
Refer to Algorithms in Java, 4th Edition, by Robert Sedgewick for the code.
Another Approach: Insert each i of a to Red-Black Tree(TreeSet in java implements Red-Black Tree) -takes O(log n). Then, search takes O(log n) as well!
For sorted array here is my code
/*Given a sorted array of distinct integers A[1; : : : ; n], you want to find out
whether there is an index i for which A[i] = i. Give a divide-and-conquer
algorithm that runs in time O(log n).*/
#include <bits/stdc++.h>
using namespace std;
int findpos(vector<int>& v, int s, int e){
if(s>e)return -1;
int m = s+(e-s)/2;
if(v[m]==m)return m;
if(v[m]<m)return findpos(v,m+1,e);
else return findpos(v,s,m-1);
}
int main() {
vector<int> in1 = {-1,0,2,4};
vector<int> in2 = {-4,-3,-2,-1};
vector<int> in3 = {-3,1,2,3};
cout<<findpos(in1)<<endl;
cout<<findpos(in2)<<endl;
cout<<findpos(in3)<<endl;
return 0;
}
For sorted array here is my code, let me know if you found any error.It returns -1 if no such index exist.
int findpos(vector<int>& v, int s, int e){
if(s>e)return -1;
int m = s+(e-s)/2;
if(v[m]==m)return m;
if(v[m]<m)return findpos(v,m+1,e);
else return findpos(v,s,m-1);
}
int main() {
vector<int> in1 = {-1,0,2,4};
vector<int> in2 = {-4,-3,-2,-1};
vector<int> in3 = {-3,1,2,3};
cout<<findpos(in1)<<endl;
cout<<findpos(in2)<<endl;
cout<<findpos(in3)<<endl;
return 0;
}
I think it is impossible to do it in log(n) in an unsorted array.... right??
If we can do it in log(n), it implies that when we test an element say a[i],
we can either find the answer or prune some elements which are not possible to be the answer.
But we can not do this in an unsorted array.....
No one should ever hire anyone unable to properly state the problem. Try telling us what they *really* asked you, joman, because this is obviously an O(N) problem. (By "logn", do you perhaps mean O(N), not O(logN)?)
The best possibility would be O(n/2) and that too if we assume that the array doesn't contain any duplicate data, but O(log N ) looks difficult to realize.
O(N/2) == O(N). But yes if there are no dups and you've already seen a[i] = j, you don't have to look at a[j], so that cuts the number of tests in half.
we can use binary search.
take the middle element and check if a[i]> i if so ignore the first half
if a[i]<i ignore the second half
if a[i]==i return i
do this recursevly.
this solution will give log(n) complexity
For input {5, 6, 2, 4, 1, 0, 4}, your solution will ignore the low half, where the only qualifying element resides, at step one.
ok, my solution only works for sorted list. i dont think there is no better solution for unsorted array than n i think.
What about the following instance:
Index : 0 1 2 3 4 5 6 7 8
a[index] : 8 1 2 3 8 9 9 8 3
Your code will fail to return 1 or 2 or 3.
It cannot be done in logn unless data in the array is sorted.
The question must've said "given sorted list", then it can be done using binary search like everyone else said
Great code...Excellent...I'm still trying to understand how could it get me the results in log(N) time...out of the world
O(n) is the trivial soln anyone can give, so yo ppl try to think sensibly.. sure there might exist some soln in O(log n)
how about creating a binary Search Tree and everytime you INSERT a node in the tree .. you also maintain an other value in the tree node ( inserted element , 1st or 2nd or 3rd .. etc ) . search does take o(logn) with the above approach .. with the disadvantage of maintinag extra information in each tree node .
Even if you do this, effectively it would take O(n) time. To insert the elements into the tree, you must read it and that'll take O(n) time, then insert it onto a tree O(logn) and then retrieve it O(logN). Also you also need an additional memory of O(n).
For sure this solution looks even worse than linear search.
This is given as sorted array.
- Anonymous May 20, 2011beust.com/algorithms.pdf
Page No 81 has this question:
2.17. Given a sorted array of distinct integers A[1; : : : ; n], you want to nd out
whether there is an index i for which A[i] = i. Give a divide-and-conquer
algorithm that runs in time O(log n).