50+ Publicis Sapient Software Developer Interview Questions and Answers

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 elements as the median.

The oldest pirate proposes to keep 98 coins for himself and give 1 coin to each of the other pirates.

• The oldest pirate will propose to keep the majority of the coins for himself to ensure the vote passes.

• The other pirates will vote in favor of the proposal to avoid being thrown overboard.

• The proposed distribution will be 98 coins for the oldest pirate and 1 coin for each of the other pirates.

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

The missing rupee is not actually missing. The calculation is misleading and does not account for the total amount paid.

• The initial amount paid by each person was Rs.10, totaling Rs.30.

• The owner gave them a discount of Rs.5, so they paid Rs.25 in total.

• The broker took Rs.2, leaving them with Rs.23.

• When the broker returned Rs.1 to each person, they each received Rs.1 back, totaling Rs.3.

• So, the total amount paid by the three friends is Rs.25 + Rs.3 = Rs.28.

• The remaining Rs.2 i...read more

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 [4, 2, 2, 6] and XOR value 6, there are 2 subarrays [4, 2]...read more

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.

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

Count the number of islands in a 2D matrix of 1s and 0s.

• Use depth-first search (DFS) to traverse the matrix and identify connected groups of 1s.

• Maintain a visited array to keep track of visited cells to avoid redundant traversal.

• Increment the island count each time a new island is encountered.

• Consider all eight possible directions for connectivity while traversing the matrix.

• Handle edge cases such as out-of-bounds indices and water cells (0s) during traversal.

Detect cycles in an undirected graph.

• Use Depth First Search (DFS) to detect cycles in the graph.

• Maintain a visited array to keep track of visited vertices.

• If a visited vertex is encountered again during DFS, a cycle exists.

• Check for cycles in each connected component of the graph.

• Consider edge cases like disconnected graphs and self-loops.

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

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.

• Randomize the selection of the pivot element to avoid predi...read more

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

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 maximum area found so far and return it as the result.

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

Use one candle as a timer and the other to measure 90 minutes.

• Light both candles at the same time.

• Let one candle burn for 30 minutes.

• Then light the other candle.

• When the second candle burns out, 90 minutes have passed.

• The first candle will have burned for 60 minutes, serving as a timer.

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 empty, the string is balanced.

• Example: For input '{}[]()', ...read more

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 items and weight capacity.

• Example: For N = 4, W = 10, weights...read more

Find the length of the longest substring consisting of repeating characters after performing K operations.

• Iterate through the string and maintain a sliding window of characters.

• Keep track of the frequency of characters in the window.

• Update the window by changing characters to maximize the length of repeating substring.

• Return the length of the longest repeating substring obtained.

Weighing 3 times is enough to find the odd ball out.

• Divide the balls into 3 groups of 3 each and weigh any 2 groups against each other.

• If they are equal, the odd ball is in the third group. Weigh 2 balls from that group to find the odd one.

• If they are not equal, the odd ball is in the heavier group. Weigh 2 balls from that group to find the odd one.

To reverse a string without using any looping and inbuilt functions, we can use recursion.

• Create a function that takes a string as input.

• If the length of the string is 0 or 1, return the string.

• Otherwise, call the function recursively with the substring starting from the second character and concatenate the first character at the end.

• Return the reversed string.

• Example: reverseString('hello') returns 'olleh'.

The ants will end up colliding at the centroid of the triangle.

• The ants will move towards each other in a straight line along the medians of the triangle.

• They will eventually meet at the centroid of the triangle, which is the point where all three medians intersect.

I would be ready to accept a project in Java even if I was trained in DotNet earlier.

• I have a strong foundation in programming principles and concepts, which can be applied to any language.

• I am confident in my ability to quickly learn and adapt to new technologies.

• I have experience working with multiple programming languages and frameworks.

• I can leverage my knowledge of DotNet to understand similar concepts in Java.

• I am motivated and enthusiastic about taking on new challenge...read more

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

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 the memory address at compile time.

• Late binding allows fo...read more

Connect 9 points in a 3x3 square using 4 lines without lifting the pen.

• Start at any point and draw a line to the adjacent point

• Continue drawing lines until all points are connected

• Make sure the lines intersect to form a square

A priority queue can be implemented using a single queue or multiple queues.

• One approach is to use a single queue and assign priorities to elements using a separate data structure.

• Another approach is to use multiple queues, each representing a different priority level.

• For example, if there are three priority levels, three queues can be used to implement the priority queue.

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.

• Example: class A is inherited by classes B and C, and then...read more

An array of objects can be used to implement a heterogeneous array.

• Each element in the array can be an object that represents a different data type.

• The objects can have different properties and methods based on their respective data types.

• For example, an element can be an object representing a string with a 'value' property and a 'length' method.

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, reports.

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.

• Example: Encapsulation is another technique used to achieve...read more

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 a bank transfer involves debiting one account and crediti...read more

C++ is an extension of C with object-oriented programming features.

• C++ supports classes and objects while C does not.

• C++ has better support for polymorphism and inheritance.

• C++ has a standard template library (STL) which C does not have.

• C++ allows function overloading while C does not.

