Minutes after posting this video, I'm going live on my second channel @Errichto2 where I will solve a practice problem of coming Google Hash Code 2020! th-cam.com/users/errichto2live
Thanks, please make more of these videos, try to simplify it more. Nick White After so many videos he started to explain things in a very good way please don't take that much time hahaha. you're awsome keep it up :)
@@mohamedsamir952 By simplifying do you mean making a video longer and thus easier to understand (more examples etc.), or making it shorter and skipping details and some extra explanation?
@@Errichto The Duration is good, we could have a very easy solution not considering time or space complexity consider only easy to understand for a kid and another one considering time and space any other aspect and combined if conditions.
@@mohamedsamir952 , what more simplification do you need than that. Personally, I don't feel there's any need to change. This video was upto the point and any change wouldn't have done much good.
From the thumbnail I found it an extremely easy problem, but the way you thought of using the fake pointer and combining the list in the end was fascinating 💕
@@arymaulana27x there are a lot of coders, and many basis of comparison. Hes the best coder as a TH-cam teacher to teach competitive algorithm building while someone like Gennady Korotkevich is the best competitive coder in Google Hash Challenges and probably a few others.
Thank you for this. Very efficient, and very well explained. I remember back in my interviewing experience, I failed this question. Also to add it, AI-based company in China have this question asked in their online coding interview.
Hi Errichto, thank you for the helpful walkthrough! I think your initial attempt had a compiler error, something similar to this: int* a, b; This will actually create “int *a” and “int b” but you then treated b as a pointer. (This is actually why “int *a” is more common than “int* a” to avoid such errors) Edit: lol I had to break the last line, because the double stars created a bold text
This is one of the questions that I got for my Amazon interview, so I had to click on it. This was by far the easiest of the questions (at least that I got) if anyone was wondering. I got the job with a very similar answer to his.
I tried to solve this on my own before watching and want to know what you think. My solution has identical time and space complexity, and it works by starting from the tails of each linked list. Compare the tails, the larger of which remains the tail, the smaller changes it’s pointer from null to the tail of the new largest. The end condition from here is that only one head corresponds to the tail. Until then, the two nodes currently pointing to the same node are compared, the larger is unchanged and the smaller changes its pointer to the larger. If two nodes are equal one is simply picked.
Great vid @Errichto! One small thing: I believe most people would find it cleaner to refactor the while loop as such: while (l1 && l2) { if (l1->val < l2->val) { last->next = l1; l1 = l1->next; } else { last->next = l2; l2 = l2->next; } last = last->next; } Essentially, I moved the advancement of 'last' to the last line in the loop, as it will run regardless of the current smaller being l1 or l2.
Haven't watched yet, this is what I came up with. 0. You have lists aList and bList. 1. Create new list, cLst, with length equal to sum of aLst's and bLst's length. 2. Define three new variables, aCnt, bCnt, and cCnt, to be either all 1 or all 0 depending on how your language handles array indices. 3. Compare aLst[aCnt] to bLst[bCnt]. 4. Define cLst[cCnt] to be whichever one is smaller. 5. Increment both cCnt and either aCnt or bCnt (depending on the result of step 3) by 1. 6. Repeat steps 3-5 until you hit the end of one of the original lists. 7. Run through the remaining original list and use the values to define the remaining values of cLst. /* Given: Two integer arrays, aLst and bLst. My "Solution": Note, I use underscores in place of tabs/whitespace. */ int aLen = sizeof(aLst)/sizeof(aLst[0]); int bLen = sizeof(bLst)/sizeof(bLst[0]); int cLen = aLen + bLen; int cLst[cLen]; int aCnt = 0, bCnt = 0, cCnt = 0; while ((aCnt < aLen) && (bCnt < bLen)) { __if (aLst[aCnt] < bLst[bCnt]) { ____cLst[cCnt] = aLst[aCnt]; ____aCnt++; } else { ____cLst[cCnt] = bLst(bCnt); ____bCnt++; } __cCnt++; } while (aCnt < aLen) { __cLst[cCnt] = aLst[aCnt]; __aCnt++; __cCnt++; } while (bCnt < bLen) { __cLst[cCnt] = bLst[bCnt]; __bCnt++; __cCnt++; }
I'm just a script kiddie, so I'm 100% sure there's a better way to do this and that I've made a few mistakes. Also, yeah I just assume aLst and bLst are int arrays.
great video but I think the linked list version is difference from the vector version since the linked list version dose not allocate extra memory its more like inplace_sort for vector
Thanks for the excellent explanation. I didn't understand why you returned fake.next or how did you save the head of the final list. In the first line, you created a node fake, then gave its address to a pointer last. Let's take an example: l1 = [1, 3, 4] and l2=[1, 2, 5, 6, 8]. As l1 ends first, last will point to 5. On line 32, last will point to 6. In all the cases last pointer is getting updated. When did the fake.next get updated? I can't picture it, please suggest any material if necessary. Thanks!
think of the constructor as a method that is called by the complier as soon as you create an object in memory. The constructor is used to initialize the variables for that object, as in the case we can set "val" for every node as 0 and "next" pointer as null
You can use OOP in C and make constructors almost like in C++: struct S { int data; }; S_constructor(struct S* This, int i) { This->data = i; } // constructor .... struct S* s = (struct S*)malloc(sizeof(S)); // allocating memory S_constructor(s, 1); // execute a constructor but OOP in C++ it is much simpler: struct C { int data; C(int i) { this->data = i; } } ... C* c = new C(1); // allocating memory and calling constructor constructors are special functions that are called automatically after allocating memory for an object. In C you have to run a function that can initialize fields but you could forget that. In C++ compiler "new" will always remember to call that function.
I know I'm wrong but wouldn't merging two sorted lists be like this (in Python): a = [4, 7, 8, 9, 10] b = [2, 5, 6, 12, 14] for i in b: a.append(i) answer = sorted(a) print(answer)
@@saiswaroop5889 yes i know, python can never meet c or c++ level in term of speed. But LOC will be quiet less😅. And yes python also don't support linked list directly. I was just showing alternative for Joshiah Valdez's code.
@@skylordak it's not about python, the approach isn't great. Adding two lists is O(m+n) and sorting it is O(x log x) where x=m+n. I am sure what errichto did would have a better run time
Nice explanation, just a couple of quick validations: - this solution will crash on two empty lists, right? - would it be more precise to say that the complexity is O( min( | L1 |, | L2 | ) ) ?
so if you're following the TechLead/Clement Mihailescu* trajectory you'll soon be creating your own code challenge website? (* and now it looks like BackToBackSWE too)
I dont understand when you're returning fake.next. Is that just going to iterate and print each node individually on multiple runs like this 2 3 5 7 Or is it going to print them inside of a linked listed in one run like this (2,3,5,7)?
Hi, does it work in an interview? var list1 = [2,5,7,8]; var list2 = [3,4,5,9,12]; var output = list1.concat(list2); console.log(output.sort(ascendingSort)); function ascendingSort(a, b) { return a - b; }
Ummmm... wont be the complexity of this algo be O(Min(n, m)) ?? Because as soon as we are done with the smaller list , it take O(1) time to point the last pointer of to second list.
I know your question is a year old, but the answer is no, because the last element of the smaller list might have the highest value. In that case you would still need to traverse the whole longer list until you can finally place that highest value at the end
@@vals7266 Hahaha .. No worries. Makes sense. I was too focused on completing smallest list. but it is not necessary that smallest list will be consumed first.
I am a beginner. Maybe that's why this is happening with me. Rather than creating that fake node like you what I did is: ListNode* fake; fake->val = 100; last=fake; . . . . . return fake->next; It's giving me run-time error. Any reason? What am I doing wrong?
Thank you for replying first of all :). Yes I did what you said too. When I write fake->next=NULL it gives me same error saying, run-time error: member access within null pointer of type 'struct ListNode'
In java, the class ListNode would have another ListNode in it representing the next. like: public class ListNode { public int val; public ListNode next; public ListNode(int val, ListNode next){ this.val = val; this.next = next; } } You can make the attributes private and create getter/setter methods
Hey errichto just a simple doubt here ..... Our main motive here is that we should keep the space complexity to be O1 so what if I create a new list and create it's node on the basis of corresponding nodes from the given lists and deleting from the head of both lists .... That way we are deleting and creating a single node at a time thus using same amount of space that we are deleting so don't you think the space complexity will be O1 here ?
What do you mean by deleting? This is exactly what my solution does ;p there is just no such thing as deleting from the front (at least not different from doing head=head.next)
@@Errichto I think this is the first video with noticeable cuts ( atleast I didn't notice anything in previous videos ). I think I would prefer videos without cuts, even if you took longer or maybe went wrong and later corrected it. Ofcourse, it can also be unavoidable, just wanted to provide a suggestion.
You’re right but interview questions are about problem solving more than knowing the specifics of a programming language. Avoiding memory leaks is also not required in competitive programming which is probably why he didn’t.
![ปฏิเสธไม่ไหว (Crush on you) - LIPTA feat. No One Else [TEASER MV]](http://i.ytimg.com/vi/VC689EgdSIw/mqdefault.jpg)
Minutes after posting this video, I'm going live on my second channel @Errichto2 where I will solve a practice problem of coming Google Hash Code 2020!
th-cam.com/users/errichto2live
Hi can you please make video on finding second largest and smallest element in an array
Thanks, please make more of these videos, try to simplify it more.
Nick White After so many videos he started to explain things in a very good way please don't take that much time hahaha. you're awsome keep it up :)
@@mohamedsamir952 By simplifying do you mean making a video longer and thus easier to understand (more examples etc.), or making it shorter and skipping details and some extra explanation?
@@Errichto The Duration is good, we could have a very easy solution not considering time or space complexity consider only easy to understand for a kid and another one considering time and space any other aspect and combined if conditions.
@@mohamedsamir952 , what more simplification do you need than that. Personally, I don't feel there's any need to change. This video was upto the point and any change wouldn't have done much good.
From the thumbnail I found it an extremely easy problem, but the way you thought of using the fake pointer and combining the list in the end was fascinating 💕
what a great luxury to be able to learn coding problems' from WORLD'S BEST CODER!!!!
Abbe chalna 😂
Damn right bro 💯
He's the second btw
@@arymaulana27x there are a lot of coders, and many basis of comparison. Hes the best coder as a TH-cam teacher to teach competitive algorithm building while someone like Gennady Korotkevich is the best competitive coder in Google Hash Challenges and probably a few others.
Arvind Sagar Gennady is the best competitive coder in the world
Thank you for this. Very efficient, and very well explained. I remember back in my interviewing experience, I failed this question.
Also to add it, AI-based company in China have this question asked in their online coding interview.
Hi Errichto, thank you for the helpful walkthrough!
I think your initial attempt had a compiler error, something similar to this:
int* a, b;
This will actually create “int *a” and “int b” but you then treated b as a pointer.
(This is actually why “int *a”
is more common than “int* a” to avoid such errors)
Edit: lol I had to break the last line, because the double stars created a bold text
This is one of the questions that I got for my Amazon interview, so I had to click on it. This was by far the easiest of the questions (at least that I got) if anyone was wondering.
I got the job with a very similar answer to his.
great explanation, and the idea of fake node is brilliant. Thanks errichto
Best explanation video on Universe
I was literally just doing this problem and had trouble finding a solution. Thank you so much!
The last efficient solution is explained very well. Thank you sir and keep making these kind of problem videos.
The fake vertex thing is awesome, never thought/heard of that before.
U finally added company names to your video titles.. 👏
Following advice from @NickWhite, we'll see how it goes :D
@@Errichto yeah noticed u saying this in your stream
Thanks. An easy problem, but still some areas for mistakes like null reference.
What an explanation brother !! Love from India
I tried to solve this on my own before watching and want to know what you think. My solution has identical time and space complexity, and it works by starting from the tails of each linked list. Compare the tails, the larger of which remains the tail, the smaller changes it’s pointer from null to the tail of the new largest. The end condition from here is that only one head corresponds to the tail. Until then, the two nodes currently pointing to the same node are compared, the larger is unchanged and the smaller changes its pointer to the larger. If two nodes are equal one is simply picked.
But how do you move from tails back?
Errichto Ya I was uncertain on implementation but it would be easier on a double linked list. How dumb would an interviewer look at me for my answer?
Please make some more videos on interview questions. Loved this one!
Great vid @Errichto! One small thing: I believe most people would find it cleaner to refactor the while loop as such:
while (l1 && l2) {
if (l1->val < l2->val) {
last->next = l1;
l1 = l1->next;
} else {
last->next = l2;
l2 = l2->next;
}
last = last->next;
}
Essentially, I moved the advancement of 'last' to the last line in the loop, as it will run regardless of the current smaller being l1 or l2.
Thanks, Errichto!
Need more such videos, awesome quality content!
You're amazing! Thanks for spreading your knowledge and view on problems.
I really enjoy your explanations! Keep them coming :)
Amazing video. Thank you so much for making it. It is very helpful!
Haven't watched yet, this is what I came up with.
0. You have lists aList and bList.
1. Create new list, cLst, with length equal to sum of aLst's and bLst's length.
2. Define three new variables, aCnt, bCnt, and cCnt, to be either all 1 or all 0 depending on how your language handles array indices.
3. Compare aLst[aCnt] to bLst[bCnt].
4. Define cLst[cCnt] to be whichever one is smaller.
5. Increment both cCnt and either aCnt or bCnt (depending on the result of step 3) by 1.
6. Repeat steps 3-5 until you hit the end of one of the original lists.
7. Run through the remaining original list and use the values to define the remaining values of cLst.
/*
Given:
Two integer arrays, aLst and bLst.
My "Solution":
Note, I use underscores in place of tabs/whitespace.
*/
int aLen = sizeof(aLst)/sizeof(aLst[0]);
int bLen = sizeof(bLst)/sizeof(bLst[0]);
int cLen = aLen + bLen;
int cLst[cLen];
int aCnt = 0, bCnt = 0, cCnt = 0;
while ((aCnt < aLen) && (bCnt < bLen)) {
__if (aLst[aCnt] < bLst[bCnt]) {
____cLst[cCnt] = aLst[aCnt];
____aCnt++;
} else {
____cLst[cCnt] = bLst(bCnt);
____bCnt++;
}
__cCnt++;
}
while (aCnt < aLen) {
__cLst[cCnt] = aLst[aCnt];
__aCnt++;
__cCnt++;
}
while (bCnt < bLen) {
__cLst[cCnt] = bLst[bCnt];
__bCnt++;
__cCnt++;
}
I'm just a script kiddie, so I'm 100% sure there's a better way to do this and that I've made a few mistakes. Also, yeah I just assume aLst and bLst are int arrays.
@@wompastompa3692 Well, maybe watch a video then ;p solving this for lists and arrays is quite different, and I explained both.
great video but I think the linked list version is difference from the vector version since the linked list version dose not allocate extra memory its more like inplace_sort for vector
That starting fake pointer is ingenious
Thanks for the excellent explanation. I didn't understand why you returned fake.next or how did you save the head of the final list. In the first line, you created a node fake, then gave its address to a pointer last.
Let's take an example: l1 = [1, 3, 4] and l2=[1, 2, 5, 6, 8]. As l1 ends first, last will point to 5. On line 32, last will point to 6. In all the cases last pointer is getting updated. When did the fake.next get updated? I can't picture it, please suggest any material if necessary. Thanks!
thank goodness i dont work for amazon, they still struggle with sort..missing the forest, for the trees
I have recently came to c++ from c I want to ask that what is that constructor used for how is it working actually..the concept would be very helpful
Read up on OOP, especially classes. The example in the video was a implementation of linked list.
think of the constructor as a method that is called by the complier as soon as you create an object in memory. The constructor is used to initialize the variables for that object, as in the case we can set "val" for every node as 0 and "next" pointer as null
You can use OOP in C and make constructors almost like in C++:
struct S {
int data;
};
S_constructor(struct S* This, int i) { This->data = i; } // constructor
....
struct S* s = (struct S*)malloc(sizeof(S)); // allocating memory
S_constructor(s, 1); // execute a constructor
but OOP in C++ it is much simpler:
struct C {
int data;
C(int i) { this->data = i; }
}
...
C* c = new C(1); // allocating memory and calling constructor
constructors are special functions that are called automatically after allocating memory for an object. In C you have to run a function that can initialize fields but you could forget that. In C++ compiler "new" will always remember to call that function.
Nice explanation
I know I'm wrong but wouldn't merging two sorted lists be like this (in Python):
a = [4, 7, 8, 9, 10]
b = [2, 5, 6, 12, 14]
for i in b:
a.append(i)
answer = sorted(a)
print(answer)
print (sorted(a+b))
This might also work😅
@@skylordak Hahaha wow, what I put was the first thing I thought of. That is way more efficient 😖😂
@@josiahvaldez8452 both of your solutions are not optimal
@@saiswaroop5889 yes i know, python can never meet c or c++ level in term of speed. But LOC will be quiet less😅. And yes python also don't support linked list directly. I was just showing alternative for Joshiah Valdez's code.
@@skylordak it's not about python, the approach isn't great. Adding two lists is O(m+n) and sorting it is O(x log x) where x=m+n.
I am sure what errichto did would have a better run time
was really helpful..... hoping more of this from u....
Nice explanation, just a couple of quick validations:
- this solution will crash on two empty lists, right?
- would it be more precise to say that the complexity is O( min( | L1 |, | L2 | ) ) ?
No, and no
Wow, awesome explanation. And i thought that my merge sort with arrays was enough hahaha.
Nice explanation.
Great explanation :)
so if you're following the TechLead/Clement Mihailescu* trajectory you'll soon be creating your own code challenge website? (* and now it looks like BackToBackSWE too)
I dont understand when you're returning fake.next. Is that just going to iterate and print each node individually on multiple runs like this
2
3
5
7
Or is it going to print them inside of a linked listed in one run like this (2,3,5,7)?
We do “fake.next” to return a reference to the start of the actual list, since fake is a dummy node and its next is the actual start of the list.
We do “fake.next” to return a reference to the start of the actual list, since fake is a dummy node and its next is the actual start of the list.
Hi, does it work in an interview?
var list1 = [2,5,7,8];
var list2 = [3,4,5,9,12];
var output = list1.concat(list2);
console.log(output.sort(ascendingSort));
function ascendingSort(a, b) {
return a - b;
}
Your example uses arrays, not linked lists
dude that`s pretty smart! thanks for the good explanation
Wow. Great explanation.🔥
Would it be worth to change my domain from pure devops to this?
Great explanation.. ✌️
What will be worst case time complexity for inserting new node in sorted linkedlist ? What's your answer errichto
You need to go through the whole list so it's O(N).
Very interesting problem
Bro what if we insert both in min heap than remove it its already sorted
amazing !!!
But Sir if you do not use fake vertex and do that if thing then runtime is 4ms. Please comment on this.
Ur really the man! Thanks for your videos! Anyway u can do data structures and algorithms problems on Java? &@Errichto
well, data structures and algo are uni-langual, but my videos will be in C++
@@Errichto C++ rocks !!
Why can we return a struct when the functions return should be a pointer to a struct?
ups my bad we actually do return a pointer by returning the next pointer of the fake ListNode struct.
Thanks for the vidoe
Ummmm... wont be the complexity of this algo be O(Min(n, m)) ??
Because as soon as we are done with the smaller list , it take O(1) time to point the last pointer of to second list.
I know your question is a year old, but the answer is no, because the last element of the smaller list might have the highest value. In that case you would still need to traverse the whole longer list until you can finally place that highest value at the end
@@vals7266 Hahaha .. No worries. Makes sense. I was too focused on completing smallest list. but it is not necessary that smallest list will be consumed first.
I am a beginner. Maybe that's why this is happening with me.
Rather than creating that fake node like you what I did is:
ListNode* fake;
fake->val = 100;
last=fake;
.
.
.
.
.
return fake->next;
It's giving me run-time error. Any reason? What am I doing wrong?
You need to also assign fake->next to something, likely to NULL. Or just use constructor like I did.
Thank you for replying first of all :). Yes I did what you said too. When I write fake->next=NULL it gives me same error saying,
run-time error: member access within null pointer of type 'struct ListNode'
@@nikhilkarve2431 And use a keyword "new" to create a new pointer.
@@Errichto to use new what struct name should I use after new?
Who else is watching this during the interview?
MEDIAN OF TWO SORTED LIST PLS!
Thanks
When u are watching it looks easy but if ur the one whos doing it its hard
Does anybody know if there is another person on yt who does the same videos but in Java? I wonder how this would look without the pointers
In java, the class ListNode would have another ListNode in it representing the next. like:
public class ListNode {
public int val;
public ListNode next;
public ListNode(int val, ListNode next){
this.val = val;
this.next = next;
}
}
You can make the attributes private and create getter/setter methods
Some one help me with this questions I am mugging this question but I want to understand this concept.
can you make a video on the best gear for competitive programming? such as stopwatch etc
You don't really need stopwatch or anything else. I use it only during streams :D
I will consider this though.
Hey errichto just a simple doubt here .....
Our main motive here is that we should keep the space complexity to be O1 so what if I create a new list and create it's node on the basis of corresponding nodes from the given lists and deleting from the head of both lists .... That way we are deleting and creating a single node at a time thus using same amount of space that we are deleting so don't you think the space complexity will be O1 here ?
@Errichto
What do you mean by deleting? This is exactly what my solution does ;p there is just no such thing as deleting from the front (at least not different from doing head=head.next)
I was asked the same problem in my interview and I gave a very bad solution I put both list together in one and then sorted it 😂
Aman Rohilla yes. This is what array.sort() is for
Can u recommend to me a data structure and alghorithms course c++
Iam a freshman year of computer science
Maybe MIT lectures?
@@Errichto yeah, they're pretty cool
I've solved this long time ago. But nothing in my mind now :(((
Why don’t you please some videos in python language?
Cool
12:10 how he did copy the code and magically change l1 to l2
I didn't copy, there is just cut in editing ;p
@@Errichto I think this is the first video with noticeable cuts ( atleast I didn't notice anything in previous videos ). I think I would prefer videos without cuts, even if you took longer or maybe went wrong and later corrected it. Ofcourse, it can also be unavoidable, just wanted to provide a suggestion.
Sir, I recommend you to joint the night's watch. Haha
How can this question be easy 🥵
Errichto you are on of the elite coders don't waste in easy problems like this.....we have enough of this on geeksforgeeks and TH-cam
g4g lol
Simplified recursive approach for merging two sorted linked lists:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == NULL)
return l2;
if(l2 == NULL)
return l1;
if(l1->val > l2->val)
l2->next = mergeTwoLists(l1, l2->next);
else
l1->next = mergeTwoLists(l1->next, l2);
return (l1->val > l2->val)?l2:l1;
}
Shiet, i dont understand this listnode struct code :/
yo listen up
Omg
#include
using namespace std;
class Node {
public:
int data;
Node* next;
};
class LinkedList {
public:
Node* head;
LinkedList() {
head = NULL;
}
void insertNode(int data) {
Node* newNode = new Node;
newNode->data = data;
newNode->next = NULL;
if (head == NULL) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
Node* mergeLists(Node* head2) {
Node dummy;
Node* tail = &dummy;
dummy.next = NULL;
Node* head1 = head;
while (head1 != NULL && head2 != NULL) {
if (head1->data < head2->data) {
tail->next = head1;
head1 = head1->next;
} else {
tail->next = head2;
head2 = head2->next;
}
tail = tail->next;
}
if (head1 != NULL) {
tail->next = head1;
} else {
tail->next = head2;
}
return dummy.next;
}
void displayList() {
Node* temp = head;
while (temp != NULL) {
cout data next;
}
cout n;
LinkedList list1;
cout data;
list1.insertNode(data);
}
LinkedList list2;
cout data;
list2.insertNode(data);
}
list1.head = list1.mergeLists(list2.head);
cout
fake.next was returned without deleting that node. hmm.. memory leak issue.
You’re right but interview questions are about problem solving more than knowing the specifics of a programming language. Avoiding memory leaks is also not required in competitive programming which is probably why he didn’t.