Check algoexpert.io/rachit and dailycodingproblem.com/rachit for Interview Prep. Hint for the Balloon Problem: You can mark balloon of height X as not important if there exists a balloon of height X+1 in its left side. Once you do that for all balloons, answer is nothing but the number of important balloons. Ofcourse, you need to take care of cases like [5,4,4]. The last balloon has a balloon on its left side with height 4+1, but still you need a separate arrow for that. Do this without worrying over time complexity. Get a working solution first, and then think of optimising this to O(N) time.
Will the height of the arrow only decrease once we hit the balloon, or the arrow goes down in trajectory consistently. For Example in your example of [5,4,4,3,3] if we assume to decrease the height of the arrow only when it hits the balloon, then the minimum no of arrow needed is 2, but if we decrease arrow height consistently by 1 then we need 3 arrows, 1st time: 5, 4 and 2nd time: 4,3 and 3rd time : 3. So which one is valid, seems like Arrow has some special powers.
@@RachitJain Thanks for the clarification, but then according to your hint, how come the answer is 2 it should be 3. [5 , 4 , 4 , 3 , 3] ---> 5 is important since it has no greater element (5+1) on the left side, 4 is marked as non-important, 4 immediate left is not X+1 so this is important, the same case with 3 and 3. So total important balloons are 3 [5, 4, 3].
Please dont confuse others as well. The balloon at index 1 and index 3 are important. I just gave a hint in the pinned comment. Use pen, paper and time to figure this out.
Yeah, I did that and totally agree that index 1 and index 3 are important, could you please just give me another hint as to why *index 5 is not important*. (Assuming indexing of array is from 1 not 0).
Did someone notice how beautifully he gave feedback to interviewers about coming late to interviews? I love how he is so honest and yet respectful at the same time. I used to screw things up when something wrong happened, or lose my temper. Respect to you, Rachit! You are doing amazing.
Will the balloon problem work with something like an unordered_multiset? Idea is, the leftmost balloon has to be shot directly, no other choice but to shoot a new arrow towards it. During this process, on visiting each ballon, we store the next value that we are expecting to see in the multiset. Also on visiting every new balloon, we check if there's any existing arrow that was waiting to hit it. On reaching 5, set is empty, so we increment arrow_count to 1, and add 5 - 1 = 4 to the set (since, the next expected value for current arrow is 4). On reaching the next 4, we find a 4 already in set, so that indicates that an existing arrow can hit 4.. we erase that 4 from set, and insert 4 - 1 = 3 (indicates that the arrow already hit it, and is now waiting for the next balloon). On reaching the next 4, we check for 4 in the set but don't find any (there's only one 3 present in set), hence we again increment arrow_count to 2. We also insert another 4 - 1 = 3 into the set, marking the current balloon hit. Currently set contains {3,3} which is why multiset was needed. This process continues. Final arrow_count is the answer. Works in O(N) (We could also use unordered_map with value as frequency to achieve the same thing as this).
Please start a series on dynamic programming from beginner level..I know u have a dp playlist but thats for someone who's has already achieved a level..so pls make something for beginners as well
I think the solution is : We will keep a set which indicate the y-cordinate of fired arrows, and we decrement the fired coordinate value. For ex : 4 3 2 1 4 init : set -> val i = 0, set.remove(4) set.add(val--) i = 1,....at i = 3 set has 1(yco) only,the last ele =4 check the set for val+1 i.e 5:since not present new arrow will be fired. Total arrows is total size of set Set set = new HashSet(); for(int num : nums) { if(set.contains(num+1)) { set.remove(num+1); set.add(num); } else { set.add(num); } } return set.size(); Correct me if am wrong.
My O(N) solution for baloon problem(considering b[i] >= b[i + 1]): Create two variable maxBaloon = 0 , currentLen = 1 For every ith element check if i + 1 th element is same as i : if same as ith: increment the currenLen by 1 else: maxBaloon = max(maxBaloon, currentLen) curLen = 1 answer is maxBaloon
Hi , I have been working in startup from beginning of my career .The main problem I faced or facing is nobody talks about scalability or how to do things in a better way.
Waiting for the answer.. Thanks man ! The cool thing is the videos are short .. so rather than downloading or to add to watch later and then never watch it.. liked it this way... Also the new inteo splash is good.. good have been with figures as well.. like linusTechTips
Sir, what do startups focus on your skills or data structures in technical interviews and if it depends on the type of startup you are going for.............Also whether your skillset affect your post in the company.
Could you please tell us how much was offered to the IIT juniors so that we can have an idea. I know there are websites like Glassdoor for that but still it would be helpful.
Bro what all the interviewer expect from the non-cse candidates other than data structures and algorithms.(I mean the subjects like os ,system design etc.)
@Rachit Jain ....That question is very interesting...I solved it(Language:-Java) but the time complexity is O(n^2)... Rachit bhaiya is there any way to solve it with O(n) time complexity
I don't know if it will work for all test cases also one question will the arrow direction will be left to right or we can shoot it from right to left also int vis[n] = {0}; int ans1 = 0; //caculating count from left to right for(int i=0;i
Hello bhaiya, like my college is starting in July my doubt is that how can I start with competitive programming like i learn c++ then what to do next to start with competitive programmin can you make a video in this topic not me many are waiting for this video
Never judge anybody by no of languages he/she know.... The knowledge of DSA matters the most not the no of languages...... As I know more than 5 programming language but its just a waste if I don't be able to solve some problem with that....
Hello Rachit. I recently got selected for mtech in iit roorkee cs. I'm a bit confused what should I focus in masters. Placements or research. I've heard that research in iitr is not up to the mark. Should I start competitive coding then and focus on placements?
yes , buddy you should start competitive programming as soon as possible and devote atleast 7 hour for competitive programming for becoming best in the market and have keen focused on placements and internships start giving internships and also start studing system design competitive programming plus system design
// Code for the Given problem in Java // Covering all edge cases public static int minArrows(int[] arr){ int ans = 0; Map map = new HashMap(); // Number of arrows at that height for(int i = 0; i < arr.length; i++){ int x = arr[i]; if(map.containsKey(x) && map.get(x) > 0){ map.put(x,map.get(x)-1); // Number of arrow decreased at current level map.put(x-1,map.getOrDefault(x-1,0)+1); // Number of arrows increased at lower level } else{ ans++; // we need one more arrow map.put(x-1,map.getOrDefault(x-1,0)+1); // Number of arrows increased at lower level } } return ans; }
Hello Rachit bhaiya, thankyou for making such interesting and informative videos.We appreciate your content a lot. I had a question that i hope you would elaborate upon. I am in my final year of my B.Tech course and want to apply for jobs. I am checking the careers website of the companies that i want to apply for, but there seems to be no open entry level positions in India, however there are many such open positions in Canada, Russia...etc. So my question is can i apply for the position in a foreign location and what would be the process for that. Thankyou.
Check algoexpert.io/rachit and dailycodingproblem.com/rachit for Interview Prep.
Hint for the Balloon Problem: You can mark balloon of height X as not important if there exists a balloon of height X+1 in its left side. Once you do that for all balloons, answer is nothing but the number of important balloons. Ofcourse, you need to take care of cases like [5,4,4]. The last balloon has a balloon on its left side with height 4+1, but still you need a separate arrow for that. Do this without worrying over time complexity. Get a working solution first, and then think of optimising this to O(N) time.
Will the height of the arrow only decrease once we hit the balloon, or the arrow goes down in trajectory consistently.
For Example in your example of [5,4,4,3,3] if we assume to decrease the height of the arrow only when it hits the balloon, then the minimum no of arrow needed is 2, but if we decrease arrow height consistently by 1 then we need 3 arrows, 1st time: 5, 4 and 2nd time: 4,3 and 3rd time : 3. So which one is valid, seems like Arrow has some special powers.
Only after it hits a balloon.
@@RachitJain Thanks for the clarification, but then according to your hint, how come the answer is 2 it should be 3.
[5 , 4 , 4 , 3 , 3] ---> 5 is important since it has no greater element (5+1) on the left side, 4 is marked as non-important, 4 immediate left is not X+1 so this is important, the same case with 3 and 3. So total important balloons are 3 [5, 4, 3].
Please dont confuse others as well. The balloon at index 1 and index 3 are important. I just gave a hint in the pinned comment. Use pen, paper and time to figure this out.
Yeah, I did that and totally agree that index 1 and index 3 are important, could you please just give me another hint as to why *index 5 is not important*. (Assuming indexing of array is from 1 not 0).
Did someone notice how beautifully he gave feedback to interviewers about coming late to interviews? I love how he is so honest and yet respectful at the same time. I used to screw things up when something wrong happened, or lose my temper. Respect to you, Rachit! You are doing amazing.
Nice Video!! Please share your Tower Research and Goldman Sachs interview experience!!
Will the balloon problem work with something like an unordered_multiset? Idea is, the leftmost balloon has to be shot directly, no other choice but to shoot a new arrow towards it. During this process, on visiting each ballon, we store the next value that we are expecting to see in the multiset. Also on visiting every new balloon, we check if there's any existing arrow that was waiting to hit it.
On reaching 5, set is empty, so we increment arrow_count to 1, and add 5 - 1 = 4 to the set (since, the next expected value for current arrow is 4). On reaching the next 4, we find a 4 already in set, so that indicates that an existing arrow can hit 4.. we erase that 4 from set, and insert 4 - 1 = 3 (indicates that the arrow already hit it, and is now waiting for the next balloon). On reaching the next 4, we check for 4 in the set but don't find any (there's only one 3 present in set), hence we again increment arrow_count to 2. We also insert another 4 - 1 = 3 into the set, marking the current balloon hit. Currently set contains {3,3} which is why multiset was needed.
This process continues. Final arrow_count is the answer. Works in O(N)
(We could also use unordered_map with value as frequency to achieve the same thing as this).
Please start a series on dynamic programming from beginner level..I know u have a dp playlist but thats for someone who's has already achieved a level..so pls make something for beginners as well
Interview experience of tower research & Goldman Sachs
You are Amazing Rachit! I always learn from your video, Gbu!
which technologies u have worked on in Microsoft?
According to you what could be the probable rating ( Codeforces Scale) of the problems who were asked in this interview?
I think the solution is :
We will keep a set which indicate the y-cordinate of fired arrows, and we decrement the fired coordinate value.
For ex : 4 3 2 1 4
init : set -> val i = 0, set.remove(4) set.add(val--) i = 1,....at i = 3 set has 1(yco) only,the last ele =4 check the set for val+1 i.e 5:since not present new arrow will be fired. Total arrows is total size of set
Set set = new HashSet();
for(int num : nums) {
if(set.contains(num+1)) {
set.remove(num+1);
set.add(num);
} else {
set.add(num);
}
}
return set.size();
Correct me if am wrong.
You motivate a lot, sir! ❤️
My O(N) solution for baloon problem(considering b[i] >= b[i + 1]):
Create two variable maxBaloon = 0 , currentLen = 1
For every ith element check if i + 1 th element is same as i :
if same as ith:
increment the currenLen by 1
else:
maxBaloon = max(maxBaloon, currentLen)
curLen = 1
answer is maxBaloon
if possible may I know the purpose of currentLen, instead increment the max ballon itself...
Can you prepare a series on interview preparation
Please share your interview experience with Goldman Sachs and Tower research capital!!!! Thanks🙏🙏🙏
y did u leave microsoft? please share goldmansachs experience
Best course for Android app development
Hi , I have been working in startup from beginning of my career .The main problem I faced or facing is nobody talks about scalability or how to do things in a better way.
Thanks for sharing you valuable experience
Waiting for the answer..
Thanks man ! The cool thing is the videos are short .. so rather than downloading or to add to watch later and then never watch it.. liked it this way... Also the new inteo splash is good.. good have been with figures as well.. like linusTechTips
Tips/Tricks regarding preparation for the internship hiring process.
Tower Research Capital, next one please!
Sir, what do startups focus on your skills or data structures in technical interviews and if it depends on the type of startup you are going for.............Also whether your skillset affect your post in the company.
awesome man!
Can be done with O(n) even if not sorted by maintening two arrays
please make a video on how to apply for software Engineer job. like in this case how did you approach the company for interview.
Can you migrate to USA or any other counties from google, microsoft, amazon? Do they have any programs like that?
Which middle man agency did you contact?
Could you please tell us how much was offered to the IIT juniors so that we can have an idea. I know there are websites like Glassdoor for that but still it would be helpful.
Bro what all the interviewer expect from the non-cse candidates other than data structures and algorithms.(I mean the subjects like os ,system design etc.)
What is the name of consultancy and from where you are getting calls,like Naukri,monster etc... fir product based companies
it would be quite helpful if you could share most of the questions asked in all the interview rounds
How do i get job at big product based companies , i'm not from any IIT, NIT, etc . I am from tier 5 college. How?
Cool intro!
Does nearest smaller to the right approach work for this one ?
Love it
I also have developed solution in O(N) time.. Would like to compare and discuss whether its completely correct or having edge case issues
How did you approach to this problem, please share that experience.
Check pinned comment for the hint.
@@RachitJain where is that.
@@naimish_singh Thanks it was not visible when I posted the comment.
Please share your work experience at Microsoft
Do you know what is the scariest thing on a coding interview?😂
@Rachit Jain ....That question is very interesting...I solved it(Language:-Java) but the time complexity is O(n^2)...
Rachit bhaiya is there any way to solve it with O(n) time complexity
I don't know if it will work for all test cases
also one question will the arrow direction will be left to right or we can shoot it from right to left also
int vis[n] = {0};
int ans1 = 0;
//caculating count from left to right
for(int i=0;i
What about ML and AI? Should I invest my time in learning new things ?
No CP
Please also share numbers that they were offering, it would help people negotiate better.
What is middle man actually can you elaborate??
Hello bhaiya, like my college is starting in July my doubt is that how can I start with competitive programming like i learn c++ then what to do next to start with competitive programmin can you make a video in this topic not me many are waiting for this video
no design round? wth!
Sir is the app Codebook written by you???
No
Can you suggest some good recruiting consultancies?
What is the solution of that ques.....
Check pinned comment.
@@RachitJain There is no pinned comment!!
Bhaiya How many language one should know(programming languages)
One is enough. Focus on learning one on great depth. Then once you are stable and have time, you may explore others.
Never judge anybody by no of languages he/she know.... The knowledge of DSA matters the most not the no of languages...... As I know more than 5 programming language but its just a waste if I don't be able to solve some problem with that....
Hi Rachit can you please make a video of some good startups a fresher should consider joining.
very cool
Can you please give the solution of the balloon question?
Would you recommend JavaScript for someone beginning with competitive programming or is looking to be in Front end zone.
Never JavaScript is not recommended for competitive programming. Use CPP instead for competitive programming
You can switch to python easily , it is kinda similar to JS
Even I was asked same baloon question in interview at curefit. 😀 Not expecting from atleast curefit interviewer
Was there any system design interview round, as you were applying for SDE-II positions?
lovely how u show the problems from interview
Hello Rachit. I recently got selected for mtech in iit roorkee cs. I'm a bit confused what should I focus in masters. Placements or research. I've heard that research in iitr is not up to the mark. Should I start competitive coding then and focus on placements?
yes , buddy you should start competitive programming as soon as possible and devote atleast 7 hour for competitive programming for becoming best in the market and have keen focused on placements and internships start giving internships and also start studing system design competitive programming plus system design
// Code for the Given problem in Java
// Covering all edge cases
public static int minArrows(int[] arr){
int ans = 0;
Map map = new HashMap(); // Number of arrows at that height
for(int i = 0; i < arr.length; i++){
int x = arr[i];
if(map.containsKey(x) && map.get(x) > 0){
map.put(x,map.get(x)-1); // Number of arrow decreased at current level
map.put(x-1,map.getOrDefault(x-1,0)+1); // Number of arrows increased at lower level
}
else{
ans++; // we need one more arrow
map.put(x-1,map.getOrDefault(x-1,0)+1); // Number of arrows increased at lower level
}
}
return ans;
}
Iit roorkee or iit guwahati.
Which one is better for cse ?
Guwahati
Please make a video for the explanation of manachers algorithm.
Salary?
Hello Rachit bhaiya, thankyou for making such interesting and informative videos.We appreciate your content a lot.
I had a question that i hope you would elaborate upon. I am in my final year of my B.Tech course and want to apply for jobs.
I am checking the careers website of the companies that i want to apply for, but there seems to be no open entry level positions in India, however there are many such open positions in Canada, Russia...etc. So my question is can i apply for the position in a foreign location and what would be the process for that. Thankyou.
Sir plz make some videos on Google interview codings plz plz
make a video of tower research
Bhai humne bhi tumhare chakkar mei chod diya tha process.
London Thumakda!
☺️
the problem was form leetcode.
I dont know.
@@RachitJain Great efforts from your side keep posting video bro.
Hey man can u share the link or SS of problem? @harsh Patel
First one😁