Page tree
Skip to end of metadata
Go to start of metadata

1.

Minimum Swaps 2
def swap(arr, a, b):
    arr[a], arr[b] = arr[b], arr[a]
    return arr

def minimumSwaps(arr):
    idx = 0
    arr_len = len(arr)
    swap_cnt = 0
    while idx < arr_len:
        if arr[idx] == arr[arr[idx] - 1]:
            idx += 1
            continue
        swap(arr, idx, arr[idx] - 1)
        idx += 1
        swap_cnt += 1
        idx -= 1
    return swap_cnt


2. 

Sherlock and Anagrams
def cal_comb(n, r):
    return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))


def sorted_str(s):
    return ''.join(sorted(s))


def sherlockAndAnagrams(s):
    dic = {}
    str_len = len(s)
    for ngram_size in range(1, str_len):
        for start in range(0, str_len + 1 - ngram_size):
            ngram = s[start:start + ngram_size]
            ngram = sorted_str(ngram)
            if ngram not in dic:
                dic[ngram] = 1
            else:
                dic[ngram] += 1

    total = 0
    for key in dic:
        n = dic[key]
        if n >= 2:
            total += cal_comb(n, 2)

    return total

3.

Queues: A Tale of Two Stacks
class MyQueue(object):
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def __move(self):
        self.stack2 = list(reversed(self.stack1))
        self.stack1 = []

    def peek(self):
        if not self.stack2:
            self.__move()
        return self.stack2[-1]

    def pop(self):
        if not self.stack2:
            self.__move()
        return self.stack2.pop()

    def put(self, value):
        self.stack1.append(value)
  • No labels