Paytm Software Engineer Interview Questions, Process, and Tips

Q1. Coding Stack Question
Add your answer

Q1. Kind of mathematical Data structures Question. DBMS question. SQL.
Add your answer

Round duration - 70 minutes
Round difficulty - Medium

Q1. 
Subtree of Another Tree Problem Statement
Given two binary trees, T and S, determine whether S is a subtree of T. The tree S should have the same structure and node values as a subtree of T.
Explanation:
...read more
Ans. 
For each node during pre-order traversal of s, use a recursive function isSame to validate if sub-tree started with this node is the same with t.
Answered Anonymously
Add your answer
Q2. 
Generate Binary Strings with No Consecutive 1s
Given an integer K, your task is to produce all binary strings of length 'K' that do not contain consecutive '1's.
Input:
The input begins with an integer ...read more
Ans. 
You can easily observe pattern. It is a Fibonacci sequence 
Answered Anonymously
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

This was a data structures round.

Q1. 
Longest Consecutive Sequence Problem Statement
You are provided with an unsorted array/list ARR of N integers. Your task is to determine the length of the longest consecutive sequence present in the array...read more
Ans. 
I thought of two points on a number line a and b and formulated a consecutive sequence [a....b], (b*(b+1))/2-(a*(a+1))/2=n. Now we have a clearly quadratic solution by brute-forcing a and b but if we simplify it further we have (b-a+1)*(b+a) = 2*n. So now we can easily find all divisors of 2*n and satisfy the equation for which we get a>=0 and b>=0 and thus we get the answer.
Answered Anonymously
Add your answer
Q2. 
Permutations Problem Statement
Given an array of distinct integers, find all possible permutations of the array.
Explanation:
A permutation is a mathematical way of determining the number of possible ar...read more
Ans. 
I knew the recursive solution as it is a very popular interview problem.The idea is much like the insertion sort. We start with only the first number, and pick next number from the rest of array, insert it to the front or back position of the first number, and pick the third number, insert it to front or mid or back position of the [first, second] array, and so on, until no element left.
Answered Anonymously
Add your answer

Round duration - 60 minutes
Round difficulty - Easy

This was a data structures round.

Q1. 
Subsequence Determination Problem
Your task is to verify if the given string STR1 is a subsequence of the string STR2. A subsequence means characters from STR2 are retained in their original order but som...read more
Ans. 
Easy problem iterate over the longer string and keep a counter for matching it with shorter string if a match occurs while iterating longer string increment the counter and if we have done iterating on the longer string if the counter value is equal to shorter string length then return true else return false.
Answered Anonymously
Add your answer
Q2. 
Minimum Falling Path Sum Problem Statement
Given a square array VEC of integers with N rows and N columns, you need to determine the minimum sum of a falling path through this square array. The array has ...read more
Ans. 
It was also an easy problem as I had done it before.The minimum path to get to element A[i][j] is the minimum of A[i - 1][j - 1], A[i - 1][j] and A[i - 1][j + 1]. Starting from row 1, we add the minimum path to each element. The smallest number in the last row is the minimum path sum.
Answered Anonymously
Add your answer

Round duration - 25 minutes
Round difficulty - Easy

This round was all about OS/DBMS questions.

Round duration - 90 Minutes
Round difficulty - Medium

The test was organized online on Amcat and there were 3 coding problems. There were no MCQs in this round.

Q1. 
Ninja Technique Problem Statement
Implement a function that determines whether a given numeric string contains any substring whose integer value equals the product of two consecutive integers. The functio...read more
Ans. Iterative Approach
• We have to find out all the substring of our given string. For this, we use the function ‘subString’ which takes the length of our string and our string ‘str’.
• We have to run three nested loops:
  • First loop iterate starting ‘i’ from ‘0’to size of string ‘str’
  • Iterate second nested loop  ‘i’ from ‘0’to ‘n-i+1
  • Through our third nested loop, we choose a starting point and ending point and provide values ...read more
Answered Anonymously
Add your answer
Q2. 
Find Nodes at a Specific Distance from Target in a Binary Tree
Given a binary tree, a target node within this tree, and an integer K, identify and return all nodes that are exactly K edges away from the t...read more
Ans. Recursion
Suppose from the current node, if the target node is at depth ‘X’ in the left subtree. So that nodes at distance ‘K-X’ in the right subtree should be part of the answer array and it is ‘K’ distance from the given target node. Go to ROOT→LEFT, now target node is at depth ‘X-1’ from the CURRENTNODE(ROOT->LEFT), then find all the nodes that are ‘K - X + 1’ depth and all should be added to the answer.
 
1. Two ...read more
Answered Anonymously
Add your answer

Round duration - 50 Minutes
Round difficulty - Medium

This round was scheduled by the college Training and Placement team virtually. The interviewer asked me questions pertaining mainly to DSA and we discussed my projects.

Q1. 
Segregate Even and Odd Nodes in a Linked List
You are given the head node of a singly linked list head. Your task is to modify the linked list so that all the even-valued nodes appear before all the odd-v...read more
Ans. Brute Force Approach
The basic idea is to divide the linked list into two parts - odd and even. The even linked list will contain only nodes whose value is even and vice - versa for the odd linked list. Finally, we will attach the odd linked list after the even linked list.
 
Algorithm
 
• Use four pointers ‘evenStart =null’, ‘oddStart =null’, ‘evenLast =null’, ‘oddLast =null’.
• Copy the ‘head’ of the linked list in ‘...read more
Answered Anonymously
Add your answer

Round duration - 60 Minutes
Round difficulty - Easy

Again, the round was virtual. This was a Tech + Managerial round organized by the college T & P cell. The interviewer asked questions related to fundamental subjects such as Operating Systems, Object-oriented programming, and DBMS. There was one coding round at the end.

