Question: [Offer] InterviewBit | Off-Campus | Internship
2
Entering edit mode
Applied at InterviewBit via off-campus mode. After a month I got a call from HR for the online coding round.
The coding round had 4 questions , 1 easy 2 moderate and 1 quite tough.
I was able to solve 3 fully and the 4th partially.
Next morning I got a call from HR for scheduling the technical interviews.

First Technical Interview

Started with resume, had to explain the backend logical part of my projects and then followed by some questions regarding (a/s)ynchronous functions, HTTP load balancing, SQL injection etc. This process consumed 40 minutes and then followed by a coding question.

Problem
You are given a sorted array of size N with each element's frequency as 2 except 1 element.
Find this element.

I solved it in O(log N) time and O(1) space.
The interviewer seemed satisfied and ended the interview.

That evening received another call from HR, you have been mailed a assignment and is to be completed within 24 hours.
The task was to develop a web-app and deploy it on gcp/aws etc. There was no restriction on the framework to be used.

Second Technical Interview


First 20 minutes went into reviewing the project, like all the objectives have been fulfilled, database scheme and finally the code quality.
Then a few questions related to system design.

The final round was scheduled for the next day.

Final Interview


There was nothing technical in it. All questions were behavioral and personality based.

Verdict : Selected
Stipend : 35k monthly
0
Entering edit mode
Given that array is sorted, is a direct hint to go for Binary Search. However, one needs to be careful with implementation, STL isn't going to help here ( :

Solution

Lets say, we are given an array A.
First of all note, size of array has to be odd, as per conditions given in problem.

For sake of understanding, lets remove the integer with frequency as 1 from the array.
Now clearly, since array is sorted and every integer occurs twice, we observe following invariant
Property(Invariant)
All integers at even indices are same as the next number. Or equivalently, all numbers at odd indices are same as previous number.

Now lets put back the 1-frequency number back into array at its right index, say j.
Now clearly, above Property holds till j-1.
And, Property doesn't holds after j-1.

In other words, we can binary search on index, say i and check if Property holds at i, if it does then i < j, if it doesn't then j > i.
We recursively apply this to find out index j in O(log N) and constant space.

C++ Code

int solve(vector A) {
    int lo = 0, hi = A.size()-1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (A[mid] == A[mid^1]) lo = mid + 1; else hi = mid;
    }
    return A[lo];
}
Note : Here, property is being checked at condition "if (A[mid] == A[mid^1])".
Its a good excercise to think how? (Explained in 1st comment)
ADD COMMENTlink 3.9 years ago admin 1.6k
Entering edit mode
0
Recall, if we represent a number in binary, all odd numbers have their last digit as "1" and all even digits have "0" as their last digit.

So, if mid is even, then mid^1 = mid + 1.
if mid is odd, then mid^1 = mid - 1.

Now review, property or invariant as explained in above answer, this part of code will become obvious. If not, let me know.
ADD REPLYlink 3.9 years ago
admin
1.6k

Login before adding your answer.

Similar Posts
Loading Similar Posts