BTech from Tier 2 college
YOE= 2 yrs in a decent PBC
Telephonic Round-
Q1) you are given maximum initial energy k (k<1000) and array A of length n denoting wind speed on n days. he is stuck on a boat and each day he can either choose to move or stay put.. each day he decides to travel he will move ahead A[i] Dist and his energy decreases by 1 and if he decides to stay put his energy increases by 1.
What is the maximum distance he can travel without dropping his energy to negative after n days.
//Clarification questions i asked- what if energy is k and he decides to rest only- would energy go beyond maximum? answer=No, it will remain k
//can the wind speed be negative as well, denoting wind flowing in other direction? answer= No (initially)
Solution=
i suggested a dp solution where
dp[i][e]= maximum distance he can travel if we have considered first i days and e is the energy at the end of the day
dp[i][e]=max(dp[i-1][e-1],dp[i-1][e+1]+A[i]);
// dp[i-1][e-1] above is the max distance that he travels if he decides to not travel on ith day
//dp[i-1][e+1] +A[i] is the max distance that he travels if he decides to travel on ith day, his energy reduces by 1 and distances increases by A[i]
// also we need to consider edge case where his energy was already maximum and he decides to rest
if(e==k)// in the state energy = max energy
dp[i][e]=max(dp[i][e],dp[i-1][e])
its extension was what if A[i] could be negative as well. I asked what would be the answer if A[i]<0 for all i
Answer=0
so i told that we could simply not travel if A[i]<0 .[fixed outcome for that day]
Runtime=O(nk)
Space =O(k)
Still about 7-10 mins were left, so she asked another question
Q) In a x-y cartesian plane , squares are made with axes paralled to x-axis and y- axis, their topleft corner x,y is given and edge length a is given for each,, we have to tell a horizontal axis that divides the area of all squares in 2 equal halves.
l=[(1,2),(2,4)] //topleft coordinates
sizes=[5,10] //edge lengths
She told me i can just give on how would i solve it, i don't have to code it since we didn't have enough time.
Solution- i was able to come up with a binary search solution, i felt we can take range for y coordinates , then we could simple check in O(n) time for how much area is above A1 and how much is below the proposed axis A2 .
this would be O(nlogy) solution.
The interviewer wasn't satisfied and told me to think of a better solution.
Wasn't able to do in the remaining time and she ended the round.
Later , i thought of the this solution..
It involves calculating weighted average.
l=[(1,2),(2,4)]
sizes=[5,10]
so for each square you can assume it as point weight equal to its area at average of their y coordinate (2+(-3))/2=-0.5. so at y coordinate=-0.5 we can assume 25(area) weight, similarly at -1 a weight of 100(area)
ans =(-0.5 *25-1*100)/125 =-0.9
O(N) solution
Edit: Thanks to quick observations of @sagarchapara , the weighted average approach fails for many test cases and is incorrect.. Any solutions for second question are greatly appreciated.
Verdict- Passed
Round 1- Given are N cities and M roads that travel between the given pair of cities and time it takes to travel that road. Also we are given a list of favourite cities L and a source city S . we have to tell the favourite city which can be reached from source city the fastest(in minimum time)
Solution- Classic Dijkshtra
It was followed by a discussion on runtime complexity and how it was O(V+E log(V))
This went on for a while, since we had a little argument about the complexity of the inner loop.
Then a couple of follow ups -1) Early Stoppage conditions
2) a fix vertex V to be travelled in the way to favourite city
for 1) i got a little confused and had to take a little help from the interviewer but eventually i told the right solution.
2) i made a wrapper function which calls dijkshtra to find dist S-V + dijkshtra to find V- C( favourite city)
Round 2 -we have a dictionary of words and a function which gives hash of these words and another function which gives score=sum of diff of adjacent characters in a string and implement another function which gives the anagram of the given word with highest score.
Hash of all anagrams is same.
`class Solution
{
public:
vectorwords={"cat","tac","dog","god","cow"}; //given
string getHash(string word);//some hidden implementation =O(1)
int getScore(string word) // sum of diff of adjacent characters in a string=O(len(word))
{
//had to write code here
}
string findAnagram(string word) //it will return highest score anagram of word -though not word
{
//had to write code here
}
}`
Solution-
unordered_map<int,vector<pair<string,int>>>info;
a precomputation method in which we traverse words array and for each word we calculate hash which would be a key in unordered_map info and for each key we store anagram with score, for each hash - we store 2 anagrams that have the highest score in the sorted order.
This would take O(N*len(word)) as for each word we calculate its score .
then findAnagram(word) would take O(1) // for hash calculation - then using info we return the anagram with the highest score if its equal to word , then we return the second anagram with second highest score for its hash.
Round 3- Given a set of points find 4 points which form a rectangle and has largest area of any such rectangle. // consider axes of rectangle parallel to x and y axis
In part 2- axis of rectangle is not parallel to x and y axis
In this , i assumed one point to be x,y then others would be (x+l,y), (x,y+b), (x+l,y+b)
so i told him that i would need 3 things (x ,y) and l and b.. then i was given a hint to think of a diagnol.
i instantly understood and coded it -- taking 2 points x,y and x+l,y+b would given all 3 things at one..
taking 2 points at random would be O(n*n) complexity.
in part 2 - axes were not parallel to x and y axis.. i was hell bent on not increasing complexity to O(n^3) and so again was given hint to use 3 points..Coded it though with O(n^3) approach
This was the worst round i had so far..
Round 4- this was supposed to be a googliness round as per my understanding, but interviewer took a DSA round
R4- given a vector<vector> sentences, we have to find next most probable word for any given word .
given sentences={{'i','am','awesome'},{'i','am','a','googler'}};
so then func(i) should return 'am'
I asked some questions regarding would it be guaranteed that the word would be in the corpus and that it would have atleast one word next to it.
was told YES
made a unordered_map<pair<string,string>,int> pairCount to keep count of each pair in the sentences . It was one -pass then did another pass to find max probable word for each word by checking each pair in pairCount map.. stored these results in another hashmap.
Runtime complexity- O(n* len(word)), n is the number of pairs of words-- if total words are x then pairs would be x-1(including repeated ones as well)
I told the interviewer that i would try to do it in one pass,, was told this was perfect and was given next question.
Part 2- given a DAG , find the maximum path distance it can go upto any node
It means from any node to any other node, what is the max distance
// can graph have no nodes- NO
had just 10 mins for it. was able to do it in O(n)time and O(n)space
dist(i)= maximum dist we can travel to any other node from ith node
=1+ maximum(dist(c)) //c is any node directly reachable from ith node
`int dist(int node, vector<vector<int>>&graph,vector<int> &distances)
{
int ans=1;
for(auto x: graph[node])
ans=max(ans,dist(x,graph,distance)+1);
return distances[node]=ans;
}
int func(vector<vector<int>>graph)
{
vector<int> distances(graph.size(),-1);
int ans;
for(int i=0;i<graph.size();i++)
{
if(distances[i]==-1)
ans=max(dist(i,graph,distances)-1,ans);
}
return ans;
}`
in the end , interviewer was happy..
Round 5- Had my googliness round pretty well recently as well
Update- Just got the news from ny HR, my feedback is positive.. she has forwarded the profile to multiple managers.. waiting for fitment call next..
Update 2- My HR pretty much ghosted me after the feedback. I later got to know she was on notice period and has left Google .After what seemed like a million mails, yesterday i got a call from a new HR that she has now forwarded my profile to managers now.My feedback - SH, LH,SH,LH,SH -> Passed