4 Hacks for Finding the Optimal Answer in Coding Interview QUICKLY!
ฝัง
- เผยแพร่เมื่อ 4 มี.ค. 2016
- *Just getting started with coding interviews? Check out my "Get Ready for Your Coding Interview" course on Lynda.com:
www.lynda.com/Software-Develo...
(You'll get a 30-day trial with the link) - วิทยาศาสตร์และเทคโนโลยี
when presented with a problem, I always go with "aaaaaaaaaaaaaaaaaa!" Gets me a job every time.
hehehehehehehe
"Is this a good strategy?"
"No"
But that was the only strategy.
: D
Lol 😂
So I wanted to see the oldest video on this channel - it's still amazing! haha
Now that you expplained it, I think I like it more expressive so nice!
Awesome video... really helpful!!
Hmm....so,from the start of the array to the end of the array,i'm gonna sum each positive num i found,if i found a negative num,i'll compare my current sum to the temporary max number,if the current sum is bigger im gonna replace the temp max with current sum,otherwise i'll just reset the current sum to 0 and carry on.The big-O is gonna be O(n)...But the small problem is what should be my inital max number?should i just put 0 since 0 is the smallest positive number that i can compare to in order to find the highest sum?
Me: Is this a good strategy?
Interviewer: No
Me: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
Nicely explained thanks a lot 👍🏻
unfortunately, this doesn't work in the online interview:( unless you are given a chance for face to face interview.
Thanks brother
Hey Dojo!, What software / hardware are you using to make this video? Thanks so much in advance, love your videos!
csdojo.io/faq!
what program are you drawing with?
really nice, thanks for your help
hey Dojo can you make a video on python IDLE, please
I don't know how I'd do this in code, but I guess to solve this very specific problem I'd separate the array into multiple arrays where negative numbers are the breakpoint, i.e I make new arrays out of the numbers between all negative numbers. After I iterate through all and find which array has the maximum sum. Any other ways of doing it?
But neighbouring positive subarrays are worth merging if they are both greeater in magnitude than the negative subarray between them. In the example given 1 -3 +3 is not an improvement over 3 but if the input was [5, -2 , -1, 4, 6, -5, 1] you would want to merge.
Nice
the interviewer may have a REALLY good poker face and say NOTHING.
The solution to this problem is O(n) if anyone is wondering
this is probably not optimal, but i would just check every possible continuos sub array and compare them to find the max sum.
Why -3 and 2 can't be subarray??
Lovely Aarohi because we need to find greatest
Sum
Because they are not next to eachother
He's asking for a Contiguous subarray, only made up of elements that are directly before &/or after each other
T(n)=2T(n/2)+n --> T(n)=theta(n)
Actually that is O(n*log(n)). This is the proof:
T(n) = 2*T(n/2) + n
T(n) = 2*(2*T(n/4) + n/2) + n
T(n) = 4*T(n/4) + n + n
T(n) = 4*T(n/4) + 2*n
In general, if you continue this k times, then you would see that it would end up like this:
T(n) = (2^k)*T(n/(2^k)) + k*n
Then you must apply a base case such as T(1) = O(1). (I'm not sure what else you can make this but it could up becoming an exponentially growing problem, which is very bad)
So to get to the base case the term inside T(n/(2^k)) must equal to 1. And
n/(2^k) = 1
n = 2^k
log_2(n) = k*log_2(2)
log_2(n) = k
Then you apply this to the original T(n) function and replace T(n/(2^k)) with T(1) because that was where we wanted to end up based on our last condition we applied.
T(n) = 2^[log_2(n)] * T(1) + log_2(n) * n
T(n) = n*T(1) + n*log_2(n)
Since we know T(1) = O(1) as the base case we can do:
T(n) = n * O(1) + n*log_2(n)
You can see here n*log_2(n) is the dominating term thus it would follow that:
T(n) = O(n*log_2(n))
In general, O(f(n)) = c*f(n). Most times you would see that people drop the base and make it O(n*log(n)) because it can be factored into the constant like so:
O(log_2(n)) = c*log_2(n) = c * (1/log(2)) * log(n) = C * log(n) = O(log(n))
What it is how can start these type where can start long o() .....
I came for Karaoke.
whats the solution Dx ?
I would assume it's something to do with weights or stopping if you come across a negative number. So just start adding each of the items in the array. If
Actually thats not the right anwser. Imagine a set of numbers in which after a small negative number there is a huge positive number, for example: 1, 2, -1, 100. In this case the biggest subsequence of numbers in array is whole array, as -1 + 100 = 99 and then we can add 1 and 2 to get 101. The actual solution is to keep a sum of all numbers already seen in a variable (lets call it "current_sum"). When we find next number we add it to our sum (doesn't matter if its negative at this point) and check if its bigger than the largest sum that we have already found (another variable - let's say "biggest_sum"). Then we countinue to add next numbers until our current_sum is < 0. That's the point where we want to reset our curr_sum.
All we have to do is (in each iteration) check if curr_sum is bigger than biggest_sum and then check if curr_sum < 0. If it is we reset it, either way we continue to add numbers. A short example:
Numbers:
15 -20 100 -> 100
Curr_sum:
15 0 100 -> 100
A differet example:
Numbers:
15 -10 100 -> 105
Curr_sum:
15 5 105 ->105
This algorithm enables to check for that subsequence in linear time :)
The term for "current sum" (accumulated sum of all elements in the preceding sequence including the current element) is called "partial sum". It's one of those fundamental problems (as in: many problems can be reduced to it).
Kadanes algorithm
What i would do is keep adding the numbers to the set, if i find a negative number, with a backtracking technique i split the problem in two, one where i add the negative number to the current set and another one where i start with a new subset, meanwhile comparing so when it finishes i get the subset with maximun sum
First video
Channel cs dojo
Easy O(n)
Shaun Patterson what's the answer?
kadane algorithm
Yup, o(n) lower bound. Decently fast.
before I watch you solve it: I have though and come up with an answer: save all contiguous positive integers in their respective subarrays, and save all the negative numbers in a single subarray. If there are positive numbers, find the positive subarray with the greatest sum and return that sum. Else, return the greatest negative integer and that is your largest sub-array. Now time to see if I was right lol
you didn't say the optimal solution but I guess what I did was okay
for Bogdan -> But the sum of all 3 is the biggest number you can find there.
No, 10 would just be the largest subarray then. Cause a subarray can just be a single thing. So whenever you hit a negative, stop adding, and see if it's bigger than the biggest one you've currently found, if it is, it replaces the "highest", and you keep going.
nope
The whole point is deciding whether a negative number somewhere (or a chunk of those) that separates two positive chunks is worth including or not... so just omitting the negative chunks is gonna take you nowhere. Imagine you have a data set of 1 million entries and just one negative number somewhere in the middle. Your "solution" would omit the negative part separating the rest into two chunks whereas clearly the total sum would be bigger, including the negative number. This holds true for any subset from npNpn (where n and p refer to a _chunk_ of neg or pos numbers), clearly you can see that it's possible for pNp to be larger than either p. That's the whole point of thinking about the code, whether and when to include any negative numbers, not just omitting them. The task is to find "maximum sub-array, not maximum contiguous positive numbers.
♥️♥️♥️♥️♥️
Ka bola hai tu😕
ahh yes the people who are waiting for his next upload since he has been gone for 2 months like this comment btw if 2021 or any year after this gets better please reply.
join back to google ):
The interviewer should not say you are going in the right or wrong direction. They should sit quietly to see how you work it out. Don't hire that interviewer.
not really
sometimes the interviewer guides you to a certain direction because he needs to see how you react in situations or adapt to a different scenario...
Horrible advice, especially for a complex question or problem at hand. In a real-life scenario, you always have other team-mates and architect(s) at your disposal to ask questions and work collaboratively. This is a key part of the interview - to ask the right questions and ask for help when and if needed, to see how well you work with other team members on solving a problem. Obviously if the interviewee fails miserably, that should be a determining factor, but otherwise - any company that outright discourages this should be avoided completely.
Why should not? Is this a interview (possible teamwork with interviewer in future) or is this competition who knows more and there is 1kk$ prize?
+responsibleparty
They absolutely should. Professional programming is about using your resources, not seeing who the autistic savant is.
+Landon J Powell During my extensive years, I found out you can learn more when you are listening than you can when you're talking.