## Linode Interview Question

Python Developers**Country:**United States

```
def sortedList(str1, str2):
zipped_list = zip(str1.split(','), str2.split(','))
sorted_list = sorted(zipped_list)
list1 = [x for x, y in sorted_list]
list2 = [y for x, y in sorted_list]
return list1, list2
str1 = "D,A,B,C"
str2 = "1,2,3,4"
l1, l2 = sortedList(str1, str2)
print(l1)
print(l2)
```

```
def sortedList(str1, str2):
zipped_list = zip(str1.split(','), str2.split(','))
sorted_list = sorted(zipped_list)
list1 = [x for x, y in sorted_list]
list2 = [y for x, y in sorted_list]
return list1, list2
str1 = "D,A,B,C"
str2 = "1,2,3,4"
l1, l2 = sortedList(str1, str2)
print(l1)
print(l2)
```

```
def sortedList(str1, str2):
zipped_list = zip(str1.split(','), str2.split(','))
sorted_list = sorted(zipped_list)
list1 = [x for x, y in sorted_list]
list2 = [y for x, y in sorted_list]
return list1, list2
str1 = "D,A,B,C"
str2 = "1,2,3,4"
l1, l2 = sortedList(str1, str2)
print(l1)
print(l2)
```

```
def sortedList(str1, str2):
zipped_list = zip(str1.split(','), str2.split(','))
sorted_list = sorted(zipped_list)
list1 = [x for x, y in sorted_list]
list2 = [y for x, y in sorted_list]
return list1, list2
str1 = "D,A,B,C"
str2 = "1,2,3,4"
l1, l2 = sortedList(str1, str2)
print(l1)
print(l2)
```

```
def sortedList(str1, str2):zipped_list = zip(str1.split(','), str2.split(',')) sorted_list = sorted(zipped_list)list1 = [x for x, y in sorted_list]
list2 = [y for x, y in sorted_list]
return list1, list2
str1 = "D,A,B,C"
str2 = "1,2,3,4"
l1, l2 = sortedList(str1, str2)
print(l1)
print(l2)
```

{{

def sortedList(str1, str2):

zipped_list = zip(str1.split(','), str2.split(','))

sorted_list = sorted(zipped_list)

list1 = [x for x, y in sorted_list]

list2 = [y for x, y in sorted_list]

return list1, list2

str1 = "D,A,B,C"

str2 = "1,2,3,4"

l1, l2 = sortedList(str1, str2)

print(l1)

print(l2)

}}

```
def sortedList(str1, str2):
zipped_list = zip(str1.split(','), str2.split(','))
sorted_list = sorted(zipped_list)
list1 = [x for x, y in sorted_list]
list2 = [y for x, y in sorted_list]
return list1, list2
str1 = "D,A,B,C"
str2 = "1,2,3,4"
l1, l2 = sortedList(str1, str2)
print(l1)
print(l2)
```

`and`

def sortedList(str1, str2):

zipped_list = zip(str1.split(','), str2.split(','))

sorted_list = sorted(zipped_list)

list1 = [x for x, y in sorted_list]

list2 = [y for x, y in sorted_list]

return list1, list2

str1 = "D,A,B,C"

str2 = "1,2,3,4"

l1, l2 = sortedList(str1, str2)

print(l1)

print(l2)

`and`

```
def sortedList(str1, str2):
zipped_list = zip(str1.split(','), str2.split(','))
sorted_list = sorted(zipped_list)
list1 = [x for x, y in sorted_list]
list2 = [y for x, y in sorted_list]
return list1, list2
str1 = "D,A,B,C"
str2 = "1,2,3,4"
l1, l2 = sortedList(str1, str2)
print(l1)
print(l2)
```

```

def sortedList(str1, str2):

zipped_list = zip(str1.split(','), str2.split(','))

sorted_list = sorted(zipped_list)

list1 = [x for x, y in sorted_list]

list2 = [y for x, y in sorted_list]

return list1, list2

str1 = "D,A,B,C"

str2 = "1,2,3,4"

l1, l2 = sortedList(str1, str2)

print(l1)

print(l2)

```

```
def sortedList(str1, str2):
zipped_list = zip(str1.split(','), str2.split(','))
sorted_list = sorted(zipped_list)
list1 = [x for x, y in sorted_list]
list2 = [y for x, y in sorted_list]
return list1, list2
str1 = "D,A,B,C"
str2 = "1,2,3,4"
l1, l2 = sortedList(str1, str2)
print(l1)
print(l2)
```

The first question you should ask is to confirm that the unique values in the second list are a subset of the unique values of the first. Call the list sizes n and m respectively.

- Yawn February 02, 2019Then we need to think about how to sort them. How does a normal sorting algorithm work? It defines a comparator so that given a and b, we can say which comes first. It then sorts in m log(m) time.

Does this work in our case? Well, there is no "natural" ordering, so a comparator would need to be generated in a way that it holds n^2 values, for a result of comparing all unique strings in the first list. Hmm... that doesn't sound too good! n^2 space to hold and n^2 time to generate.

Can we do better? What are some non-comparison sorts that we know? Bucket sort? Yes, that might work. What if we make a "bucket" for each word in the first list? Then we just split the second list into these buckets and we're done.

How would we implement that? Well, a hashmap of course! We scan through list two (splitting on commas, I'll leave the Python details to you), and if we've not see the word yet we at it into our hashmap with a value of 1 (map.put(word, 1). If we have seen it, we increment the current key. Then we scan our first list, and for each word we look it up in the hashmap, and output that word map.get(word) number of times.

How efficient is this solution? We first need to scan the second list and add them all to a hash. Assuming O(1) hashmap operations, we use O(m) time. Then we have to scan through the first list O(n) time and output the second list. Assuming you don't do anything silly (ie. just try and build up one long string in Java, which is very inefficient due to immutability), we can do this in O(m) time. So our solution takes O(n+m) time and O(m) space.