10+ Paytm Software Developer Interview Questions and Answers for Freshers

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

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.

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.

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.

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.

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