 # Code Challenge #22: September 13, 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer’s job interview at places such as Google and Facebook.

This week’s challenge was reported to have been asked in interviews at Google:

### Basic Difficulty

Write a function, `timesTables`, that prints out multiplication tables (the type you learned in primary / grade school) up to 12x12.

• Function Name: `timesTables`
• Output: Example output:

`1 2 3 4 5 6 7 8 9 10 11 12`
`2 4 6 8 10 12 14 16 18 20 22 24`
`3 6 9 12 15 18 21 24 27 30 33 36`
`4 8 12 16 20 24 28 32 36 40 44 48`
`5 10 15 20 25 30 35 40 45 50 55 60`
`6 12 18 24 30 36 42 48 54 60 66 72`
`7 14 21 28 35 42 49 56 63 70 77 84`
`8 16 24 32 40 48 56 64 72 80 88 96`
`9 18 27 36 45 54 63 72 81 90 99 108`
`10 20 30 40 50 60 70 80 90 100 110 120`
`11 22 33 44 55 66 77 88 99 110 121 132`
`12 24 36 48 60 72 84 96 108 120 132 144`

• This challenge may appear to be quite easy, and part of the point of many code challenges asked in interviews is that they are easy (see here)! You should be able to solve this in under ten minutes. How elegantly can you write your solution? Plan your strategy for solving this question and walk your “interviewer” through your thought processes (that is, write down an explanation for your code and your thinking behind it). What’s the best way to solve this problem? What are some interesting non-standard approaches to solving this problem?
• What if your interviewer had follow-up questions or extensions to this challenge? Don’t anticipate what exactly those follow-ups or changes may be, but try to write your code so that it is easily read, easily maintained, and can be adapted to potential modifications in the interviewer’s questioning.

### Intermediate difficulty

Write a function, `oddTimesTables`, that will print only the odd numbers from the multiplication tables up to 12x12.

• Function Name: `oddTimesTables`
• Output:
`1 3 5 7 9 11`
`3 9 15 21 27 33`
`5 15 25 35 45 55`
`7 21 35 49 63 77`
`9 27 45 63 81 99`
`11 33 55 77 99 121`
• You must explain your submission to be able to win!
• You can reason which numbers will be odd based on the patterns in multiplication tables, but whatever method you choose, you should also write a test that makes sure that the numbers to be printed are indeed odd.

### Hard Difficulty

Write `timesTables` and `oddTimesTables` as efficiently as possible.

• Don’t forget to explain your submission just as you would do in a job interview setting!

#### `Reply` to this thread with a link to your code on repl.itand paste your properly formatted code to participate! Don’t just submit your code, remember to `explain` your solution, too! If you want to be considered as the winner, your function `must` have the `correct name` and provide `output in the format specified` above, you also need to abide by our other simple rules.

As always solutions using imports to do all the heavy lifting such as `itertools` will not be considered for the winner.

When including your repl.it link, please just give us the link and not the code preview! Just put a space before your URL so that the preview box doesn’t show – too many preview boxes can make the thread hard to read.

The fine print:

Here’s my code:
https://repl.it/LD6w/4

Everything it’s commented. I optimised the code as good as I could.
NOTE: I’m using c++

1 Like

Code:
https://repl.it/LDnM/5
This is all programmed in Lua, everything included in the code is explained with reason.

To repeat… Entries must follow the instructions to be accepted.

1 Like

Python 3.6 https://repl.it/LEDG

``````# This is an evening for one-liners, so I decided to look past the fact
# that all multiplications except the ones on the diagonal line at 1*1
# to n*n are calculated twice. I didn't want to spoil the generator
# comprehensions with memoization :)

def timesTables():
# nested loop generating the required 2d array. All numbers in
# x and y are multiplied with each other resulting in a 12 x 12
# grid of stringified numbers.
print_table((str(x * y) for x in range(1, 13)) for y in range(1, 13))

def oddTimesTables():
# multiplying any number with an even number results in an even number,
# so we skip even numbers on both axis. Besides that, it works the same
# as times_tables(). This results in a 6 x 6 grid. A quarter of the
# original. No extra checks needed.
print_table((str(x * y) for x in range(1, 13, 2)) for y in range(1, 13, 2))

def print_table(table):
print('\n'.join([' '.join(row) for row in table]))

print(timesTables.__name__)
timesTables()
print('\n%s' % oddTimesTables.__name__)
oddTimesTables()
``````
5 Likes

Here is my submission in Python 3:

