109 questions from 8 interviews · updated from reports 2015-2021
About
Mentor Graphics, now part of Siemens EDA, makes electronic design automation software for chip and electronic system design. In India, it hires software engineers, software developers, and Senior Member Technical Staff for EDA tools, verification, and product development.
The roles that come up most are Software Engineer, Software Developer and Senior MTS. This covers 8 candidate interviews reported from 2015 to 2021. Most sat it at entry level (5 of 8 that recorded a level). Among the 4 that recorded either route, arrivals split between campus drives (3, 75%) and off-campus applications (1, 25%). Most questions fall under DSA and CS fundamentals.
Ans. Object-oriented programming organises software as objects that combine data and behaviour. A class is a blueprint, and an object is its instance. Encapsulation hides internal state behind methods. Abstraction exposes only essential details. Inheritance reuses and extends behaviour. Polymorphism lets the same interface work with different implementations.
Ans. Break the block into 1, 3, 9 and 27 unit pieces. With a balance scale, each piece can go on the same pan, the opposite pan, or be unused. That gives balanced ternary combinations, covering every whole weight from 1 to 40, since 1 plus 3 plus 9 plus 27 equals 40.
Ans. Reverse each block of K nodes by iterating through the list, reversing K links at a time, and connecting the previous block’s tail to the new head. Use three pointers for reversal and keep track of the previous group tail. If fewer than K nodes remain, usually leave them unchanged. Time is O(n), space is O(1).
Ans. A binary tree is symmetric if its left and right subtrees are mirror images. Compare pairs of nodes: left child of one with right child of the other, and right child with left. If both are null they match, if one is null or values differ they fail. Time is O(n), space is O(h) recursively.
Ans. Use a postorder traversal to verify that every non-leaf node equals the sum of values in its left and right subtrees. For each node, return both whether its subtree is valid and the subtree sum. A null node has sum 0, and a leaf is valid. Time is O(n), with O(h) recursion space.
Ans. Use recursion to explore one path fully before backtracking, marking each node or cell as visited to avoid cycles. For graphs, store neighbours in an adjacency list; for grids, try four or eight directions. The time complexity is usually O(V + E) for graphs or O(rows × columns) for grids.
Ans. Reverse the linked list by swapping every pair of adjacent nodes. Use a dummy node before the head, then repeatedly adjust pointers for prev, first and second nodes in each pair. Move prev forward after each swap. If one node remains at the end, leave it unchanged. Time is O(n), space is O(1).
Ans. BST search compares the target with the current node, moves left if smaller, right if larger, and stops when found or null, taking O(h) time. A BST Iterator usually simulates inorder traversal using a stack of left nodes, giving sorted values with next in O(1) amortised time and O(h) space.
Ans. Do a depth first traversal, keeping the current path from the root to the current node. Add each visited node to a list; when you reach a leaf, print the list. After returning from a child, remove the node to backtrack. Time is O(n), excluding output size, and space is O(h).
Ans. Reverse each group of k nodes by iterating through the list and reversing pointers within the current group, then connect the previous group’s tail to the new head. Use only node pointers, not an extra data structure. If fewer than k nodes remain, usually leave them unchanged. Time complexity is O(n), space is O(1).
Ans. Traverse the matrix by maintaining four boundaries: top, bottom, left, and right, and repeatedly visit the top row, right column, bottom row, and left column in order. After each side, move that boundary inward. Stop when boundaries cross. Use a result list. Time complexity is O(mn), space is O(1) excluding output.
Ans. Reverse each block of k nodes by rewiring next pointers, then connect the previous block’s tail to the new head of the reversed block. Use three pointers to reverse a block in place, and first check that k nodes remain if partial groups should stay unchanged. Time complexity is O(n), space complexity is O(1).
Ans. Use BFS while assigning each node a column index, with root at 0, left child at column minus 1 and right child at column plus 1. Store values in a map from column to list. Finally output lists from smallest to largest column. Time is O(n log n) with an ordered map.
Ans. Use binary search to find the point where the sorted order restarts. Keep two pointers, left and right, and compare the middle value with the right value. If middle is greater, the minimum is to the right; otherwise it is at middle or to the left. This uses no extra data structure and runs in O(log n).
Ans. Use five 4:1 multiplexers. Connect the 16 inputs into four groups of four, each feeding one first-stage 4:1 multiplexer controlled by the two least significant select lines. Feed those four outputs into a fifth 4:1 multiplexer controlled by the two most significant select lines.
Ans. Topological sorting orders the vertices of a directed acyclic graph so every edge u to v places u before v. Implement it with Kahn’s algorithm: store adjacency lists and an indegree array, push all zero-indegree vertices into a queue, remove them, and reduce neighbours’ indegrees. If not all vertices are output, a cycle exists. Time is O(V + E).
Ans. Use an explicit stack to simulate an inorder traversal, so the iterator returns BST values in sorted order. Initialise by pushing the root and all its left children. next pops the top node, then pushes the left path of its right child. hasNext checks the stack. Space is O(h), next is amortised O(1).
Ans. Do an inorder traversal of the BST and return the node visited kth, because inorder visits keys in sorted ascending order. Use a recursive counter or an explicit stack, stopping as soon as the kth node is reached. The time complexity is O(h + k), and the space complexity is O(h).
Ans. Use exponentiation by squaring. Keep a result initially 1, repeatedly square x and halve n; when the current exponent bit is odd, multiply the result by x. For negative n, compute using the absolute exponent and return its reciprocal. This runs in O(log |n|) time and O(1) space.
Ans. For a directed graph, I would usually check strong connectivity by running DFS or BFS from any vertex, then doing the same on the graph with all edges reversed. If every vertex is reached in both traversals, the graph is strongly connected. This takes O(V + E) time.
Ans. Virtual functions in C++ are member functions declared with virtual so calls are resolved at runtime based on the actual object type, enabling polymorphism. A virtual destructor ensures the derived destructor runs when deleting an object through a base-class pointer. Base classes meant for polymorphic use should almost always have a virtual destructor.
Ans. Use DFS: for a directed graph, track visited nodes and a recursion stack; reaching a node already in the current stack means a cycle. For an undirected graph, track visited nodes and the parent; reaching a visited neighbour that is not the parent means a cycle. Time complexity is O(V + E).
Ans. Use depth first search with backtracking from the root, keeping a current path list. Add the current node, and if it has no children, copy the path into the result. Otherwise recurse on each child, then remove the node when returning. Time complexity is O(total path output size), with O(height) extra recursion space.
Ans. KMP finds all occurrences of a pattern in a text in linear time by avoiding repeated comparisons after a mismatch. It first builds an LPS table, which stores the longest proper prefix that is also a suffix for each pattern prefix. During matching, it uses this table to shift the pattern without moving the text pointer backwards.
Ans. Use the orientation test with cross products to decide whether two line segments intersect. For segments AB and CD, they intersect if A and B are on different sides of CD and C and D are on different sides of AB, including collinear overlap cases. This runs in constant time, O(1).
Ans. Choose any two vertical grid lines and any two horizontal grid lines. A chessboard has 9 lines each way, so the number of rectangles is C(9,2) × C(9,2) = 36 × 36 = 1296. This includes squares. The squares alone are 1² + 2² + … + 8² = 204.
Ans. Represent the board as a 3 by 3 array and choose moves using minimax, because Tic-Tac-Toe has a small complete game tree. The system should validate moves, detect wins or draws, generate legal moves, score terminal states as win, loss or draw, and pick the move with the best guaranteed outcome.
Ans. Yes, a function can run before main() during static initialisation. Common ways are calling it in the initialiser of a global or namespace-scope variable, or from the constructor of a global object. Some compilers also provide extensions such as constructor attributes, but those are not standard C++.
Ans. Re-solve each coding question by first clarifying input limits, expected output, and invalid or empty inputs. Then choose the simplest correct approach, state the data structure, and check boundary cases such as zero size, one element, duplicates, negatives, maximum values, sorted input, and all equal values. Finally, give time and space complexity.
Ans. Start with the simplest correct approach, usually brute force, and state its cost. Then show what repeated work it does and how a better data structure or algorithm removes it. The optimal approach is the one that matches the lower bound, such as visiting each input item once, giving O(n) when every item must be inspected.
Ans. Templates in C++ let you write generic functions or classes where the type is supplied later, allowing the same code to work with different data types. A generic class is declared by placing a template parameter list before the class, typically using template, angle brackets, typename or class, then the class definition.
Ans. Traverse the tree in preorder and print a child whenever its parent has exactly one child. For each node, if only the left child exists, print the left child; if only the right child exists, print the right child. Then recurse left and right. The BST property is irrelevant. Time is O(n), stack is O(h).
Ans. Use a linear scan with the right data structure, usually a hash map, set, stack, two pointers, or trie, depending on the string task. Track only the needed state, such as character counts, last seen positions, or window bounds. Most optimal string solutions run in O(n) time with O(k) space.
Ans. The circuit’s logic is found by labelling each gate output, writing the Boolean expression from inputs to final output, then evaluating every input combination in a truth table. For n inputs, list 2^n rows, compute intermediate columns if needed, and fill the final output column from the gate operations.
Ans. Traverse the tree while keeping each node’s parent, and when the target node is found, print that parent and the parent’s other child as the sibling. If the target is the root, it has no parent or sibling. Use DFS recursion or BFS with a queue. Time complexity is O(n), with extra space O(h) for DFS.
Ans. Track the longest subarray ending at each index with positive and negative product, and return the best positive length seen. For each number, update positive and negative lengths; swap roles on a negative value, and reset both on zero. This single pass uses constant extra space and runs in O(n) time.
Ans. Model the graph with an adjacency list, validate empty or single-node inputs first, then choose BFS or DFS for traversal, shortest path in unweighted graphs, or Dijkstra for weighted non-negative graphs. Track visited nodes, parents or distances as needed. Time complexity is usually O(V + E), or O((V + E) log V) with Dijkstra.
Ans. Reverse the whole character array, then reverse each word in place. For “i am a boy”, full reversal gives “yob a ma i”, and reversing characters inside each word gives “boy a am i”. This uses two pointers, O(n) time, and O(1) extra space if the string is mutable.
Ans. Use dynamic programming: store the minimum cost to reach each cell from the top-left. Set the first cell to its matrix cost, fill the first row and column from their only possible predecessor, then each other cell takes its cost plus the minimum of top and left. The answer is the bottom-right value. Time is O(mn).
Ans. Virtual functions work through dynamic dispatch using a VTABLE and a VPTR. For each polymorphic class, the compiler creates a VTABLE containing addresses of virtual function implementations. Each object stores a hidden VPTR pointing to its class VTABLE. When a virtual function is called through a base pointer or reference, the compiler generates lookup code through the VPTR.
Ans. Create one tree node per index, then scan the matrix and whenever M(i,j) is 1, attach node j as a child of node i and record that j has a parent. After the scan, the node with no recorded parent is the root. Use an array of nodes and parent flags. Time complexity is O(n²).
Ans. Use a lookup table to precompute bit-change counts for all 8-bit values, then split the 32-bit integer into four bytes and sum their stored counts. Add three comparisons for the byte boundaries, between bit 7 and bit 8, and so on. This uses extra space, but runs in constant time.
Ans. Start at the top right element and do a staircase search. If the current value equals the target, return found. If it is smaller than the target, move left because values increase to the left. If it is larger, move down because values decrease downwards. This takes O(rows + columns) time.
Ans. Convert the index to row and column, then check whether the same number already exists in that row, that column, or the corresponding 3 by 3 box. If none contain it, the index is valid for that number. Use the board as a 2D array; this takes constant time for Sudoku.
Ans. Store the smaller array in a hash set, then scan the larger array and report elements found in the set. This gives expected O(m + n) time and O(n) extra space, which is optimal for unsorted arrays because every element may need to be inspected. Use an output set if duplicates must be avoided.
Ans. The inorder successor is the next larger node in the BST. If the node has a right child, return the leftmost node in its right subtree. Otherwise, move up through parent pointers until you find an ancestor for which the current node is in the left subtree. That ancestor is the successor. Time is O(h), space is O(1).
Ans. Sort the jobs by start time, then scan them while keeping a min heap of active jobs ordered by end time. Before adding a job, remove all jobs whose end time is not after its start and subtract their loads. Add the new load, update the maximum. Time complexity is O(n log n).
Ans. Use a queue for breadth first traversal, storing each node together with its level number. Start by pushing the root with level 0 or 1, depending on convention. Repeatedly pop the front, print the node value and level, then push its children with level plus one. Time is O(n), space is O(w).
Ans. Create one tree node for each index, then scan the matrix and whenever M[i][j] is 1, add node j as a child of node i. Keep a hasParent array and mark j true for each such edge. After the scan, the root is the only node not marked. Time complexity is O(n²), space is O(n).
Ans. Find the next greater by moving the rightmost non-trailing zero left of a block of ones, then place the remaining ones at the far right; find the next smaller symmetrically by moving the rightmost non-trailing one down and packing ones just to its left. This uses bit manipulation only, runs in O(number of bits) time and O(1) space.
Ans. Start at the top left element and eliminate one row or column at each step. If the key is larger, move right because rows increase. If the key is smaller, move down because columns decrease. Stop when found or outside the matrix. This uses no extra data structure and runs in O(rows + columns) time.
Ans. In C++, static gives a variable static storage duration or makes a class member belong to the class rather than each object. A static member function has no this pointer, so it cannot directly access non-static members. To access them, it must use an object, reference, or pointer to an instance.
Ans. Use a postorder DFS and count a subtree when both children are univalue subtrees and their values, if present, match the current node’s value. Return to the parent whether the current subtree is univalue. A null child counts as valid. This visits each node once, uses recursion stack space, and runs in O(n) time.
Ans. Model the boxes as a directed graph and use topological sorting. For each inequality A < B, add an edge from A to B, then take any topological order and assign the sorted integers in increasing order along it. If the graph has a cycle, no valid placement exists. Time is O(n + m).
Ans. Five weighings are enough, and four cannot be enough. Each balance weighing has three outcomes, so four weighings distinguish only 81 outcomes. If the ball may be heavier or lighter, there are 200 cases. Use a five-weighing ternary coding scheme, placing coded groups left, right, or off each time. The outcome pattern identifies the ball.
Ans. Return a generated ID string made from a unique machine identifier, the current timestamp, and an atomic per-machine sequence counter. The critical detail is that machine identifiers must never overlap. For calls in the same timestamp tick, increment the counter atomically. Store only the counter and last timestamp. Time complexity is O(1).
Ans. Use signal controllers with road sensors that emit vehicle id, timestamp and location events, then compute speed from the time taken between two known points. Keep a hash map from vehicle id to its latest detection and update rolling totals per road segment. Each event is processed in O(1) time, with O(n) storage for active vehicles.
Ans. Storage classes in C++ define an object’s lifetime, visibility, and linkage. The main specifiers are static, extern, thread_local, and mutable. Historically, auto and register were also storage class specifiers, but auto now means type deduction and register is obsolete. The key idea is how long data exists and where it can be accessed.
Ans. A virtual function in C++ is a member function declared with virtual so calls are resolved at runtime based on the actual object type. This enables polymorphism: a base class pointer or reference can call an overridden derived class method. Destructors should often be virtual in polymorphic base classes.
Ans. Pick a real workplace situation where your conduct affected trust, fairness, confidentiality, safety, or accountability. Emphasise the standard you recognised, the action you took, and how you handled pressure or conflict. Interviewers listen for judgement, honesty, respect for others, ownership of mistakes, and consistency with company values.
No question matches those filters. Reset filters.
Showing 60 of 109 questions. Ranked by how often the same question came back across interviews.
A spoken interview built from these questions, scored when you finish; the feedback is yours.
Start practisingWhen you are ready, record The One: a single interview hiring teams watch, so you stop repeating first rounds.
Candidate interviews most often cover DSA (63%) and CS fundamentals (22%).
Candidate interviews show an average of 4.6 rounds per experience, with a typical sequence of Online test → Technical → Technical → HR → HR. Individual interview paths can vary.
Among questions with a recorded difficulty, the mix is easy 30%, medium 61%, hard 9%.
