Status: Undergrad, B.Tech, CSE
Position: SWE Intern (Winter 2023)
Location: Bangalore/Hyderabad
Date: September 2-4, 2022

2 X 45 mins Technical Interview (Based strictly on Problem Solving with DSA)

Technical Interview 1: [LEVEL : MEDIUM]
Algorithm question -
[WARMUP]

You are given a series of intervals in the form of list of lists, and a target x. Your task is to return True if x lies in the interval, or False otherwise. 

Testcase 1:
Input:
[[1-3],[4-7],[9-21]], x = 15

Output:
True 

Explanation: 15 exists in interval [9-21]. 

[MAIN QUESTION]
Follow up after explaining the warmup question''s approach -
Instead of a single target x, you will be given a stream of queries (q), where
each query will have a target x. Return a boolean array ({True,False,True,...])
for given queries,True if they exist in one/more intervals, and False, if they do 
not exist in any of the given interval. 

Testcase 2:
Input:
[[1-3],[4-7],[9-21]], queries = [4,6,8,10,15]

Output - [True,True,False,True,True]

Explanation - 
Every query except 8, exists in the given intervals.

He clarified these after I asked some questions -
**1. Intervals are non overlapping.

2. They are sorted.
3. You can assume there will be no negative intervals.**

Required Time Complexity - O(log N)
Required Space Complexity - O(1)

Final follow up - What if the intervals were overlapping?

Feedback gained : Positive. I explained brute, better and optimal approaches. He expected a binary search approach. At the end he asked me to practice coding in time bounded environment for fast paced coding.

P.S - Interviewer was very chill and helpful person. Gave hints. Focused more on problem solving approaches than code.

Technical Interview 2: [LEVEL: HARD]

Given two lists of integers, A and B, list A represents the daily profit of working at CityA 
and list B represents the daily profit of working at CityB. You are a salesman and you have to
switch between cityA and cityB due to various client requirements. When you switch from cityA 
to cityB, you have to travel. The day you travel (T), cannot be considered as a working day,
and hence your net profit on travel days are 0. 
Your task is to output a schedule which includes working as well as travelling such that your profit is maximized. 

The only example testcase he provided, is given below-
Testcase1: 
Input:
A[] = [23,4,5,2], B[] = [20,1,10,100]

Output:
"ATBB"

Explanation -
An optimal schedule will be-
Day 1 : Work at cityA -> profit is 23
Day 2 : Travel -> profit is 0
Day 3: Work at cityB -> profit is 10
Day 4: Work at cityB -> profit is 100

After some questions from my side, he clarified these -

1. The length of array A and array B will always be equal. Each index of array A/B is treated as day(i), and the value at day(i) is your profit for that day (if you worked). If you travelled at day(i), profit for that day won't be added to your net profit.
2. You can work in a city for more than 1 day. But, travelling is mandatory. You cannot work in only city A or city B.
3. There will be no dreaded zeroes in any of the array values.

After much struggle, I figured out it's recursion type problem. I said that, he agreed and asked me to show a memoized dynamic programming solution.

Required Time Complexity - O(N)
Required Space Complexity - O(N)

I could not solve this, and required a lot of hints. I solved a good amount of dp problems, but never came accross this kindof problem, hence I was stuck.
In the last few minutes, after taking some help, I was just able to code 3 lines, that too with awfully broken code.

Feedback gained : He asked me to solve hard tagged dynamic programming problems from leetcode.

P.S - Interviewer didn't mesh well. He was not at all helpful, neither gave a hint. He kept pin drop silence even after watching me struggle. In the final minutes, he spoke to explain the approach. He himself struggled to explain it properly though. I couldn't undertsand what he meant.

Ik I have to work a lot on myself too, but I am very straight to this point that, if he tried to be helpful, I could have solved it.
A short piece of advice would be to NOT assume by default that all Google/ or rather all interviewers are always helpful, and prepare in such a way that minimal help is needed from interviewers.

Bad day. Happens. NVM.

I request the brilliant coders and problem solvers present in the LeetCode community to provide meaningful approaches and/or solutions to the problems I stated. It will be very helpful to me and others.

A humble request - I would be highly thankful if somebody puts their effort to present a Java/Python solution. I really struggle with CPP codes.

Thanks in advance! 

Happy LeetCoding!