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 Find the critical path delay of a gate network given as a DAG.
mediumProcess 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.
pythonfrom 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)])) # 82 Detect a cycle in a directed graph with three-colour DFS.
mediumMark 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.
pythondef 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 Group pins into nets with union-find and return the size of the largest net.
mediumUnion 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.
pythondef 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)])) # 34 Route between two points on a grid with obstacles (Lee algorithm) and return the path.
hardLee 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.
pythonfrom 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 Implement a trie for hierarchical names with insert, search and prefix count.
mediumEach 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.
pythonclass 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 26 Simulate an AND-OR circuit on 64 test patterns at once using bit-parallel operations.
hardPack 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.
pythonMASK = (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)) # 0b10117 Merge overlapping timing windows (intervals).
mediumSort 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.
pythondef 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 Merge k sorted lists of event times with a heap.
mediumPush 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.
pythonimport 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 Evaluate a Boolean expression written in postfix (reverse Polish) notation.
mediumScan 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.
pythondef 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 110 Sort cells by slack ascending, breaking ties by name.
mediumUse 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.
pythoncells = [("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 Maintain the running median of a stream of values with two heaps.
hardKeep 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.
pythonimport 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 Count the number of nets connected to each cell from a list of (cell, net) pairs.
easyUse 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.
pythonfrom 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
- Synopsys Interview Questions and Answers for India R&D Software Roles
- Target Coding Round Questions
- Target Interview Questions with Answers
- TCS Coding Round Questions with Solutions
- TCS Interview Questions for Freshers
- Tech Mahindra Coding Round Questions with Solutions
- Tech Mahindra Interview Questions for Freshers
- Texas Instruments Coding Round Questions with Solutions
- Texas Instruments Interview Questions and Answers for India Embedded Roles
- Thoughtworks Coding Round Questions
- Thoughtworks Interview Questions with Answers
- Tiger Analytics Coding Round Questions