``````def printTable(last, odds=False):
if odds:
numbers = range(1,last+1,2)
else:
numbers = range(1,last+1)
for i in numbers:
for j in numbers:
print('{:>4}'.format(i*j),end="")
print()

def timesTables():
printTable(12)

def oddTimesTables():
printTable(12, odds=True)

timesTables()
print()
oddTimesTables()

``````

I decided to implement a generic routine `printTable` that takes a parameter `last` that determines the size of the multiplication table. Also there is an optional parameter `odds` which if True, causes only odd numbers to be used.
I create a “range” generator `numbers` from those parameters, that gets used for both the rows and the columns.

Here is the corresponding output:

``````   1   2   3   4   5   6   7   8   9  10  11  12
2   4   6   8  10  12  14  16  18  20  22  24
3   6   9  12  15  18  21  24  27  30  33  36
4   8  12  16  20  24  28  32  36  40  44  48
5  10  15  20  25  30  35  40  45  50  55  60
6  12  18  24  30  36  42  48  54  60  66  72
7  14  21  28  35  42  49  56  63  70  77  84
8  16  24  32  40  48  56  64  72  80  88  96
9  18  27  36  45  54  63  72  81  90  99 108
10  20  30  40  50  60  70  80  90 100 110 120
11  22  33  44  55  66  77  88  99 110 121 132
12  24  36  48  60  72  84  96 108 120 132 144

1   3   5   7   9  11
3   9  15  21  27  33
5  15  25  35  45  55
7  21  35  49  63  77
9  27  45  63  81  99
11  33  55  77  99 121
``````

Here is the IDE link: https://repl.it/LEFg/8

1 Like

Python 3.6 -
Basic / Intermediate / Hard :

``````def timesTables():
return ultimateTimesTables(12)           # start is default 1, end is 12 and difference is default 1; this gets tables of all the numbers from 1 to 12

def oddTimesTables():
return ultimateTimesTables(12, 2)      # difference is 2, start is default 1 and end is 12; this gets all tables of all odd numbers till 12

def ultimateTimesTables(end, steps=1, start=1):  # O(n^2)
# Get all the numbers between start and end, in steps
# Example - from 1 to 12 in intervals of 3 gives - 1, 4, 7, 10
numbers = range(start, end+1, steps)            # O(n)
# Now, iterate through each number
for x in numbers:                                    # O(n)
# Multiply current number of loop i.e. x, with all the initial numbers and retrieve all of them
print(*map(lambda y: x*y, numbers))

timesTables()
oddTimesTables()
ultimateTimesTables(100, 10, 10)
``````
``````Output :
timesTables() =>
1 2 3 4 5 6 7 8 9 10 11 12
2 4 6 8 10 12 14 16 18 20 22 24
3 6 9 12 15 18 21 24 27 30 33 36
4 8 12 16 20 24 28 32 36 40 44 48
5 10 15 20 25 30 35 40 45 50 55 60
6 12 18 24 30 36 42 48 54 60 66 72
7 14 21 28 35 42 49 56 63 70 77 84
8 16 24 32 40 48 56 64 72 80 88 96
9 18 27 36 45 54 63 72 81 90 99 108
10 20 30 40 50 60 70 80 90 100 110 120
11 22 33 44 55 66 77 88 99 110 121 132
12 24 36 48 60 72 84 96 108 120 132 144
--------------------------------------------------

oddTimesTables() =>
1 3 5 7 9 11
3 9 15 21 27 33
5 15 25 35 45 55
7 21 35 49 63 77
9 27 45 63 81 99
11 33 55 77 99 121
--------------------------------------------------

ultimateTimesTables(100, 10, 10) =>
100 200 300 400 500 600 700 800 900 1000
200 400 600 800 1000 1200 1400 1600 1800 2000
300 600 900 1200 1500 1800 2100 2400 2700 3000
400 800 1200 1600 2000 2400 2800 3200 3600 4000
500 1000 1500 2000 2500 3000 3500 4000 4500 5000
600 1200 1800 2400 3000 3600 4200 4800 5400 6000
700 1400 2100 2800 3500 4200 4900 5600 6300 7000
800 1600 2400 3200 4000 4800 5600 6400 7200 8000
900 1800 2700 3600 4500 5400 6300 7200 8100 9000
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
--------------------------------------------------
``````

https://repl.it/LEWu/5

The time complexity of my solution is O(n^2), which I don’t like, so I will try to come up with different solution.

