PhonePe Software Engineer- Backend (0 to 3 Years) Pune

DSA round 1

Q1. Given an array of integers arr and a integer k, you have to remove exactly k elements either from the start or the end or a mix of both.

Return maximum sum of integers that can be removed

Example 1:
Input:

	arr = [1,2,3,4,5]
	k = 2
	

Output:
9

Example 2:
Input:

	arr = [5,1,2,3,4]
	k = 2
	

Output:
9

Q2. You are given a string s. You can add any character at any place in the string. Output the minimum number of characters that have to be added to string to make it a palindrome

Example 1:
Input:

	s = "abcd"
	

Output:
3

Example 2:
Input:

	s = "abac"
	

Output:
1

Example 3:
Input:

	s = "abdab"
	

Output:
2

---

DSA round 2

Q1. Given a string s, and integer k, you have to perform this operation as many times as possible:

Remove k consecutive characters from s which are same, and concatenate the left and right part.

Return the string after the above operation can no longer be performed.

Example 1:
Input:

	s = "abdc"
	k = 2
	

Output:
"abdc"

Example 2:
Input:

	s = "abbadc"
	k = 2
	

Output:
"dc"

Example 3:
Input:

	s = "pqqqqppeeeeepppqq"
	k = 5
	

Output:
"pq"

Q2. You are given a undirected graph G in form of adjacency matrix of size n x n, containing n nodes, indexed from 0 to n-1. You are also given a list of infected nodes infected.

A healthy node is infected if it connected to the infected node. At time t=0 the nodes in infected are the only nodes that are infected. But after time, more and more nodes get infected, as the infection propagates. Let's say at t=infinite, there are MAX_INFECTED nodes.

Now you can disinfect one and only one, at the start at t=0. Your task is to find a node n, disinfecting which will minimise the MAX_INFECTED nodes count. Print that node's index. If more that one node can cause minimum MAX_INFECTED, return the node with smallest index.

Example 1:
Input:

	G = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
	infected = [0, 2]
	

Output:
0

Example 2:
Input:

	G = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
	infected = [1, 2]
	

Output:
1

Example 3:
Input:

	G = [[1, 1, 0], [1, 1, 0], [0, 0, 1]]
	infected = [0, 1]
	

Output:
0

Explanation

3 nodes are there. node 0 and node 1 are connected, and node 2 is not connected to anything.

• Example 1: removing infection from 0 will cause MAX_INFECTED = 1, which is minimum
• Example 2: removing infection from 1 will cause MAX_INFECTED = 1, which is minimum
• Example 3: removing infection from either 0 or 1 will cause MAX_INFECTED = 2, but 0 has smaller index, so res=0

---

Managerial round

• Intro
• Why changing company
• Why phonepe
• Current company project discussion in detail
• What and why in current company project
• Design blinkit. High variation in number of users of users and number of dark store per square area. (And a lot of roasting here)

Result

Rejected.