DSA & Algorithms · Full Mock 1

1
2
3
4
5
6
7
8
9
10
11

def rev(a, i, j):
    while i < j:
        a[i], a[j] = a[j], a[i]
        i, j = i + 1, j - 1

a = [1, 2, 3, 4, 5, 6, 7]
k = 2
rev(a, 0, k - 1)
rev(a, k, len(a) - 1)
rev(a, 0, len(a) - 1)
print(*a)

1
2
3
4
5
6
7
8
9
10
11

calls = 0

def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

fib(5)
print(calls)

1
2
3
4
5
6
7
8
9
10

def min_coins(coins, amount):
    INF = float('inf')
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                ____________
    return dp[amount] if dp[amount] != INF else -1

print(min_coins([5, 2, 1], 11), min_coins([2], 3))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

from collections import deque

def bipartite(adj):
    color = {}
    for s in adj:
        if s in color:
            continue
        color[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if v not in color:
                    color[v] = 1 - color[u]; q.append(v)
                elif color[v] == color[u]:
                    return False
    return True

g1 = {'A': 'BD', 'B': 'ACE', 'C': 'BF', 'D': 'AE', 'E': 'BDF', 'F': 'CE'}
tri = {'X': 'YZ', 'Y': 'XZ', 'Z': 'XY'}
print(bipartite(g1), bipartite(tri))

1
2

x = 40
print(x & -x, x & (x - 1), x | (x - 1))

1
2
3
4
5
6
7
8
9
10

def has_zero_sum(a):
    seen, s = {0}, 0
    for x in a:
        s += x
        if s in seen:
            return True
        seen.add(s)
    return False

print(has_zero_sum([4, 2, -3, 1, 6]), has_zero_sum([1, 2, 3]))

1
2
3
4
5
6
7

d = {}
d['b'] = 1
d['a'] = 2
d['b'] = 3
del d['a']
d['a'] = 4
print(list(d.items()))

1
2
3
4
5

import heapq

h = [5, 3, 8, 1]
heapq.heapify(h)
print(h[0], h)

1
2
3
4
5
6

import heapq
from collections import Counter

nums = [1, 1, 1, 2, 2, 3, 4, 4, 4, 4]
c = Counter(nums)
print(heapq.nlargest(2, c, key=c.get))

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
29
30

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

def build(vals):
    head = None
    for v in reversed(vals):
        head = Node(v, head)
    return head

def show(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    print(*out)

def merge(a, b):
    dummy = tail = Node(0)
    while a and b:
        if a.val <= b.val:
            tail.next, a = a, a.next
        else:
            tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

show(merge(build([1, 4, 9]), build([2, 3, 10, 11])))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

from collections import OrderedDict

class LRU:
    def __init__(self, cap):
        self.cap, self.d = cap, OrderedDict()

    def get(self, k):
        if k not in self.d:
            return -1
        self.d.move_to_end(k)
        return self.d[k]

    def put(self, k, v):
        self.d[k] = v
        self.d.move_to_end(k)
        if len(self.d) > self.cap:
            self.d.popitem(last=False)

c = LRU(2)
c.put(1, 10)
c.put(2, 20)
r1 = c.get(1)
c.put(3, 30)
print(r1, c.get(2), c.get(3), c.get(1))

1
2
3
4
5
6
7
8
9
10
11
12

#include <iostream>

void f(int n) {
    if (n == 0) return;
    f(n - 1);
    std::cout << n << ' ';
}

int main() {
    f(3);
    std::cout << '\n';
}

1
2
3
4
5
6
7

s = []
for ch in "code":
    s.append(ch)
out = ""
while s:
    out += s.pop()
print(out)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def naive(n):
    if n is None:
        return True
    if n.left and n.left.val >= n.val:
        return False
    if n.right and n.right.val <= n.val:
        return False
    return naive(n.left) and naive(n.right)

def valid(n, lo=float('-inf'), hi=float('inf')):
    if n is None:
        return True
    if not lo < n.val < hi:
        return False
    return valid(n.left, lo, n.val) and valid(n.right, n.val, hi)

root = Node(10, Node(5), Node(15, Node(6), Node(20)))
print(naive(root), valid(root))

1
2
3
4
5
6

for (int i = 0; i < n; i++) {
    sumA += a[i];
}
for (int j = 0; j < m; j++) {
    sumB += b[j];
}

1
2
3
4
5
6
7

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)