Algorithm - Interview

Google

Google 暑期实习电话面算法题。

Phone Interview

Compare keyboard events sequences

1
2
# abc123\b123\b  -> abc1212
# abc1212        -> abc1212

Time O(n), Space O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def convert(s):
    res = []
    index = 0
    for i in range(len(s)):
        # abc12123
        if s[i] != '\b':
            if len(res) == index:
                res.append(s[i])
            else:
                res[index] = s[i]
            index += 1
        else:
            if index == 0:
                continue
            else:
                index -= 1
        return ''.join(res[:index])

def compare(s1, s2):
    return convert(s1) == convert(s2)

Time O(n), Space O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def get_char(s, p):
    cnt = 0
    while p >= 0 and (cnt > 0 or s[p] == '\b'):
        if s[p] == '\b':
            cnt += 1
        else:
            cnt -= 1
        p -= 1
    return p

def compare_(s1, s2):
        p1 = len(s1) - 1
        p2 = len(s2) - 1
        
        while p1 >= 0 and p2 >= 0:
            p1 = get_char(s1, p1)
            p2 = get_char(s2, p2)

            if p1 >= 0 and p2 >= 0:
                if s1[p1] != s2[p2]:
                    return False
                else:
                    p1 -= 1
                    p2 -= 1

        p1 = get_char(s1, p1)
        p2 = get_char(s2, p2)
        return p1 < 0 and p2 < 0
  • 能抽象就抽象。多写几个函数。

Test Case

1
2
3
4
5
6
assert(compare_('', '2\b') == True)
assert(compare_('', '12\b') == False)
assert(compare_('1', '12\b') == True)
assert(compare_('', '\b2\b') == True)
assert(compare_('', '12\b2\b') == False)
assert(compare_('1', '123\b2\b\b') == True)