Publicis Sapient Software Developer Interview Questions, Process, and Tips

Round duration - 90 minutes
Round difficulty - Medium

There were 2 coding questions . 

Q1. 
0/1 Knapsack Problem Statement
A thief plans to rob a store and can carry a knapsack with a maximum weight capacity of 'W'. The store contains 'N' items, each with a specified weight and value known to th...read more
Ans. 
The 0/1 Knapsack Problem involves maximizing profit by selecting items with specified weights and values within a knapsack's weight capacity.
• Create a 2D array to store the maximum profit that can be achieved at each weight capacity and item index.

• Iterate through each item and weight capacity, updating the maximum profit based on whether the item is included or not.

• Return the maximum profit achievable with the given ite...read more
Answered by AI
Add your answer
Q2. 
Minimum Cost Path Problem Statement
Given an N x M matrix filled with integers, determine the minimum sum obtainable from a path that starts at a specified cell (x, y) and ends at the top left corner of t...read more
Ans. 
Find the minimum sum path from a specified cell to the top left corner of a matrix.
• Use dynamic programming to keep track of the minimum sum at each cell

• Consider all possible moves (down, right, diagonal) from each cell

• Start from the specified cell and work towards the top left corner

• Add the value of the current cell to the minimum sum of the previous cells
Answered by AI
Add your answer

Round duration - 75 minutes
Round difficulty - Medium

The round had 2 coding problems to solve with varying difficulty. Each candidate had a different set of questions. The round was around 2 pm. The webcam was turned on to keep an eye on candidates.

Q1. 
Merge Two Sorted Lists (In-Place) Problem Statement
You are given two sorted linked lists. Your task is to merge them to form a combined sorted linked list and return the head of this final linked list.
...read more
Ans. 
Merge two sorted linked lists in-place to form a combined sorted linked list.
• Create a dummy node to start the merged list

• Compare nodes from both lists and link them accordingly

• Update the pointer to the next node in the merged list

• Handle cases where one list is longer than the other

• Return the head of the merged list
Answered by AI
Add your answer
Q2. 
Make Array Elements Equal Problem Statement
Given an integer array, your objective is to change all elements to the same value, minimizing the cost. The cost of changing an element from x to y is defined ...read more
Ans. 
Find the minimum cost to make all elements of an array equal by changing them to a common value.
• Calculate the median of the array and find the sum of absolute differences between each element and the median.

• Sort the array and find the median element, then calculate the sum of absolute differences between each element and the median.

• If the array has an even number of elements, consider the average of the two middle elem
Answered by AI
Add your answer

Round duration - 50 minutes
Round difficulty - Medium

This round had 2 questions related to DSA. I was first asked to explain my approach with proper complexity analysis and then code the soution in any IDE that I prefer.

Q1. 
Count Subarrays with XOR=X Problem Statement
You are given an array of integers 'ARR' and an integer 'X'. Your task is to determine the number of subarrays in 'ARR' whose elements have a bitwise XOR equal...read more
Ans. 
Count the number of subarrays in an array whose elements have a bitwise XOR equal to a given value.
• Iterate through all subarrays and calculate the XOR value for each subarray.

• Keep track of the count of subarrays with XOR equal to the given value.

• Use a hashmap to store the XOR values encountered and their frequencies for efficient lookup.

• Handle edge cases like empty array or XOR value of 0 separately.

• Example: For input ...read more
Answered by AI
Add your answer
Q2. 
Merge K Sorted Arrays Problem Statement
Given 'K' different arrays that are individually sorted in ascending order, merge all these arrays into a single array that is also sorted in ascending order.
Inpu...read more
Ans. 
Merge K sorted arrays into a single sorted array.
• Iterate through all arrays and merge them using a min-heap.

• Use a priority queue to efficiently merge the arrays.

