How do I count the occurrence of a given string in list that has more nested lists/dictionaries?

Question

During a technical phone screen, I was given a list similar to below and asked to count the number of times the string 'a' occurs:

input = ['a', 'b', ['a', 'b', {'a': ['b', 'a', [{'b': ['a', 'b', {'a': 'a'}]}]]}]]

As you can see, in addition to the 'a' being an item in the list, it can also be an item in nested lists, as well as the keys and/or values in nested dictionaries.

This is the code I have so far in Python:

def count_letter_a(arr):

    count = 0

    for item in arr:
        if item == 'a':
            count += 1
        elif isinstance(item, list):
            count_letter_a(item)
        elif isinstance(item, dict):
            for k, v in item.items():
                pass

    return count

I'm stuck on what to do with the handling of dictionary keys/values portion of my function. What do I need to do?

Refer : https://stackoverflow.com/questions/9807634/find-all-occurrences-of-a-key-in-nested-python-dictionaries-and-lists — radix, Dec 14 '18 at 07:45

user2390182 · Answer 1 · 2018-12-14T08:38:46.460

4

You can just add the 'a' count of keys and values, or simple recursively apply it to the items directly. This requires that you count occurrences in tuples as well (I included sets to complete the built-in collections):

def count_a(obj):
    if isinstance(obj, (list, tuple, set)):
        return sum(map(count_a, obj))
    if isinstance(obj, dict):
        return sum(map(count_a, obj.items()))
    if obj == 'a':
        return 1
    return 0

>>> x = ['a', 'b', ['a', 'b', {'a': ['b', 'a', [{'b': ['a', 'b', {'a': 'a'}]}]]}]]
>>> count_a(x)
7

edited Dec 14 '18 at 08:38

answered Dec 14 '18 at 07:50

user2390182

72,016
6
67
89

nice adaptation to include `tuple` and `set` – Mulan Dec 14 '18 at 08:01
1

Nice answer. I'd rather not use `input` as a variable name though. – RoadRunner Dec 14 '18 at 08:27
@schwobaseggl, not sure if the use of sum and map would be allowed in an interview setting, especially if the person is not familiar with the python. – Jeffrey Lee Dec 14 '18 at 17:26

score 3 · Answer 2 · answered Dec 14 '18 at 08:00

You're really close!

def count (x):
  if isinstance (x, list):
    return sum (count (y) for y in x)
  elif isinstance (x, dict):
    return sum (count ([ k, v ]) for k,v in x.items ())
  elif x == "a":
    return 1
  else:
    return 0

It works like this

count ('foo')
# 0

count ([ 'a', 'b', 'c' ])
# 1

count (['a', 'b', ['a', 'b', {'a': ['b', 'a', [{'b': ['a', 'b', {'a': 'a'}]}]]}]])
# 7

How do I count the occurrence of a given string in list that has more nested lists/dictionaries?

2 Answers2