Paytm Interview Questions, Process, and Tips

Round duration - 45 minutes
Round difficulty - Medium

The nature of the interviewer was very kind. The test was proctored, our webcam and mic were on, and shared my screen.

Q1. Diagonal Traversal of a binary tree.
You have been given a binary tree of integers. You are supposed to find the diagonal traversal(refer to Example) of the given binary tree.
Example:
Consider lines at...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 by CodingNinjas
Add your answer
Q2. Diameter Of Binary Tree
You are given a Binary Tree. You are supposed to return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two end...read more
Ans. Recursion
The basic idea of this approach is to break the problem into subproblems. 
Now, there are three possible cases:
 
1. The diameter of the tree is present in the left subtree.
2. The diameter of the tree is present in the right subtree.
3. The diameter of the tree passes through the root node.
 
Let us define a recursive function, ‘getDiamter’, which takes the root of the binary tree as input parameter and return...read more
Answered by CodingNinjas
View 1 more answer

Round duration - 45 Minutes
Round difficulty - Medium

The nature of the interviewer was very kind, helped me when I stuck. The test was proctored, our webcam and mic were on, and shared my screen.

Q1. Next Greater Element
For a given array/list of integers of size N, print the Next Greater Element(NGE) for every element. The Next Greater Element for an element X is the first element on the right side of...read more
Ans. Brute Force
For every element in the array, we will run a loop on its right side. As soon as we find an element on its right side which is greater than it, we will break the loop, assign it as the NGE of this element, move forward, and do the same for the next element.
Space Complexity: O(1)Explanation:
O(1)
 
No extra space is used.
Time Complexity: O(n^2)Explanation:
O(N ^ 2),  Where N is the number of elements ...read more
Answered by CodingNinjas
View 1 more answer
Q2. Subset Sum Equal To K
You are given an array/list ‘ARR’ of ‘N’ positive integers and an integer ‘K’. Your task is to check if there exists a subset in ‘ARR’ with a sum equal to ‘K’.
Note: Return true if ...read more
Ans. Recursion
The idea is to generate all possible subsets and check if any of them sums up to ‘K’. This can be done through recursion.
 
Here is the algorithm:
 
subsetSumToK(N , K , ARR):
1. Initialize integer variable ‘ANS’ = ‘helper(ARR, N, K)’. Here ‘helper’ is the recursive function that returns true/false.
2. If ‘ANS’ is equal to 1 then:
   • Return true.
3. Else:
   • Return false.
 
helper(ARR, N, K):
1. Base case: If ‘N’ is less tha...read more
Answered by CodingNinjas
View 2 more answers

Round duration - 45 Minutes
Round difficulty - Medium

The nature of the interviewer was very kind, helped me when I stuck. The test was proctored, our webcam and mic were on, and shared my screen.

Q1. Buy and Sell Stock
You are Harshad Mehta’s friend. He told you the price of a particular stock for the next ‘N’ days. You can either buy or sell a stock. Also, you can only complete at most 2-transactions....read more
Ans. Recursion
This problem can be solved by solving its subproblems and then combining the solutions of the solved subproblems to solve the original problem. We will do this using recursion.
Basically, we have to buy the stock at the minimum possible price and sell at the maximum possible price, keeping in mind that we have to sell the stock before buying it again.
 
 
Below is the detailed algorithm: 
 
1. Call ...read more
Answered by CodingNinjas
View 3 more answers
Q2. DBMS Questions
SQL command
ACID properties
Difference between unique primary and foreign key.
Add your answer
Q3. OS Questions
What is segementation.
Difference between internal and external fragmentation.
Add your answer

Round duration - 60 minutes
Round difficulty - Easy

Coding round with 3 coding questions.

Q1. Print Nodes at distance K from a given node
You are given an arbitrary binary tree, a node of the tree, and an integer 'K'. You need to find all such nodes which have a distance K from the given no...read more
Ans. DFS
• Create a map to store the parent of each node in the tree, Traverse the tree recursively (via depth-first search), at each step if the current node is not NULL. Store its parent in the map, then traverse the left and right subtree.
• Now assume that the given node is the root of the tree. In such a case, we can simply run a breadth-first search from the root, and track the current level of the tree. When the level = ‘K...read more
Answered by CodingNinjas
View 1 more answer
Q2. Rahul And Minimum Subarray
Rahul is a programming enthusiast. He is currently learning about arrays/lists. One day his teacher asked him to solve a very difficult problem. The problem was to find the leng...read more
Ans. Brute Force
The basic idea of this approach is to iterate the whole ‘ARR’ from start and find the sum of all the possible subarrays and find out the length of the minimum subarray whose sum is greater than the given value. We will use two loops and calculate the sum for all the possible subarrays and select the subarrays that match our given conditions.
 
Here is the algorithm:
 
1. Declare a variable ‘MIN_LENGTH’ wh...read more
Answered by CodingNinjas
View 1 more answer
Q3. Encrypt The Digits
Given a numeric string ‘STR’ which is a string containing numeric characters from ‘0’ to ‘9’, you have to encrypt the string by changing each numeric character as shown below:
‘0’ ->...read more
Ans. Iterating
The idea is to simply encrypt each character using switch case statement or if-else ladder, where output character for each input character is taken care of.
 
