So, do you think there will be any interview problem that will take me more time than this one? Also, all codes are here github.com/Errichto/youtube/tree/master/leetcode/april-2020-challenge

@ManishKumar-jj1nt

4 жыл бұрын

Yes, there are many. It's just the beginning. No I don't think so just kidding. Everyone subscribe him to see him struggling 😂..just kidding...

@nikhilmakam8794

4 жыл бұрын

Hi @Errichto can you please solve LFU cache implementation? It'd be really helpful to everyone who are preparing for interviews. Thank you:)

@SubhramRana

4 жыл бұрын

@Errichto Can this is solved by DEQUEUE(most and least recent) and HASHMAP( for O(1))

@isupportcharliehebdo-moham3081

4 жыл бұрын

yeh ..can u make a video on yesterday's SRM 784 ..speedingupbozosort problem explaining it ..thank u..!

@miteshkumar3183

4 жыл бұрын

You should make an explanation on how to do the last Hack the interview III problem on hackerrank. The other three are fairly self explanatory.

I love it when I see pro(Errichto) takes time to think like normal people this is inspiring, Thanks! ❤️

@abdelrahmanadel8998

4 жыл бұрын

😂😂

@shashanktiwari4442

4 жыл бұрын

lol until now u thought he is abnormal??XD

@BarkaDog

4 жыл бұрын

@@shashanktiwari4442 if someone who takes hours to solve a problem and then sees someone solve it in minutes, of course you will think he is more than normal XD

@johnhammer8668

4 жыл бұрын

When i see a pro being generous to inspire others and performs a Oscar level acting(acting like mortal average devs) is what gives me hope for humanity.

@wilsonemmanuel1352

4 жыл бұрын

I feel relieved that I'm not alone. He's still the pro

Even experienced programmers take time at the first go for a new problem (albeit an interesting and non-trivial one) - Errichto just proved that. Love the genuine approach :)

You are an original, Errichto!! Very good to see you actually struggle through and still nail this problem!!

Love these kinds of complete thinking, drawing and whole process videos (long ones) :) Helps us understand the process of solving things. At least for me :D

I found this more interesting and informative than a 'tutorial' because you improved your solution while solving it for first time

and i was expected to solve it in 20 mins in todays interview, these interviewers expect you to know everything and write down the code from memory

@sourenasahraian2055

2 жыл бұрын

The interview system is broken and it’s irrelevant, if Google and Facebook do it , every other company thinks , they ought to replicate the process otherwise it’s not good for their image even if it has no overlap with what a developer needs to do in his day to day routin . They need to weed people out they may just as well organize a running contest , it would be just as irrelevant

for those coding in c++ there is std::list.splice function which is so useful to give an element priority in a list. it does actually in O(1) replace an element from a list to wherever you like on the same list(in particular n the beginning)

It is so good to know that he is still human. He always kills the algorithm questions in 5 mins and it was frustrating to see. Thanks! XD

Thank you so much Kamil! This was fun to watch :)

Small C++ tip n.2.: If you initialize member variables in constructor the name of the member variable can be the same as name of the argument and if you use the initializer list you dont even need to write any this keyword. LRUcache(const int capacity) : capacity(capacity) {} Just a warning - if you initialize multiple variables and they depend on each other (not recommended) they are not initialized in the order they are present in the initializer list, but in the order they are declared in the class body.

I used Doubly linked list, With head as most recent and tail as least recent and used an unordered_map to remember which key is present where to bring down time complexity to O(1)

@that_funny_guy496

4 жыл бұрын

This is the only way I knew, but after my successful submission was able to see LinkedHashMap implementation in Java, which is very easy to code.

@ineverchangemyplayericon3016

4 жыл бұрын

Same it took me 1hour and 40 mins to implement using Doubly LL.

@yunjiehong4649

4 жыл бұрын

I wonder whether hashmap is O(1)?

@magnushoklandhegdahl1218

4 жыл бұрын

@@yunjiehong4649 on average, yes.

@that_funny_guy496

4 жыл бұрын

@@yunjiehong4649 So do u have any other data structure for faster access ?

