Cadence Design Systems Interview Questions, Process, and Tips

Round duration - 60 minutes
Round difficulty - Medium

Standard Data Structures and Algorithms round . One has to be fairly comfortable in solving algorithmic problems to pass this round with ease.

Q1. 
Find All Pairs with Given Sum
Given an integer array arr and an integer Sum, count and return the total number of pairs in the array whose elements add up to the given Sum.
Input:
The first line contain...read more
Ans. 
Naive Solution :
 
A simple solution is to traverse each element and check if there’s another number in the array which can be added to it to give sum.

TC : O(n^2)
SC : O(1)


Efficient Solution (Using Hashing ) :

We create an empty hash table. Now we traverse through the array and check for pairs in the hash table. If a matching element is found, we print the pair number of times equal to the number of occurrences of the...read more
Answered Anonymously
Add your answer
Q2. 
Minimum Number of Jumps Problem
Given an array ARR of N integers, determine the minimum number of jumps required to reach the last index of the array (i.e., N - 1). From any index i, you can jump to an in...read more
Ans. 
Approach 1 : Naive Recursive Approach

A naive approach is to start from the first element and recursively call for all the elements reachable from first element. The minimum number of jumps to reach end from first can be calculated using minimum number of jumps needed to reach end from the elements reachable from first.

minJumps(start, end) = Min ( minJumps(k, end) ) for all k reachable from start

TC : O(n^n)
SC : O(n)


Appr...read more
Answered Anonymously
Add your answer

Round duration - 70 minutes
Round difficulty - Medium

This round was preety intense and went for over 1 hour . I was asked 2 preety good coding questions (one was from Graphs and the other one was from DP) . After that I was grilled on my Computer Networks and Operating System concepts but luckily I was able to answer all the questions and the interviewer was also quite impressed.

Q1. 
Two Teams (Check Whether Graph is Bipartite or Not)
Determine if a given undirected graph can be divided into exactly two disjoint cliques. Print 1 if possible, otherwise print 0.
Input:
The first line ...read more
Ans. 
Algorithm :

1) Create a graph such that there is a edge between each pair of enemies.

2) We need to find that the above graph is bipartite or not. Check whether the graph is 2-colorable or not

3) We can do that by running dfs and using an auxilary array col to store the assigned col of the node.

4) If we can color the graph with two color such that no two enemies have same color then only we can create two teams.


TC : O(V+E...read more
Answered Anonymously
Add your answer
Q2. 
Maximum Length Pair Chain Problem
You are provided with 'N' pairs of integers, where the first number in each pair is less than the second number, i.e., in pair (a, b) -> a < b. A pair chain is defi...read more
Ans. 
Approach 1 (Using DP ) :

Observe that , If a chain of length k ends at some pairs[i], and pairs[i][1] < pairs[j][0], we can extend this chain to a chain of length k+1

Steps :

1) Sort the pairs by first coordinate, and let dp[i] be the length of the longest chain ending at pairs[i].

2) When i < j and pairs[i][1] < pairs[j][0], we can extend the chain, and so we have the candidate answer dp[j] = max(dp[j], dp[i] + 1...read more
Answered Anonymously
Add your answer
Q3. Can you explain the TCP/IP Protocol?
Ans. 
1) TCP or TCP/IP is the Transmission Control Protocol/Internet Protocol.

2) It is a set of rules that decides how a computer connects to the Internet and how to transmit the data over the network.

3) It creates a virtual network when more than one computer is connected to the network and uses the three ways handshake model to establish the connection which makes it more reliable.
Answered Anonymously
Add your answer
Q4. Can you explain the DHCP Protocol?
Ans. 
1) DHCP is the Dynamic Host Configuration Protocol.

2) It is an application layer protocol used to auto-configure devices on IP networks enabling them to use the TCP and UDP-based protocols.

3) The DHCP servers auto-assign the IPs and other network configurations to the devices individually which enables them to communicate over the IP network.

4) It helps to get the subnet mask, IP address and helps to resolve the DNS. I
Answered Anonymously
Add your answer
Q5. What is meant by multitasking and multithreading in operating systems?
Ans. 
Multitasking : It refers to the process in which a CPU happens to execute multiple tasks at any given time. CPU switching occurs very often when multitasking between various tasks. This way, the users get to collaborate with every program together at the same time. Since it involves rapid CPU switching, it requires some time. It is because switching from one user to another might need some resources. The processes in m...read more
Answered Anonymously
Add your answer

Round duration - 60 minutes
Round difficulty - Hard

This round majorly focused on past projects and experiences from my Resume and some standard System Design + LLD questions + some basic OOPS questions which a SDE-2 is expected to know .

Q1. How would you design a system like Pastebin?
Ans. 
Approach :

Pastebin allows users to store text-based data over the internet for a set period of time and generate a unique URL corresponding uploaded data to share that with anyone. Users who create that data, can also modify it by logging in to the same account.

Database Schema :

i) users(userID, name, createdAT, metaData)
ii) paste(pasteID, content, URL, createdAt, expiryAt)

Algorithm :

1) create_paste(api_key, content, ex...read more
Answered Anonymously
Add your answer
Q2. What is data abstraction and how can it be achieved?
Ans. 
1) Data abstraction is a very important feature of OOPs that allows displaying only the important information and hiding the implementation details.

2) For example, while riding a bike, you know that if you raise the accelerator, the speed will increase, but you don’t know how it actually happens.

3) This is data abstraction as the implementation details are hidden from the rider.

Data abstraction can be achieved through:

Answered Anonymously
Add your answer
Q3. What is the Diamond Problem in C++ and how can it be resolved?
Ans. 
The Diamond Problem : The Diamond Problem occurs when a child class inherits from two parent classes who both share a common grandparent class i.e., when two superclasses of a class have a common base class.

Solving the Diamond Problem in C++ : The solution to the diamond problem is to use the virtual keyword. We make the two parent classes (who inherit from the same grandparent class) into virtual classes in order to a...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

General aptitude questions multiple choice

Questions related to Verilog, college projects

Q1. Questions around SystemVerilog specially oops concepts
Add your answer

Q1. What is your family background?
Add your answer
Q2. What are your strengths and weaknesses?
Add your answer
Q3. Tell me about yourself.
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

DSA C++ basic question