Edit :
I have come up with different solution to find the tables.

``````def ultimateTimesTablesNew(end, steps=1, start=1):  # O(n^2)
# Using the symmetry of the square matrix, we only have to find product of (n)+(n-1)+(n-2)+...+1 = n*(n+1)/2 numbers instead of n*n numbers
# Here i*j element is equal to j*i element of the matrix, where i represents row and j represents column
numbers = list(range(start, end+1, steps))
nLength = len(numbers)
# initialize with first row
tables = [ [start*each for each in numbers] ]
# get the remaining rows
for j in range(1, nLength):
# use elements from jth column of the previous rows to fill current row
# Example - 1st row - 1 2 3 4 5, 2nd row - 2 4 6 8 10, so for 3rd row, fill 3 and 6 directly from 3rd column of 1st and 2nd row without calculating the products 3*1 and 3*2
row = [ tables[i][j] for i in range(j) ]
# Calculate products for the remaining elements as their product is unknown
row += [ numbers[i]*numbers[j] for i in range(j, nLength) ]
tables.append(row)
return tables

# Or alternatively

def ultimateTimesTablesNew2(end, steps=1, start=1):  # O(n^2)
# Using the symmetry of the square matrix, we only have to find product of n numbers and sum of (n-1)+(n-2)+...+1 = n*(n-1)/2 numbers instead of finding the product of n*n numbers
# Here i*j element is equal to j*i element of the matrix, where i represents row and j represents column
numbers = list(range(start, end+1, steps))
nLength = len(numbers)
# initialize with first row
tables = [ [start*each for each in numbers] ]
# get the remaining rows
for j in range(1, nLength):
# use elements from jth column of the previous rows to fill current row
# Example - 1st row - 1 2 3 4 5, 2nd row - 2 4 6 8 10, so for 3rd row, fill 3 and 6 directly from 3rd column of 1st and 2nd row without calculating the sum or product
row = [ tables[i][j] for i in range(j) ]
# Calculate the remaining elements as they are unknown
# Every number in the matrix is sum of the first number of that column and the number above
# In the previous example after 3, 6 comes 9 which is calculated from the sum of numbers above it
above = j-1          # the row above current row
row += [ tables[above][i]+tables[i] for i in range(j, nLength) ]
tables.append(row)
return tables
``````

I would still go with my previous solution as calculating products is still faster in this case because it doesn’t create and store lists, also no array lookups which more then compensate for the speed (also more elegant and very precise)
But I have implemented this new method in java, and it gets faster as the number increases.
https://repl.it/LSbz

Edit 2 :
I realised that range function sitting in the plain sight is perfect for this job, faster than manually adding in the program(as range is in-built function which are optimised for performance) and twice as fast as using multiplication.

``````def ultimateTimesTablesNew_range(end, steps=1, start=1, printThem=True):  # O(n^2)
# Get the first row - all numbers multiplied by first number
# Example - from 3 to 12 in intervals of 3 gives - 9, 18, 27, 36
numbers = range(start*start, (start*end)+1, steps*start)            # O(n)
# Total numbers is each row
nLength = len(numbers)
# Now, iterate through each number
for x in numbers:                                    # O(n)
# Start each row with respectively indexed number from first row i.e. x, then, increment numbers in x and retrieve all of them
print(*range(x, (nLength*x)+1, x))
``````

https://repl.it/LEWu/6

2 Likes

Basic Difficulty (Java)
https://repl.it/LFdz/1

``````class Main{
public static void timesTables(){
for(int i=1;i<=12;i++){
for(int j=1;j<=12;j++){
System.out.print(i*j+" ");
}
System.out.println();
}
}
public static void main(String[]args){
timesTables();
}
}
``````

Intermediate Difficulty (Java)
https://repl.it/LFeq/1

``````class Main{
public static void oddTimesTables(){
for(int i=1;i<=12;i++){
for(int j=1;j<12;j++){
if((i*j)%2==1){
System.out.print(i*j+" ");
}
}
System.out.println();
}
}
public static void main(String[]args){
oddTimesTables();
}
}
``````
1 Like

Submission in Python 3:
https://repl.it/LFHo/8

Python 3 code: https://repl.it/LLq4/2

``````def timesTables(skip=1):
# in every line n of the times table...
for n in range(1, 13, skip):
# ... the products start from n and increase by n
for product in range(n, 12*n+1, n*skip):
print(product, end=' ')
print()

def oddTimesTables():
timesTables(skip=2)
``````