For those people who are thinking pro is taking the same time as an average dev, try solving it and see how much time you think it would take and how much time it really took. Its just impossible without lot having a lot practice to solve a new problem. What is possible for an average dev is to come up with a logic that has errors to solve the problem. But coding is totally a different ball game.

@ArpitKharbandaIsAwesome

4 жыл бұрын

I'm inclined to agree with you!

Can you do a video on such optimisations since questions like do everything in O(1) often comes up in interviews. Ideas like knowing list iterators from before , min stack , min queue etc which can decrease time complexities of obvious tasks . That would be a interesting video to watch

After this video you know the following points : 1) first understand the problem statement 2) determine the suitable data structure according to need 3) gets a rough idea of your process 4) write code and dry run 5) compile and debug your code 6) improve your code

Hi, could you share what's the software you are using to record this video (the drawing, etc.)? Thank you in advance!

Can you elaborate on the last bit about amortized time complexity in your initial code and how an event could trigger more erases in future?

I have done this before still took me more than half an hour, @Errichto how about you also solve LFU!! it will be fun.

YAY! I made a solution in O(1) algorithmic complexity and O(n) memory complexity. Time to watch the video to see if we made the same solution.

@kacperozieblowski3809

3 жыл бұрын

yes, it is the same idea. However yours is clearer and more concise. I implemented my own linked list for some reason and other stuff that makes mine less lisible.

can anyone tell where can I get that timer? looks like it is the same timer that shows up when I google 'timer'... but wanted it to be floating on my screen like Errichto!

I honestly thought he would've eaten this question alive :) this question seem easy compared to Codeforces questions (which I struggle to even read)

20:42 -> that statement was GOLD!

How can I get better at calculating big O ?

Dear Errichto, how to transform this code to run in a distributed and fault tolerant manner ? For e.g we want to achieve extremely high throughput for LRU cache. How do we orchestrate this?

Thanks for the great video.

0:54 fair thinking as a competitive programmer. (What a hell no limitation for n) Because in the interview the program must achieve the time complexity wanted. If there is no time complexity, I guess that should be asked during the interview.

What tools (hardware & software) do you use to draw designs?

Shouldn't find for unordered map give O(N) time complexity at worst case?

What was the time?

What program does he use to draw?

I got this problem at microsoft onsite interview and had 30 minutes to implement. sucked at it.

Love u from the bottom of my heart ❤️💓❤️

I used a queue and a hashmap. The queue was for the recently used items. Used meant adding and getting. The hashmap was having a key which mapped to a pair of integers, the first one being the value and the second one is its frequency of the element being used. This was done such that the frequency of the number of elements in the queue is equal to the sum of frequencies of all the elements. Now the queue and map keep on storing and the capacity is reached. We will do the following till an element is removed We dequeue the queue and for that element, we see if the frequency is greater than 1, then we decrease the frequency. If the frequency is 1, we remove it. After removing an element we add the new element.

@nitishchoudhary9049

4 жыл бұрын

What will be the time complexity of this algo?

@lovvyparhar393

4 жыл бұрын

@@nitishchoudhary9049 for the average case it can be (times used)/(total keys). In the worst case it can be (times used).

@nitishchoudhary9049

4 жыл бұрын

@@lovvyparhar393 thanks.

I know it has to have desirable properties of both hash table and doubly linked list for fast lookup and fast reordering, so I tried to write an int array based approach where each node takes 3 int space (in c++). The first int would be the key, and the third would be the value. The second would be metadata that has a collision flag, 15 bits for previous node position in array, and 15 bits for next node position in array. Although this limits the cache size to 2^15-1, I don't think their test case would be an issue and an LRU cache shouldn't be any bigger than this anyway. But then collision handling would be quite a pain, and I have a lot of course work to do and I'm lazy, so I just went over to Java and used their LinkedHashMap 😂

@Errichto

4 жыл бұрын

No reason to reinvent the wheel. Use struct in C++ instead of having some chunks of int array. And it isn't that easy to implement a good hashmap.

I was very tired from work yesterday, that I decided not to try this one. I'm watching this in a few hours

Similar to LRU cache. There is another interesting problem - given a dictionary (long list of words) find to top k words (k suppose to be small) .

