Autocoder

Synopsys Coding Round Questions with Solutions

Last updated 2026-11-19

Coding problems for EDA software roles often wear a chip-design costume over a standard algorithm: the longest path in a gate network, loops in a netlist, connected pins, a router on a grid. This page gives twelve practice problems in that style with complete runnable Python or C solutions, complexity and common mistakes.

They are practice problems in the style of topics such rounds are commonly reported to cover, not real papers. Read Synopsys interview questions for the concept side, and use how to crack a DSA coding round for general strategy.

How to approach them

Translate the story into a standard model first: gates are nodes, wires are edges, delays are weights. Then name the algorithm and its complexity before writing code. For inputs that could be millions of nodes, say which part of your solution would need an iterative version or compact arrays.

State what you do with a cycle, an empty graph or a disconnected node. Real netlists contain all three.

Hiring status

No sourced hiring facts for Synopsys are held on this site, so no dates, openings or packages are quoted. Use the company's own careers site.

Synopsys Coding Round Questions with Solutions: questions with worked answers

  1. 1

    Find the critical path delay of a gate network given as a DAG.

    medium

    Process nodes in topological order and set arrival[v] to the delay of v plus the largest arrival among its inputs. The answer is the largest arrival time. For gates A(2), B(3) feeding C(4), and C feeding D(1), the critical path is B, C, D with delay 8. Time O(V + E), space O(V). Common mistake: summing all delays or adding the delay of an input twice.

    python
    from collections import deque
    
    def critical_path(delay, edges):
        n = len(delay)
        g = [[] for _ in range(n)]
        indeg = [0] * n
        for u, v in edges:
            g[u].append(v); indeg[v] += 1
        arr = delay[:]
        q = deque(i for i in range(n) if indeg[i] == 0)
        seen = 0
        while q:
            u = q.popleft(); seen += 1
            for v in g[u]:
                arr[v] = max(arr[v], arr[u] + delay[v])
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)
        return max(arr) if seen == n else None   # None: combinational loop
    
    # 0=A(2) 1=B(3) 2=C(4) 3=D(1)
    print(critical_path([2, 3, 4, 1], [(0, 2), (1, 2), (2, 3)]))  # 8
  2. 2

    Detect a cycle in a directed graph with three-colour DFS.

    medium

    Mark nodes white, grey while on the DFS stack and black when finished. An edge to a grey node is a back edge and proves a cycle. Time O(V + E), space O(V). For the edges 0 to 1, 1 to 2, 2 to 0 there is a loop; removing the last edge removes it. Common mistake: using a single visited flag, which reports a cycle for a diamond shape where two paths reach the same node.

    python
    def has_cycle(n, edges):
        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
        color = [0] * n          # 0 white, 1 grey, 2 black
        def dfs(u):
            color[u] = 1
            for v in g[u]:
                if color[v] == 1 or (color[v] == 0 and dfs(v)):
                    return True
            color[u] = 2
            return False
        return any(color[i] == 0 and dfs(i) for i in range(n))
    
    print(has_cycle(3, [(0, 1), (1, 2), (2, 0)]), has_cycle(3, [(0, 1), (1, 2)]))  # True False
    print(has_cycle(4, [(0, 1), (0, 2), (1, 3), (2, 3)]))  # False (diamond)
  3. 3

    Group pins into nets with union-find and return the size of the largest net.

    medium

    Union the two pins of every connection, then count the members of each root. For 6 pins and connections (0,1), (1,2), (3,4) the nets are {0,1,2}, {3,4} and {5}, so the largest has size 3. With path compression and union by size, the time is nearly linear. Common mistake: counting sizes from the parent array without calling find for each pin.

    python
    def largest_net(n, links):
        p = list(range(n))
        def find(x):
            while p[x] != x:
                p[x] = p[p[x]]
                x = p[x]
            return x
        for a, b in links:
            p[find(a)] = find(b)
        from collections import Counter
        return max(Counter(find(i) for i in range(n)).values())
    
    print(largest_net(6, [(0, 1), (1, 2), (3, 4)]))  # 3
  4. 4

    Route between two points on a grid with obstacles (Lee algorithm) and return the path.

    hard

    Lee routing is BFS from the source, which labels each reachable cell with its distance, followed by a backtrace from the target to the source using the labels. BFS guarantees the first arrival is a shortest path in cells. For the sample the path length is 6 moves. Time O(R x C), space O(R x C). Common mistake: failing to store parents or labels, so only the length can be reported, not the path.

    python
    from collections import deque
    
    def route(grid, s, t):
        r, c = len(grid), len(grid[0])
        par = {s: None}
        q = deque([s])
        while q:
            u = q.popleft()
            if u == t:
                break
            for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                v = (u[0] + dx, u[1] + dy)
                if 0 <= v[0] < r and 0 <= v[1] < c and grid[v[0]][v[1]] == 0 and v not in par:
                    par[v] = u
                    q.append(v)
        if t not in par:
            return None
        path, u = [], t
        while u:
            path.append(u); u = par[u]
        return path[::-1]
    
    g = [[0, 0, 0, 0],
         [1, 1, 0, 1],
         [0, 0, 0, 0]]
    p = route(g, (0, 0), (2, 0))
    print(len(p) - 1, p)  # 6 [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 1), (2, 0)]
  5. 5

    Implement a trie for hierarchical names with insert, search and prefix count.

    medium

    Each node holds a dictionary from character to child plus a flag for the end of a word and a count of words passing through. Insert and search take O(L) for a name of length L, and counting words with a prefix is O(L) by reading the count at the prefix node. Space is O(total characters) in the worst case. Common mistake: returning true for a search of a prefix that was never inserted as a word.

    python
    class Trie:
        def __init__(self):
            self.root = {"n": 0, "end": False, "ch": {}}
        def insert(self, w):
            node = self.root
            for ch in w:
                node = node["ch"].setdefault(ch, {"n": 0, "end": False, "ch": {}})
                node["n"] += 1
            node["end"] = True
        def _find(self, s):
            node = self.root
            for ch in s:
                node = node["ch"].get(ch)
                if node is None:
                    return None
            return node
        def search(self, w):
            n = self._find(w)
            return bool(n and n["end"])
        def count_prefix(self, p):
            n = self._find(p)
            return n["n"] if n else 0
    
    t = Trie()
    for name in ["top/cpu/alu", "top/cpu/reg", "top/mem"]:
        t.insert(name)
    print(t.search("top/cpu"), t.search("top/mem"), t.count_prefix("top/cpu"))  # False True 2
  6. 6

    Simulate an AND-OR circuit on 64 test patterns at once using bit-parallel operations.

    hard

    Pack the values of one signal across 64 patterns into the bits of a 64-bit integer. A two-input AND gate on all 64 patterns is a single bitwise AND, an OR is a bitwise OR and an inverter is a XOR with all ones. For y = (a AND b) OR (NOT c) with the packed values below, one evaluation computes the whole truth table. Time O(gates) per 64 patterns. This is the idea behind bit-parallel fault and logic simulation. Common mistake: using Python's ~ on an unbounded integer without masking to 64 bits.

    python
    MASK = (1 << 64) - 1
    
    def circuit(a, b, c):
        return ((a & b) | (~c & MASK)) & MASK
    
    # first four patterns: (a,b,c) = (0,0,0) (1,0,0) (0,1,1) (1,1,1) in bits 0..3
    a, b, c = 0b1010, 0b1100, 0b1100
    y = circuit(a, b, c)
    print(bin(y & 0b1111))  # 0b1011
  7. 7

    Merge overlapping timing windows (intervals).

    medium

    Sort the intervals by start, then sweep: if the next interval starts at or before the end of the current one, extend the end; otherwise emit the current and start a new one. [(1,3), (2,6), (8,10), (9,12), (15,18)] becomes [(1,6), (8,12), (15,18)]. Time O(n log n), space O(n). Common mistake: not sorting first, or comparing against the start of the previous interval rather than the end of the merged one.

    python
    def merge(iv):
        iv = sorted(iv)
        out = [list(iv[0])]
        for s, e in iv[1:]:
            if s <= out[-1][1]:
                out[-1][1] = max(out[-1][1], e)
            else:
                out.append([s, e])
        return [tuple(x) for x in out]
    
    print(merge([(1, 3), (2, 6), (8, 10), (9, 12), (15, 18)]))  # [(1, 6), (8, 12), (15, 18)]
  8. 8

    Merge k sorted lists of event times with a heap.

    medium

    Push the first element of each list with its list and position into a min-heap; repeatedly pop the smallest, append it and push the next element from the same list. Time O(N log k) for N total items, space O(k). For [1,4,7], [2,5], [3,6,9] the result is 1 through 7 and 9 in order. Common mistake: pushing every element at once, which costs O(N) memory and O(N log N) time.

    python
    import heapq
    
    def merge_k(lists):
        h = [(l[0], i, 0) for i, l in enumerate(lists) if l]
        heapq.heapify(h)
        out = []
        while h:
            v, i, j = heapq.heappop(h)
            out.append(v)
            if j + 1 < len(lists[i]):
                heapq.heappush(h, (lists[i][j + 1], i, j + 1))
        return out
    
    print(merge_k([[1, 4, 7], [2, 5], [3, 6, 9]]))  # [1, 2, 3, 4, 5, 6, 7, 9]
  9. 9

    Evaluate a Boolean expression written in postfix (reverse Polish) notation.

    medium

    Scan tokens; push operands, and on an operator pop one value for NOT or two for AND, OR and XOR, apply it and push the result. The result is the single value left on the stack. "1 0 AND 1 OR" evaluates to 1, and "1 1 XOR NOT" to 1. Time O(n), space O(n). Common mistake: popping operands in the wrong order, which matters for non-commutative operators such as implication.

    python
    def eval_rpn(tokens):
        st = []
        for t in tokens.split():
            if t in ("0", "1"):
                st.append(int(t))
            elif t == "NOT":
                st.append(1 - st.pop())
            else:
                b, a = st.pop(), st.pop()
                st.append({"AND": a & b, "OR": a | b, "XOR": a ^ b}[t])
        return st[0]
    
    print(eval_rpn("1 0 AND 1 OR"), eval_rpn("1 1 XOR NOT"))  # 1 1
  10. 10

    Sort cells by slack ascending, breaking ties by name.

    medium

    Use a compound sort key (slack, name). With cells [("u3", 0.2), ("u1", -0.1), ("u2", 0.2)] the order is u1, u2, u3: the negative slack comes first, and the tie between u3 and u2 is resolved alphabetically. Time O(n log n), space O(n). Common mistake: sorting by name then by slack with an unstable algorithm, or sorting on a string when the slack is a number.

    python
    cells = [("u3", 0.2), ("u1", -0.1), ("u2", 0.2)]
    order = sorted(cells, key=lambda c: (c[1], c[0]))
    print([n for n, _ in order])  # ['u1', 'u2', 'u3']
  11. 11

    Maintain the running median of a stream of values with two heaps.

    hard

    Keep a max-heap for the lower half and a min-heap for the upper half, with sizes differing by at most one. Insert into one heap, rebalance, and read the median from the tops. For 5, 15, 1, 3 the medians are 5, 10, 5, 4. Time O(log n) per insert, O(1) per query. Common mistake: forgetting that Python's heapq is a min-heap, so the lower half stores negated values.

    python
    import heapq
    
    class Median:
        def __init__(self):
            self.lo, self.hi = [], []          # lo is a max-heap via negation
        def add(self, x):
            heapq.heappush(self.lo, -x)
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
            if len(self.hi) > len(self.lo):
                heapq.heappush(self.lo, -heapq.heappop(self.hi))
        def median(self):
            if len(self.lo) > len(self.hi):
                return float(-self.lo[0])
            return (-self.lo[0] + self.hi[0]) / 2
    
    m = Median()
    out = []
    for x in [5, 15, 1, 3]:
        m.add(x); out.append(m.median())
    print(out)  # [5.0, 10.0, 5.0, 4.0]
  12. 12

    Count the number of nets connected to each cell from a list of (cell, net) pairs.

    easy

    Use a dictionary of sets: for each pair add the net to the cell's set, then report the size of each set. Duplicate pairs must not be counted twice, which is why a set is used. For [("u1","n1"), ("u1","n2"), ("u2","n1"), ("u1","n1")] the result is u1 with 2 and u2 with 1. Time O(n), space O(n). Common mistake: using a list and counting duplicates.

    python
    from collections import defaultdict
    
    def fanout(pairs):
        d = defaultdict(set)
        for cell, net in pairs:
            d[cell].add(net)
        return {k: len(v) for k, v in sorted(d.items())}
    
    print(fanout([("u1", "n1"), ("u1", "n2"), ("u2", "n1"), ("u1", "n1")]))  # {'u1': 2, 'u2': 1}

Frequently asked questions

What kind of coding problems do EDA companies ask?

Commonly reported are graph algorithms, trees and tries, heaps, intervals, strings and bit manipulation in C++ or another language, plus questions on scaling to large inputs.

Should I use C++ or Python?

Use C++ if the role or test asks for it, as EDA tools are typically written in C++. Python is fine when the platform allows and you know it better.

Are these real Synopsys problems?

No. They are practice problems in the style of topics such rounds are commonly reported to cover. The company does not publish its papers.

How do I prepare for scaling questions?

Practise stating the memory and time of your solution for 10^6 and 10^8 items, and know what you would change, such as iterative instead of recursive search and arrays instead of objects.

Related guides

More in Company Interview Questions

See all in this section