The code is explained in the comments (as much as there is to explain). It is based on the observation that each product at line n differs by its previous one by n.

Hi, here is my code with comments
https://repl.it/LLwz/0

Saludos

This is what i did in C

``````#include <stdio.h>

void timesTables(void)
{
int x, y, array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};

for(x=1; x<=12; x=x+1)
{
for(y=0; y<=11; y=y+1)
{
printf("%d ", array[y]*x);
}
printf("\n");
}
}

int main(void)
{
timesTables();

return 0;
}

``````

Basic and Intermediate
JavaScript

Commented in the code.

Basic Level in Python

``````def timesTables():
a = range(1,13)
c = 1
while c<13:
for x in a:
print c*x,
c+=1
print ''
return

timesTables()
``````

Output:

``````1 2 3 4 5 6 7 8 9 10 11 12
2 4 6 8 10 12 14 16 18 20 22 24
3 6 9 12 15 18 21 24 27 30 33 36
4 8 12 16 20 24 28 32 36 40 44 48
5 10 15 20 25 30 35 40 45 50 55 60
6 12 18 24 30 36 42 48 54 60 66 72
7 14 21 28 35 42 49 56 63 70 77 84
8 16 24 32 40 48 56 64 72 80 88 96
9 18 27 36 45 54 63 72 81 90 99 108
10 20 30 40 50 60 70 80 90 100 110 120
11 22 33 44 55 66 77 88 99 110 121 132
12 24 36 48 60 72 84 96 108 120 132 144
``````

The function creates a counter variable and an array with a given length, and the uses “while” loop to print values in the array mutiplied by the accumulative counter.

https://repl.it/LWNo/12

1 Like

Intermediate Difficulty in Python

``````def oddTimesTables():
a = range(1,13,2)
for x in a:
for y in a:
print x*y,
print ''
return

oddTimesTables()
``````

Output:

``````
1 3 5 7 9 11
3 9 15 21 27 33
5 15 25 35 45 55
7 21 35 49 63 77
9 27 45 63 81 99
11 33 55 77 99 121
``````

The function creates a range of odd values from 1 to 12 and uses nested loop to multiply these values.
[Edited to take into account the comments]

https://repl.it/LWRI/12

1 Like

2 posts were split to a new topic: Why use modulo?

Here’s my solution with explanation (using Python): https://repl.it/LWzv/0

C++ submission here: https://repl.it/LThu/19

Since the definition of ‘efficiency’ is rather vague and a naive implementation is basically as fast as the function possibly could be, I instead decided to interpret ‘efficiency’ as if I were programming a more complicated mathematical table on an old CPU where memory accesses are cheap and mathematical operations (i.e. multiplications) are expensive. Therefore, my ‘efficient’ implementation of timesTables performs the minimum required number of multiplications (i.e. the upper-triangular portion of the table), stores the result, and prints the full table from this ‘compressed’ list of numbers. The total number of multiplications performed is therefore (N^2 + N)/2 instead of N^2, with in increase in ‘efficiency’ by a factor of nearly 2 for large N.

If we want to define efficiency by minimizing the number of multiplications performed then I offer up this for your consideration:

``````def printTable(last, odds=False):
if odds:
numbers = range(1,last+1,2)
else:
numbers = range(1,last+1)
for i in numbers:
p = i
for j in numbers:
print('{:>4}'.format(p),end="")
p += i
if odds:
p += i
print()

def timesTables():
printTable(12)

def oddTimesTables():
printTable(12, odds=True)

timesTables()
print()
oddTimesTables()
``````

Here is the output, same as before:

``````   1   2   3   4   5   6   7   8   9  10  11  12
2   4   6   8  10  12  14  16  18  20  22  24
3   6   9  12  15  18  21  24  27  30  33  36
4   8  12  16  20  24  28  32  36  40  44  48
5  10  15  20  25  30  35  40  45  50  55  60
6  12  18  24  30  36  42  48  54  60  66  72
7  14  21  28  35  42  49  56  63  70  77  84
8  16  24  32  40  48  56  64  72  80  88  96
9  18  27  36  45  54  63  72  81  90  99 108
10  20  30  40  50  60  70  80  90 100 110 120
11  22  33  44  55  66  77  88  99 110 121 132
12  24  36  48  60  72  84  96 108 120 132 144

1   3   5   7   9  11
3   9  15  21  27  33
5  15  25  35  45  55
7  21  35  49  63  77
9  27  45  63  81  99
11  33  55  77  99 121
``````