## Huawei Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
3
of 3 vote

This is given as sorted array.

beust.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).

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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!

Comment hidden because of low score. Click to expand.
0

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;``````

}

Comment hidden because of low score. Click to expand.
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;``````

}

Comment hidden because of low score. Click to expand.
1
of 1 vote

I don't think this can be done in log(n) in an unsorted array.

Comment hidden because of low score. Click to expand.
0
of 0 vote

seem difficult to do for unsorted array in O(logn)

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.....

Comment hidden because of low score. Click to expand.
0
of 0 vote

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)?)

Comment hidden because of low score. Click to expand.
0

like the comment.

I think the responders should skip such stupid guy's question at all!

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Still you need to do the comparison to see if i == j. O(N) only. No N/2 business

Comment hidden because of low score. Click to expand.
0

Yes, you're right ... if you see that a[i] == j, you could skip the test of a[j] if knowing that j was already seen was free, but of course it isn't.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

ok, my solution only works for sorted list. i dont think there is no better solution for unsorted array than n i think.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

"ok, my solution only works for sorted list." -- No kidding.

"i dont think there is no better solution for unsorted array than n" -- Welcome to the club ... better late than never.

Comment hidden because of low score. Click to expand.
0
of 0 vote

The question must've said "given sorted list", then it can be done using binary search like everyone else said

Comment hidden because of low score. Click to expand.
0

In sorted array also you can not find this number in log(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

whenever you have unsorted array you have to search it linearly until and unless there are any more conditions.
linear search will be O(n)
Chances of log(n) is too difficult.
i was also searching for the solution of the same question before but couldn't find 1.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Inserting data into binary Search tree will be O(n). So if you want to do the search in logn its of no use to do search after that.

Comment hidden because of low score. Click to expand.
0
of 0 vote

to get O(logN) we should have algorithm which divides the problem size into half.
Unless the array is sorted, the best time complexity u are going is O(N).

Comment hidden because of low score. Click to expand.
0
of 0 vote

there is O(log N) solution, it is a text book question, from the book "Algorithm" it has a divide & conque solution. it takes me over 20 minutes to figure it out.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple binary search solves the problem

Comment hidden because of low score. Click to expand.
0

For this case: 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).

Comment hidden because of low score. Click to expand.
-1
of 1 vote

in log(N)

for (int i = 0; i < arr.length; i++) {
if (arr[i] == i)
return i;
}

Comment hidden because of low score. Click to expand.
0

Dude abhi13 you are bond..

Comment hidden because of low score. Click to expand.
0

Great code...Excellent...I'm still trying to understand how could it get me the results in log(N) time...out of the world

Comment hidden because of low score. Click to expand.
0

amazing invention by abhi13.....

Comment hidden because of low score. Click to expand.
0

the code run in N time.

Comment hidden because of low score. Click to expand.
0

seriosuly abhi13 is bond.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)

Comment hidden because of low score. Click to expand.
1
of 1 vote

There is *obviously* no O(log n) solution, not with the given conditions. If you don't grasp that, then you fail the interview.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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 .

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

if its sorted.... it can be done in O(1) ..... just check the first element.....

Comment hidden because of low score. Click to expand.
0

test for the following sorted input
{-5, -3, 1, 3, 7, 10}
O(1) is even not possible

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.