7 Steps to Solve Algorithm Problems

 

 

 

 

 

 

현업 개발자분들의 블로그를 찾아보다가

어찌어찌 알게된 '오키'라는 개발자 커뮤니티,

 

 

그곳에서 곰개발자님의

'해외 취업 팁' 이라는 글을 보고

알게 된 유튜브 사이트

 

 

알고리즘 및 코딩 테스트 입문자들은

먼저 한번 쭉 보라고 하시길래

올커니 하고 들어갔다가

켁 하고 나왔다

 

 

이곳에 글을 쓰고

공부를 시작하도록

동기부여받은 영상

 

---

 

아래는 인터뷰어의 강의 내용 전문

 

 

모르는 단어 체크해 두고

끝까지 소리내어 읽어보고

영상 틀어놓고 듣는 것에 집중해 보고

위 방법을 반복한다

 

 

 

Today's topic is one that you really don't want to miss, 'hash tables'. A hash table is possibly the most useful data structure for interview questions. It comes up all the time both in interviews and in real life. In fact one technique I often tell people is just, for any problem, have hash tables at the top of your mind as a possible technique to solve the problem.

So let's talk a bit about what a hash table is.

 

 

At a high level, a hash table is a key value look up. So it gives you a way of given a key, associating a value with it, for very very quick lookups. So suppose you had some situation where you needed to associate somebody's name with some set of information about them. A hash table would be the perfect solution for this problem because you can just put this into the hash table and then you can say, okay give me the data associated with Mary and then boom we can get that information immediately. So in a hash table the key as well as the value can be basically any type of data structure. A string is often used but it could be a circle, a square, a person, pretty much anything as long as you have a hash function. So what does that mean? Well let's turn to the implementation to talk about that.

 

 

So at a high-level we do want to store the objects in an array. So let's picture that. But how do we actually jump from a string to a particular index in the array? Well that's what a hash function does. So a hash function takes in a string, converts into some sort of integer, and then remaps that integer into an index into that array. And then that's where we can find the person we're looking for. So it's important to understand that the hash is not actually the index in this array. We map actually from the key to the hash code and then over to the index. And one of the reasons for this is that the array that actually stores the data from the hash table, might be much much smaller than all the available potential hash codes. And so we don't want to have an array of three billion just because there's three billion potential hash codes. So we actually remap it into something smaller.

 

 

Now note here that two different strings could actually have the same hash code and that's because there are an infinite number of strings out there but a finite number of hash codes. So it's theoretically possible for Alex and Sarah actually have the same hash code. Additionally since we're remapping the hash code into an even smaller index, two things with different hash codes could actually wind up mapped to the same index. So what do we do with this, when this happens, which is called the collision? There are different ways of resolving collisions and I really do encourage you to look this up on your own time, but I'll just talk about one of them which is called chaining. And chaining is possibly the most common one and it's very simple. But it basically means is just, hey when there is collisions just store them in a linked list. So rather than this being an array of people, it's actually going to be an array of a linked list of people. And so that means though that when you get a call to say hey get the values of Alex, you actually need to look through all the values in that linked list, and pull out the value for Alex.

 

 

Now as you'll note here this linked list contains not just the actual person objects but the actual keys as well. And the reason for that is that if you only store the person object you'd see all these people who mapped to this index but you wouldn't know which one they are. And so you actually need to store the keys with them. So when you get a call to say get me the value for Alex, then you actually call this hash function, you get a hash code back, you map over to this index and then you walk through and look for the thing with the key of Alex. So that's the basics of how a hash table operates. So let's walk through this from start to end. We're going to have this hash table class that underneath it has a array that actually holds the data. And the array isn't going to be an array of the actual values, it's going to be an array of the linked list of the values. Then when someone says put the value of Alex, put the value Alex mapping to this person, we call this hash code function that gets us back the hash code. Then we map from this hash code over to an index and that gets us over to this index in the array and then we put it into this linked list. If there's nothing else, great, then we're just going to have a one element linked list. But there could be multiple values in there, in which case we walk through it. 

 

 

Now what if there is already a value of Alex in there? Well then we just fix that value immediately. So let's talk now about the 'runtime' of a hash table. Well it really depends on what we're talking about and what assumptions we make. In many cases we assume that we have a good hash table and a good hash function that really distributes our values well and so for the purpose of an interview, we often just summarize this and say okay, getting and setting in a hash table is constant time. In reality if something weird happens we have a bad hash function pop of blah, we could also say it is linear time in the very worst case. But for the purpose of most problems we generally talk about constant time because in the real world we're going to make pretty sure hopefully that we have a good hash table. So this is a bit of a high level view of what a hash table is and how it works.

 

 

There's a whole lot of complexity you can dive into here about different ways of handling collisions and exactly what happens when a hash table, you start to put a ton of elements in the hash table, how does it grow with new elements? Does it can be resized? All that sort of stuff. I really do encourage you to go look at this stuff on your own time. It's a fantastic thing to really understand a lot of the complexity here. But the purpose of a lot of interview questions we just sort of simplify all this down and summarize things as, let's assume we have a good hash table and so we get this beautiful constant-time insert find and delete. So now that you understand the basics. Go ahead and do try to learn these more complex details of hash tables, but also go practice some if this basics on your own time on your own problems. Good luck.

 

 

 

뭐라는겨

 

 

---

 

from : 7 Steps to Solve Algorithm Problems

https://www.youtube.com/watch?v=shs0KM3wKv8&list=PLOuZYwbmgZWXvkghUyMLdI90IwxbNCiWK