How to Answer: How many jewels are there?
Advice and answer examples written specifically for a Python Beginner Level Strings job interview.
3. How many jewels are there?
This interview question tests the developer's skills with Python strings and loops.
You are two given strings- jewels and stones. A jewel is a special and precious stone. All jewels are stones but not vice-versa. Each character of stones represents the type of stones that you have. So if,
stones = 'aAAqbb', you have:
â— one stone of type 'a'
â— two stones of type 'A'
â— one stone of type 'q'
â— two stones of type 'b'
Each character in jewels represents the type of stone that is a jewel. So if,
jewels = 'aA', then:
â— stone of type 'a' is a jewel
â— stone of type 'A' is a jewel
Your task is to find how many stones you have that are jewels
/*Example*/
stones = 'aAAqbb'
jewels = 'aA'
expected output = 3 // ('aAA' are all jewels)Solution:
The solution is simple. We will iterate over each character in the stones and will check if it is a jewel. To check if a stone is a jewel, we will check if the character is contained in the string jewels.
def findJewels(jewels: str, stones: str) -> int:
count = 0
for stone in stones:
# search for stone in complete jewels array
if stone in jewels:
count += 1
return countm = length of string jewels
n = length of string stones
Time complexity- O(m * n)
Space complexity- O(1)
There is one optimization we can do. The time complexity of in operator is O(m). Instead of checking if a stone is a jewel using in, we can have a set of stones that are jewels made from string jewels.
set(jewels) converts the string jewels to a set of characters.
So if jewels = 'aA',
set(jewels) = {'a', 'A'}
def findJewels(jewels: str, stones: str) -> int:
count = 0
jewels = set(jewels)
for stone in stones:
if stone in jewels:
count += 1
return countm = length of string jewels
n = length of string stones
Time complexity- O(n + m)
Space complexity- O(m)
Written by S. Kumar on June 27th, 2021