InterviewBit academy

general
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
71

The same approach can be used for solving 4th question of Day 1.

1 Like
72

Question 2-
Remove minimum number of elements to make array with all numbers distinct. You select any 3 elements and remove the largest and smallest element from the array while retaining the mid one. For ex- let numbers be 1 1 2 3 4, then you pick 1 1 and 2, remove 1 and 2 and retain 1, so final array looks like 1 3 4. You have to get the final array with as distinct elements as possible.

Solution-
This question was all about observation. Each number in the array obviously has either odd or even frequency. Letā€™s handle both the cases.

  1. Odd(and > 1)-
    If the frequency of number is > 1 and odd, we repeatedly pick 3 instances of it and remove 2 of them(the smaller and the larger). So, in each round itā€™s frequency reduces by two. For ex- let there be 5 instances of 1- 1 1 1 1 1.
    After first round of only 3 instances are left, and after the second round only instance of 1 is left. And we are done here, we successfully eliminated all the duplicates.
    Thus, for any number with frequency > 1 and odd, we can safely remove all itā€™s duplicates without having to remove anything extra.

  2. Even Frequency -
    This part is little tricky, letā€™s suppose for the simplicity we have frequency > 2, i.e. 4, 6, ā€¦ and so on. We can start doing the same thing we did in the last step. We pick three instances of it and remove two of them and repeat the process. At last, we will be left with only 2 instances of it. So, what to do from here? We can not proceed any further. Think about it?

Answer

Suppose there is one other such number who has even frequency(= 2, if it is not equal to 2, we can use the same process and reduce it to 2). Letā€™s say for example -
2 2 4 5 1 3 3.
You can see that 2 and 3 appear two times. So, what we can do is that pick 2 instances of either of them and 1 of the other and do the elimination. Letā€™s say we pick 2, 2 and 3. So after elimination one instance of 2 and one instances of 3 is removed. And our array now reduces to
2 4 5 1 3.
Bingo!
This helps us reach an important conclusion - we can pair numbers with even frequency and remove duplicates.

But what if there is no pair of numbers with even frequency? Such as in
2 2 3 4 5 or in 2 2 3 3 4 5 5. In the later case, 5 can not be paired with any other number with even frequency as 2 and 3 already makes a pair and 4 has an odd frequency?
In such a case, we have no other option but to remove one extra element. For example, the above arrays can be reduced to 2 4 5 and 2 3 5(these are only one such way and ofcourse there can be other ways).

So, to summarize-

Summary
  1. Count the number of numbers with an odd frequency, let say their count is O.
  2. Count the number of numbers with an even frequency, let say their count is E.
  3. If E is even, then the answer will be O + E, otherwise it would be O + E - 1.
6 Likes
73

@sorb1997 Had you attempted test on day 2?

74

So in 2nd question we only had to pick 3 elements once or repetedly?

75

repeatedly, until all the elements in the array are distinct.

1 Like
76

4th question was from Codechef Luchtime or Cook-Off. You can see the editorial there. Itā€™s a Binary Search question.

1 Like
77

Thank you dude and congratulations on your selection.

1 Like
78

No. I busy with some stuff and since I had solved 5 questions from the previous day, I didnā€™t see any point in giving another attempt. :slight_smile:

79

Lol, yeah
Just realised what Iā€™ve explained isnā€™t even question no. 5, itā€™s question 4

80

xD,
:joy::joy::joy::joy::joy:

1 Like