Q1. 
Diagonal Traversal of a Binary Tree
Given a binary tree of integers, find its diagonal traversal. Refer to the example for clarification on diagonal traversal.
Example:
Explanation:
Consider lines at a...read more
Ans. Map based approach
The idea is to use the Map to store all the nodes of a particular diagonal number. We will use preorder traversal to update the Map. The key of the Map will be the diagonal number and the value of the Map will be an array/list that will store all nodes belonging to that diagonal. 
 
The steps are as follows:
 
1. Assign the diagonal number of the root as 0.
2. Do a preorder traversal of the binary...read more
Answered Anonymously
Add your answer

Round duration - 40 Minutes
Round difficulty - Easy

The round was virtual and was organized by the T & P cell of the college. The interviewer asked some behavioural and situation-based questions. There was one puzzle at the end.

Round duration - 60 minutes
Round difficulty - Medium

It was held in the evening around 4 pm. The camera was on during the test to invigilate the activity of students. On any doubtful action, warning was given. Platform was easy to code in.

Q1. 
Replace 0s Problem Statement
You are given a matrix where every element is either a 1 or a 0. The task is to replace 0 with 1 if it is surrounded by 1s. A 0 (or a set of 0s) is considered to be surrounded...read more
Ans. 
I made some syntax errors in this one. Be careful.
Answered Anonymously
Add your answer
Q2. 
Ways To Make Coin Change
Given an infinite supply of coins of varying denominations, determine the total number of ways to make change for a specified value using these coins. If it's not possible to make...read more
Ans. 
This was a greedy problem.
1. Sort the array of coins in decreasing order. Initialize result as empty.
2. Find the largest denomination that is smaller than current amount.
3. Add found denomination to result.
4. Subtract value of found denomination from amount.
5. If amount becomes 0, then print result.
6. Else repeat steps 3 and 4 for new value of V.
Answered Anonymously
Add your answer
Q3. 
Minimum Subset Sum Difference Problem
Given an array of non-negative integers, your task is to partition this array into two subsets such that the absolute difference between the sums of the subsets is mi...read more
Ans. 
The recursive approach is to generate all possible sums from all the values of the array and to check which solution is the most optimal one. 
To generate sums we either include the i’th item in set 1 or don’t include, i.e., include in set 2.
More optimized solution is Dynamic Programming.
Answered Anonymously
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

It was held in the morning around 11:30 am. The interview was scheduled on google meet. The interviewer was quite friendly. He started by a brief introduction. This round was mostly based on Data structures and algorithms. At the end he asked some concepts of OOPs and Operating System.

Q1. 
String Transformation Problem
Given a string (STR) of length N, you are tasked to create a new string through the following method:
Select the smallest character from the first K characters of STR, remov...read more
Ans. Brute Force Approach
• Create a new “answer” string that will contain the modified string
• While the input string's length is greater than 0
  • Find the minimum character in the first K characters of the string (or the entire string if its length is less than K)
  • Append that character to the “answer” string
  • Remove that character from the input string
• Return the “answer” string
Space Complexity: O(1)Explanation:
O(1)
 
Since we ar...read more
Answered Anonymously
Add your answer
Q2. 
SpecialStack Design Problem
Design a stack that efficiently supports the getMin() operation in O(1) time with O(1) extra space. This stack should include the following operations: push(), pop(), top(), is...read more
Ans. 
1. Start from brute force approach by using another stack.
2. Optimise it with reducing push and pop operations.
3. Optimise it to O(1) space complexity.
Answered Anonymously
Add your answer
Q3. 
Geometric Progression Subsequences Problem Statement
Given an array of ‘N’ integers, determine the number of subsequences of length 3 that form a geometric progression with a specified common ratio ‘R’.
...read more
Ans. 
1. I started with brute force approach using three loops.
2. I optimized it to two loops by using sorting and two pointer technique.
Answered Anonymously
Add your answer
Q4. What are the conditions for a deadlock to occur?
Ans. 
Tip 1 : Explain what deadlock is briefly.
Tip 2 : Be confident while answering.
Tip 3 : Explain its conditions in detail. Refer to youtube channel gate smashers for clarity of topic.
Answered Anonymously
Add your answer

Round duration - 45 minutes
Round difficulty - Medium

It was held in the afternoon around 3pm. The interviewer was quite friendly. She started with my introduction. She asked 2-3 problems related to data structures and then asked about python libraries which I used in my projects.

Q1. 
Group Anagrams Problem Statement
Given an array or list of strings called inputStr, your task is to return the strings grouped as anagrams. Each group should contain strings that are anagrams of one anoth...read more
Ans. 
I used hash maps to solve the problems.
 
Answered Anonymously
Add your answer
Q2. 
Kth Smallest Element Problem Statement
You are provided with an array of integers ARR of size N and an integer K. Your task is to find and return the K-th smallest value present in the array. All elements...read more
Ans. 
1. I started with brute force approach of sorting the array and then finding the kth smallest element. This was O(nlogn) approach.
2. Then I solved using heaps with an O(n) approach.
Answered Anonymously
Add your answer

Round duration - 45 minutes
Round difficulty - Medium

It was held in the evening around 6 pm. The interviewer started with a brief introduction of me. He asked about my projects and then asked some concepts of Operating System and problems related to data structures. I had projects of Machine Learning and Deep learning. Discussion about projects continued for about 25 minutes.

Q1. 
Middle of a Linked List
You are given the head node of a singly linked list. Your task is to return a pointer pointing to the middle of the linked list.
If there is an odd number of elements, return the ...read more
Ans. 
Used hare and tortoise method to solve this problem.
Answered Anonymously
Add your answer