Efficiency Matters

From quadratic to linear time with a few small touches.

(image created by author with Midjourney)

I’ll show you a question that you’re likely to encounter in the live-coding session of an interview.

It’s not a difficult one. You can tackle it down if you’re familiar with Python basics and its built-in data structures.

However, there are different ways of solving it. How you approach the problem and create a solution tells the interviewer a lot about your knowledge of data structures and algorithms.

We’ll first use a naive approach and implement a solution without thinking about efficiency.

Then, we’ll try to find the time complexity of our solution, which is also a highly probable interview question.

Finally, we’ll implement a more efficient solution with time complexity in mind.

By the time we reach the final answer, you’ll have learned a lot about Python’s data structures and how to leverage them for increasing efficiency.

Question

Write a function that takes as input a list of words and a sentence and determines if the given sentence can be written using the words in the given word list.

Here are our input examples of word list and sentence:

word_list = [
    "a", "an", "the", "is", "high"…