Learning Python with Interview Questions 1. 3–6–9

Have you ever think about switching your primary interview language? I started thinking about that for a while, but I hesitate to switch them since most of my previous solution was written in Java. Also, I was a bit lazy to switch them.

One day, I had an interview with a big tech company. It was the final round for getting an intern job, but I was too intimidating, and nervous. Even though I answered questions verbally, I couldn’t finish my code within the time. That’s not just because of my typing speed(yes, I can tell my typing speed is very slow), but also my fingers are shaken, and my heart was beaten too hard. Additionally, I wrote all codes in Java which needed to write a lot of lines of code to answer.

I lose the chance to get the job, but I learned that it’s challenging to write the “workable” code in a short amount of time. (The interviewer asked 2 medium-level questions for 40 minutes.) So I decide to change my interview language even though it would be a bit painful.

For the learning purpose, I start my algorithm challenge with python mostly with easy interview questions. The focus is more on learning python rather than problem-solving.

python logo https://www.python.org/

Algorithm challenge Day 1

Question. 3–6–9 (from binarysearch.com)
Given an integer n, return a list with each number from 1 to n, except if it's a multiple of 3 or has a 3, 6, or 9 in the number, it should be the string "clap". Note: return the number as a string.
Constraints n ≤ 100,000

Input

n = 16

Output

["1", "2", "clap", "4", "5", "clap", "7", "8", "clap", "10", "11", "clap", "clap", "14", "clap", "clap"]

Explanation

• 3, 6, 9, 12, and 15 are replaced by “clap” since they are divisible by 3.
• 13 is replaced since it has a 3 in the number.
• 16 is replaced since it has a 6 in the number.

Understanding

This question reminds me of the game 3–6–9. (I’m sure this idea is from that one). The first approach is the understanding question.

What are the cases for replacing ‘clap’?

• Case of least significant number with 3, 6, 9. : [3, 6, 9, 13, 16, 19 ...]
• Case of non-least number with 3, 6, 9: [30, 60, 90, 132, 300 ...]

Those two cases are in the question which referred to ‘a multiple of 3’ or ‘has a 3, 6, 9’.

The intuitive solution that comes to mind is converting the number to a string. probably this is the easiest approach to solve this problem.

Approach 1: Convert to String, Linear searching

1. Adding a for loop

class Solution: 
    def solve(self, n): 
       ret = []
       for num in range(1, n+1):
       #starts from 1 otherwise n will be 0 rather than 1

range(n)

range() function can be used with for that create a sequence of numbers from start to end by step. (w3schools)

range(start, end, step)

eg. for i in range(5): looping 0 to 4, i represents the element of each number 0 to 4.
for i in range(1, 5): same as for(int i=1; i≤5; i++), looping 1 to 5
for i in range(1, 5, 2): same as for(int i=1; i≤5; i+=2), looping 1 to 5 by increment by 2

2. Add condition for multiple of 3

class Solution: 
    def solve(self, n): 
       ret = []
       for i in range(1, n+1):
           if i % 3 == 0:
              ret.append('clap')
           elif '3' in str(i) or '6' in str(i) or '9' in str(i):
              ret.append('clap')
           else: 
              ret.append(str(i))
       return ret

if condition

Python if condition is very simple. Just add : and remember elif rather than else if.

if condition :
elif condition :
else condition :

class Solution: 
    def solve(self, n): 
       ret = []
       for i in range(1, n+1)
           if i % 3 == 0:
              ret.append('clap')
           elif '3' in str(i) or '6' in str(i) or '9' in str(i):
              ret.append('clap')
           else: 
              ret.append(str(i))
       return ret

Complexity

Time: O(n) iterate 1..n+1 once, so it is linear time.
Spece: O(1) no extra space allocated rather than return value.

Okay, let’s submit the first code in python.

Of course, this question can be approachable to nlogn way without using strings. However, I’d like to move on next easy question until I feel comfortable writing Python.