CCI moderate, hard

16.1 Number Swapper

16.2 Word Frequencies : Design a method to find the frequency of occurences of any given word in a book.  What if we were running this algorithm multiple times?

-kmp

def getPi(p):
    m = len(p)
    j = 0
    pi = [0 for _ in range(m)]
    for i in range(1, m):
        while  j>0 and p[i] != p[j]:
            j = pi[j - 1]
        if(p[i] == p[j]):
            j += 1
            pi[i] = j
    print(pi)
    return pi
 
def kmp(s, p):
    ans = []
    pi = getPi(p)
 
    n = len(s)
    m = len(p)
    j = 0
 
    for i in range(0, n):
        while j > 0 and s[i] != p[j]:
            j = pi[j - 1]
        if s[i] == p[j]:
            if j == m - 1:
                ans.append(i-m+1)
                j = pi[j]
            else:
                j += 1
    return ans
 
print(kmp("ABABABABBABABABABC", "ABABABABC"))
 

16.3 Intersection: Given two straight line segments (represented as a start point and an end point), compute the point of intersection, if any.

16.4 Tic Tac Win: Design an algorithm to figure out if someone has won a game of tic-tac-toe.

class TIcTacToe:
    def __init__(self):
        self.board = [[None for _ in range(3)] for _ in range(3)]
        self.type = ["black", "white"]
 
    def putStone(self, type, x, y):
        if self.board[x][y] == None:
            self.board[x][y] = self.type[type]
            self.showBoard()
            if self.checkResult(x, y):
                print("complete : ", self.type[type])
                return True
            else:
 
                return False
        else:
            return False
 
    def showBoard(self):
        for line in self.board:
            print(line)
        print()
 
    def checkResult(self, x, y):
        if self.isLeftRight(x, y) or self.isTopBottom(x, y) or self.isDiagonal(x, y):
            return True
        else:
            return False
 
    def isLeftRight(self, x, y):
        if y == 1:
            if self.board[x][y - 1] != None and self.board[x][y + 1]:
                return True
        elif y == 2:
            if self.board[x][y - 1] != None and self.board[x][y - 2]:
                return True
        elif y == 0:
            if self.board[x][y + 1] != None and self.board[x][y + 2]:
                return True
 
        return False
 
    def isTopBottom(self, x, y):
        if x == 1:
            if self.board[x - 1][y] != None and self.board[x + 1][y]:
                return True
        elif x == 2:
            print(x, y)
            if self.board[x - 1][y] != None and self.board[x - 2][y]:
                return True
        elif x == 0:
            if self.board[x + 1][y] != None and self.board[x + 2][y]:
                return True
        return False
 
    def isDiagonal(self, x, y):
        if x == 1 and y == 1:
            if self.board[x - 1][y - 1] != None and self.board[x + 1][y + 1] != None:
                return True
            elif self.board[x + 1][y - 1] != None and self.board[x - 1][y + 1] != None:
                return True
 
        elif x == 0 and y == 0:
            if self.board[x + 1][y + 1] != None and self.board[x + 2][y + 2] != None:
                return True
 
        elif x == 0 and y == 2:
            if self.board[x + 1][y - 1] != None and self.board[x + 2][y - 2] != None:
                return True
 
        elif x == 2 and y == 2:
            if self.board[x - 1][y - 1] != None and self.board[x - 2][y - 2] != None:
                return True
 
        elif x == 2 and y == 0:
            if self.board[x - 1][y + 1] != None and self.board[x - 2][y + 2] != None:
                return True
        else:
            return True
 
        return False
 
ttt = TIcTacToe()
ttt.putStone(0, 1, 1)
ttt.putStone(1, 1, 2)
ttt.putStone(0, 2, 1)
ttt.putStone(1, 0, 2)
ttt.putStone(0, 0, 0)
ttt.putStone(1, 2, 2)

16.5 Factorial Zeros: Write an algorithm which computes the number of trailing zeros in n factorial.

trailing zero 개념

trailing zeros

 n factorial에 몇 개의 0이 뒤에 붙는지를 묻는 문제.

def factorialZero(num):
    result = 0
 
    while num > 0:
        num = int(num / 5)
        result += num
    return result
 
print(factorialZero(100))

16.6 Smallest Difference: Given two arrays of integers, compute the pair of values (one value in each array) with the smallest (non-negative) difference.  Return the difference.

Example

Input : {1, 3, 15, 11, 2}, {23, 127, 235, 19, 8}

Output : 3. That is, the pair {11, 8}

A = [1,3,15,11,2]
B = [23, 127, 235, 19, 8]
 
def quickSort(l, left, right):
    i = left
    j = right
    pivot = l[int((left + right) / 2)]
    while i <= j:
        while pivot > l[i]:
            i += 1
        while pivot < l[j]:
            j -= 1
        if i <= j:
            l[i], l[j] = l[j], l[i]
            i += 1
            j -= 1
    if left < j:
        quickSort(l, left, j)
    if right > i:
        quickSort(l, i, right)
 
