Cadence Design Systems Software Developer Interview Questions, Process, and Tips

Medium coding qs with technical interview

Q1. Reverse an array
Add your answer

Q1. Question on merge sort
Add your answer

Round duration - 75 minutes
Round difficulty - Medium

This was an online coding round where I had 2 questions to solve under 75 minutes. Both the coding questions were related to DP and were of Medium to Hard level of difficulty.

Q1. 
Longest Common Prime Subsequence Problem Statement
Imagine Ninja is tackling a puzzle during his long summer vacation. He has two arrays of integers, each with lengths 'N' and 'M'. Ninja's task is to dete...read more
Ans. 
Algorithm :

1) Generate all the prime numbers in the range of values of the given array using Sieve Of Eratosthenes.

2) Now make an iteration for ‘arr1’ and check the elements in ‘arr1’ which are prime and store the elements in an array, say ‘finalA’.
 
3) Now make an iteration for ‘arr2’ and check the elements in ‘arr2’ which are prime and store the elements in an array, say ‘finalB’.
 
4) Now calculate the LCS fo...read more
Answered Anonymously
Add your answer
Q2. 
Maximum Sum Problem Statement
You are given an array ARR of N integers. Your task is to perform operations on this array until it becomes empty, and maximize the sum of selected elements. In each operatio...read more
Ans. 
Algorithm:

1) Find the maximum number max in the array.

2) Create a new auxiliary array dp of size max+1 and store frequencies of unique elements in the array, where dp[i] denotes the number of times i as an element is present in the input array.
 
3) Iterate the dp array(we will use this array to store the results), now for each index i from 2 to MAX we have two choices: dp[i] = max(dp[i-1], dp[i-2] + dp[i]*i).
 
...read more
Answered Anonymously
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

This round had 2 Algorithmic questions wherein I was supposed to code both the problems after discussing their approaches and respective time and space complexities . After that , I was grilled on some OOPS concepts related to C++.

Q1. 
Cycle Detection in a Linked List
Your task is to determine if a given Singly Linked List of integers forms a cycle.
Explanation: A cycle in a linked list occurs when there is a node in the list that conn...read more
Ans. 
Approach 1(Using Hashing) :

We are going to maintain a lookup table(a Hashmap) that basically tells if we have already visited a node or not, during the course of traversal.

Steps :
1) Visit every node one by one, until null is not reached.

2) Check if the current node is present in the loop up table, if present then there is a cycle and will return true, otherwise, put the node reference into the lookup table and repeat t...read more
Answered Anonymously
Add your answer
Q2. 
Check If Preorder Traversal Is Valid
Determine whether a given array ARR of positive integers is a valid Preorder Traversal of a Binary Search Tree (BST).
A binary search tree (BST) is a tree structure w...read more
Ans. 
Approach (Using Stack) : 

1) Initialize an empty stack of integers.

2) Initialize a variable lowerBound to store the value of the root of the current tree. Initialize is as INT_MIN. 

3) Iterate through i = 0 to N - 1
3.1) If ARR[i] is smaller than lowerBound, then we will return 0. 

3.2) Repeatedly,
If the stack is non-empty, then remove the element at the top of the stack if it is smaller than ARR[i] and make...read more
Answered Anonymously
Add your answer
Q3. What are Vtable and VPTR in C++?
Ans. 
Vtable : It is a table that contains the memory addresses of all virtual functions of a class in the order in which they are declared in a class. This table is used to resolve function calls in dynamic/late binding manner. Every class that has virtual function will get its own Vtable.


VPTR : After creating Vtable address of that table gets stored inside a pointer i.e. VPTR (Virtual Pointer). When you create an object of...read more
Answered Anonymously
Add your answer
Q4. What are friend functions in C++?
Ans. 
1) Friend functions of the class are granted permission to access private and protected members of the class in C++. They are defined globally outside the class scope. Friend functions are not member functions of the class.

2) A friend function is a function that is declared outside a class but is capable of accessing the private and protected members of the class.

3) There could be situations in programming wherein we w...read more
Answered Anonymously
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

This was also a DS/Algo round where I was given 2 questions to solve and I was expected to come up with the optimal approach as far as possible. I solved both the questions with the optimal time and space complexities and then I was asked some more questions related to DBMS towards the end of the interview.

