Implement a function to find element at any rank.
Closed this issue · 28 comments
Do the checklist before filing the issue:
- Do you have Node.js and all the relevant dev-dependencies installed?
- Is this a bug fix?
- Is this an enhancement?
- Is this a feature request?
NOTE: Provide a clear and concise description of the feature that needs to be added! Or if its a bug, then provide the necessary steps to reproduce it along with screenshots.
- Give your answer below:
Write a function to find a element with the given rank. If no such element exists, then return an error. Time complexity must be O(n).
rank = 1 +(number of >= elements)
Example: arr = [1,2,3,4,2,6]
EleAtRank(2) = 4;
EleAtRank(5) = 2;
EleAtRank(4) = //error;
I will work on this if you approve of it.
@sateslayer just to be clear we'd implement it like so:
const EleAtRank = M.rankify([ 1, 2, 3, 4, 2, 6 ]); /* returns a function */
EleAtRank(1); /* 6 */
EleAtRank(2); /* 4 */
EleAtRank(3); /* 3 */
EleAtRank(4.5); /* 2 */
EleAtRank(6); /* 1 */
And your time complexity would be O(n)?
Yes, almost.
EleAtRank(2) = 5 not 4;
There is an additional space complexity of O(n).
And I guess you meant 4 instead of 4.5 .
The code will be using a partitioning scheme similar to Merge Sort.
This is useful for the median() function too.
Why the element at rank 2 is 5, cause 5 isn't present in the array!
Oh my bad, the ranks are all integers. So we round up the fractional ranks.
That's how I defined my rank function above.
Alternatively I think we can round down as well, but that may lead to errors, I will have to check that out.
For this array, [1, 5, 3, 8, 1, 3, 3]. Let me know, what's the rank of all the elements!
OK!
8 is at rank 1.
5 at rank 2.
3 at rank 5.
1 at rank 7.
Alright, got it!
So, shall I get 1 at rank 6, or 3 at rank 4 & 3?
Rank 6 will be an invalid input.
Because all equal numbers are assigned the same rank due to same priority.
OK!
8 is at rank 1.
5 at rank 2.
3 at rank 5.
1 at rank 7.
Any rank values apart from these will be considered invalid.
Alright! Implement it like this:
const EleAtRank = M.rankify([1, 5, 3, 8, 1, 3, 3]);
EleAtRank(1); /* 8 */
EleAtRank(2); /* 5 */
EleAtRank(5); /* 3 */
EleAtRank(7); /* 1 */
All right. Thanks!
Wait where is the input for the array? What exactly does rankify do?
Alright! Implement it like this:
const EleAtRank = M.rankify([1, 5, 3, 8, 1, 3, 3]); EleAtRank(1); /* 8 */ EleAtRank(2); /* 5 */ EleAtRank(5); /* 3 */ EleAtRank(7); /* 1 */
Hey, @pbiswas101 I don't think I will be able to complete it within the stipulated time. I have too many projects to complete. I am extremely sorry :-/ .
@sateslayer No problem! I can extend the time until 11:59 pm if you want!
Um no use, I was busy till now for some project. I'll see if I can do it now.
I have implemented the code, it's working but with slight variations to the definitions I have described above. However I don't think my code is worth adding to Mathball, because it's unstable. I suggest you close this issue or assign it to someone else.
If I can somehow wrap my C code into JavaScript, then it will work perfectly fine.
Sorry for the trouble caused.
@sateslayer No problem.
Can I implement the normal way to do this? It will be O(n*log n) because it involves sorting. If I can get the O(n) algorithm working some other time, I'll update it(outside of GsSOC issues).
@sateslayer sure! You're assigned
@sateslayer your time's up!
Can i work on this issue?
@AishwaryaDASH can you confirm your gssoc19
slack username?
My username is Aishwarya(P). I joined the Mathball channel just today.
@AishwaryaDASH okay, you're assigned!
@AishwaryaDASH your time's up!
I believe this issue is pretty useless if it can't be implemented with efficient time complexity.