It's a treat for my eyes to see you struggle even if it's for just a second 😌. You're freaking awesome man keep up the good work. I love your videos. Hope for more tutorials. You explain things with the mindset of a Competitive Programmer which is really helpful. Siddhant 'kdKodes' Kedia

I'd like to know more problems like these. Where can I find them

@mohitthorat8580

4 жыл бұрын

LeetCode

I wanna be like you erritcho can you give me your advice??

I am curious about multiple return statements. Like in his put method couldn’t he have fit that in an if/else if structure? I’ve always been told to never have more than one return but is there a better reason?

@simonhrabec9973

4 жыл бұрын

You can have multiple return statements. What it affects is the RVO (return value optimization). It is a more complicated topic but simplifying it is if you have multiple returns statements of some unlucky type, the compiler cannot do an RVO and you will get copies/moves.

@31redorange08

4 жыл бұрын

The people who told you this have no idea.

what is your geany theme ?

@Errichto

4 жыл бұрын

monokai

Nice video

Hi Errichto , thanks for your work, could you please solve problems in live videos?

What program do you use for stopwatch?

@31redorange08

4 жыл бұрын

google.com

@chauhan1999

4 жыл бұрын

@@31redorange08 I can;t find it on chrome for windows. Can you help me how to get it on my current page?