def smallestDifference(AList, BList):
    quickSort(AList, 0, len(AList) - 1)
    quickSort(BList, 0, len(BList) - 1)
    print(AList)
    print(BList)
 
    i = 0
    j = 0
    minVal = None
    while i < len(AList) and j < len(BList):
        buf = AList[i] - BList[j]
 
        if buf < 0:
            i += 1
        elif buf > 0:
            j += 1
        elif buf == 0:
            return 0
 
        buf = abs(buf)
        
        if minVal == None:
            minVal = buf
        elif minVal > buf:
            minVal = buf
            
    return minVal
 
print(smallestDifference(A, B))
 

16.7 Number Max: Write a method that finds the maximum of two numbers.  You should not use if-else or any other comparison operator.

bit manipulation in C

def flip(bit):
    return 1^bit
 
def sign(a):
    return flip((a >> 31) & 0x1)
 
def getMaxNaive(a, b): # 20, -10
    c = a - b
 
    sa = sign(a) # 1
    sb = sign(b) # 0
    sc = sign(c) # 1
 
    use_sign_of_a = sa ^ sb # 1
    use_sign_of_c = flip(sa ^ sb) # 0
 
    k = use_sign_of_a * sa + use_sign_of_c * sc # 1 * 1 + 0 * 1 == 1
    q = flip(k) # 0
 
    return a* k + b * q
 
print(getMaxNaive(20, 10))

#include <stdio.h>
#include <math.h>
 
int flip(int k){
    return k ^ 1;
}
 
int sign(int k){
    return flip((k >> 31) & 1);
}
 
int getMaxNaive(int a, int b){
    int c = a - b;
    int sa = sign(a);
    int sb = sign(b);
    int sc = sign(c);
    
    int sign_of_a = sa ^ sb;
    int sign_of_c = flip(sa ^ sb);
    
    int k = sign_of_a * sa + sign_of_c * sc;
    int q = flip(k);
 
    return k * a + q * b;
}
 
int main(){
    int a = -125;
    int b = 20;
    printf("%d\n", (a>>31) & 1);
    printf("%d", getMaxNaive(a, b));
    return 0;
}

16.8 English Int : Given any integer, print an English phrase that describes the integer (e.g., "One Thousand, Two Hundred Thirty Four").

pos1 = ["one", "two", "three", "four",
        "five", "six", "seven", "eight", "nine"]
pos2 = ["eleven", "twelve", "thirteen",
        "fourteen", "fifteen", "sixteen",
        "seventeen", "eighteen", "nineteen"]
pos10 = ["ten", "twenty", "thirty", "fourty", "fifty", "sixty", "seventy", "eighty", "ninety"]
posMore10 = ["hundred", "thousand", "million", "billion", "trillion", "zillion"]
 
def englishInt(intVal):
    result = ''
    level = 0
    p1 = intVal % 10
    p2 = int((intVal % 100 - p1) / 10)
 
    if p1 == 0:
        if p2 != 0:
            result = pos10[p2 - 1]
    elif p1 != 0:
        if p2 == 1:
            result = pos2[p1 - 1]
        elif p2 == 0:
            result = pos1[p1 - 1]
        else:
            result = pos10[p2 - 1] + ' ' + pos1[p1 - 1]
    intVal = int(intVal / 100)
    while intVal != 0:
        p1 = intVal % 10
        if p1 != 0:
            result = pos1[p1 - 1] + ' ' + posMore10[level] + ' ' + result
        level += 1
        intVal = int(intVal / 10)
    return result
 
 
testCase = [1005, 1123, 5812, 80000]
for el in testCase:
    print(englishInt(el))

16.9 Operations: Write methods to implement the multiply, subtract, and divide operations for integers.  The results of all of these are integers.  Use only the add operator.

16.10 Living People: Given a list of people with their birth and death years, implement a method to compute the year with the most number of people alive.  You may assume that all people were born between 1900 and 2000(inclusive).  If a person was alive during any portion of that year, they should be included in that year's count.  For example, Person(birth = 1907, death = 1909) is included in the counts for both 1908 and 1909.

class Person:
    def __init__(self, birth, death):
        self.birth = birth
        self.death = death
 
def mostNumberOfAllOfPerson(persons):
    mostAlive = 0
    for person in persons:
        aliveTime = person.death - person.birth - 1
        if mostAlive < aliveTime:
            mostAlive = aliveTime
    return mostAlive
 
import random
persons = []
for i in range(100):
    persons.append(Person(random.randint(1900, 1980), random.randint(1980, 2080)))
print(mostNumberOfAllOfPerson(persons))