谷歌秋季实习OA

第一题


Basically, my interpretation is that we can look at all the possible starting indices for a starting array and compare the first value. All elements are unique (distinct), so one value within an array will always be larger or smaller than another–giving us the largest subarray if we just compare that first index.

Python solution:

def largest_subarray(a, k):
  # store first starting index for a subarray as the largest, since 'a' will always be <= 'k'
  first_idx = 0
  # check indices where a subarray of size k can be made
  for x in range(1, len(a) - k):
    # replace the largest first index if a larger value is found
    if a[first_idx] < a[x]:
      first_idx = x

  # return subarray starting at that largest possible first index with size k
  return a[first_idx:first_idx+k]

第二题


My solution ended up looking more lengthy than I would’ve liked, but I basically I do the following:

split a and b into arrays
use hash maps to look at individual strings within ‘a’ where characters are small (while keeping track of smallest char within a string too)
store those frequencies for later use
do the same for ‘b’, but compare each string with a’s frequencies on the spot
add the number of times ‘b’ is larger than ‘a’ to the solution array
Python solution:

def compare_strings(a ,b):
  # create arrays from both strings, which are delimited by ',' according to the problem statement
  a = a.split(',')
  b = b.split(',')
  # hold the frequencies for all the smallest characters for a
  a_comp = []
  # iterate through each string in a
  for string in a:
    char_map = {}
    # arbitrary char initialization that will always be larger than a-z
    smallest = '~'
    # get frequencies for each char within each of those strings
    # we only care about smaller ones since the larger ones will not be used for comparison
    for char in string:
      # <= may redundantly set smallest to char when it already equals it, but we need it to keep track of counts accuractely since letters won't always be consecutive
      if char <= smallest:
        smallest = char
        if char in char_map:
          char_map[char] += 1
        else:
          char_map[char] = 1
    # hold those frequencies so we can compare to b
    a_comp.append(char_map[smallest])  

  # final array to return, which holds the number of strings a given string in b is larger than in a
  # excuse the bad name lol
  b_string_largeness = []

  # find all the smallest character frequencies for b too
  for string in b:
    char_map = {}
    smallest = '~'
    for char in string:
      if char <= smallest:
        smallest = char
        if char in char_map:
          char_map[char] += 1
        else:
          char_map[char] = 1
    # store number of occurrences where the frequency of b's smallest char is more than a string within a
    num_larger = 0
    # go through each stored frequency in a and compare to b
    for a_freq in a_comp:
      if a_freq < char_map[smallest]:
        num_larger += 1
    # add the final array with the number of arrays this string in b is larger than
    b_string_largeness.append(num_larger)

  return b_string_largeness

I certainly missed some bases or could’ve been more efficient, so it would be cool to hear other thoughts!