• C++ has exception handling while C does not.

For loop is used for iterating over a sequence while while loop is used for iterating until a condition is met.

• For loop is used when the number of iterations is known beforehand

• While loop is used when the number of iterations is not known beforehand

• For loop is faster than while loop for iterating over a sequence

• While loop is useful for iterating until a specific condition is met

• For loop can be used with range() function to iterate over a sequence

• While loop can be used with br...read more

Method overloading is having multiple methods with the same name but different parameters. Method overriding is having a subclass method with the same name and parameters as a superclass method.

• Method overloading is used to provide different ways of calling the same method with different parameters.

• Method overriding is used to provide a specific implementation of a method in a subclass that is already defined in the superclass.

• Method overloading is resolved at compile-time ba...read more

Switch case is used for multiple conditions while if else is used for binary conditions.

• Switch case is faster than if else for multiple conditions.

• If else can handle complex conditions while switch case cannot.

• Switch case can only compare values of the same data type.

• If else can handle null values while switch case cannot.

• Example: switch (day) { case 1: console.log('Monday'); break; case 2: console.log('Tuesday'); break; default: console.log('Invalid day'); }

• Example: if (age ...read more

Program to add two numbers without using + operator

• Use bitwise operators like XOR, AND, and left shift to perform addition

• Create a function that takes two numbers as input and returns their sum

• Example: function add(a, b) { return a ^ b + ((a & b) << 1); }

Interface and abstract class are both used for abstraction in object-oriented programming.

• An interface is a collection of abstract methods that define a contract for a class to implement.

• An abstract class is a class that cannot be instantiated and may contain abstract methods.

• Interfaces are used to achieve multiple inheritance in Java.

• Abstract classes can have non-abstract methods and instance variables.

• An example of an interface is the Comparable interface in Java.

• An example...read more

A program to check if a given number is a palindrome or not.

• Convert the number to a string.

• Reverse the string and compare it with the original string.

• If they are equal, the number is a palindrome.

• If not, the number is not a palindrome.

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.

• Example: friend void displayDetails(Student);

Inheritance in Java allows a class to inherit properties and methods from another class.

• Inheritance is achieved using the 'extends' keyword.

• The class that is being inherited from is called the superclass or parent class.

• The class that inherits from the superclass is called the subclass or child class.

• Subclasses can access the public and protected members of the superclass.

• Inheritance promotes code reusability and allows for the creation of hierarchical relationships.

Yes, they are similar.

• All 8 metal balls are of the same material.

• They have the same size and weight.

• They have the same physical properties.

• They are interchangeable in any given situation.

Polymorphism is the ability of an object to take on many forms.

• It allows objects of different classes to be treated as if they were objects of the same class.

• It is achieved through method overriding and method overloading.

• Example: A shape class can have multiple subclasses like circle, square, etc. and all can be treated as shapes.

• Example: A method can have different implementations in different classes but with the same name and signature.

Inheritance is a mechanism in object-oriented programming where a new class is created by inheriting properties of an existing class.

• Inheritance allows code reusability and saves time and effort in writing new code.

• The existing class is called the parent or base class, and the new class is called the child or derived class.

• The child class inherits all the properties and methods of the parent class and can also add its own unique properties and methods.

• For example, a class 'An...read more

Paging and Segmentation are memory management techniques used by operating systems.

• Paging divides memory into fixed-size pages and stores them in physical memory.

• Segmentation divides memory into logical segments and stores them in physical memory.

• Paging allows for efficient use of physical memory and reduces fragmentation.

• Segmentation allows for protection and sharing of memory between processes.

• Examples of operating systems that use paging and segmentation are Windows and Li...read more

List is mutable, tuple is immutable in Python.

• List can be modified after creation, tuple cannot.

• List is defined using square brackets [], tuple using parentheses ().

• List is slower than tuple due to mutability.

• Example: list_example = [1, 2, 3], tuple_example = (1, 2, 3)

Network layers are a hierarchical way of organizing communication protocols.

• Network layers provide a modular approach to networking.

• Each layer has a specific function and communicates with adjacent layers.

• The OSI model has 7 layers, while the TCP/IP model has 4 layers.

• Examples of layers include the physical layer, data link layer, network layer, transport layer, and application layer.

Deadlock is a situation where two or more processes are unable to proceed because they are waiting for each other to release resources.

• Occurs in multi-threaded/multi-process environments

• Can lead to system freeze or crash

• Prevention techniques include resource ordering and timeouts

• Example: Process A holds resource X and waits for resource Y, while Process B holds resource Y and waits for resource X

Default case in switch case statement

• Default case is executed when no other case matches the switch expression

• It is optional and can be placed anywhere in the switch statement

• It is often used to handle unexpected input or errors

• It should always be the last case in the switch statement

SOLID principles are a set of five design principles that help make software designs more understandable, flexible, and maintainable.

• S - Single Responsibility Principle: A class should have only one reason to change.

• O - Open/Closed Principle: Software entities should be open for extension but closed for modification.

• L - Liskov Substitution Principle: Objects of a superclass should be replaceable with objects of its subclasses without affecting the functionality.

• I - Interface ...read more