Paytm Software Developer Interview Questions, Process, and Tips for Freshers

Two questions on dynamic programming

This was a behavioural round and was completely non technical

Round duration - 70 Minutes
Round difficulty - Medium

Their were 3 DSA coding questions of medium and hard level. I need to solve them in 70 minutes. Coding questions were of Arrays, Linked list and Binary search trees

Q1. Reverse Linked List
Given a singly linked list of integers. Your task is to return the head of the reversed linked list.
For example:
The given linked list is 1 -> 2 -> 3 -> 4-> NULL. Then th...read more
Ans. Brute Force
The brute force approach is to use recursion. First, we reach the end of the Linked List recursively and at last node, we return the last node, which becomes the new head of the partially reversed Linked List. While coming back from each recursion call we add the current node in the current recursion call to the last node of the partially reversed Linked List and assign the current node to null.
 
Steps:
&...read more
Answered by CodingNinjas
View 5 more amswers
Q2. Sort An Array of 0s, 1s and 2s
You have been given an array/list ARR consisting of ‘N’ elements. Each element in the array is either 0, 1 or 2.
Now, your task is to sort this array/list in increasing ord...read more
Ans. NAIVE APPROACH
Simply, we will sort the array.
Space Complexity: O(1)Explanation:
O(1), i.e. constant space complexity. 
 
Since we are not using any extra space. Hence, the space complexity is constant.
Time Complexity: O(nlogn)Explanation:
O(Nlog(N)), where N is the length of the array/list.
 
Since we are using the inbuilt sort function. Hence, the time complexity is O(Nlog(N)).

Java (SE 1.8)

