SDE - 1 MagicPIN interview experience | Anonymous

Interview rounds

Round

Easy

Video Call

Duration60 Minutes

Interview date15 Jun 2022

Coding problem3

This round was conducted on Google Meet and was taken by a Senior engineer at MagicPin. This round had 2 DSA questions followed by some SQL queries.

1. Best Time to Buy and Sell Stock II

Moderate

22m average time

0/80

Asked in companies

You have been given stock values/prices for N number of days. Every i-th day signifies the price of a stock on that day. Your task is to find the maximum profit which you can make by buying and selling the stocks.

Note :

You may make as many transactions as you want but can not have more than one transaction at a time i.e, if you have the stock, you need to sell it first, and then only you can buy it again.

Problem approach

We buy the stock on the day with least local rate and sell it when we find a peak that is raise in prices again. i.e; we just need to find the next greater element and subtract it from the current element so that the difference keeps increasing and so does the profit.
If the sequence is decreasing sequence then, no profit can be made because no matter on which day we buy the stock, we would have to sell it incurring a loss. So then we don't buy and make '0' profit rather than negative.

Try solving now

2. Best Time to Buy and Sell Stock III

Hard

0/120

Asked in companies

You are Harshad Mehta’s friend. He told you the price of a particular stock for the next ‘n’ days.

You are given an array ‘prices’ which such that ‘prices[i]’ denotes the price of the stock on the ith day.

You don't want to do more than 2 transactions. Find the maximum profit that you can earn from these transactions.

Note

1. Buying a stock and then selling it is called one transaction.

2. You are not allowed to do multiple transactions at the same time. This means you have to sell the stock before buying it again.

Example:

Input: ‘n’ = 7, ‘prices’ = [3, 3, 5, 0, 3, 1, 4].

Output: 6

Explanation: 
The maximum profit can be earned by:
Transaction 1: Buying the stock on day 4 (price 0) and then selling it on day 5 (price 3). 
Transaction 2: Buying the stock on day 6 (price 1) and then selling it on day 6 (price 4).
Total profit earned will be (3 - 0) + ( 4 - 1) = 6.

Problem approach

First assume that we have no money, so buy1 means that we have to borrow money from others, we want to borrow less so that we have to make our balance as max as we can(because this is negative).

sell1 means we decide to sell the stock, after selling it we have price[i] money and we have to give back the money we owed, so we have price[i] - |buy1| = prices[i ] + buy1, we want to make this max.

buy2 means we want to buy another stock, we already have sell1 money, so after buying stock2 we have buy2 = sell1 - price[i] money left, we want more money left, so we make it max

sell2 means we want to sell stock2, we can have price[i] money after selling it, and we have buy2 money left before, so sell2 = buy2 + prices[i], we make this max.

So sell2 is the most money we can have.

Try solving now

3. SQL Questions

Asked to Design an employee table by thinking of the possible fields and keys myself and was asked the following queries
1) How to fetch monthly Salary of Employee if annual salary is given
2) How to get 3 Highest salaries records from Employee table?

Problem approach

Tip 1 : Tell the interviewer about the thought process.
Tip 2 : study previous questions. you can use different online platforms for that

Round

Easy

Video Call

Duration60 Minutes

Interview date17 Jun 2022

Coding problem2

This round was conducted on Google Meet and was more of a Discussion round. Questions on my Resume, Projects and past internships were asked followed by 2 DSA questions

1. Longest Palindromic Substring

Moderate

20m average time

80% success

0/80

Asked in companies

You are given a string 'str' of length 'N'.

Your task is to return the longest palindromic substring. If there are multiple strings, return any.

A substring is a contiguous segment of a string.

For example :

str = "ababc"

The longest palindromic substring of "ababc" is "aba", since "aba" is a palindrome and it is the longest substring of length 3 which is a palindrome. 

There is another palindromic substring of length 3 is "bab". Since starting index of "aba" is less than "bab", so "aba" is the answer.

Problem approach

Maintain a boolean table[n][n] that is filled in bottom up manner.
The value of table[i][j] is true, if the substring is palindrome, otherwise false.
To calculate table[i][j], check the value of table[i+1][j-1], if the value is true and str[i] is same as str[j], then we make table[i][j] true.
Otherwise, the value of table[i][j] is made false.
We have to fill table previously for substring of length = 1 and length =2 because
as we are finding , if table[i+1][j-1] is true or false , so in case of
(i) length == 1 , lets say i=2 , j=2 and i+1,j-1 doesn’t lies between [i , j]
(ii) length == 2 ,lets say i=2 , j=3 and i+1,j-1 again doesn’t lies between [i , j].

Try solving now

2. Course Schedule

Easy

15m average time

85% success

0/40

Asked in companies

You are a student of Netaji Subhas Institute of Technology. You have to take ‘N’ number of courses labelled from 1 to N to complete your B.Tech Degree.

Some courses may have prerequisites, for example, to take course 1 you have to first take course 2, which is expressed as a pair: [1, 2]. Now, your task is to find is it possible for you to finish all courses.

Note: There are no duplicate pairs in the prerequisites array.

For example-

If N = 2 and prerequisite = [[1, 2]]. Then, there are a total of 2 courses you need to take. To take course 1 you need to finish course 2. So, it is possible to complete all courses.

Problem approach

This problem is equivalent to detecting a cycle in the directed graph represented by prerequisites. Both BFS and DFS can be used to solve it using the idea of topological sort. Since pair is inconvenient for implementing graph algorithms, we first transform it to the adjacency-list representation. If course u is a prerequisite of course v, then the adjacency list of u will contain v.

Try solving now

Round

Easy

HR Round

Duration15 Minutes

Interview date21 Jun 2022

Coding problem1

This is not a typical HR round, it is more like a discussion.