search

Just-A-Visitor / Algorithmic-Pseudocode

This repository contains the pseudocode(pdf) of various algorithms and data structures necessary for Interview Preparation and Competitive Coding
GNU General Public License v3.0
762 stars 167 forks source link

Pseudocode for k-th largest element in a stream #40

Closed ghost closed 4 years ago

ymoullec commented 4 years ago

Hello, I'm a beginner as far as contributing to git repositories is concerned. I'd like to help on this algorithm if that's alright. I already know the basic fork / pull request workflow. I've read the main README file and the thread about contributing and still have some questions. Are the coding standards mentioned in the README the ones used by the algorithmicx package ? Also, I'm not sure that I understand what LeetCode is and how it should be used to solve the problem. Is there another README that describes this workflow ? If there's anything else I should know before starting working on this, let me know. Thank you.

ghost commented 4 years ago

Hi, Welcome to the repository.

1) The coding standards aren't necessarily the ones followed by algorithmicx package. To be honest, I haven't yet written them down in a concrete manner. (They are spread amongst a bunch of pull request reviews). I'll make the standards concrete once I'm free. For now, you don't need to worry so much about it. Just go through the existing codes, such as Wildcard Matching, Bipartite Matching, etc to get a basic idea. Once you make the pull request, I'll review the pull request and introduce you to the coding standards of the repo.

2) LeetCode is a online judge (for Interview Preparation). In short, it removes the need for manual testing of the correctness of the code. The workflow is, you search the question on Leetcode, write the code in your favourite language and submit it on LeetCode. Once it gives a clear verdict, you can then convert it to psuedocode using TeX. Here is the link of the website.

3) Sorry, I haven't been able to prepare a separate README for the workflow. I plan on doing it soon.

4) No specific request for the first PR. Just make a PR and I'll review the code in the PR section.

Feel free to post any queries that you have in this thread

ymoullec commented 4 years ago

Thank you for your answer, I'll get to working on this soon !

ymoullec commented 4 years ago

I came up with two solutions for this problem, both of which pass LeetCode tests. The two solutions mainly differ from a "coding level" point of view :

  1. The first one uses a priority queue (high-level). It is very efficient, and the code is short. However, uses a priority queue hides the complexity of the actual processes used.

  2. The second one uses a simple array (low-level). It is less efficient, as my implementation uses a rather simple algorithm (quick sort and insertion in sorted array). It is also longer.

Should I translate any of these to pseudocode ?

ghost commented 4 years ago

Yes, I think you should go ahead and implement the first one. (Just mention the time complexity in the description).