Performing add/delete/count operations on a list

Question

Problem Statement (HackerRank)

You have a list of integers, initially the list is empty.

You have to process Q operations of three kinds:

• add s: Add integer s to your list, note that an integer can exist more than one time in the list

• del s: Delete one copy of integer s from the list, it's guaranteed that at least one copy of s will exist in the list.

• cnt s: Count how many integers a are there in the list such that a AND s = a, where AND is bitwise AND operator

Input Format

First line contains an integer Q. Each of the following Q lines contains an operation type string T and an integer s.

Constraints

• \$1 \le Q \le 200000\$
• \$0 \le s \lt 2^{16}\$

Output Format

For each cnt s operation, output the answer in a new line.

Sample Input

7 
add 11 
cnt 15 
add 4 
add 0 
cnt 6 
del 4 
cnt 15

Sample Output

1 
2 
2

Explanation

For first line, we have 15 AND 11 = 11 so the answer is 1

For second line, 6 AND 0 = 0 and 6 AND 4 = 4 so the answer is 2

For third line, 4 has been deleted and we have 15 AND 11 = 11 and 15 AND 0 = 0 so the answer is 2

My working code:

operations = int(raw_input())
current = 1
lst = []
while current <= operations:
    count = 0
    input_ = raw_input().split()
    operation = input_[0]
    num = int(input_[1])
    if operation == 'add':
        lst.append(num)
    elif operation == 'cnt':
        for number in lst:
            if number & num == number:
                count += 1
        print(count)
    elif operation == 'del':
        lst.remove(num)
    current += 1

Answer 1

You don't exploit the nature of the question.

Constraints

• \$1 \le Q \le 200000\$
• \$0 \le s \lt 2 ^ {16}\$

Why are these important? It's so you can achieve greater performance, for a price in memory.

You know that there is \$2 ^ {16}\$ possible numerical inputs, and there is a maximum of 200000 inputs.

If the last input is count, and all the rest are add, you will be recounting numbers a lot. Leading to a dramatic performance loss.

First you would want to prevent recounting if possible. One way to do this is to make a dictionary to count the occurrences of numbers. However due to constant type changes you can just use a list instead.

lst = [0] * (2 ** 16)

This takes more time than using lst = [], but it will pay off.

---

If we look at the performance of your 3 functions. I use the information from Python's time complexity page.

Add

lst.append(num)

This is average case \$O(1)\$, worst case \$O(n)\$, (not amortized worst case).

lst is internally stored as an array, and so if you grow past the bounds all the data must move.

And so I will say this is \$O(n)\$.

Del

lst.remove(num)

This is average case \$O(n)\$, worst case \$O(n)\$.

And so this is \$O(n)\$.

cnt

for number in lst:
    if number & num == number:
        count += 1
print(count)

And again this is \$O(n)\$.

Overall

You can have 200000 calls to functions that are \$O(n)\$. If you ask me that's not good on performance.

---

You can easly make add and del \$O(1)\$.

If you use lst = [0] * (2 ** 16).

if operation == 'add':
    lst[num] += 1
elif operation == 'del':
    lst[num] -= 1

It's like using a default-dictionary where the index is only numbers. However this currently will have the drawback of cnt always being \$O(2 ^ {16})\$.

If you wish to fix that you can use a set, to store the numbers, so it is \$O(n)\$.

Here is a solution that passes a few more of the tests. It does not pass them all.

operations = int(raw_input())
nums = set()
storage = [0] * (2 ** 16)

for _ in xrange(operations): 
    input_ = raw_input().split()
    operation = input_[0]
    num = int(input_[1])

    if operation == 'add':
        nums |= {num}
        storage[num] += 1
    elif operation == 'cnt':
        print(sum(
            storage[number]
            for number in nums
            if (number & num) == number
        ))
    elif operation == 'del':
        storage[num] -= 1

This uses a similar solution as yours, my lst is nums. However, I aimed at obtaining \$O(1)\$ in both add and del.

---

I can't complete the problem. The way Python programmers that solved this use [0] * (2 ** 16) and binary logic I don't know. Which make all the functions \$O(256)\$.

Answer 2

This kind of looping structure:

loop_counter = start_value
while loop_count < end_value:
    # Several lines of other code
    loop_counter += 1

is discouraged in most languages, because it spreads details about what is really one logical operation across your code. The preferred Python for this is:

for loop_counter in range(start_value, end_value):
    # Other code

Note that end_value is not included in the range, and you may need to choose it with that in mind.

You initialise a variable called count at the top of your loop, but it's only used in one of the branches of the if statement. For the same reason as above, it should go near where it's used:

elif operation == 'cnt':
    count = 0
    # Your current loop

You can check that this list comprehension will give you all the True/False results of that if in that loop:

[(number & num) == number for number in lst]

Once you're happy with that, you can count how many are True just by adding them up (try these: True + True, True + True + True + False). That means that this (dropping the [] to make it a generator expression because we don't need it as a list to do this):

count = sum((number & num) == number for number in lst)

will give you the same answer as your for loop. You can almost read it as a sentence: "to get count, add up which numbers in lst have this interesting property".

Answer 3

You are requested to implement a data structure which can implement the three commands: add, cnt, del. What is the minimal information you have to hold? To respond to a cnt command it is enough to store 216 possible answers, corresponding to 216 possible values of s. That is enough. When you add a number a, just add 1 to the count of all s such that a&s == a. To del a number just decrement the counter. So here is the core of a possible (not tested) implementation:

class CountMachine(object):
   def __init__(self):
      self.count = [0] * 216

   def cnt(self, s):
      return self.count[s]

   def add(self, a, step=1):
      for s in range(len(self.count)):
          if (a & s) == a:
             self.count[s] += step

   def del(self, a):
      self.add(a, step=-1)