Create an account


Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
[Tut] Google’s FooBar Challenge | See How I Passed Levels 1 to 5 in Real-Time

#1
Google’s FooBar Challenge | See How I Passed Levels 1 to 5 in Real-Time

I just got invited to perform Google’s FooBar challenge. In this article, I want to share with you how I solved the problems in real-time. The purpose of this article is to educate you—and to have some fun. So, are you ready?

Level 1: Prime Numbers


The first goal was to find an identifier for a new employee at the “minions” company.

The identifier is selected base on a random number i. How do we come from the random integer i to the identifier of the new minion employee?

  • Create a sequence of prime numbers '23571113...'.
  • The identifier is the subsequence starting from index i and ending in index i+4 (included).
  • The value i is an integer between 0 and 10000.


Here’s the solution I implemented in the video:

def solution(i): # Determine prime sequence primes = getPrimeNumbers() return primes[i:i+5] def getPrimeNumbers(): '''Returns the string of prime numbers up to 10k+5 positions.''' s = '' prime = 2 while len(s) < 10005: # Add new prime to s s += str(prime) # Calculate next prime prime += 1 while not is_prime(prime): prime += 1 return s def is_prime(n): '''Tests if a number is prime. ''' for i in range(2,n): if n % i == 0: return False return True print(solution(0))
# 23571 print(solution(3))
# 71113

Level 2 | Part 1: Sequence Sum




Here’s the problem posed by Google:

Numbers Station Coded Messages
When you went undercover in Commander Lambda's organization, you set up a coded messaging system with Bunny Headquarters to allow them to send you important mission updates. Now that you're here and promoted to Henchman, you need to make sure you can receive those messages - but since you need to sneak them past Commander Lambda's spies, it won't be easy! Bunny HQ has secretly taken control of two of the galaxy's more obscure numbers stations, and will use them to broadcast lists of numbers. They've given you a numerical key, and their messages will be encrypted within the first sequence of numbers that adds up to that key within any given list of numbers. Given a non-empty list of positive integers l and a
target positive integer t, write a function solution(l,
t) which verifies if there is at least one consecutive
sequence of positive integers within the list l (i.e.
a contiguous sub-list) that can be summed up to the
given target positive integer t (the key) and returns
the lexicographically smallest list containing the
smallest start and end indexes where this sequence can
be found, or returns the array [-1, -1] in the case
that there is no such sequence (to throw off Lambda's spies, not all number broadcasts will contain a coded message). For example, given the broadcast list l as [4, 3, 5, 7, 8] and the key t as 12, the function solution(l, t) would return the list [0, 2] because the list l contains the sub-list [4, 3, 5] starting at index 0 and ending at index 2, for which 4 + 3 + 5 = 12, even though there is a shorter sequence that happens later in the list (5 + 7). On the other hand, given the list l as [1, 2, 3, 4] and the key t as 15, the function solution(l, t) would return [-1, -1] because there is no sub-list of list l that can be summed up to the given target value t = 15. To help you identify the coded broadcasts, Bunny HQ has agreed to the following standards: - Each list l will contain at least 1 element but never more than 100.
- Each element of l will be between 1 and 100.
- t will be a positive integer, not exceeding 250.
- The first element of the list l has index 0.
- For the list returned by solution(l, t), the start index must be equal or smaller than the end index. Remember, to throw off Lambda's spies, Bunny HQ might include more than one contiguous sublist of a number broadcast that can be summed up to the key. You know that the message will always be hidden in the first sublist that sums up to the key, so solution(l, t) should only return that sublist. Languages
To provide a Python solution, edit solution.py
To provide a Java solution, edit Solution.java Test cases
Your code should pass the following test cases.
Note that it may also be run against hidden test cases not shown here. -- Python cases --
Input:
solution.solution([1, 2, 3, 4], 15)
Output:
-1,-1
Input:
solution.solution([4, 3, 10, 2, 8], 12)
Output:
2,3 -- Java cases --
Input:
Solution.solution({1, 2, 3, 4}, 15)
Output:
-1,-1
Input:
Solution.solution({4, 3, 10, 2, 8}, 12)
Output:
2,3 Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.

Here’s the first code that I tried:

def solution(l, t): start = 0 while start < len(l): for stop in range(start, len(l)): s = sum(l[start:stop+1]) if s == t: return [start, stop] elif s > t: break start += 1 return [-1, -1] 

The code solves the problem but it takes quadratic runtime so I though—can we do better? Yes, we can! There’s a linear runtime solution:

def solution(l, t): start = stop = 0 while start <= stop and stop < len(l): s = sum(l[start:stop+1]) if s == t: return [start, stop] elif s < t: stop += 1 else: start += 1 stop = max(start, stop) return [-1, -1]

Both solutions work—but the latter is much faster. Here’s the output and the test cases:

print(solution([250,0,0], 250))
print(solution([1,2,3,4], 15))
print(solution([4, 3, 10, 2, 8], 12))
print(solution([4, 3, 5, 7, 8], 12))
print(solution([260], 260)) '''
[0, 0]
[-1, -1]
[2, 3]
[0, 2]
[0, 0] '''

After submitting the solution in my browser shell, Google tells me that there is one more challenge to go to reach the next level:



https://www.sickgaming.net/blog/2020/05/...real-time/
Reply



Forum Jump:


Users browsing this thread:
1 Guest(s)

[-]
Discord

[-]
Active Threads
(Indie Deal) RE8, Frontier, Slitherine, ...
Last Post: xSicKxBot
Today 05:00 AM
» Replies: 0
» Views: 4
Microsoft - Inclusion for all this Inter...
Last Post: xSicKxBot
Today 02:39 AM
» Replies: 0
» Views: 4
News - .hack//G.U. Last Recode Is Coming...
Last Post: xSicKxBot
Today 02:39 AM
» Replies: 0
» Views: 2
News - A New Peacemaker TV Show Trailer ...
Last Post: xSicKxBot
Today 02:39 AM
» Replies: 0
» Views: 2
(Indie Deal) 2K, SNK, Ziggurat & Graffit...
Last Post: xSicKxBot
Yesterday 11:12 PM
» Replies: 0
» Views: 10
News - George Clooney Reveals Why He Tur...
Last Post: xSicKxBot
Yesterday 08:39 PM
» Replies: 0
» Views: 9
(Indie Deal) 2K, SNK, Ziggurat & Graffit...
Last Post: xSicKxBot
Yesterday 05:39 PM
» Replies: 0
» Views: 10
Microsoft - Fund manager RFP opens for M...
Last Post: xSicKxBot
Yesterday 05:39 PM
» Replies: 0
» Views: 3
News - Fortnite's Midas Is Still Alive A...
Last Post: xSicKxBot
Yesterday 05:38 PM
» Replies: 0
» Views: 3
[Tut] La forma más pitónica de comparar ...
Last Post: xSicKxBot
Yesterday 12:46 PM
» Replies: 0
» Views: 15

[-]
Twitter

[-]
Sponsored
Get the Deal of the Week at RefurBees.com



Discord Server © SickGaming.net 2012-2021