I was looking up some questions late at night (I think it was dependency injections in Go) and saw “Curious developers are known to seek interesting problems. Solve one from Google?” prompt appear in the search bar. Although I’m not Googler-smart, I thought I’d give them a try. In this blog post, I’ll provide solutions to those that I have solved - up to the one that I couldn’t.

Braille Translation

Braille is a writing system for visually impaired people. It’s composed of a set of 6 dots (“Braille cell”) read from top-down, left-to-right using bumps and dots as such:

Each of the Braille cells represents a symbol in a natural language. In the foobar challenge, that symbol range was basic Latin alphabets - lowercase and uppercase - and a space. Thankfully, as this constraint allowed me to not consider punctuations, the following table from the Wikipedia Braille article was extremely helpful to solve this problem.

I think an important pattern to recognize here are the colors red, green, and purple. The positions 3, 3-6, and 6 act like a control mechanism to provide derivatives to the repeating set: 1, 2, 4, 5. Also interestingly, the ‘w’ is in its’ own set because apparently when Louis Braille invented the Braille alphabet back in the 1800s’, the French alphabet did not have that letter!

Another interesting observation is that the repeating set doesn’t have the following patterns.

My guess is - after trying to read my apartment’s Braille fire escape instructions using my fingers - it’s very hard to differentiate the above sets with zero visual guidance.

Nonetheless, as I can’t think straight during interviews (and sadly it’s always after that I recover my clarity), I decided to hack together a replication of the Wikipedia Braille table and add Google’s two additional constraints about capitalization and spaces.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
BRAILLE_SPACE = '000000'
BRAILLE_CAPITAL = '000001'

BRAILLE_CHARSET = (
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
    'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
    'u', 'v', 'x', 'y', 'z', '',  '',  '',  '',  'w',
)

# After the [a,j] set, the rest are repetitions with only 3rd
# and last bit flipped. So we'll just recycle the base set.
BRAILLE_BITSET = {
    0: ('1', '0', '0', '0', '0', '0'),  # a
    1: ('1', '1', '0', '0', '0', '0'),  # b
    2: ('1', '0', '0', '1', '0', '0'),  # c
    3: ('1', '0', '0', '1', '1', '0'),  # d
    4: ('1', '0', '0', '0', '1', '0'),  # e
    5: ('1', '1', '0', '1', '0', '0'),  # f
    6: ('1', '1', '0', '1', '1', '0'),  # g
    7: ('1', '1', '0', '0', '1', '0'),  # h
    8: ('0', '1', '0', '1', '0', '0'),  # i
    9: ('0', '1', '0', '1', '1', '0'),  # j
}

def BrailleCharacter(char):
    v = char.lower()
    if v == ' ':
        return BRAILLE_SPACE

    # Convert the character into mutable "bitarray".
    i = BRAILLE_CHARSET.index(v) % len(BRAILLE_BITSET)
    b = list(BRAILLE_BITSET.get(i, BRAILLE_SPACE))

    # Flip bits based on control conditions.
    if v >= 'k':
        b[2] = '1'
    if v >= 'u':
        b[-1] = '1'
    if v == 'w':
        b[2] = '0'

    # Prepend capital bitset if capitalized.
    if char.isupper():
        b.insert(0, BRAILLE_CAPITAL)

    # Return "bitstring".
    return "".join(b)

def solution(s):
    return "".join([BrailleCharacter(c) for c in s])

And there we have it! This is what we get if we translate “Braille is cool”:

000001110000111010100000010100111000111000100010000000010100011100000000100100101010101010111000

Bunny Worker Locations

In this problem, we are given a right triangle that’s formed as a successive diagonal series.

And the task is to find which number is at the (x, y) position where x and y are (0, 100,000]. For example, here are a few test cases.

xy(x, y)
111
329
51096

I remembered learning about quadratic sequences during middle school that could be utilized for this challenge - but that would require finding the formula for each y set using the difference method. Instead here’s a much faster solution through a pattern I found.

This is an important relationship between the x-axis and the y=1 number series.

As you probably noticed as well, the y=1 number series is basically the addition of the x-axis.

So we can deduce that we can get any xth of y=1 by using this formula.

