Linode Interview Question for Python Developers


Country: United States




Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Then 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.

- Yawn February 02, 2019 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More