• Time complexity can be optimized to O(N log K) using a min-heap.
Answered by AI
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. 
Longest Palindromic Substring Problem Statement
You are provided with a string STR of length N. The goal is to identify the longest palindromic substring within this string. In cases where multiple palind...read more
Ans. 
Identify the longest palindromic substring in a given string.
• Iterate through the string and expand around each character to find palindromes

• Keep track of the longest palindrome found

• Return the longest palindrome with the smallest start index
Answered by AI
Add your answer
Q2. 
Quick Sort Algorithm
Sort the given array of integers in ascending order using the quick sort algorithm.
Explanation:
Quick sort is a divide and conquer algorithm where a pivot is chosen to partition th...read more
Ans. 
Yes, the quick sort algorithm can be optimized to achieve NlogN complexity in the worst case by choosing the pivot element strategically.
• Choose the pivot element as the median of the first, middle, and last elements of the array to reduce the chances of worst-case scenarios.

• Implement a hybrid sorting algorithm that switches to a different sorting algorithm like insertion sort for small subarrays to improve efficiency.

• R...read more
Answered by AI
Add your answer
Q3. What is the difference between Early Binding and Late Binding in C++?
Ans. 
Early binding is resolved at compile time, while late binding is resolved at runtime in C++.
• Early binding is also known as static binding, where the function call is resolved at compile time based on the type of the object.

• Late binding is also known as dynamic binding, where the function call is resolved at runtime based on the actual type of the object.

• Early binding is faster as the function call is directly mapped to...read more
Answered by AI
Add your answer
Q4. What is data abstraction and how can it be achieved?
Ans. 
Data abstraction is the process of hiding the implementation details of a data structure and only showing the necessary information to the user.
• Data abstraction can be achieved through the use of abstract classes and interfaces in object-oriented programming.

• It helps in reducing complexity by providing a simplified view of the data.

• Example: In Java, abstract classes and interfaces are used to achieve data abstraction.

• E...read more
Answered by AI
Add your answer
Q5. What is the Diamond Problem in C++ and how can it be resolved?
Ans. 
Diamond Problem is a common issue in multiple inheritance in C++ where a class inherits from two classes that have a common base class.
• Diamond Problem occurs when a class inherits from two classes that have a common base class, leading to ambiguity in accessing members.

• It can be resolved in C++ using virtual inheritance, where the common base class is inherited virtually to avoid duplicate copies of base class members.

• ...read more
Answered by AI
Add your answer
Q6. What are friend functions in C++?
Ans. 
Friend functions in C++ are functions that are not members of a class but have access to its private and protected members.
• Friend functions are declared inside a class with the 'friend' keyword.

• They can access private and protected members of the class they are friends with.

• Friend functions are not member functions of the class.

• They can be used to allow external functions or classes to access private members of a class
Answered by AI
Add your answer

Round duration - 75 minutes
Round difficulty - Medium

This was an online coding round where we had 2 questions to solve under 75 minutes. I found both the questions to be of Easy to Medium level of difficulty.

Q1. 
Line Reflection Problem Statement
You are given several sets of points on a 2D plane, each set represented as a list of coordinates. Your task is to determine if there exists a line parallel to the Y-axis...read more
Ans. 
The task is to determine if there exists a line parallel to the Y-axis that reflects given points symmetrically.
• Iterate through each test case and check if a vertical reflection line exists for the given points

• Calculate the midpoint of the x-coordinates and check if it reflects the points symmetrically

• Consider edge cases where points are on the reflection line or have the same x-coordinate
Answered by AI
Add your answer
Q2. 
Number of Islands Problem Statement
You are provided with a 2-dimensional matrix having N rows and M columns, containing only 1s (land) and 0s (water). Your goal is to determine the number of islands in t...read more
Ans. 
Count the number of islands in a 2D matrix of 1s and 0s.
• Iterate through the matrix and perform depth-first search (DFS) to find connected 1s.

• Mark visited cells to avoid redundant traversal.

• Increment island count whenever a new island is encountered.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

This round had 2 coding questions followed by some questions from DBMS.

