Today, many TH-camrs are only focused on sharing more materials, without considering how companies are asking questions or how freshers can really face interviews. Great work by Striver and GFG for providing practical advice on these topics.
Here i can see Arjit is struggling to get approach in the very start that clearly shows a real feel to interview ...a nice video to learn a lot from thank you @striver for such gem content ❤️❤️.....I want to know how you choose interviewee?
First thought comes to mind after seeing this question is Coin Change. 1. Find first 3 primes(precompute primes if given lot of queries) 2. BFS to get minimum primes
The very first intuition i got after seeing the question was that , first i will prepare M primes in some array/vector. Then i can relate this qn. to unbounded knapsack problem (coin change problem where I've to find minimum number of denominations to make Target price). Or target sum problem to find minimum number of elements to make target . Striver Dp series helped me alot to think out of the box also ❤️❤️. thanks @striver
I think what he was talking at the end about functions is "Pure Functions". Changing a global variable from within a function is a "Side effect" and it's a bad practice to do that unless absolutely necessary. Pure functions should not have any side effects and given a set of input you can be rest assured that the output will always be the same no matter how many times the function is called.
This is so insightful for freshers who have never given an interview , have so many questions and they are getting answered here . The anxiety of giving an interview and everything else how it happens goes the process.
Brute force of this solution that strike in my mind is making a vector to store all the m primes and after that use unbounded knapsack to find minimun number of prime to make n
For brute force approach we can tell that storing ist M prime no in array then simple do combination sum where duplicacy allowed that is we can use same element again T.c : exponential S.c O(M)
The first approach that came to my mind is to create a vector/array of size M, which stores the first M prime numbers up to the given number N. After this, we apply the Combination Sum.
after seeing the second test case it was pretty simple to undeerstand that there are so many ways so when many ways comes it comes to recursion and then we can move for dp also
What if we find first M primes using a Sieve, and then use a recursion on that list with a constraint of M[prime] < N ? that would just take around O(n) time asymptotically? (I'm not sure Im solving it as I see the question 1st time so I'll update later). Lets take an example: Say I take N=10 and M=1. So my M list is: M[]={2} //since 1st prime is M Now of course here 10%2 is 0 so it works (we can do 10/2 to see how many 2's we need) For the next problem: N=11 M=3 So my M list is: M[]={2,3,5} //3 primes Here, we can see M[3] < N //and M is strictly increasing list so we don't need to check more We see 11%5 !=0 We store 5 in a list say K. So we subtract 5 from 11 i.e. 6 and call this same function on 6 with M[]={2,3}, and concatenate the output on K[]. so what I mean is we get 5 first, then we send 6, so we have M[]={2,3} so we check 6%3 and its 0 so we do 6/3 to see how many 3's we need. So finally we get {5,3,3} is that correct? lemme check P.S. the answer is 5,3,2 in the doc and it seems my disappointment is immeasurable, and my day is ruined.
Can You Add These Questions To GFG, I Have Prepared Solution For Few But Can't Find An Online Judge To Check Them I Don't Wanna See The Solution Mentioned In The Video As I Wanna Approach To Correct Answer Myself. Please Add Them
Why can't we use greedy approach here? Like for N=11 and M=3, I could have started from the biggest prime no. that's gonna be 5 and subtract that value from N and update value of N until I don't get value of N less than the current prime no or value of N==current prime no+1. In that case, I will move towards the smaller prime no and try to do the same thing with that. If N!=0 then we can't make N with the help of first M prime no.
Here greedy can give -1 because from 4, it'll subtract 3, then 1 remains which is not possible.... So we'll have to add a condition that after the subtraction, the remaining no. Should not be 1
import java.util.*; class HelloWorld { static boolean a[]; static ArrayList b=new ArrayList(); public static void solve(int n,int m) { Arrays.fill(a,true); int o=0; for(int i=2;ib.get(i)) { ans+=(n/b.get(i)-1); n=n%b.get(i)+b.get(i); } } System.out.println(ans); } } I checked for these edge cases and it is working can you let me know any case in which it is failing
Step1: Make an array with first M prime numbers Step2: Use unbounded knapsack code: import java.util.*; class Solution { public static int minPrimes(int N, int M) { int[] arr = findPrimes(M); int ans = unbounded_Knapsack(arr, N); return ans; } public static int unbounded_Knapsack(int[] nums, int N) { int len = nums.length; int[][] t = new int[len + 1][N + 1]; for (int i = 0; i
@@shamsulhaque55 stfu... those who work hard to improve problem solving skills are good at it... So, go first improve yourself it's better than criticising someone who is 1000X better than you. Btw what's your codechef or codeforces profile?
Today, many TH-camrs are only focused on sharing more materials, without considering how companies are asking questions or how freshers can really face interviews. Great work by Striver and GFG for providing practical advice on these topics.
Here i can see Arjit is struggling to get approach in the very start that clearly shows a real feel to interview ...a nice video to learn a lot from thank you @striver for such gem content ❤️❤️.....I want to know how you choose interviewee?
We need more such type of mock interviews
First thought comes to mind after seeing this question is Coin Change.
1. Find first 3 primes(precompute primes if given lot of queries)
2. BFS to get minimum primes
BFS or DFS ?!
Coin Change problem can be solved by DFS.
@@rajrajesh1669 BFS we can use
why do we need bfs?
just apply the coin change problem and the coins available are all the prime numbers upto the given target limit
Sieve of eratosthenes + dp on subsequences
Sieve is enough without dp
Generating prime number till 10
Will make a cnt aswell
Then return the cnt directly
The very first intuition i got after seeing the question was that , first i will prepare M primes in some array/vector. Then i can relate this qn. to unbounded knapsack problem (coin change problem where I've to find minimum number of denominations to make Target price). Or target sum problem to find minimum number of elements to make target . Striver Dp series helped me alot to think out of the box also ❤️❤️. thanks @striver
I thought the same approach bro
in same I thought
Same
ya the same thing i realted it to , and same with help of striver's dp series . but don't you think the constraints are too tight.
same thought process bro....
I think what he was talking at the end about functions is "Pure Functions". Changing a global variable from within a function is a "Side effect" and it's a bad practice to do that unless absolutely necessary. Pure functions should not have any side effects and given a set of input you can be rest assured that the output will always be the same no matter how many times the function is called.
This is so insightful for freshers who have never given an interview , have so many questions and they are getting answered here . The anxiety of giving an interview and everything else how it happens goes the process.
minimum coin required + seive
Brute force of this solution that strike in my mind is making a vector to store all the m primes and after that use unbounded knapsack to find minimun number of prime to make n
Mixture of Sieve and Knapsack.
For brute force approach we can tell that
storing ist M prime no in array then simple do combination sum where duplicacy allowed that is we can use same element again
T.c : exponential
S.c O(M)
I am thinking of same approach when i first saw problem
I also thought of the same approach
Minimum coin change with repetions allowed and the array filled with first M primes
Show us an interview as well where the candidate barely knows anything...!
But still clears it...!
Scripted karne bol rahe ho 😂
@@takeUforward Just kisi random CS student ka interview lene ko... jahan usey kuchh na aata ho... which would reflect the reality for most students. 😂
@@takeUforward bahi...video aayi nhi yrrr...subah se wait kar rahe hain
@@suvigyabasnotra7378 realistically someone with no knowledge won't clear the OA of MAANG level companies and won't get a chance of interview.
The first approach that came to my mind is to create a vector/array of size M, which stores the first M prime numbers up to the given number N. After this, we apply the Combination Sum.
Clearly understood 💯...How companies approach a fresher
7:33 LOL, sieve of.....what !!? 😂
If they're asking this level of questions for an OA. Then I won't even make it to the interviews lol.
after seeing the second test case it was pretty simple to undeerstand that there are so many ways so when many ways comes it comes to recursion and then we can move for dp also
thanks! lot to learn here even if you get the question by yourself.
loved this session so much
@striver@GeeksforGeeks
if N
No the qn is minimum numbers of prime numbers less than m is required to sum up to n
This qn is quite similar to coin change
@@kasiruyamagata7716yeah! I could relate this to the coin change with infinite supply!
What about we use bfs algorithm? Like simply store first m primes in a queue and then just simply keep iterating until you get the value
So inspiring men striver you are really great!!!
Thank you man❤
Definitely top notch content
binary search lower bound 1st que
Coin Change variation where coins are M, and target sum is N, and how come 5+3+2 is 11 ?
5+3+3=11 . We can take infinite supplies.
I think most people puzzled with the solution as it was iterative approach, doing the memoization way would have been easy to absorb
i think quetion can be easily solved using lower bound concept. in nlogn complexity.
25:00
Million dollar DSA problem -
Given k, X and a stream of numbers , determine the average of the last k numbers , excluding the largest X numbers
Loved it Sir ❤❤❤
Can anyone give a test case where gready fail?
very useful !
Is it possible .. to get the the list or all M primes and thn apply Target sum and count minimum counts
Yess
do all companies ask CP based questions?....as sieve is a CP topic
sieve of eratosthenes + dp on subsequences(coin change problem modified)
Unbound Knapsack ... Dekhte hi bola 😂😂😂
What if we find first M primes using a Sieve, and then use a recursion on that list with a constraint of M[prime] < N ? that would just take around O(n) time asymptotically? (I'm not sure Im solving it as I see the question 1st time so I'll update later).
Lets take an example:
Say I take N=10 and M=1.
So my M list is:
M[]={2} //since 1st prime is M
Now of course here 10%2 is 0 so it works
(we can do 10/2 to see how many 2's we need)
For the next problem:
N=11
M=3
So my M list is:
M[]={2,3,5} //3 primes
Here, we can see M[3] < N //and M is strictly increasing list so we don't need to check more
We see 11%5 !=0
We store 5 in a list say K.
So we subtract 5 from 11 i.e. 6
and call this same function on 6 with M[]={2,3}, and concatenate the output on K[].
so what I mean is we get 5 first, then we send 6, so we have M[]={2,3} so we check 6%3 and its 0 so we do 6/3 to see how many 3's we need.
So finally we get {5,3,3} is that correct? lemme check
P.S. the answer is 5,3,2 in the doc and it seems my disappointment is immeasurable, and my day is ruined.
Last time I checked this video, I was scared.
This time, I'm still scared. Phak, I have made no improvement
After how long did you rewatch ?
Any similar question to practice ? (Dp + sieves combination)
yaar itna time kaha dete hain wo log bas 5-10 min and btw ye question 10 min ka hai
baki aap jaisa interviewer milega to badhiya kismat
At 7:34 which thing he mentioned he can use to find first n primes?
sieve of eratosthenes
Can You Add These Questions To GFG, I Have Prepared Solution For Few But Can't Find An Online Judge To Check Them
I Don't Wanna See The Solution Mentioned In The Video As I Wanna Approach To Correct Answer Myself.
Please Add Them
why he just started with tabulation i.e most optimal approach rather giving bruteforce approach first, at 22:02
There is no generic rule to problems which are not standard ones.
similar to combination sum
7:35 whaaaat
Sieve of erathosthenes.
❤️❤️
i don't get the first question, what does it mean? help?
can we do sieve and binary search on search to get lower bound till n=0 if anyway in mid way lower bound out of sieve return -1
ya but if by subtracting you go 1 then at that time add one instance of last lower bound number and do ans--
I also solver the question but take an hour 🙁
2+3+5 is 10 right. Why he told its 11?
5, 3, 3
This qn is similar to coin change
Striver se sikh ke striver ko interview dene ka maza hi alag h😂
Why can't we use greedy approach here? Like for N=11 and M=3, I could have started from the biggest prime no. that's gonna be 5 and subtract that value from N and update value of N until I don't get value of N less than the current prime no or value of N==current prime no+1. In that case, I will move towards the smaller prime no and try to do the same thing with that. If N!=0 then we can't make N with the help of first M prime no.
You'll also have to handle an edge case like n=4, m=2
Or n=6 m=3
Here greedy can give -1 because from 4, it'll subtract 3, then 1 remains which is not possible.... So we'll have to add a condition that after the subtraction, the remaining no. Should not be 1
import java.util.*;
class HelloWorld {
static boolean a[];
static ArrayList b=new ArrayList();
public static void solve(int n,int m)
{
Arrays.fill(a,true);
int o=0;
for(int i=2;ib.get(i))
{ ans+=(n/b.get(i)-1);
n=n%b.get(i)+b.get(i);
}
}
System.out.println(ans);
}
}
I checked for these edge cases and it is working can you let me know any case in which it is failing
@@shardendushekharchaubey5582 after subtracting if its 0 we got answer, but if we get 1 then don't take it, move towards smaller prime.
agar esa hota hai to meri job toh lagne se rahi😰😰😭
hello
kabhi kisi ko amazon ko amahzin bolte suna hai
his voice was shaking
test
Step1: Make an array with first M prime numbers
Step2: Use unbounded knapsack
code:
import java.util.*;
class Solution {
public static int minPrimes(int N, int M) {
int[] arr = findPrimes(M);
int ans = unbounded_Knapsack(arr, N);
return ans;
}
public static int unbounded_Knapsack(int[] nums, int N) {
int len = nums.length;
int[][] t = new int[len + 1][N + 1];
for (int i = 0; i
All fake and bogus
Are you good at problem solving?
@@Sushank777 No one is !
@@shamsulhaque55 stfu... those who work hard to improve problem solving skills are good at it... So, go first improve yourself it's better than criticising someone who is 1000X better than you.
Btw what's your codechef or codeforces profile?
🤣
@@shamsulhaque55 i am
How can I get a chance to give a live mock with striver?? @striver @take U forward
38:30