« first day (22 days earlier)   

4:14 AM
@JohnRennie Hello
 
@Aladdin Hi :-)
 
if you are free ,can u explain ur code
 
Your code was working fine, and you can see that I've left your code mostly unchanged. I just added two things:
Firstly I removed unnecessary repeats of numbers in the input list.
Suppose your input list is [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Then the only triple that sums to zero is '[0, 0, 0]`. Yes?
 
yes
 
And no matter how many zeroes there are we can only ever have three of them in the output.
 
4:22 AM
yea
 
So if there are more than three zeroes in the input list we can remove the extra ones leaving only three.
And for non-zero numbers we can only have two of the same number appear in a triple.
e.g. suppose the input is [2, 2, 2, 2, 2, 2, 2, 2, 2, -1, -1, -1, -1, -1, -1, -1, -1]
The only possible output is [2, -1, -1]
 
yes
that makes sense
 
So we can shrink the list down to [2, 2, -1, -1] without changing the output.
 
yea
 
That's what this code does:
        # Find the number of occurrences of each number
        hashtable={}
        for num in nums:
            if not num in hashtable:
                hashtable[num] = 1
            elif num != 0 and hashtable[num] < 2:
                hashtable[num] += 1
            elif num == 0 and hashtable[num] < 3:
                hashtable[num] += 1

        # Build a new list of the numbers in the hash table but with no
        # more than three occurrences of each number
        newlist = []
        for num in hashtable:
 
4:27 AM
if not num in hashtable:
                hashtable[num] = 1
shouldn't it be : if num not in hashtable?
 
Either form works.
 
ah ok
 
Can you see how this works?
 
yes
it gets occurances of the numbers in the array and stores it in hashmap
 
Yes, so the dictionary ends up with an entry for every number that appears in the input list and a count of how many times that number appears, but that count is limited to 2 for non-zeros and 3 for zero.
 
4:32 AM
yea
then using that u build the sorted array
 
Then the next chunk:
 
and use hashmap on it
 
        # Build a new list of the numbers in the hash table but with no
        # more than three occurrences of each number
        newlist = []
        for num in hashtable:
            for i in range(hashtable[num]):
                newlist.append(num)
        newlist = sorted(newlist)
Recreates the input string from the dictionary.
 
yep
what does dups do?
 
So now newlist contains all the numbers from the input, but it limits the number of duplicates to 2 for non-zeroes and 3 for zeroes.
 
4:35 AM
ok
 
dups is another dictionary/hash table.
In Python you can use a surprising large range of types as keys in a dictionary.
When working with the hashtable dictionary we are using an integer as the key, but you can also use a tuple of three numbers as a key.
 
oh nice
 
So I could write dups[(1,2,3)] = true to add the key (1,2,3) to the dictionary with the value true.
 
that makes sense
 
So this is an easy way to check for duplicate tuples.
Unfortunately you cannot use a list [1,2,3] as a key, so that's whi you see me converting the list to a tuple in the code so I can use it as a key.
 
4:40 AM
ohk
 
Using a dictionary to check for duplicates tuples is very fast. Much faster than using if mylist in outputlist.
 
yep
one last doubt
 
So:
1. we reduce th size of the input by removing duplicates
2. we use a much faster way of checking for duplicates in the output
And those two changes did the trick! :-)
 
yea your solution is very clever
            if y in hashtable and hashtable[y] > j:
can u tell me why u used hashtable[y]>j
 
Note that I'm using:
for i in range(len(newlist)):
    for j in range(i+1, len(newlist)):
So j is always greater than i. Yes?
 
4:44 AM
yes
 
And hashtable[y] is the index of the third number i.e. effectively k if we did:
    for i in range(len(newlist)):
        for j in range(i+1, len(newlist)):
            for k in range(j+1, len(newlist)):
So all we need to check is that hashtable[y] > j.
 
ohhk
that makes sense
thanks a lot!
i can try the code now
 
:-)
 

« first day (22 days earlier)