Maintain insert order from a tuple and count k(3) unique paths/products

Question

While preparing for an interview I saw the following question as follows:

Following tuple is given as input, where first element is CustomerID and second element is ProductID. We need to find the output as consecutive longest in order sequence of ProductID which every customer buys.

Input: [('A','Milk'), ('B','Milk'), ('A','Apples'), ('A','Coffee'),
 ('B','Apples'),('C','Apples'), ('B','Coffee'), ('A','Vegetable'), ('B', 'Hat')]

Output: Milk, Apples, Coffee (Max order 3)
# Maintain the order of the tuple

My attempt is as follows:

Input= [('A','Milk'), ('B','Milk'), ('A','Apples'), ('A','Coffee'),
 ('B','Apples'),('C','Apples'), ('B','Coffee'), ('A','Vegetable'), ('B', 'Hat')]

result=[]
for a, b in Input:
    if b not in result and len(result)<3: 
       result.append(b)

print ', '.join(result)

The answer for the above solution is as expected. Is there any easier solution or can I use other data structure to solve it? Thanks!

Possible duplicate of [How do you remove duplicates from a list whilst preserving order?](https://stackoverflow.com/questions/480214/how-do-you-remove-duplicates-from-a-list-whilst-preserving-order) — Chris, Oct 04 '19 at 06:38
I think my question was was relevant to https://stackoverflow.com/questions/8683060/finding-the-most-common-three-item-sequence-in-a-very-large-file — deep, Oct 04 '19 at 23:16

score 1 · Answer 1 · answered Oct 04 '19 at 06:49

1

Let's look at your approach with more depth and compute its time complexity :

result=[]
for a, b in Input:
    if b not in result and len(result)<3: 
       result.append(b)

You are scanning Input once, it is O(N). after that you check out the array result to check whether b has been found before or not, it is also O(N), but in this case the length of b is small. so we can assume that it is a constant c.

The final order would be :

Scanning Input * scanning b = O(N) * c ≈ O(N)

because in worst case c=2 !

it's really ideal, so you don't need to use a data structure considering the presumed conditions.

answered Oct 04 '19 at 06:49

Mohsen_Fatemi

2,183
2
16
25

Is this not a case of longest subsequence in order? Can we use that algorithm too to solve it? Thanks – deep Oct 04 '19 at 22:36
if you choose `c` to be a great number, the order of this algorithm will be `O(N^2)`. it really depends on the input of your problem – Mohsen_Fatemi Oct 05 '19 at 08:16

score 1 · Answer 2 · answered Oct 04 '19 at 07:14

1

Using Python 3.7+, you can use the fact that dictionaries are ordered, as follows:

d = {b:a for a,b in Input}
result = list(d)[:3]
print(', '.join(result))
# Milk, Apples, Coffee

answered Oct 04 '19 at 07:14

Laurent H.

6,316
1
18
40

Maintain insert order from a tuple and count k(3) unique paths/products

2 Answers2