Q1. 
Largest Rectangle in Histogram Problem Statement
You are given an array/list HEIGHTS of length N, where each element represents the height of a histogram bar. The width of each bar is considered to be 1.
...read more
Ans. 
Find the area of the largest rectangle that can be formed within the bounds of a given histogram.
• Iterate through the histogram bars and calculate the area of the largest rectangle that can be formed using each bar as the height.

• Use a stack to keep track of the indices of the bars in non-decreasing order of height.

• Pop elements from the stack and calculate the area until a smaller height bar is encountered.

• Update the max...read more
Answered by AI
Add your answer
Q2. 
Valid Parentheses Problem Statement
Given a string 'STR' consisting solely of the characters “{”, “}”, “(”, “)”, “[” and “]”, determine if the parentheses are balanced.
Input:
The first line contains an...read more
Ans. 
The task is to determine if a given string consisting of parentheses is balanced or not.
• Iterate through the characters of the string and use a stack to keep track of opening parentheses.

• If an opening parenthesis is encountered, push it onto the stack.

• If a closing parenthesis is encountered, check if it matches the top of the stack. If it does, pop the stack, else the string is not balanced.

• At the end, if the stack is e...read more
Answered by AI
Add your answer
Q3. Can you explain the concept of ACID properties in DBMS?
Ans. 
ACID properties in DBMS ensure data integrity and consistency in transactions.
• Atomicity: All operations in a transaction are completed successfully or none at all.

• Consistency: Data is always in a valid state before and after a transaction.

• Isolation: Transactions are isolated from each other to prevent interference.

• Durability: Once a transaction is committed, changes are permanent and survive system failures.

• Example: If...read more
Answered by AI
Add your answer
Q4. Can you explain the different levels of data abstraction in a DBMS?
Ans. 
Levels of data abstraction in a DBMS refer to the different views of data provided to users and applications.
• Physical level: Deals with how data is stored on the storage media. Example: data blocks, pages, indexes.

• Logical level: Focuses on how data is represented to users. Example: tables, views, constraints.

• View level: Provides a customized view of the database for specific users or applications. Example: queries, rep
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

Standard DS/Algo round with 2 coding questions followed by 2 interesting puzzles.

Q1. 
Cycle Detection in Undirected Graph Problem Statement
You are provided with an undirected graph containing 'N' vertices and 'M' edges. The vertices are numbered from 1 to 'N'. Your objective is to determi...read more
Ans. 
Detect if an undirected graph contains a cycle by exploring all possible paths.
• Use Depth First Search (DFS) algorithm to traverse the graph and detect cycles.

• Maintain a visited set to keep track of visited vertices and a parent pointer to avoid visiting the same vertex twice.

• If a visited vertex is encountered that is not the parent of the current vertex, a cycle is present.

• Consider edge cases like disconnected graphs a
Answered by AI
Add your answer
Q2. 
Maximum 1s in a Row Problem
Given a matrix ARR with dimensions N * M, consisting only of 0s and 1s where each row is sorted, determine the index of the row that contains the highest number of 1s. If multi...read more
Ans. 
Find the row with the maximum number of 1s in a sorted matrix.
• Iterate through each row of the matrix and count the number of 1s in each row

• Keep track of the row index with the maximum number of 1s

• Return the index of the row with the highest count of 1s
Answered by AI
Add your answer
Q3. You have two wires of different lengths, each taking different amounts of time to burn completely. How can you use these wires to measure a specific duration of time?
Ans. 
By lighting both wires at the same time, the shorter wire will burn out first, allowing you to measure a specific duration of time.
• Light both wires at the same time

• Measure the time it takes for the shorter wire to burn out completely

• The remaining length of the longer wire will indicate the specific duration of time
Answered by AI
Add your answer
Q4. You have 3 ants located at the corners of a triangle. The challenge is to determine the movement pattern of the ants if they all start moving towards each other. What will be the outcome?
Add your answer