Here is the algorithm:
 
1. Run a loop from 0 to ‘N-1’ (say iterator = i):
   • Initialize a character ‘ch’ = ‘STR[i]’.
   • Use an if-else ladder to initialize the value of ‘STR[i]’ according to ‘ch’. For eg - if ‘ch’ equals ‘0’ , ‘STR[i]’ = ‘9’, if ‘ch’ equals...read more
Answered by CodingNinjas
View 1 more answer

Round duration - 50 minutes
Round difficulty - Medium

The nature of the interviewer was very kind. The test was proctored, our webcam and mic were on, and shared my screen.

Q1. Diagonal Traversal of a binary tree.
You have been given a binary tree of integers. You are supposed to find the diagonal traversal(refer to Example) of the given binary tree.
Example:
Consider lines at...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 by CodingNinjas
Add your answer
Q2. Parth And His OCD
Parth is a nerd programmer. He has started learning array/list programming. Parth has received an array/list ‘ARR’ of ‘N’ positive integers as a gift. Parth’s OCD gets triggered every tim...read more
Ans. Brute Force
The basic idea of this approach is to iterate the whole ‘ARR’ from start and see if the element present at the current position satisfies the conditions or not. If the element at the current index is not as per requirement then we will find an element which can take that position from ‘ARR’ after that index and replace it with the current element. 
 
Here is the algorithm:
 
1. Run a loop for ‘i’ = 0...read more
Answered by CodingNinjas
View 2 more answers

Round duration - 50 minutes
Round difficulty - Easy

The nature of the interviewer was very kind. The test was proctored, our webcam and mic were on, and shared my screen.

Q1. Subset Sum Equal To K
You are given an array/list ‘ARR’ of ‘N’ positive integers and an integer ‘K’. Your task is to check if there exists a subset in ‘ARR’ with a sum equal to ‘K’.
Note: Return true if ...read more
Ans. Recursion
The idea is to generate all possible subsets and check if any of them sums up to ‘K’. This can be done through recursion.
 
Here is the algorithm:
 
subsetSumToK(N , K , ARR):
1. Initialize integer variable ‘ANS’ = ‘helper(ARR, N, K)’. Here ‘helper’ is the recursive function that returns true/false.
2. If ‘ANS’ is equal to 1 then:
   • Return true.
3. Else:
   • Return false.
 
helper(ARR, N, K):
1. Base case: If ‘N’ is less tha...read more
Answered by CodingNinjas
View 2 more answers
Q2. Next Greater Element
For a given array/list of integers of size N, print the Next Greater Element(NGE) for every element. The Next Greater Element for an element X is the first element on the right side of...read more
Ans. Brute Force
For every element in the array, we will run a loop on its right side. As soon as we find an element on its right side which is greater than it, we will break the loop, assign it as the NGE of this element, move forward, and do the same for the next element.
Space Complexity: O(1)Explanation:
O(1)
 
No extra space is used.
Time Complexity: O(n^2)Explanation:
O(N ^ 2),  Where N is the number of elements ...read more
Answered by CodingNinjas
View 1 more answer

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
Given a matrix where every element is either 1 or 0(zero), replace 0 with 1 if surrounded by 1. A 0 (or a set of 0s) is considered to be surrounded by 1 if there are 1 at locations just below, j...read more
Ans. 
I made some syntax errors in this one. Be careful.
Answered by CodingNinjas
View 1 more answer
Q2. Ways To Make Coin Change
You are given an infinite supply of coins of each of denominations D = {D0, D1, D2, D3, ...... Dn-1}. You need to figure out the total number of ways W, in which you can make a cha...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 by CodingNinjas
View 4 more answers
Q3.  Partition a set into two subsets such that the difference of subset sums is minimum.
You are given an array containing N non-negative integers. Your task is to partition this array into two subsets such t...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 by CodingNinjas
View 2 more answers

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
Given a string (STR) of length N, you have to create a new string by performing the following operation:
Take the smallest character from the first 'K' characters of STR, re...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 by CodingNinjas
View 2 more answers
Q2.  Design a stack that supports getMin() in O(1) time and O(1) extra space
Implement a SpecialStack Data Structure that supports getMin() in O(1) time and O(1) extra space along with 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 by CodingNinjas
View 3 more answers
Q3. Number of GP sequence
You are given an array containing ‘N’ integers. You need to find the number of subsequences of length 3 which are in Geometric progression with common ratio ‘R’.
A geometric progre...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 by CodingNinjas
View 2 more answers
Q4. Operating System
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 by CodingNinjas
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
You have been given an array/list of strings 'inputStr'. You are supposed to return the strings as groups of anagrams such that strings belonging to a particular group are anagrams o...read more
Ans. 
I used hash maps to solve the problems.
 
Answered by CodingNinjas
View 1 more answer
Q2. Kth Smallest Element
You are given an array of integers 'ARR' of size 'N' and another integer 'K'. Your task is to find and return 'K'th smallest value present in the array.
...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 by CodingNinjas
View 3 more answers

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 Linked List
Given the head node of the singly linked list, return a pointer pointing to the middle of the linked list.
If there are an odd number of elements, return the middle element if there...read more
Ans. 
Used hare and tortoise method to solve this problem.
Answered by CodingNinjas
View 2 more answers

Can't Disclose