40+ Publicis Sapient Interview Questions and Answers

Find minimum vertices to place policemen in an acyclic graph of a city to cover all roads.

• Use Depth First Search (DFS) to traverse the graph

• Maintain a set of visited vertices to avoid revisiting

• For each unvisited vertex, place a policeman and mark all connected edges as covered

• Repeat until all edges are covered

• Return the minimum number of policemen placed

Find shortest path between 'S' and 'E' in a matrix filled with '0's and 'x's

• Use Breadth First Search (BFS) algorithm to find shortest path

• Create a visited matrix to keep track of visited cells

• Create a queue to store cells to be visited

• Start BFS from 'S' and keep track of distance to each cell

• When 'E' is found, return the distance to it

Find all permutations of a given string, handling duplicates.

• Use recursion to generate all possible permutations

• Use a hash set to keep track of already generated permutations

• Handle duplicates by skipping already generated permutations

• Time complexity is O(n!)

• Return an array of strings containing all permutations

Pre-process a dictionary to output anagrams of a given string. Data structure, time and space complexity?

• Create a hash table with sorted string as key and list of anagrams as value

• Iterate through dictionary and sort each string, add to hash table

• To find anagrams of given string, sort it and look up in hash table

• Time complexity: O(n * klogk), space complexity: O(n)

• n = number of strings in dictionary, k = length of longest string

Find minimum length substring of string a containing all characters of string b.

• Use sliding window approach

• Maintain a frequency map of characters in b

• Move the window until all characters of b are present

• Update the minimum length substring as you move the window

Find the number of elements shifted in a sorted array after shifting n elements from right to first.

• Find the index of the minimum element in the shifted array

• The number of elements shifted is equal to the index of the minimum element

• Use binary search to find the minimum element in O(log n) time

Find the first level in a complete binary tree where the height difference between left and right subtrees is more than 1.

• Traverse the binary tree level by level using breadth-first search

• For each level, calculate the height difference between the left and right subtrees

• Return the level number when the height difference is more than 1

Prove that in-order traversal of a BST is always sorted and vice versa

• In-order traversal of a BST visits nodes in ascending order

• If a binary tree's in-order traversal is sorted, it is a BST

• A BST's left subtree contains only nodes with values less than its root

• A BST's right subtree contains only nodes with values greater than its root

Implement Facebook's 'People you may know' feature using BFS and mutual friend counter.

• Create a graph of users and their friends

• Perform BFS on the graph starting from the user in question

• For each friend of the user, increment a counter for their mutual friends

• Sort the list of potential friends by mutual friend count

• Exclude already connected friends and suggest top potential friends

Find an element k in a sorted array such that Max(k) < n.

• Use binary search to find the largest element smaller than n

• Start with mid element and adjust search range based on comparison with n

• Return -1 if no such element exists

Yes, we can use Breadth First Search (BFS) algorithm to determine if we can reach index 0 with the given operations.

• Use BFS algorithm to explore all possible paths starting from index 0.

• Keep track of visited indices to avoid infinite loops.

• If we reach an index with value 0, return true; otherwise, return false.

Given a matrix and value k, find k*k submatrix with maximum sum.

• Iterate over all submatrices of size k*k and calculate their sum.

• Keep track of the maximum sum and the corresponding submatrix.

• Use dynamic programming to optimize the solution.

• Time complexity can be reduced to O(m*n*k^2) using prefix sum technique.

Shortest path in 2D matrix

• Use BFS or Dijkstra's algorithm

• Create a visited matrix to avoid revisiting cells

• Keep track of distance and path

• Consider obstacles or blocked cells

Check if a binary tree is a BST or not and give time and space complexity.

• Traverse the tree in-order and check if the elements are in ascending order

• Keep track of the maximum value seen so far while traversing

• If any element violates the ascending order, return false

• Time complexity: O(n), Space complexity: O(h) where h is the height of the tree

Sort an array of 0s, 1s, and 2s without using counting sort.

• Use three pointers to keep track of the positions of 0s, 1s, and 2s.

• Traverse the array and swap elements to their respective positions.

• Time complexity: O(n), Space complexity: O(1).

Find the first occurrence of 1 in a sorted array of 0s and 1s.

• Use binary search to find the first occurrence of 1.

• If mid element is 1, check left subarray for first occurrence.

• If mid element is 0, check right subarray for first occurrence.

Calculate the maximum absolute difference between the sums of any two levels in a binary tree.

• Traverse the binary tree level by level and calculate the sum of nodes at each level.

• Keep track of the maximum absolute difference between the sums of any two levels encountered so far.

• Return the maximum absolute difference found.

Use a hashmap to separate prime and non-prime numbers in an array of strings.

• Iterate through the array and convert each string to an integer.

• Use a hashmap to store prime and non-prime numbers based on their divisibility.

• Convert the hashmap back to separate arrays for prime and non-prime numbers.

Separate prime numbers from non-prime numbers in a linked list while preserving their order.

• Iterate through the linked list and separate prime numbers from non-prime numbers

• Create two separate linked lists for prime and non-prime numbers

• Maintain the order of numbers while separating them

• Example: Input: 1 -> 2 -> 3 -> 4 -> 5, Output: Prime: 2 -> 3 -> 5, Non-prime: 1 -> 4

Count number of flips required to balance parentheses in a string

• Iterate through the string and keep track of open and close brackets

• If a close bracket is encountered without a corresponding open bracket, increment flip count

• Return the total number of flips required to balance the parentheses

Efficient way to search a given element in an array of integers with adjacent elements 1+ or 1- from each other.

• Use binary search algorithm to search the element in O(log n) time complexity.

• Check the middle element and compare it with the given element.

• If the middle element is greater than the given element, search in the left half of the array.

• If the middle element is smaller than the given element, search in the right half of the array.

• Repeat until the element is found or t...read more

The number of binary strings of length N without consecutive 1s.

• Use dynamic programming to solve the problem.

• Create an array to store the number of valid strings for each length.

• Initialize the array with base cases.

• Iterate through the array and calculate the number of valid strings for each length.

• Return the value at the Nth index of the array.

Use two separate arrays to store prime and non-prime numbers from the input array.

• Iterate through the input array and check if each element is prime or not.

• Store prime numbers in one array and non-prime numbers in another array.

• Maintain the order of elements in the input array while separating prime and non-prime numbers.

Find the nth largest element from last in a singly linked list

• Traverse the list to find its length

• Traverse again to the (length-n)th node

• Return its value

Find the merge point of two linked lists.

• Traverse both linked lists to find their lengths.

• Calculate the difference in lengths and move the pointer of the longer list by the difference.

• Traverse both lists in parallel until the merge point is found.

Yes, it can be improved by considering alternative approaches or technologies.

• Consider different algorithms or data structures for optimization

• Explore new technologies or frameworks that may offer better performance

• Collaborate with team members to brainstorm alternative solutions

• Conduct code reviews and seek feedback for improvement

Design a data structure for efficient insert(),delete(),search(), return_any_value().

• Consider using a hash table or a balanced binary search tree

• For return_any_value(), use a random number generator to select a value

• Optimize for the most frequently used operations

DFS based question to find number of rotten tomatoes in an array of strings.

• Implement DFS to traverse the array of strings

• Check each element for rotten tomatoes

• Keep track of the count of rotten tomatoes

Design a lift system using OOPs concepts.

• Create a Lift class with methods like moveUp(), moveDown(), openDoor(), closeDoor()

• Create a Floor class with methods like requestLift()

• Use inheritance to create different types of lifts like passenger lift, cargo lift, etc.

• Use encapsulation to hide the internal workings of the lift system from the outside world.

• Use polymorphism to allow different types of lifts to respond differently to the same method calls.

Using BFS to find the minimum number of steps for oranges to decay in a grid

• Implement BFS algorithm to traverse the grid and decay the oranges

• Keep track of the number of steps taken to decay all oranges

• Return the minimum number of steps required to decay all oranges

Design a system for booking tickets for events like movies, concerts, etc.

• Use microservices architecture for scalability and flexibility

• Implement a user-friendly interface for easy ticket booking

• Include features like seat selection, payment gateway integration, and booking history

• Utilize a database to store event details, user information, and booking records

To find third maximum salary in DBMS, we can use the ORDER BY and LIMIT clauses.

• Use ORDER BY to sort the salaries in descending order

• Use LIMIT to select the third highest salary

• Example: SELECT salary FROM employees ORDER BY salary DESC LIMIT 2,1

LRU caching algorithm stores most recently used items, discarding least recently used items when full.

• Use a doubly linked list to maintain order of items based on recent usage

• Use a hashmap to quickly access items in the cache

• When an item is accessed, move it to the front of the linked list

• When cache is full, remove the last item in the linked list

JSP servlets were used for dynamic web page generation and server-side processing.

• Used for creating dynamic web pages by embedding Java code in HTML

• Facilitates server-side processing of user requests

• Enables separation of presentation and business logic

• Provides scalability and reusability of code

• Example: Used JSP servlets to generate personalized user profiles on a website

Diagonal traversal of a binary tree involves printing the nodes of the tree in a diagonal pattern.

• Start with the root node and move to its right child, then move down to its left child.

• Repeat this process for each diagonal of the tree, printing the nodes as you traverse.

• Use a queue to keep track of the nodes at each level of the tree.

Reverse a linked-list

• Iterate through the linked-list and change the direction of the pointers

• Keep track of the previous, current and next nodes

• Set the head of the linked-list to the last node after reversing

Reverse a singly linked list

• Iterate through the list and change the direction of the pointers

• Keep track of the previous, current, and next nodes

• Set the head of the list to the last node after reversing

The time complexity of the code can be determined by analyzing the number of operations performed as a function of the input size.

• Time complexity is typically expressed using Big O notation, which describes the upper bound on the growth rate of the algorithm.

• Common time complexities include O(1) for constant time, O(log n) for logarithmic time, O(n) for linear time, O(n^2) for quadratic time, and O(n!) for factorial time.

• To determine the time complexity of a code, analyze the...read more

To find the height of a binary tree, we can recursively calculate the height of left and right subtrees and return the maximum height + 1.

• Start by checking if the tree is empty, in which case the height is 0.

• Recursively calculate the height of the left and right subtrees.

• Return the maximum height of the left and right subtrees + 1 as the height of the binary tree.

Use quickselect algorithm to find the kth min element from an array

• Implement quickselect algorithm to partition the array based on a pivot element

• Recursively select the partition to search for the kth min element

• Time complexity is O(n) on average, O(n^2) worst case

Find the length of the longest increasing subsequence in an array.

• Use dynamic programming to solve the problem.

• The time complexity of the algorithm should be O(n^2).

• Example: For the array [10, 22, 9, 33, 21, 50, 41, 60, 80], the longest increasing subsequence is [10, 22, 33, 50, 60, 80] with length 6.

The Next Greater Element problem involves finding the next greater element for each element in an array.

• Use a stack to keep track of elements for which the next greater element is yet to be found.

• Iterate through the array and for each element, pop elements from the stack until a greater element is found.

• Store the next greater element for each element in a result array.

Design system design for bitly

• Use a distributed system architecture to handle high traffic and scalability

• Implement a URL shortening algorithm to generate unique short links

• Utilize caching mechanisms to improve performance and reduce database load

• Include analytics and tracking features to monitor link performance

• Ensure data security and privacy measures are in place to protect user information

Kadane's algorithm is used to find the maximum subarray sum in an array of integers.

• Iterate through the array and keep track of the maximum sum ending at each index.

• At each index, choose between extending the previous subarray or starting a new subarray.

• The final result is the maximum sum found during the iteration.