Great solution. I have small doubt in line #26. skirtAndTops[limit] < remaining, here it should be greater than(>)? Remaining cost greater than skirtAndTops than increment limit by 1
good stuff. two bugs: 1. limit = 0 should be inside the for loop, before the while loop; 2. In the while loop, skirtsAndTops[limit] should be > remaining
Hey byakunine, `limit = 0` is intentionally outside the for loop. We do not want to reset it. We will keep moving it forward by one as the `jeansAndShoes` we're iterating through in the for loop will get more and more expensive. As for the while loop, you're right. Stupid typo. I'm going to make a note of it now in the annotations. Thank you! :)
Why can't list combination if all the 4 input lists and then sort the final list? lst = [] for j in jeans: for s in shoes: for sk in skirts: for t in tops: lst.append(j+s+sk+t) lst.sort() i=0 while i < len(lst) and lst[i]
@@krishnakumar-pj9dd Yup! The brute force approach is a great one to mention as a starting point; however, more often than not, you can improve on that :)
Wow *facepalm*. Laughing out loud at this. I agree this problem is worthy of being the favorite. I was doing recursion with a memo of dimensions Classes X (Budget + 1), and getting memory error (presumably when the budget was enormous, the memo got too big). This solution is mind blowing. Thank you so much for posting.
right?? incredible problem + solution -- wish i was clever enough to have come up with it all myself ahahah.. but we made it here, that's all that counts :D
a hack as a we know the array will be of type int we can implement counting /bucket sort which is of linear complexity and might end up saving some time .
You're absolutely right, I hadn't thought about that. Radix sort would be lovely here to implement on lines 18 and 19. Thanks a lot for the suggestion!
Great solution! I wish I could think of this when I did my OA lol. But I think there is a mistake in your solution as different integers can sum up to the same amount. So you have to keep 2 maps of counts, for example, there could be 4 different combos of JS that sum up to the price of 16.
ahah it was a real toughie man. i know there's def one typo (see pinned comment) where i confused an inequality on line 26 b/c that's just what happens when i don't shut up enough wile coding. as for the count, i'm not sure i follow! We're essentially checking every possible combination here!
Thanks so much for this solution, I was breaking my head over it and I couldn't think of anything but the brute force algorithm. Is this complexity of n^3, then?
I'd actually argue that it's O(N^2) as I mentioned in the video; the reason is that the first two `for` loops are O(N^2) operations, while the second walkthrough is a "linear" one. The reason I use linear in quotes is because it consists of N^2 elements, not N elements. (For simplicity sake, I'm assuming that each input array has N elements). So, that gives us O(3 * N^2) operations => O(N^2) :)
Hey I'm preparing for my vmware interview next week and I've watched a few of your videos. They are really helpful. Have you considered using repl.it btw for your online ide? I find it better than this website
Hey Ayush, very happy to hear they've been helpful. Best of luck with the interview!! As for the IDE, I know I'm very much a minority in this opinion but I'm not a huge fan of repl (not that this one is much better, per se). Maybe next time I'll just run with VSC :)
Great solution. I have small doubt in line #26. skirtAndTops[limit] < remaining, here it should be greater than(>)? Remaining cost greater than skirtAndTops than increment limit by 1
Yup! I've made a note of that error in the description :) I'll pin your comment so that others see it as well.
Hey , I got this question in my cisco interview . Was able to solve the question because of your video. Really appreciate the video . Thanks
BOOM you love to see it!!!!
good stuff. two bugs: 1. limit = 0 should be inside the for loop, before the while loop; 2. In the while loop, skirtsAndTops[limit] should be > remaining
Hey byakunine,
`limit = 0` is intentionally outside the for loop. We do not want to reset it. We will keep moving it forward by one as the `jeansAndShoes` we're iterating through in the for loop will get more and more expensive.
As for the while loop, you're right. Stupid typo. I'm going to make a note of it now in the annotations. Thank you! :)
Why can't list combination if all the 4 input lists and then sort the final list?
lst = []
for j in jeans:
for s in shoes:
for sk in skirts:
for t in tops:
lst.append(j+s+sk+t)
lst.sort()
i=0
while i < len(lst) and lst[i]
You could, but this would be the brute force approach with time complexity of O(n^4).
@@babybear-hq9yd OK. So we should avoid it as much possible? Just to understand so that I can avoid the bad practices
@@krishnakumar-pj9dd Yup! The brute force approach is a great one to mention as a starting point; however, more often than not, you can improve on that :)
Wow *facepalm*. Laughing out loud at this. I agree this problem is worthy of being the favorite. I was doing recursion with a memo of dimensions Classes X (Budget + 1), and getting memory error (presumably when the budget was enormous, the memo got too big). This solution is mind blowing. Thank you so much for posting.
right?? incredible problem + solution -- wish i was clever enough to have come up with it all myself ahahah.. but we made it here, that's all that counts :D
Great stuff! It would be great if you run some test cases though in the end to test the solution.
Yeah that's a fair point, my lazy ass should've definitely thought of that. I'll make sure to do so in the next similar video!! :)
a hack as a we know the array will be of type int we can implement counting /bucket sort which is of linear complexity and might end up saving some time .
You're absolutely right, I hadn't thought about that. Radix sort would be lovely here to implement on lines 18 and 19. Thanks a lot for the suggestion!
Great solution! I wish I could think of this when I did my OA lol. But I think there is a mistake in your solution as different integers can sum up to the same amount. So you have to keep 2 maps of counts, for example, there could be 4 different combos of JS that sum up to the price of 16.
ahah it was a real toughie man. i know there's def one typo (see pinned comment) where i confused an inequality on line 26 b/c that's just what happens when i don't shut up enough wile coding. as for the count, i'm not sure i follow! We're essentially checking every possible combination here!
@@babybear-hq9yd Hey, now that I gave it another thought, you're right!
Thanks so much for this solution, I was breaking my head over it and I couldn't think of anything but the brute force algorithm. Is this complexity of n^3, then?
I'd actually argue that it's O(N^2) as I mentioned in the video; the reason is that the first two `for` loops are O(N^2) operations, while the second walkthrough is a "linear" one. The reason I use linear in quotes is because it consists of N^2 elements, not N elements. (For simplicity sake, I'm assuming that each input array has N elements). So, that gives us O(3 * N^2) operations => O(N^2) :)
@@babybear-hq9yd Oh, alright, thanks!
@@babybear-hq9yd Wouldn't it be O(n^2 log n^2) since you need to sort each of the resulting permutation arrays?
you can use binary search here for faster time
wheres your solution then? SHow us
Hey I'm preparing for my vmware interview next week and I've watched a few of your videos. They are really helpful.
Have you considered using repl.it btw for your online ide? I find it better than this website
Hey Ayush, very happy to hear they've been helpful. Best of luck with the interview!!
As for the IDE, I know I'm very much a minority in this opinion but I'm not a huge fan of repl (not that this one is much better, per se). Maybe next time I'll just run with VSC :)
@@babybear-hq9yd thanks man! Best of luck growing your channel
Chad coder
LMFAOO!!