A. Most Frequent Number Following Key In an Array (opens new window)

Count the occurence of each element.

DETAILS

def mostFrequent(self, A: List[int], key: int) -> int:
        freq = collections.defaultdict(int)
        n = len(A)
        for i in range(1, n):
            if A[i - 1] == key:
                freq[A[i]] += 1
        c = max(freq.values())
        ans = 0
        print(freq)
        for x in list(freq.keys()):
            if freq[x] == c:
                ans = max(ans, x)
        return ans

B. Sort the Jumbled Numbers (opens new window)

Map integer to string using the given dictionary. Sort by:

• The value after mapping
• The original order in A.

DETAILS

def sortJumbled(self, mapping: List[int], A: List[int]) -> List[int]:
        nums = [list(map(int, list(str(x)))) for x in A]
        for num in nums:
            for i in range(len(num)):
                num[i] = mapping[num[i]]
        res = [int("".join(list(map(str, x)))) for x in nums]
        tmp = list(zip(res, list(range(len(A))), A))
        tmp.sort(key = lambda x: [x[0], x[1]])
        return [x[2] for x in tmp]

C. All Ancestors of a Node in a Directed Acyclic Graph (opens new window)

BFS, start from nodes of 0 indegree.

DETAILS

def getAncestors(self, n: int, A: List[List[int]]) -> List[List[int]]:
        parent, child = collections.defaultdict(set), collections.defaultdict(list)
        ans, indegree, dq = [], [0] * n, collections.deque()
        for a, b in A:
            parent[b].add(a)
            child[a].append(b)
            indegree[b] += 1
        for i in range(n):
            if indegree[i] == 0: dq.append(i)
        while dq:
            curr = dq.popleft()
            for nxt in child[curr]:
                parent[nxt] |= parent[curr]
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    dq.append(nxt)
        for i in range(n):
            ans.append(sorted(list(parent[i])))
        return ans

D. Minimum Number of Moves to Make Palindrome (opens new window)

Greedy.

DETAILS

def minMovesToMakePalindrome(self, s: str) -> int:
        n, s = len(s), list(s)
        l, r, ans = 0, n - 1, 0
        while r > l:
            if s[l] != s[r]:
                kk = r
                while kk > l and s[kk] != s[l]:
                    kk -= 1
                if kk == l:
                    s[l], s[l + 1] = s[l + 1], s[l]
                    ans += 1
                else:
                    while kk < r:
                        s[kk], s[kk + 1] = s[kk + 1], s[kk]
                        ans += 1
                        kk += 1
                    l += 1
                    r -= 1
            else:
                l += 1
                r -= 1
        return ans

func minMovesToMakePalindrome(s string) int {
    n := len(s)
    tmp := []rune(s)
    l, r, ans := 0, n - 1, 0
    for r > l {
        if tmp[l] != tmp[r] {
            kk := r
            for kk > l && tmp[kk] != tmp[l] {
                kk -= 1
            }
            if kk == l {
                tmp[l], tmp[l + 1] = tmp[l + 1], tmp[l]
                ans += 1
            } else {
                for kk < r {
                    tmp[kk], tmp[kk + 1] = tmp[kk + 1], tmp[kk]
                    ans += 1
                    kk += 1
                }
                l += 1
                r -= 1
            }
        } else {
            l += 1
            r -= 1
        }
    }
    return ans
    return 1
}

public:
    int minMovesToMakePalindrome(string s) {
        int s_size = s.size();
        int result = 0;
        int start = 0, end = s_size - 1;
        while (end > start) {
            if (s[start] != s[end]) {
                int i = end; 
                while (i > start && s[i] != s[start]) { 
                    i -= 1; 
                }
                if (i == start) {
                    swap(s[start], s[start + 1]);
                    result += 1;
                }
                else {
                    while (i < end) {
                        swap(s[i], s[i + 1]);
                        result += 1;
                        i += 1;
                    }
                    start += 1; 
                    end -= 1;
                }
            }
            else {
                start += 1; 
                end -= 1;
            }
        }
        return result;
    }