Short'n'Sweet Python Code, beats 98%


  • 2
    class TwoSum(object):
    
        def __init__(self):
            self.d = {}
            
        def add(self, n):
            self.d[n] = self.d.get(n, 0) + 1
    
        def find(self, v):
            d = self.d
            for nbr in d:
                t = v - nbr
                if t in d and d[t] - (t is nbr):
                    return True
            return False

  • 0

    I have a question. Is it efficient to use for to traverse a dictionary? Since dictionary is a hashtable, there will be a lot of unused slots that will largely increase the traversal time.


  • 0
    F

    Are you sure you need to traverse every "slot"? I suggest you read https://en.wikipedia.org/wiki/Hash_table


  • 0

    The dictionary in Python uses double hashing method to resolve conflicts. Thus, it will allocate bigger space than chaining method and makes the traversal slow. You can check its source code.


  • 0

    I don't get it. Traversal of what? The keys? Or the values? for nbr in d traverses the keys, not the values.


  • 0

    @agave Tried your solution, it told me True even though I had only added a single number:

    >>> t = TwoSum()
    >>> t.add(8**12 - 4**18)
    >>> print t.find(0)
    True
    

  • 0

    @StefanPochmann Weird, I am executing on CoderPad with both Python 3 and 2 and the result is False. What version are you using?


  • 0

    @agave Python 2.7.11. Managed to reproduce it on CoderPad now.


  • 0

    @StefanPochmann I think the problem is in the is keyword. I should have used ==. Apparently it works on the OJ because it depends on the particular implementation of is.


  • 0

    @agave Yep, the moral/point of this exercise was... don't use is unless you really mean to :stuck_out_tongue_winking_eye:

    Certain small ints are interned, I think -5 to 256. So including 0. But not 0L, the long type version. You don't have a problem on LeetCode because the test data is the same for all languages, so all ints here will be 32-bit int, not long.

    And my example at first didn't produce the problem on CoderPad because 8**12 - 4**18 does leave 32-bit range, but CoderPad runs 64-bit Python. So I had to make my numbers larger in order to get 0L instead of 0.

    Neat expression, btw. Though I think my solution (with if v - nbr in d ... without storing v - nbr in a variable) is still a bit faster.


  • 0

    @StefanPochmann lol I thought I had gotten away with it, but your never-ending quest for code perfection beat me!


  • 0

    @agave CoderPad is stupid, btw. I had to enter my name and they suggested Erlich Bachman. Which doesn't make sense. What would Erlich do on CoderPad? He doesn't code anymore. Remember? Carpal Tunnel Syndrome.

    Just kidding, it's good. Fun watching you test there for a bit. Seems to work well.


  • 0

    @StefanPochmann ahah yes! Regarding CoderPad, it works well (almost all the time). I use it when I code and I don't have my laptop handy. I know for a fact that is used by Dropbox for phone interviews.


  • 0

    @agave Just changed my mind. CoderPad does suck. Minimum $50 per month?!? Are they insane?


  • 0

    @StefanPochmann I know, but you can use a small trick and use it for free, for as much as you want.


  • 0

    @agave Ok I just tried it with Tor Browser and it works (and I guess will keep working) but the shell was a little laggy. And it just didn't feel right :-). Is your trick better?


  • 1

    @StefanPochmann sorry, I've just seen your reply! Yes, disable cookies for https://coderpad.io and it will work like a charm.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.