Q1. 
Top View of a Binary Tree
You are given a binary tree. Your task is to print the Top View of the Binary Tree, displaying the nodes from left to right order.
Input:
The first line contains an integer 't'...read more
Ans. 
Approach 1 : 

1) Like vertical Order Traversal, we need to put nodes of same horizontal distance together. 

2) We do a level order traversal so that the topmost node at a horizontal node is visited before any other node of same horizontal distance below it. 

3) Hashing is used to check if a node at given horizontal distance is seen or not. 

TC : O(N*log(N)), where N = number of nodes in the binary tree
S...read more
Answered Anonymously
Add your answer
Q2. 
Count Palindromic Substrings Problem Statement
Given a string STR, determine the total number of palindromic substrings within STR.
Input:
The first line contains an integer 't' representing the number ...read more
Ans. 
I solved it using DP as I was able to figure out what my dp table would store and the dp transition state .

Approach :
1) Create a 2-D dp boolean vector(with all false initially) where dp[i][j] states whether s[i...j] is a palindrome or not .

2) Base Case : For every i from 0 to n-1 fill dp[i][i]=1 ( as a single character is always a palindrome )and increment the counter where counter=0 initially

3) Now, run 2 loops first ...read more
Answered Anonymously
Add your answer
Q3. What is the difference between the DELETE and TRUNCATE commands in a DBMS?
Ans. 
DELETE command :

1) This command is needed to delete rows from a table based on the condition provided by the WHERE clause.

2) It can be rolled back if required.
 
3) It maintains a log to lock the row of the table before deleting it and hence it’s slow.

 

TRUNCATE command :

1) This command is needed to remove complete data from a table in a database. It is like a DELETE command which
has no WHERE clause.
 
2) It ...read more
Answered Anonymously
Add your answer
Q4. What is meant by normalization and denormalization?
Ans. 
NORMALIZATION :
 
1) Normalization is a process of reducing redundancy by organizing the data into multiple tables.

2) Normalization leads to better usage of disk spaces and makes it easier to maintain the integrity of the database.


DENORMALIZATION :

1) Denormalization is the reverse process of normalization as it combines the tables which have been normalized into a single table so that data retrieval becomes faster.
&...read more
Answered Anonymously
Add your answer

Round duration - 75 minutes
Round difficulty - Medium

This was an online coding round where I had 2 questions to solve under 75 minutes. Both the coding questions were of Medium to Hard level of difficulty.

Q1. 
Smallest Window Problem Statement
Given two strings, S and X, your task is to find the smallest substring in S that contains all the characters present in X.
Example:
Input:
S = "abdd"
X = "bd"
Output:
...read more
Add your answer
Q2. 
K - Sum Path In A Binary Tree
Given a binary tree where each node contains an integer value, and a value 'K', your task is to find all the paths in the binary tree such that the sum of the node values in ...read more
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

This round had 2 questions of DS/Algo to solve under 60 minutes and 2 questions related to Operating Systems.

Q1. 
Validate Partial Binary Search Tree (BST) Problem Statement
You are provided with a binary tree containing 'N' nodes. Your task is to determine if this tree is a Partial Binary Search Tree (BST). Return t...read more
Add your answer
Q2. 
Longest Increasing Subsequence Problem Statement
Given an array of integers with 'N' elements, determine the length of the longest subsequence where each element is greater than the previous element. This...read more
Add your answer
Q3. Can you define process and threads in operating systems?
Add your answer
Q4. What are the different types of semaphores?
Add your answer

Round duration - 60 Minutes
Round difficulty - Hard

In this round, I was asked 3 coding questions out of which I had to implement the first two and for the last question I was only asked the optimal approach. The main challenge in this round was to implement the first two questions in a production ready manner without any bugs and so I had to spent some time thinking about some Edge Cases which were important with respect to the question.

Q1. 
Next Greater Element Problem Statement
You are given an array arr of length N. For each element in the array, find the next greater element (NGE) that appears to the right. If there is no such greater ele...read more
Add your answer
Q2. 
Power Set Generation
Given a sorted array of 'N' integers, your task is to generate the power set for this array. Each subset of this power set should be individually sorted.
A power set of a set 'ARR' i...read more
Add your answer
Q3. 
Counting Sort Problem Statement
Ninja is learning about sorting algorithms, specifically those that do not rely on comparisons. Can you help Ninja implement the counting sort algorithm?
Example:
Input:
...read more
Add your answer