The world’s leading publication for data science, AI, and ML professionals.

Master Data Structure Dictionary in Python from Zero to Hero, Part 1

LeetCode your way to a data science position

Crack Data Science Interview

Photo by Pisit Heng on Unsplash
Photo by Pisit Heng on Unsplash


As many of you know, I’m transitioning my programming language from R to Python and have been practicing coding in Python for the past year. Not to brag, but I’m constantly amazed by my progress and quick turnover from the guy who only knows "Hello, World!" to the one who comfortably solves complex coding challenges on Leetcode.

For example, I live-code through fivedata science interview questions here:

FAANG Ask These 5 Python Questions in 2021

Python offers so many data types, and dictionaries are on the top of the list. Mastering Python dictionaries helps us crack any coding interviews. In today’s content, I select four interview questions and demonstrate how to use dictionaries in Python.


As a light refresher, let’s check what a dictionary is and its main attributes. A dictionary has three major features: unordered, changeable, and no duplicate.

1 A dictionary is not ordered, so we can’t use positions to access elements; instead, we have to use the key-value pair.

2 It is changeable, which allows us to update dictionary elements.

3 No duplicate allowed.

Here is a quick example.

We create a new dictionary, called _dictionary1, that has three key-value pairs.

{'brand': 'BMW', 'model': 'Model 3', 'year': 2000}

#1. Get keys of the dictionary

dict_keys(['brand', 'model', 'year'])

#2. Get the values of the dictionary

dict_values(['BMW', 'Model 3', 2000])

#3. Get the key-value pair

dict_items([('brand', 'BMW'), ('model', 'Model 3'), ('year', 2000)])

Question 1: Two Sum, by every tech company

  • Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
  • You may assume that each input would have exactly one solution, and you may not use the same element twice.
  • You can return the answer in any order.
  • https://leetcode.com/problems/two-sum/

Walk Through My Thinking

This is the "notorious" and probably most well-known interview question that every major company asks or has asked before. Newbie and mature programmers would approach this question differently.

For beginners, the first thing that comes to mind is to iterate over the list and continuously check if the sum of two elements adds up to the target value, aka brutal force.

If they do add up, we output the index, respectively. The only catch is we can’t use the same element twice, and there is only one solution.

Solution 1: nested for loop (brutal force)

[0, 1]

Sure, it works, but slowly. It has an O(N²) time complexity, making it a poor choice if the target array has millions of elements to check.

Your interviewer asks for improvement.

Solution 2: dictionary

Unlike beginners, experienced programmers analyze the question at hand and transform it into an easily understandable question. Mature coders think hard about how to access and store the values at each position more efficiently.

First hint: a dictionary is helpful!

To create and use an empty dictionary, we have to set conditions and specify what to do when the value is not in the dictionary and when it is. Following the same line of thinking, we create a new variable, diff, which records the difference between the target value and array elements. If the difference is not included in the dictionary, we add the key-value back to the dictionary; if included in the dictionary, we return the index of the original element and the key (index) of the dictionary.

Let’s check the code.

[0, 1]

WOW!

The second approach is way more efficient and faster with linear time complexity of O(N).

If you can grasp Solution 1, you have entered the door and become a Python beginner. After mastering Solution 2, you have advanced to the next level.


Question 2: Unique Number of Occurrences, by Google

Walk Through My Thinking

Google includes this question. The first step of any technical coding is to read the question and make sure you understand it. Ask for clarification if something doesn’t make sense, which adds point and do us favor.

After reading and analyzing the question, there are two parts:

1. calculate the occurrences of each value.

2. check if they are unique.

To calculate the occurrences (step #1), we create an empty dictionary and use if-else statements to store the key-value pairs.

To check for unique values (step #2), we can use another built-in data type, set, that does not allow duplicates. As a side note, we typically compare the lengths of two outputs after iterations and decide if they are the same in Python: if the length changes, the result has changed.

Solution

True

Again, set in Python does not allow duplicates. The combination of a dictionary and a set is powerful.

Photo by Annelies Geneyn on Unsplash
Photo by Annelies Geneyn on Unsplash

Question 3: N-Repeated Element in Size 2N Array, by Apple

Walk Through My Thinking

Apple asks this question. There are two pieces of useful information:

1. N+1 unique elements.

2. One element repeats N times.

The most natural thing to do is to count the occurrence and return the element that occurred N times.

Solution 1: built-in Counter()

3

First, let’s try the built-in method, Counter(), and return the element that occurred more than 1 time.

It’s easy and simple, but the catch is we may not import built-in functions in interviews.

Solution 2: dictionary.items()

We construct an empty dictionary and store the key-value pairs via a for loop. Next, we iterate over the dictionary and return the key when its value (occurrences) equals N.

Done!

As a side note, division in Python creates a float, which can’t be used to access items. That’s why we need to use floor division, len(A)//2 as in line 5, to calculate N.

type(22/2)
float
type(22//2)
int

Question 4: Single-Row Keyboard, by Google

  • There is a special keyboard with all keys in a single row.
  • Given a string keyboard of length 26 indicating the layout of the keyboard (indexed from 0 to 25), initially, your finger is at index 0. To type a character, you have to move your finger to the index of the desired character.
  • The time taken to move your finger from index i to index j is |i – j|.
  • You want to type a string word. Write a function to calculate how much time it takes to type it with one finger.
  • https://leetcode.com/problems/single-row-keyboard/

Walk Through My Thinking

Google asks this genius question. A lot of times, it’s not about how complicated but how tricky the question is. And, the challenge is to break down the problem and translate it into a more readable form.

A special keyboard with keys in a single row?

Never seen it before. But after some thinking, we can translate the question into the following: "Please calculate the total distances of indices for each element."

We can further break it down into two steps:

1. find the key-value pair.

2. calculate the total sum of the differences.

We map the key-value pairs to the empty dictionary (step #1) and add up the distances using a for loop, as follows.

Solution

4

In line 14, we update the temp value with the current index and prepare for the next iteration.


_The complete Python code is available on my Github._


Takeaways

  • If the question hints at key-value pairs, dictionaries could be helpful.
  • The tricky part is how to store values in dictionaries: do you have to update it for multiple occurrences? How?
  • There are three ways of filtering elements in dictionary: keys(), values(), and items().

_If you find my post useful and want to learn more about my other content, plz check out the entire content repository here: https://linktr.ee/leihua_ye._


My Data Science Interview Sequence:

Crack Data Science Interviews: Essential Machine Learning Concepts

Crack Data Science Interviews: Essential Statistics Concepts

Essential SQL Skills for Data Scientists in 2021


Enjoy reading this one?

Please find me on LinkedIn and Youtube.

Also, check my other posts on Artificial Intelligence and Machine Learning.


Related Articles