A small C++ coding tip. if statements now have init-statement. It means you can initialize a variable and its scope will be just within the if condition and if body. Therefore you can do: if (const auto it = myMap.find(key); it != std::end(myMay) { do some with e.g. with it->second } it does not exist here anymore.

@adhishmalviya2408

4 жыл бұрын

Thanks'

Using Java : stackoverflow.com/a/46545788 class LRUCache extends LinkedHashMap{ private int maxSize; public LRUCache(int capacity) { super(capacity, 0.75f, true); this.maxSize = capacity; } //return -1 if miss public int get(int key) { Integer v = super.get(key); return v == null ? -1 : v; } public void put(int key, int value) { super.put(key, value); } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return this.size() > maxSize; //must override it if used in a fixed cache } }

I was asked the same problem in Amazon SDE1 interview.....fortunately, I had solved this problem before :D

You can also solve this with Doubly Linked List. The tail will indicate the least recently used element while the head will indicate the last used element. When a key in the LRU cache is accessed remove it from the linked list and put it at the place of head To remove an element just move the tail to its next element.

@gonzalo9558

4 жыл бұрын

okey, but to do this in O(1), you need a hashmap to get the correct node in the get() operation, aswell as to see if there already exists a node in the put operation, right? is there a way to to this in O(1) without the hashmap?

@mahirshahriyar8004

4 жыл бұрын

@@gonzalo9558 unordered_map is O(1) in average case and O(n) in worst case....so I think it will do

@aj9706

4 жыл бұрын

Lru cache using linked hash map kzread.info/dash/bejne/dq6bj5N-gMvdiso.html

In Love With The Teddy. Each Time It seems to have more charm and cuteness!!!

I don't understand how this is O(1) time complexity?

@simonhrabec9973

4 жыл бұрын

HashMap has O(1) amortized and on average (you can mitigate the amortized by initializing the hashmap with a specific size, but cannot mitigate the average as you can get just unlucky keys to fit into the same bucket) for both accessing and inserting. Linked list (c++ std::list is doubly linked) have all operations in O(1) unless you iterate over the whole (or part) list. Removing element (if you have an iterator) is constant, removing/adding/accessing an element from either of the ends is also constant. List is great for these operations but horrible if you have to iterate over multiple elements (not only due to linear complexity, but the memory layout will result in poor performance).

@khushitshah678

4 жыл бұрын

@@simonhrabec9973 thanks now it's getting clear👍

List doesn't gaurantee o(1) removal

@Errichto

4 жыл бұрын

C++ reference says it is O(1) www.cplusplus.com/reference/list/list/erase/

@simonhrabec9973

4 жыл бұрын

I think you might have confused it with "remove" - www.cplusplus.com/reference/list/list/remove/ It is quite understandable, the C++ naming of STL container methods is a mess. If you need to go over a list and remove all occurrences of value (or just the first) then you get linear time complexity. However, if you already have a pointer to the node (i.e. iterator that has not been invalidated), you can just access that node and all that is required is change pointers of the neighbouring elements (+ maybe start of the LL). Different containers have different rules about iterator invalidations, it is interesting to know - www.tutorialspoint.com/iterator-invalidation-in-cplusplus

love the bear

I hate this problem. I got it once in an interview with Apple. I actually managed to solve it in time with some guidance from the interviewer, but I don't understand why would you ask this question. First, you need to figure out a linked hash map. And after that, all the creativity is over. Then comes stupid implementation where it's really easy to forget some stupid corner case or put a wrong reference.

@Errichto

4 жыл бұрын

It's indeed too hard for a coding interview.

@user-mr-m12312

4 жыл бұрын

I don't agree this question is stupid. I'm not that good at solving problems yet, but I've managed to solve this by using hashmap and doubly linked list, and personally for me there were harder problems at leetcode30 challenge wich I couldn't even solve without some help. Well, yes, you need to figure out what data structures to use and handle some edge cases, but it's about everything, for solving dp problems you need to know dp, same for two pointers, bit manipulations, backtracking and so on, otherwise you'll come up with brute force or some ugly solution.

And my Amazon phone screen interviewer wanted me to do this in 20 mins.

Which drawing software do you use

@Errichto

4 жыл бұрын

OneNote

one like for your hard work to solve this problem yourself without checking solution again

How can I smash hard that like button????

This can be easily solved using LinkedHashMap in java in O(1) time with just 6 lines of code

@adhishmalviya2408

4 жыл бұрын

You cant use that in interviews, or maybe you should know how that linked hashmap is implemented

@chriswysocki8816

2 жыл бұрын

That's exactly what I thought and did. It is much simpler than storing iterators (yikes!). As for not being allowed to use LinkedHashMap in an interview, just build it out of ......,.... a linked list and a hashmap! The hashmap simply stores the references to items in the linked list (so that you can find a key in the linked list in O(1) time)

I used LinkedHashMap to solve this

@simonhrabec9973

4 жыл бұрын

I have seen the solution and it feels like cheating lol. With Java, you can just write maybe 5 lines of code :D

@aj9706

4 жыл бұрын

Lru cache using linked hash map kzread.info/dash/bejne/dq6bj5N-gMvdiso.html

its a good example and i don't speak english xD.

In python we can easily solve this by using OrderedDict from the collections library.

@vijays296

4 жыл бұрын

Python has a lot of libraries that can solve some problems easily. But, C++ has many more advantages in competitive programming.

@Paradise-kv7fn

4 жыл бұрын

you can also solve it directly using linkedhashmap in java...but if you say that it in an interview, then the interviewer might ask you to use your own implementation

@L0Ls0ul

4 жыл бұрын

I used that as well. Felt like cheating tbh but I didn't have much time, so I went with it regardless.

@aj9706

4 жыл бұрын

Java Lru cache using linked hash map kzread.info/dash/bejne/dq6bj5N-gMvdiso.html

What I did: (Very Simple) (Accepted) I write in python so the approach is python-like? Have a list, Have a dictionary, (hashmap equivalent in c++?) and a variable which stores capacity. list stores the keys-only and corresponding key-val pairs are in the dictionary. how put works given ( key , val) if( key already in list): just update the value in dictionary which is I believe done in O(1) if not: if(capacity has not reached): good to go and just put the key in list and key-val pair in dict if(capacity has reached): oldkey=list[0] list=list[1:] list.append(key) //append helps in putting at the end. dictionary.add(key,val) dictionary.remove(oldkey) this solution was accepted. now I believe list removal costs O(n), and it is not the fastest way to write but it gets the job done.

stackies is the solution

OrderedDict for Python works very well.

@anilkrajamoni1484

4 жыл бұрын

How?

Hey Errichto, I need your help in problem Painting fence DP problem, If I try the standard algorithm then answer for n = 4, k = 3 gives 66, but if I try brute force it gives 60, I think 60 is correct, could plz figure it out.

Third

second

third

first

I'm assuming any freshmen CS student from Stanford, Berkeley, MIT, Cal Tech, and so on can solve this problem under 10 minutes.