/*

    Time Compl...read more
Answered by CodingNinjas
View 2 more amswers

Round duration - 60 Minutes
Round difficulty - Medium

This round was majorly focused on problem solving skills and DSA. Interviewer asked me three DSA questions of medium and hard level. He started with the hard question, he asked me zig-zag binary tree traversal. we discussed the approach than I coded it and explained its Time and space complexity. Than he asked me max sum subarray modified question, I solved it using Kadane algorithm. Than he discussed one of my online assesments question and asked me to further optimize that approach that I used in the online test. Than I optimized that approach and coded that. Than he asked me for any questions and we dropped the call.

Q1. Spiral Order Traversal of a Binary Tree
You have been given a binary tree of 'N' nodes. Print the Spiral Order traversal of this binary tree.
For example
For the given binary tree [1, 2, 3, -1, -...read more
Ans. Level Order Traversal
We can use level order traversal (recursive) to explore all levels of the tree. Also, at each level nodes should be printed in alternating order. 
 
For example - The first level of the tree should be printed in left to the right manner, the Second level of the tree should be printed in right to the left manner, Third again in left to right order and so on
 
So, we will use a Direction v...read more
Answered by CodingNinjas
View 2 more amswers
Q2. Maximum Subarray Sum
Given an array of numbers, find the maximum sum of any contiguous subarray of the array.
For example, given the array [34, -50, 42, 14, -5, 86], the maximum sum would be 137, since w...read more
Ans. Brute Force Approach
1. Create a nested loop. The outer loop will go from i = 0 to i = n - k. This will cover the starting indices of all k-subarrays
2. The inner loop will go from j = i to j = i + k - 1. This will cover all the elements of the k-subarray starting from index i
3. Keep track of the maximum element in the inner loop and print it.
Space Complexity: O(1)Explanation:
O(1) because the extra space being used (looping vari...read more
Answered by CodingNinjas
View 3 more amswers

Round duration - 40 Minutes
Round difficulty - Medium

This round was mainly focused on operating systems, DBMS and past projects. we started with the introduction. Interviewer asked me explain a functionality of one of my projects that I wrote in my resume, I done that than he started asking OS and DBMS questions. After that we asked me about any bad experience in my past internship, I told that than he asked for any questions to me and we dropped the call and after 2 days I got HR mail that I'm selected.

Q1. Operating System based Questions
Questions about scheduling algorithms, dead lock, synchronization etc. were asked.
Add your answer

Round duration - 75 minutes
Round difficulty - Easy

This round was conducted in Hackerrank portal for a total duration of 75 minutes and was divided into 4 sections.

1st Section : Aptitude Section : 14 questions , 28 minutes
2nd Section : Technical Section : 12 questions , 17 minutes
3rd Section :1 coding Questions : 20 minutes+30 minutes

This Round was Conducted on Hackerrank (Webcam Enabled).

Q1. Container with most water
Given a sequence of ‘N’ space-separated non-negative integers A[1],A[2],A[3],......A[i]…...A[n]. Where each number of the sequence represents the height of the line drawn at poin...read more
Ans. Brute Force Approach
Since we need to find the container with most water, let us try to find all possible containers and choose the one which has the maximum area.
So how can we find the area of all possible containers?
We can, for each line with the position ‘i’ find another line ‘j’ such that ‘j’ > ‘i’ and find the amount of water contained i.e (‘j’-’i’)*min('A[i]', ‘A[j]’) where ‘A[i]’ and ‘A[j]’ represents the heig...read more
Answered by CodingNinjas
View 1 more amswer
Q2. Maze obstacles
Given a ‘N’ * ’M’ maze with obstacles, count and return the number of paths to reach the right-bottom cell from the top-left cell. A cell in the given maze has a value -1 if it is a blockage...read more
Ans. Recursion
We can observe that we can reach cell (i, j) only through two cells if they exist -
(i - 1, j) and (i, j - 1). Also if the cell (i, j) is blocked we can simply calculate the number of ways to reach it as zero.
So if we know the number of ways to reach cell (i - 1, j) and (i, j - 1) we can simply add these two to get the number of ways to reach cell (i, j). 

 
Let paths(i, j) be the number of ways to reac...read more
Answered by CodingNinjas
View 2 more amswers

Round duration - 100 minutes
Round difficulty - Medium

This was an Online F2F Technical Round conducted on CodePair : Hackerrank. So, Basically You have to Run and Submit ( Pass All Test cases) in the Interview Round also (Like normal Coding Test) in Codepair : Hackerrank & along with that You should have to explain your Code and Approach to the Interviewers.
The Interviewers were helpful and didn't hesitate in giving hints.
Timing - 10:00 A.M to 12:00 P.M

Q1. Minimum Fountains
There is a one-dimensional garden of length 'N'. On each of the positions from 0 to 'N', there is a fountain, and this fountain’s water can reach up to a certain range as ...read more
Ans. Dynamic programming
• For every fountain, we can try to find the pair area = (left, right), where left and right are the leftmost and the rightmost index respectively where the current fountain can reach.For every index 'I' = 0 to 'I' = 'N' -1, 'LEFT' = max(0, 'I' - 'ARR'['I']) and  'right' = min('I' + ('ARR'['I'] + 1), 'N').
• Now we can sort the array of pairs in non-decreasing order according to 'LEFT' to find the mi...read more
Answered by CodingNinjas
View 1 more amswer
Q2. Minimize Cash Flow
You are given a list of ‘transactions’ between ‘n’ number of friends. who have to give each other money. The list consists of data of receiver, sender, and transaction.
Your task is to...read more
Ans. Greedy
We can calculate the net amount of every person as-
Net amount = sum of all received money  - the sum of all sent money.
 
Find the person with the maximum and the minimum net amount, suppose ‘x’ person has maximum net amount ‘maxAmount’ and ‘y’ person has a minimum amount ‘minAmount’, then ‘y’ person will pay ‘minAmount’ to ‘x’ person after this transaction net amount of ‘x’ person is ‘maxAmount = maxAmou...read more
Answered by CodingNinjas
Add your answer

Round duration - 30 minutes
Round difficulty - Easy

This was a Telephonic Round (Audio Call). The HR was friendly and asked basic questions.
The timing was 2:00 PM to 2:30 PM.

Q1. Basic HR Questions
Who is your Ideal?
Why should we hire you?
Ans. 
Tip 1 : Prepare Subjects in Depth for Technical Coding & Interview Round. 
Tip 2 : All the Questions were basic in the HR Round ! Be Honest in HR Round as well as Technical Rounds.
Tip 3 : Be Confident in HR Round and don't hesitate while answering and explaining situation based questions.
Tip 4 : It is ok to ask the question again till you don't understand and take the time.
Answered by CodingNinjas
Add your answer

Round duration - 60 Minutes
Round difficulty - Easy

Q1. Lexicographically smallest array
You have been given an array/list ARR consisting of ‘N’ integers. You are also given a positive integer ‘K’.
Your task is to find the lexicographically smallest ARR that ...read more
Ans. Greedy Approach
Looking at the problem, we observe that-
• The lexicographically smallest ARR is obtained if the smallest element is present at the beginning i.e ARR[0], followed by the next smallest at index 1 (ARR[1]) and so on.
• The number of swaps to move an element from index ‘i’ to index ‘j’ (where i > j) is i - j as we can swap only neighbouring elements.
• The maximum swaps allowed are ‘K’.
 
Keeping the above poi...read more
Answered by CodingNinjas
Add your answer

Round duration - 20 Minutes
Round difficulty - Easy

Q1. Basic HR Questions
Who is your role model?
Why should we hire you?
Add your answer

Round duration - 70 minutes
Round difficulty - Easy

The first round was the Online Coding Round of 70 minutes with 3 problems of 3 marks, 3 marks, and 4 marks respectively.
The first two questions were easy and the third one was a bit tricky. The round started at 6 PM. 
Anyone who is practicing continuously could have solved these questions easily within the time limit. The test cases were also not so hard and distinct. I coded in C++ language.
The questions asked were-
1. Minimum insertions required to make a string palindrome
2. To find the distance of the closest leaf from a node with given data.
3. Add two numbers represented by linked lists

22 students were selected for the next round.

Q1. Minimum insertions to make a string palindrome
A palindrome string is one that reads the same backward as well as forward. Given a string 'STR', you need to tell the minimum number of characters ne...read more
Ans. 
I used a recursive approach to solve the problem.
Let's say we have a string S[L.......H].
Then our solution can be found as-
if(S[L]==S[H])
minInsertion(S[L+1....H-1]
else (minInsertion(S[L....H-1]), minInsertion(S[L+1....H])+1)
Answered by CodingNinjas
View 3 more amswers
Q2. Closest Leaf To Given Node In Binary Tree
Ninja is stuck in a maze which is in a form of a binary tree. He needs your help in order to get out.
Ninja is presently at the node ‘X’. The only exit points of...read more
Ans. 
I used a simple traverse approach to solve the question.
The idea was to first traverse the subtree rooted with give node and find the closest leaf in this subtree. Store this distance. Now traverse tree starting from root. If given node x is in left subtree of root, then find the closest leaf in right subtree, else find the closest left in left subtree.
Answered by CodingNinjas
View 2 more amswers
Q3.  Add two linked lists
You have been given two singly Linked Lists, where each of them represents a positive number without any leading zeros.
Your task is to add these two numbers and print the summation...read more
Ans. 
I used an optimized approach to solve it.
1. Reverse Both Lists
2. Now traverse both lists and add numbers
3. Reverse resultant linked list and return head
Answered by CodingNinjas
View 2 more amswers

Round duration - 80 minutes
Round difficulty - Easy

It was a technical interview. The platform used was google meet for online video calling. The interviewer first introduced himself then asked me to introduce myself. He also asked about my well-being amid the Covid-19 pandemic. He asked me 3 problems from data structures. He put a lot of focus on my project. We discussed about my project for about 20 mins. He asked various questions related to my project and I answered them confidently. After 70-75 mins he said that interview was over and that I may ask him anything. I asked him to give me feedback about my resume and my project. He gave me advice to improve my resume and the interview was over. The first technical interview was easy and was not so challenging as I was prepared.

Q1.  Two Sum
You are given an array of integers 'ARR' of length 'N' and an integer Target. Your task is to return all pairs of elements such that they add up to Target.
Note:
We cannot use t...read more
Ans. 
It is quite an easy problem if you know about arrays.
1. Firstly I sorted the array
2. Then I took 2 pointers.
3. I iterated one from start and other from end and checked sum at each step.
4. I returned the value of element if sum equals K else continue until start<= last
Answered by CodingNinjas
View 1 more amswer
Q2. Quick Sort
You are given an array of integers. You need to sort the array in ascending order using quick sort.
Quick sort is a divide and conquer algorithm in which we choose a pivot point and partition...read more
Ans. 
I explained the algorithm of Quick Sort and wrote its code in C++.He also asked me to explain its time complexity.
Answered by CodingNinjas
View 3 more amswers
Q3. Merge Sort
Given a sequence of numbers ‘ARR’. Your task is to return a sorted sequence of ‘ARR’ in non-descending order with help of the merge sort algorithm.
Example :
Merge Sort Algorithm -

Merge so...read more
Ans. 
I explained the algorithm of Merge Sort and wrote its code in C++.He also asked me to explain its time complexity.
Answered by CodingNinjas
View 2 more amswers

Round duration - 60 minutes
Round difficulty - Medium

This was also a technical round. The interviewer focused on data structures and resume. Apart from some basic questions about my resume, he asked majorly about data structures and algorithms. The interview was an hour long and he asked only 2 problems. Both of them were from trees. In this round, he focused if I can change my approach if a slight change is made in the question. Like he asked me to write code for inorder traversal. Obviously, I used a recursive approach. He then asked me to use the iterative method to find inorder traversal of the tree.

The questions he asked were-
1. Inorder traversal (both recursive and iterative method)
2. Level Order Traversal
( For obvious reasons I knew level order traversal very well. I coded it swiftly, so he asked me to write code for Zig-Zag traversal)

Q1. Inorder Sucessor
You have been given an arbitrary binary tree and a node of this tree. You need to find the inorder successor of this node in the tree.
The inorder successor of a node in a binary tree is...read more
Ans. 
1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
a) Pop the top item from stack.
b) Print the popped item, set current = popped_item->right
c) Go to step 3.
5) If current is NULL and stack is empty then we are done.

 
Answered by CodingNinjas
View 3 more amswers
Q2. Zig zag traversal
You have been given a Binary Tree of 'N' nodes, where the nodes have integer values. Your task is to print the zigzag traversal of the given tree.
Note:
In zigzag order, level 1...read more
Ans. 
1. Zigzag traversal can be implemented using two stacks.
2. Keep track of the direction to traverse using the bool variable isLtoR. If isLtoR is true, then the current level needs to be traversed from left to right and vice versa.
3. Push the root node into curr and set isLtoR to false for the next level.
4. Pop a node from curr and store it in the variable temp. Deduce the direction from isLtoR and decide, depending on t...read more
Answered by CodingNinjas
View 4 more amswers

Round duration - 50 minutes
Round difficulty - Medium

This was the final round of the Interview process. My interview was scheduled for 7.30 PM. It started at approximately 7.40 PM. The main focus of the interviewer was on my projects and my skills. He asked me many questions regarding my project like what problems I faced, what did you learn from this, apart from developing skills what else did you learn while developing the project, why did you use this tech instead of this, security features, scalability of the project and many more. I answered almost every question as perfectly as I can. Later he asked me some basic questions from NodeJS (as I am a full stack developer). In the end, he asked a puzzle. I didn't know the solution to the puzzle but we discussed it and I figured out the solution.

Q1. Camel and banana puzzle
A person has 3000 bananas and a camel. He wants to transport the maximum number of bananas to a destination 1000 KMs away, using only the camel as a mode of transportation. The camel...read more
Ans. 
Tip 1 : Instead of traveling the full distance in one go, divide the distance into 2/3 Parts.
Tip 2 : Try to maintain the number of remaining bananas multiple of 1000 at each intermediate point.
Answered by CodingNinjas
Add your answer