CareerCup

Knuth shuffle then order by original list. O(n + len(L))

import random
from copy import copy

def random_subset(original_list, n):
  L = copy(original_list)
  // Differentiate items which have the same value by adding a second "count" int
  for i, val in enumerate(L):
    if i == 0:
      L[i] = (val, 1)
    else:
      prev_val, prev_count = L[i-1]
      L[i] = (val, prev_count + 1) if val == prev_val else (val, 1)

  // Hash each value to its index, so that we maintain the order at the end
  val2i = {val: i for i, val in enumerate(L)}

  // Choose items randomly, and move them to the end of the list so they don't get chosen twice.
  for i in range(n):
    rand_i = random.randint(0, len(L)-1-i)
    L[rand_i], L[len(L)-1-i] = L[len(L)-1-i], L[rand_i]

  // bucket sort the randomly selected items, now at the end of our list
  bucket = [False] * len(L)
  for val in L[len(L)-n:]:
    bucket[val2i[val]] = True
  subset = []
  for i, inSubset in enumerate(bucket):
    if inSubset:
      subset.append(original_list[i])
  return subset

The numbers don't all have an equal chance of getting in the subset.

O(n + k log(n)) where k = 10

import heapq

def find_top_k(L, k):
  heap = []
  dictionary = {}
  for video, rate in L:
    if video in dictionary:
      dictionary[video] += rate
    else:
      dictionary[video] = rate
  for video, rate in dictionary.items():
    heapq.heappush(heap, (-rate, video))
  result = []
  for _ in range(min(k, len(dictionary))):
    rate, video = heapq.heappop(heap)
    result.append(video)
  return result

Hash map all pairs of horizontal segments with overlapping ranges by the distance between them. for example {5: [((10, 20, 4, H), (19, 21, 9, H))]}. This is O(n^2)

For all pairs of vertical segments with overlapping ranges, get the distance between them, look up this distance in the hash map, and for each pair of horizontal segments found there (if any), check if the intersect the vertical pair to form a square. O(n^2) generally, worst case O(n^3) when all segments are the same range and equidistant.

If you want the output in the same string format as the input:

def sort_giant_string(giant, col, col_type=(str, str, int)):
  data = [row.split(" ") for row in giant.split("\n")]
  data.sort(key=lambda x: col_type[col - 1](x[col - 1]))
  return "\n".join([" ".join([str(cell) for cell in row]) for row in data])

O(n):

def count_different(input):
    if not input:
        return 0
    front = back = max_length = this_length = 0
    running_set = set()
    while front < len(input):
        if input[front] in running_set:
            while True:
                back += 1
                max_length = max(max_length, this_length)
                running_set.remove(input[back - 1])
                this_length -= 1
                if input[back - 1] == input[front]:
                    break
        running_set.add(input[front])
        this_length += 1
        front += 1
    return max(this_length, max_length)

def unique_words(s):
    uniques = defaultdict(int)
    word = []
    for c in s:
        if c == ' ':
            uniques["".join(word)] += 1
            word = []
        else:
            word.append(c)
    uniques["".join(word)] += 1
    return len([u for u in uniques if u and uniques[u] == 1])