InterviewBit academy

general
51

3 and a half

52

You probably get in, you should ping them too. :slight_smile:

53

I checked the website, it says, “Congrats, you have cleared the entrance test. As a next step please select a slot of 30 mins for personal interview”, but I didn’t receive any mail, Lol, I was worried, anyways, thanks for the support, good luck to all of you.

1 Like
54

What happens when the array is [1, 2, 2, 2, 2, 2], where will the upper bound pointer point at ??

1 Like
55

Didn’t know that there is also a case of direct selection .

56

You didn’t specify the number N, but lets take both 1 and 2
1-
lower_bound points to 0 and upper_bound points to 1. So, 1 - 0 = 1, and there only 1 instance of 1
2-
lower bound points to 1 and upper bound points to the end of the array that is 6, so 6 - 1 = 5 and there are 5 instances of 2.

1 Like
57

I meant n to be 2, anyways good solution, congrats on your selection!
Hopefully I’ll see you in IBAcademy then

1 Like
58

don’t you think the answer for the second question is 3!.5!.3!.6! , if the same type of fruits should be together and duplication is allowed

59

If same type fruit are together it’s 3!
Because we think of same fruits together as a single unit, looking at the question i think the examiner means that same type of fruits are idemtical

2 Likes
60

Share your approach for 5th question

61 
iterator left = lower_bound(arr)
iterator right = upper_bound(arr)
return right - left;

approx pseudo code
upper_boudn and lower_bound functions run in log(n) time, these functions are available in algorithm header file

2 Likes
62

Because the array is sorted you can do better than by just naively counting the instances of that number, which by the way, in the worst case takes O(N) time.
The idea is to realise that because the array is sorted, all instances of N would lie in one continuous sequence. Therefore, if we can find where this sequence begins and ends we can find the number of times N appears in this sequence and thus in the array.
lower_bound and upper_bound can be used for this purpose. The lower_bound returns an iterator (pointer) to the first element that is not smaller (that is either equal or greater than) the number passed to it as parameter, similarly the upper_bound returns an iterator the first element which is greater the number passed to it as parameter. So, if there are any instances of N in the array then lower_bound and upper_bound would point to different elements and we can count the instances of N by taking their difference. See @i_64’s psuedo-code for detail.

1 Like
63

Bro, I was asking the interviewbit academy test A 5th question.
I think @i_64 and you got excited.:sweat_smile::stuck_out_tongue:

1 Like
64

Oops sorry. My bad :sweat_smile:
Well, for that question, first I spent some 10 minutes or something trying to come up with some formula or pattern but couldn’t come up with any. Then I looked at the constraints and realised that I could just use Brute-Force and get it passed. The constraint was 1 <= N <= 10^{5}. This means that an O(N * log(N)) approach is acceptable. Now, the elimination would stop if there are only 2 people left, and infact, the elimination would always end with some 2 people.
Now, in each round of elimination, half of people get eliminated (Thanos smiles in a corner :joy:). This means even if naively do the elimination, the code should just pass as per the constraints. As it takes N * log_{2}N operations to eliminate all people till only 2 of them are left.
So, I just used a dequeue. I, initially inserted all numbers into the dequeue then, repeated the below process till the size of dequeue is greater than 2.-
Grab the front element of the dequeue and store it somewhere and remove it from the dequeue, remove the next element from the front and again before removing Store it somewhere. Finally remove the next element from the front. Now, insert the element you removed first at the back of the dequeue and the element removed second at the front of the dequeue.
When the process completes, only 2 elements are left in the dequeue, you simply return them in the sorted order.

2 Likes
65

Here is the pseudo-code by the way-

deque<int> dq;

// insert all the elements in dq
for(int i = 1; i <= N; ++i)
	dq.push_back(i);

while(dq.size() > 2) {
	// remove the killer
	int killer = dq.front();
	dq.pop_front();

	// remove the one who is spared
	int spared = dq.front();
	dq.pop_front();

	// remove the person to be killed
	dq.pop_front();

	// insert killer and spared at their right positions
	dq.push_back(killer);
	dq.push_front(spared);
}

vector<int> result;
for(auto num : dq)
	result.push_back(dq);

sort(result.begin(), result.end());
return result;
5 Likes
66

@sorb1997 can you please share the approach for interviewbit 2nd and 4th question of test A.

1 Like
67

sure, wait for sometime. :slight_smile:

1 Like
68

Can you share the question statement or anything ?
Actually, i also solved them, but don’t remember the questions exactly.

1 Like
69

Thanks!!! man, actually I thought a solution of O(n) would only pass. I even didn’t give it a try using Brute-force. My bad!!!:frowning_face:

2 Likes
70

Sure the 2nd question was that we had to pick any 3 elements from an array discard the maximum and minimum and keep the middle back so we need to tell how many maximum distinct elements we can end up with?

And 4th was we have an operation del(l,r) l<=r which deletes a[l],a[l+1]…a[r] to make array non-decreasing so we need to tell all possible count of such del(l,r) for an array

2 Likes