There has beenabout a Google recruiting method calledFoobar. Supposedly if you search enough programming-related issues like python mutex lock, your account is flagged and youre offered to play a game with a series of programming challenges. If you do well, people claim youre invited for an interview.
x will always be a positive integer, no larger than 1000000000.
With these two, we can solve our problem:
It turns out this challenge has its roots in ternary, a base-3 numeral system similar to binary. And there is a way of representing ternary in a balanced form, where each digit is represented with either +, 0, or – (or something similar). Using this system,anynumber can be represented. I find this fact fascinating.
The first element of the output list should correspond to the 1-unit weight, the second element to the 3-unit weight, and so on. Each string is one of:
// is not larger than num. Add 0s for the index
To help Beta get into the room, write a method called answer(x), which outputs a list of strings representing where the weights should be placed, in order for the two sides to be balanced, assuming that weight on the left has mass x units.
// were working right to left through the conversion
The idea that any mass on the scale can be balanced using weights with only powers of three (with only one weight per power of 3) doesnt seem intuitive.
We can test this by runninganswer(546)for the scenario where our rabbit super hero sees an initial weight of 546 on the left side of the scale. Our output list becomes[-, L, R, L, R, L, R], where our left side is 546 + 3^1 + 3^3 + 3^5 and our right side is 3^2 + 3^4 + 3^6. Both sides become balanced at a weight of 819.
// We leave our loop with i being 1 too large
// Need to turn our number into an array. Reversing it since
For example, the number 23 in the decimal system in ternary is 212 (2*3^0 + 1*3^1 + 2*3^2). We can represent 212 in a balanced form as +0– the following way: moving from right to left, convert each 2 value to a -+, where the + takes the 2s position and the negative character is carried to the next column. The negative carried value is added to the existing column and the process continues. There arenice write-upson conversion to ternary.
From the streets to enterprise software.
To ensure that the output is the smallest possible, the last element of the list must not be -.
Well, I wasnt offered to play this game. Thankfully, my friend was, and he shared one of challenges below:
Next, we can take the result and balance it with our challenges notation:
Output:(string list) [L, R]
// Since we can use up to 2, see if we can fit 2
First, well convert our initial scale value to ternary with adecimal_to_ternary(num)method. Then, well balance the ternary result usingbalance(num)based on our strategy above, taking into account that well represent our +, 0, and – characters as either L, R, and -.
This method seems ideal for our challenge.
Output:(string list) [L, -, R]
A JavaScipt method for converting to ternary with a few comments is below:
Can we save them? Beta Rabbit is trying to break into a lab that contains the only known zombie cure – but theres an obstacle. The door will only open if a challenge is solved correctly. The future of the zombified rabbit population is at stake, so Beta reads the challenge: There is a scale with an object on the left-hand side, whose mass is given in some number of units. Predictably, the task is to balance the two sides. But there is a catch: You only have this peculiar weight set, having masses 1, 3, 9, 27, … units. That is, one for each power of 3. Being a brilliant mathematician, Beta Rabbit quickly discovers that any number of units of mass can be balanced exactly using this set.
; i++) temp = array[i] + carry; carry =
// Looking for the largest power of 3 where 3^i
As a side note: This is likely not an efficient way to solve this problem. Its possible to convert a decimal number directly to balanced ternary, but breaking the steps up helped me better learn the process.