But this doesn’t accurately reflect when x>1. So this is another important relationship between the y-axis and the x=1 number series.

And you probably saw it as well that the x=1 series is basically the addition of the y-axis minus the last series.

So we can deduce that we can get any yth of x=1 by using this formula.

1
2
3
4
5
6
7
8
9
def solution(x, y):
    # The i-th x on x-coordinate with y=0 will always be the sum.
    xn = sum(range(1, x+1))

    # This is the deltas from the y-coordinate growth series.
    yn = sum(range(1, y-1))

    # This is the organic growth from the y-coordinate.
    return str(xn + yn + (x * (y-1)))

Don’t Get Volunteered!

This problem is very similar to a challenge in LeetCode about finding the minimal movement for a knight to get from a position (a, b) to (x, y). Since knights can move forwards and backwards in the L-shape, this makes a good problem for dynamic programming strategies. However, the difference in the foobar challenge is the following array instead of a straightforward index.

So given an 8x8 2-dimensional array, I needed to “pre-process” the starting and ending position to their respective (x, y) coordinates so that I could recycle the Leetcode-based solution.

Afterwards I utilized BFS strategy that keeps a queue of indexes + traveled cost and a matrix to keep track of where we have traveled to.

For example, for a knight to move from 0 to 63, the following would be populated by the time the knight reached the destination.

Queue:
  [((0, 7), 5), ((6, 5), 5), ((6, 7), 5),
   ((7, 0), 5), ((7, 2), 5), ((7, 4), 5),
   ((7, 6), 5), ((7, 7), 6)]

Visited:
  [[1, 1, 1, 1, 1, 1, 1, 1],
   [1, 1, 1, 1, 1, 1, 1, 1],
   [1, 1, 1, 1, 1, 1, 1, 1],
   [1, 1, 1, 1, 1, 1, 1, 1],
   [1, 1, 1, 1, 1, 1, 1, 1],
   [1, 1, 1, 1, 1, 1, 1, 1],
   [1, 1, 1, 1, 1, 1, 1, 1],
   [1, 1, 1, 1, 1, 1, 1, 1]]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import math

KNIGHT_MOVES_DELTA = (
    (-1, -2), (-1, 2), (-2, -1),
    (-2, 1),  (1, -2), (1, 2),
    (2, -1),  (2, 1),
)

def convert_position_to_index(position, rows=8, columns=8):
    return (
        position % columns,                # x
        int(math.floor(position / rows)),  # y
    )

def solution(src, dst):
    x1, y1 = convert_position_to_index(src)
    x2, y2 = convert_position_to_index(dst)
    visited = [[0 for _ in range(8)] for _ in range(8)]
    queue = [((x1, y1), 0)]
    def solve(x, y, p, q):
        while queue:
            (x, y), cost = queue.pop(0)
            if (x, y) == (x2, y2):
                return cost
            for dx, dy in KNIGHT_MOVES_DELTA:
                _x = x + dx
                _y = y + dy
                if (0 <= _x < 8 and 0 <= _y < 8 and not visitedt[_x][_y]):
                    visited[_x][_y] = 1
                    queue.append(((_x, _y), cost + 1))
    return solve(x1, y1, x2, y2)

Bomb, Baby!

Unfortunately I got blocked here because I didn’t understand the instructions.

Every Mach bomb retrieves a sync unit from a Facula bomb; for every Mach bomb, a Facula bomb is created;

I’m not too familar with bomb terms, but when I read “X retrieves a sync unit from Y”, I kept thinking about mutexes or semaphores so I wasn’t sure if the “Facula bomb” is an array composed of “syncable” elements and for each pop goes to the “Mach bomb”.

Every Facula bomb spontaneously creates a Mach bomb.

I think here the word “spontaneously” kind of threw me off. The way I interpreted this was if something is spontaneous, that would infer that it’s non-deterministic. So Facula bomb may or may not generate a Mach bomb - which I didn’t know how I can express this without using probabilities like 50%. But no probability thresholds were given so I was a bit stuck.

My guess is that the challenge wanted to use some kind of generation or genetic algorithms so that I can fully expand on the children of the Mach (“male”?) and Facula (“female”?) bombs.