 Hacker Earth Amazon All India Hiring Contest

Anyone who was able to solve both the problems of this contest GOOD RANGES & The Maximum Depth can please discuss the approach.

After seeing questions i thought the first one can be done with some optimizations but can do it partially for 25 points only and 2nd one was tough for me i tried all i can but couldn’t solve it , so if anybody who have done both will discuss the approach will surely help programmers like us to learn new things. 2 Likes

I was able to solve the first one completely but don’t why the second one was getting wrong answer but my approach was correct i think but couldn’t resolve the WA.

1 Like

@gagangaur I was able to get only 25 points (average solution) in first question can you explain its approach and can i get your Hackerearth id. here goes my link to hackerearth profile bro https://www.hackerearth.com/@gagan113 and ya i would love to share my solution question was a little bit tricky you just need to catch the pattern and once you get that you 'll get AC.

@karangreat234 bro can you help me out in finding that where was i going wrong in the second question i just fist find out the level order traversal of the tree and then later answered the each query in (logn) time.

1 Like

@rk_221b bro here is an quick explanation for the 1st one
it is quite simple you just need to keep 3 cases in your mind when the element you are inserting is getting inserted at 0 position , in somewhere in between middle or at the last of the set.
In first one, u need to get the max range in which one element is there.
let’s take an example
10 6
2
7
5
9
6
1
8

for 1st query
the set will contain {2} so answer will be 1-10 = 11
now suppose 7 is going to get added the set will be like {2,7} right now we have to keep in mind that the range should be maximum and the element btw the range should only be 1 so max range for 2 can be from 1-6 and for 7 can be 3-10 right now take a closer look at the pattern in ranges
1-6 3-10
now here if we take sum of these ranges it will lead to 20 right
but as we have already calculated the sum of 1-10 so don’t need to calculate it again we only need to add two values in our previous answer and those are {2,7} was our set so 2+1=3 and 7-1=6 adding 1 in previous element and subtracting one from current element and adding it to previous sum and you will get your answer
now let’s insert the 5 in our set so after inserting the set will be like {2 , 5 , 7} now the range for 2 will be from 1-4 and range for 5 will be 3-6 and for 7 will be 6-10
take a closer look at ranges you will get the pattern
2 -> 1-4
5 -> 3-6
7 -> 6-10
now previously the sum calculated was 20 and the values due to which sum was 20 was 1,3,6,10 right now the new values getting added to the ranges are 4 and 6 right now if you take a closer look then you will se that current element (which is 5 in this case) current element -1(4) and current element +1 (6) and adding these two values in our previous sum and you will get the answer.
and similary you can proceed further.
Hope it helped

1 Like

Hi @rk_221b, I did them in the following way.
Good ranges:
It requires knowledge on stl.
The thing to be observed is for every distinct query, two numbers will be added to the answer.

We use stl set here.
For each query,
First insert the given number into the set.Now find the position of the inserted number in the set by using stl find().
There will always be these cases after you inserted the number.
Case 1:if the set has one element add n+2 to the answer.
Case 2:if the position of the inserted element is in between any two elements in the set add the insertedvalue-1 and insertedvalue+1 to the answer.
Case 3:If the position of the inserted element is at the beginning in the set, add insertedvalue+1 and the (adjacent value of the inserted element in set)-1 to the answer.
Case 4:If the inserted element is at the last add the insertedvalue-1 and the (adjacent value of the inserted element in set)+1 to the answer.

Time complexity:log n per query

Maximum depth:

It too requires knowledge of stl.
I used vector of sets.

Just do a traversal of the tree and insert each level in vector of sets.
vector<set> v
Level 0 values are inserted into v and similarly.now for each query find the lower_bound(k) for given v[l] where l is the level and k is the value.

Time complexity:log n per query

1 Like

anyone has prob statements ?

3 Likes

@gagangaur Thanks bro you explained clearly and i got the points where i lacked . THANKS @manuruvenkatar Thanks bro for you explanation  even explanation the ques would be helpful
jst the ques
not solution

i had got 25 points in first question and as some test case got time limit exceed. and 2nd one i had solved the problem using bfs.

The second question was a basic DFS question. Here is the link to my solution. I think its pretty clear. And in first question instead of calculating the answer again for each query you just had to kind of look for change in range of its left element and its right element and you also have to check if x is already present in the set or not as if its present the answer from previous query will not change.

1 Like

Yes I’m able to solve both questions and got 200 points …

both problems are really very easy if you have good knowledge of STLs…

solutions:

@ samarthtandon Thanks for the link Java solutions - with Problem statement

Have anyone receive email from amazon regarding interview? HackerEarth has extended the shortlisting result date to 10 june.

1 Like

Did you get the call for interview?

1 Like

YES i got a email but they have not mentioned any thing about hackerearth or coding test.

1 Like