We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Sorting
  4. Find the Median
  5. Discussions

Find the Median

Problem
Submissions
Leaderboard
Discussions

    You are viewing a single comment's thread. Return to all comments →

  • gnawer
    7 years ago+ 8 comments

    The problem wants to demonstrate "selection algorithm". Specifically the implementation is Quickselect.

    https://en.wikipedia.org/wiki/Selection_algorithm
    https://en.wikipedia.org/wiki/Quickselect

    Quickselect has worst-case time complexity O(n2) same as quicksort, but practical complexity O(n).

    The problem should have explained that. From the definition it's unclear what we were supposed to do. Easiest approach is to just sort the array and get the middle element. Unless you know math, it's unclear why selection is supposed to have better complexity than sort, because from simply eyeballing it it looks exactly the same.

    103|
    Permalink
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature