40+ Paytm Software Developer Interview Questions and Answers

Reverse a singly linked list of integers and return the head of the reversed linked list.

• Iterate through the linked list and reverse the pointers to point to the previous node instead of the next node.

• Use three pointers to keep track of the current, previous, and next nodes while reversing the linked list.

• Update the head of the reversed linked list as the last node encountered during the reversal process.

Find the minimum time required to rot all fresh oranges in a grid.

• Use Breadth First Search (BFS) to simulate the rotting process of oranges.

• Track the time taken to rot all fresh oranges and return the result.

• If any fresh oranges remain after simulation, return -1 as it is impossible to rot all oranges.

Find the maximum sum of any contiguous subarray within an array of integers.

• Iterate through the array and keep track of the maximum sum of subarrays encountered so far.

• At each index, decide whether to include the current element in the subarray or start a new subarray.

• The maximum subarray sum can be calculated using Kadane's algorithm.

• Example: For array [34, -50, 42, 14, -5, 86], the maximum sum is 137.

• Example: For array [-5, -1, -8, -9], the maximum sum is -1.

Implement a function to delete a node at a specified position in a linked list.

• Traverse the linked list to find the node at the specified position.

• Update the pointers to skip the node to be deleted.

• Handle edge cases like deleting the head or tail node.

• Return the modified linked list.

To delete a node in a singly linked list given a reference to the node.

• Traverse the linked list to find the node to be deleted.

• Update the value of the node to be deleted with the value of the next node.

• Point the next pointer of the node to be deleted to the next node's next pointer.

The task is to find the smallest positive integer value that cannot be represented as a sum of elements of any proper subset of the given array.

• The array is sorted in non-decreasing order, so we can iterate through the array and keep track of the maximum sum we can form.

• If the current element is greater than the maximum sum + 1, then the maximum sum + 1 is the smallest positive integer that cannot be represented.

• If all elements in the array can be represented as a sum of subs...read more

This question asks to find the minimum number of platforms required at a railway station so that no train needs to wait.

• Sort the arrival and departure times arrays in ascending order.

• Initialize a variable 'platforms' to 1 and 'maxPlatforms' to 1.

• Iterate through the arrival and departure times arrays simultaneously.

• If the current arrival time is less than or equal to the current departure time, increment 'platforms'.

• If 'platforms' is greater than 'maxPlatforms', update 'maxPla...read more

Find the minimum number of fountains to activate to water the entire garden.

• Iterate through the array to find the coverage of each fountain.

• Keep track of the farthest coverage reached by each activated fountain.

• Activate the fountain that covers the farthest distance not yet covered.

• Repeat until the entire garden is watered.

Sort an array of 0s, 1s, and 2s in increasing order.

• Use a three-pointer approach to sort the array in a single pass.

• Initialize low, mid, and high pointers at the start, iterate through the array, and swap elements accordingly.

• Example: If the current element is 0, swap it with the element at the low pointer and increment both low and mid pointers.

Print nodes of a binary tree in spiral order traversal.

• Use a queue to perform level order traversal.

• Alternate between printing nodes from left to right and right to left at each level.

• Handle null nodes appropriately.

• Example: For input '1 2 3 -1 -1 4 5 -1 -1 -1 -1', output should be '1 3 2 4 5'.

Create a deep copy of a linked list with random pointers.

• Iterate through the original linked list and create a new node for each node in the list.

• Store the mapping of original nodes to their corresponding new nodes in a hashmap.

• Iterate through the list again to set the next and random pointers of the new nodes based on the mapping.

• Return the head of the newly created deep copied linked list.

Find the inorder successor of a given node in a binary tree.

• Perform an inorder traversal of the binary tree to find the successor of the given node.

• If the given node has a right child, the successor will be the leftmost node in the right subtree.

• If the given node does not have a right child, backtrack to the parent nodes to find the successor.

Delete the middle node of a singly linked list in O(N) time complexity and O(1) space complexity.

• Identify the middle node using slow and fast pointers technique.

• Update the pointers to skip the middle node.

• Handle edge cases like no middle node or two middle nodes.

• Perform the deletion in a single traversal of the linked list.

• Return the modified linked list after deletion.

Identify and return the bottom right view of a given binary tree by viewing it from an angle of 45 degrees from the bottom right side.

• Traverse the binary tree in a right-to-left manner and keep track of the last node encountered at each level.

• Use a queue for level order traversal and update the result array with the last node at each level.

• Return the result array sorted in ascending order as the bottom right view of the binary tree.

Find the minimum distance from a given node to the nearest leaf node in a binary tree.

• Traverse the binary tree from the given node 'X' to find the nearest leaf node using BFS or DFS.

• Keep track of the distance from 'X' to each leaf node encountered during traversal.

• Return the minimum distance found as the output.

Find all unique pairs of elements in an array that add up to a given target sum.

• Use a hashmap to store the difference between the target sum and each element as keys and their indices as values.

• Iterate through the array and check if the current element's complement exists in the hashmap.

• Return the pairs of elements that add up to the target sum.

Implement quick sort algorithm to sort an array of integers in ascending order.

• Choose a pivot element (e.g., rightmost element) to partition the array into two subarrays.

• Recursively apply quick sort on the subarrays until the entire array is sorted.

• Time complexity can be optimized to NlogN for worst-case scenarios.

Find two lines to form a container with maximum water capacity based on given heights.

• Iterate through the array and use two pointers to find the maximum area.

• Calculate the area using the formula: min(height[left], height[right]) * (right - left).

• Move the pointer with the smaller height towards the center to potentially find a larger area.

Find the total number of distinct paths in a maze with obstacles from top-left to bottom-right cell.

• Use dynamic programming to keep track of the number of paths to reach each cell.

• Handle blocked cells by setting their path count to 0.

• Only move right or down from any given cell to calculate the number of paths.

• Return the total number of valid paths modulo 10^9 + 7.

Minimize cash flow among friends by optimizing transactions.

• Create a graph where nodes represent friends and edges represent transactions.

• Calculate net amount each friend owes or is owed by summing up all transactions.

• Use a recursive algorithm to minimize cash flow by settling debts between friends.

• Update the graph after each settlement and continue until all debts are settled.

• Output the minimized cash flow in a 2-D matrix for each test case.

Given a list of integers, find the next greater element for each element in the list.

• Iterate through the list from right to left and use a stack to keep track of elements.

• Pop elements from the stack until a greater element is found or the stack is empty.

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

• If no greater element is found, store -1 in the result array.

The task is to find the length of the longest common subsequence between two given strings.

• Implement a function to find the longest common subsequence between two strings.

• Use dynamic programming to solve this problem efficiently.

• Iterate through the strings and build a matrix to store the lengths of common subsequences.

• The value in the bottom-right corner of the matrix will be the length of the longest common subsequence.

Group anagrams together in a list of strings.

• Iterate through the list of strings and sort each string to group anagrams together.

• Use a hashmap to store the sorted string as key and the original string as value.

• Return the values of the hashmap as the grouped anagrams.

Maximize profit by scheduling jobs within their deadlines.

• Sort the jobs array in descending order of profits.

• Iterate through the sorted array and schedule jobs based on deadlines.

• Keep track of completed jobs and their profits to calculate the total profit.

• Return the maximum profit achieved by scheduling jobs within deadlines.

Add two numbers represented by linked lists and return the result as a new linked list.

• Traverse both linked lists simultaneously while adding corresponding elements and carry over the sum if needed

• Handle cases where one linked list is longer than the other

• Create a new linked list to store the sum of the two numbers

Implement Merge Sort algorithm to sort a sequence of numbers in non-descending order.

• Implement the Merge Sort algorithm which involves dividing the array into two halves, sorting each half, and then merging them back together.

• Recursively call the Merge Sort function on each half of the array until the base case of having a single element in the array is reached.

• Merge the sorted halves back together in a new array in non-descending order.

• Ensure to handle the edge cases such as...read more

Implement a function to print the zigzag traversal of a binary tree.

• Use a queue to perform level order traversal of the binary tree.

• Maintain a flag to switch between printing nodes from left to right and right to left at each level.

• Store nodes at each level in a list and reverse the list if the flag is set to print in zigzag order.

The task is to find the minimum number of characters needed to insert into a given string to make it a palindrome.

• Use dynamic programming to find the longest palindromic subsequence of the given string.

• Subtract the length of the longest palindromic subsequence from the length of the original string to get the minimum insertions required.

• Handle edge cases like an empty string or a string that is already a palindrome.

• Example: For input 'abcaa', the longest palindromic subsequen...read more

The task is to determine the lexicographically smallest array that can be obtained by performing at most 'K' swaps of consecutive elements.

• Sort the array in non-decreasing order and keep track of the number of swaps made.

• Iterate through the array and swap adjacent elements if it results in a lexicographically smaller array.

• Continue swapping until the maximum number of swaps 'K' is reached or the array is lexicographically smallest.

• Return the final lexicographically smallest a...read more

Given an array and a target sum, find a subarray that sums up to the target sum.

• Iterate through the array while keeping track of the running sum and the starting index of the subarray.

• Use a hashmap to store the running sum and its corresponding index.

• If the running sum - target sum is found in the hashmap, it means a subarray with the target sum exists.

• Return the starting and ending indices of the subarray or [-1, -1] if no such subarray exists.

Find the largest element in a sorted array smaller than or equal to a given integer X.

• Use binary search to efficiently find the floor value of X in the sorted array.

• Compare the middle element of the array with X and adjust the search accordingly.

• Return the element before or equal to X as the floor value, or -1 if no such element exists.

Function to swap '3' and '4' without using if-else

• Use XOR operator to swap the values

• Convert the input to ASCII code and perform the swap

• Use a lookup table to map the values

Finding an element in a sorted 2D matrix

• Start from the top right corner or bottom left corner

• Compare the target element with the current element

• Move left or down if the target is smaller, else move right or up

• Repeat until the target is found or all elements are checked

The interviewer asked about JavaScript questions and the work culture of the team during the managerial round.

• JavaScript questions related to closures, prototypes, event handling, and asynchronous programming may have been asked.

• Work culture may involve collaboration, innovation, agile methodologies, and continuous learning.

• Examples of work culture could include regular team meetings, code reviews, hackathons, and mentorship programs.

Find the odd repeating element from an array of strings

• Use a hash table to count the frequency of each element

• Iterate through the hash table to find the element with an odd count

Design a dictionary using trie with insert, update and delete operations.

• Implement a Trie data structure with nodes containing a character and a boolean flag to indicate end of word

• For insert operation, traverse the trie and add nodes for each character in the word

• For update operation, delete the existing word and insert the updated word

• For delete operation, mark the end of word flag as false and delete the node if it has no children

• Use recursion for traversal and deletion

• Exa...read more

Print all the connected components in a given graph.

• Traverse the graph using DFS or BFS algorithm.

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

• For each unvisited node, perform DFS or BFS and add all visited nodes to a connected component.

• Repeat until all nodes are visited.

• Print all connected components.

SQL query to find Nth highest salary from table

• Use ORDER BY and LIMIT clauses

• Use subquery to get the Nth highest salary

• Handle cases where there are less than N distinct salaries

Fill the glass to the brim, then pour out exactly half.

• Fill the glass completely with water

• Pour the water into another container until the glass is half full

• Pour the remaining water back into the glass

A program to find the minimum length of a string containing a given substring.

• Use a sliding window approach to iterate through the string and check for the substring.

• Keep track of the minimum length of the string containing the substring.

• Return the minimum length found.

Program to create a spiral array using 2D-array

• Create a 2D-array with given dimensions

• Initialize variables for row, column, and direction

• Fill the array in a spiral pattern by changing direction when necessary

• Return the spiral array

Sharding is a database partitioning technique to improve performance and scalability by distributing data across multiple servers.

• Sharding involves breaking up a database into smaller, more manageable parts called shards.

• Each shard contains a subset of the data, allowing for parallel processing and improved performance.

• Sharding helps distribute the workload across multiple servers, preventing bottlenecks and improving scalability.

• Examples of sharding implementations include M...read more

Types of DS and a real life scenario

• Arrays - storing a list of names

• Linked Lists - managing a playlist

• Stacks - undo/redo functionality in text editors

• Queues - managing customer requests in a call center

• Trees - organizing files in a computer

• Graphs - social network connections

OOPs in Python refers to Object-Oriented Programming concepts like classes, objects, inheritance, encapsulation, and polymorphism.

• Classes: Blueprint for creating objects with attributes and methods.

• Objects: Instances of classes that contain data and behavior.

• Inheritance: Ability to create a new class based on an existing class.

• Encapsulation: Restricting access to certain components of an object.

• Polymorphism: Ability to use a single interface for different data types.

Multithreading is the ability of a CPU to execute multiple threads concurrently.

• Allows for parallel execution of tasks

• Improves performance by utilizing multiple CPU cores

• Requires synchronization to prevent race conditions

• Example: Running a web server that can handle multiple client requests simultaneously