1
\$\begingroup\$

I have a function that looks like this:

def getMaxUserLevelByUserId(userId: Muid)(
      implicit connection: Connection): Option[OrganizationMembership.Level.Value] = {
    val organizationMemberships = getAllByUserId(userId)

    if (organizationMemberships.exists(_.level == OrganizationMembership.Level.Admin)) {
      Some(OrganizationMembership.Level.Admin)
    } else if (organizationMemberships.exists(_.level == OrganizationMembership.Level.Member)) {
      Some(OrganizationMembership.Level.Member)
    } else if (organizationMemberships.exists(_.level == OrganizationMembership.Level.Guest)) {
      Some(OrganizationMembership.Level.Guest)
    } else {
      None
    }
  }

The gets the highest role of a user across all the organizations he is member of. As you can see, the function is pretty straightforward and works. However, it has a complexity of O(n3). I was wondering if there is a way to get it to O(n) or at least a bit lower?

\$\endgroup\$
  • \$\begingroup\$ I don't see the \$\mathcal O(n^3)\$ complexity. I only see \$\mathcal O(3n)\$, which by definition is equivalent to \$\mathcal O(n)\$. \$\endgroup\$ – Roland Illig Oct 17 '17 at 6:46
  • \$\begingroup\$ hmmm... You are so right! I am usually not that slow. )))) Sorry.. \$\endgroup\$ – Shurik Agulyansky Oct 17 '17 at 6:50
  • \$\begingroup\$ It was a fun exercise though :) \$\endgroup\$ – Shurik Agulyansky Oct 17 '17 at 6:50
0
\$\begingroup\$

Well, this is what I did. Not sure if that's the best way to go.

def getMaxUserLevelByUserId(userId: Muid)(
      implicit connection: Connection): Option[OrganizationMembership.Level.Value] = {
    val organizationMemberships = getAllByUserId(userId)

    if (organizationMemberships.nonEmpty) {

      val levelMap = Map(
          OrganizationMembership.Level.Guest -> 0,
          OrganizationMembership.Level.Member -> 1,
          OrganizationMembership.Level.Admin -> 2
      )

      val maxLevel = organizationMemberships.foldLeft(OrganizationMembership.Level.Guest) {
        (level, organizationMembership) =>
          if (levelMap(organizationMembership.level) > levelMap(level)) {
            organizationMembership.level
          } else {
            level
          }
      }

      Some(maxLevel)

    } else {

      None

    }
  }

The idea behind the code above, is the fact that we are iterating through the collection only once, regardless of the collection size. The levelMap was created strictly for the reason of easier comparison.

The cool thing about foldLeft in this case is that we don't need to create mutable variables while iterating through the collection and it is actually very short and quite readable code.

\$\endgroup\$
  • \$\begingroup\$ Self answers are allowed, but code dumps (with no explanation of the motivations behind your changes) are not valid answers. Furthermore, if you are seeking a review of this revised code, then you should make it the new question instead (assuming that no other answers have been posted in the meantime). \$\endgroup\$ – 200_success Oct 17 '17 at 0:18
  • \$\begingroup\$ I apologize, and agree. I had about 2 minutes to do it before I had to run. I will put an explanation a bit later. I am not seeking review of my answer though... I was seeking for an idea of original question \$\endgroup\$ – Shurik Agulyansky Oct 17 '17 at 0:21
  • 1
    \$\begingroup\$ @200_success Here you go. I updated the answer with more explanation. \$\endgroup\$ – Shurik Agulyansky Oct 17 '17 at 5:21
0
\$\begingroup\$

It looks like what you're doing could be expressed thusly.

import scala.util.Try

val levelMap = Map(...

Try(getAllByUserId(userId).maxBy(org => levelMap(org.level)).level).toOption

It's worth noting that this will also catch any exceptions thrown by levelMap. (Maybe a new level is encountered not yet included in levelMap.) That might or might not be considered a good thing.

You can unpack it some to avoid the try/catch overhead hidden inside the Try type.

if (organizationMemberships.isEmpty)
  None
else
  Some(organizationMemberships.maxBy(om => levelMap(om.level)).level)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.