I just had an interview with a startup company in Python, and I’m looking for a better solutions than mine… (I had 15 min to come with the solution).
- comment – what is better? I assume the interviewer aimed for better performance.
The question is:
You get a list of lists of strings, for example: lst = [['id_2','id_3'],['id_3','id_4','id_2'],['id_5']]
The answer you should return is how many connections each string has.
In our example in the first list id_2 connected with id_3. in the second list id_2 connected with id_3 and with id_4.
Therefor the expected solution is {id_2:2, id_3:2 , id_4:2 , id_5:0}
My solution is as follows:
lst = [['id_2','id_3'],['id_3','id_4','id_2'],['id_5']]
#Answer:- {id_2:2, id_3:2 , id_4:2 , id_5:0}
class sln:
def __init__(self, lst: list):
self._data = {} # key: id_X, value: list of connections [id_y, id_z]
self._build_data(lst)
def count_relations(self):
result = {}
for entry in self._data:
result[entry] = len(self._data[entry])
return result
def _build_data(self, lst: list):
for outter_lst in lst:
for item in outter_lst:
if item not in self._data.keys():
self._data[item] = []
self._append_relevant_keys(item, outter_lst)
def _append_relevant_keys(self, item: str, outter_lst: list):
for entry in outter_lst:
if entry not in self._data[item] and item != entry:
self._data[item].append(entry)
if __name__ == '__main__':
print(sln(lst).count_relations())
I did mention that I could the lists inside the data object with dictionaries to improve access speed even more.
4
Better is subjective, but IIUC you could loop through the lists and populate a dict of str->set, then get the length of the sets:
d = {}
for l in lst:
for e in l:
d.setdefault(e, set()).update([i for i in l if i != e])
d = {k: len(v) for k, v in d.items()}
{'id_2': 2, 'id_3': 2, 'id_4': 2, 'id_5': 0}
1