Really helpful video. This reminds me of the classic Two Sum problem on LeetCode. Since we are told a pair of numbers equals a target sum, we can say that x + y = target. And solving for y (complement of x), we see that y = target - x. Therefore, we can just walk through the input sequence and for every element, insert it into a hash set while performing a lookup in the hash set to see if for a given `x` value (arr[i]) we can find a `y` that satisfies x + y = target.
Yeah, interviews are much much harder than this now. Honestly, if you were asked 2 sum today (which you probably will not be), and it took you just as long to solve as in this video, with all the same dialog and clarifying questions etc, you will probably be rejected along with pissing the interviewer off. All LC easies should be trivial for anyone looking to break anywhere into Big Tech.
sum = 0 for element in array: sum += element return sum array1 = [0,1,5,2] total_sum = array_sum(my_array) print("The sum of the array is:", total_sum)
Since comp.find is logarithmic and you are repeating this for every value in data, then the actual time complexity of the function is O(N*logN). Why did they say it was linear?
Not trying to be mean or anything, but I think you may need to review how data is stored in an unordered set. From my understanding, The add function will take the integer and using something similar to a hashing function, get a unique key which is probably used to get the index in the container of the stored value. When you use the find function, it probably uses the same hashing function to get the index of the stored value. If the value isn't found, at that index, the find function goes through the rest of the container to find the value. Here are two facts for you - Average case of find is constant time complexity O(1), and worst case is linear in container size O(n) which can be found at the bottom of the page here: www.cplusplus.com/reference/unordered_set/unordered_set/find/ The worst case of using this function is O(n) so if for all n values in data we have an O(n) time complexity for the find function, the solution will have an O(n^2) time complexity. However, that is highly unlikely seeing as even a basic hashing algorithm with a relatively small prime number can prove to yield O(1) time complexity more often than not. I hope this helps you to learn why they said it was linear! I have a phone interview coming up and I'm hoping to learn and help as many people as I can along the way.
Well The Question goes like this I suppose: lets say (python 3) lst = [1,2,3,4,5,6] for i1 in lst: i2 = 8 - i1 if i2 in lst: print(i1, i2) we get the pairs
Depends. For data science, game development, A LOT of high level maths knowledge is essential. For web/app development, depends on what you're working on. In general, not very much. Although, the mindset is pretty much the same. I could be calculating some integral, or I could be designing a complex architecture for data flow in my webapp, in both cases I feel like I'm solving very similar problems. In both cases, you'll be running through a lot of alternatives in your mind, and quickly choosing the best ones to work with. Problem-solving is what computer science is all about.
For this problem specifically, since there will only be an addition of two number, all you need to do is to subtract one elements of the arrays from 8. If the result matches one of the remaining elements then the number you subtract from and the result will be the pair of two number that sums up to 8. You will only have to do this four times or the number of elements you have in an array.
I haven't been programming for long (and I only know Java), but from the api, I think that comp.end returns true once it goes past the last value in the HashSet. So the IF statement basically says: If this value in the vector equals one of the compliments in the HashSet (which means that it found a sum pair) AND we have NOT reached the end of the HashSet, the return true. In other words, once one of the vector values matches a value in the compliment HashSet, comp.find(value) will be true and comp.end will be false. And since false != true, we will enter the IF statement.
@@58book comp.find(value) returns the index of the value in comp if the value is present, else it returns comp.end(), which is the pointer to the last element of comp(the pointer where the next value will be inserted). If value is present in comp, then comp.find(value) != comp.end(), hence the above if statement.
`+data[hi]`… AND… You've just invoke undefined behavior. EDIT: Wait nevermind. My bad. Implicit conv… Well technically it's still UB. Just way earlier. Signed overflow is still ub (granted if you that large a vector you might want to rethink something. (also infinite loop but that's cheating). Still why use an int where you get a `std::vector::size_type` smh. And that while loop confuses me. (Besides being potentially wrong) I'm way too sleep deprived for that amount of questions. iterators wouldn't kill either. (So many whys) Fix is obviously don't pass keep a `std::numeric_limits::max() + 2ULL` sized vector to the function… Or don't have so many implicit conversations. The answer in itself is fine though. (I'm just over sensitive to potential UB)
Awesome. Thanks for this, is really helpful. You could use a Bloom Filter instead of the hash set to save on space complexity(O(1)) as per you only need to know if the complement is NOT in the list.
For the last part of the problem, wouldn't it have made sense to do some pruning along the way for repeat complements? It would have bumped up the running time, but for a case where space seems to be the main issue, that would be a necessary sacrifice for the problem if you were to not use multiple systems, wouldn't it?
Can someone explain the scaling part to me. 19:47 “If my set fits in memory, but my whole input doesn’t fit in memory then I can just process it in chunks. I chunk it, I just put it in a set, and accumulate it in the set.” -This doesn’t make sense to me. If the whole input doesn’t fit in memory, in worst case the set would contain the whole input (the case where there is no sum) sooo the set wouldn’t fit in memory either? Even if your processing the data in chunks, you would be using the same set for every chunk which doesn’t work?
I don't know if my understanding is correct or not. I think because the interviewer mentioned that the range of the value is limited, also HashSet would not contain repeated values. So the size of the HashSet would be limited and will be able to fit in the memory.
Wow great job brilliant solution. but am worried what if the set was of the form [1, 2, 2 ,4]. This algorithm seems to dual mostly on two digits that sum to the required number and not when we have multiple digits.
I wanna one help I'm a AI& DS student you suggest me back end program language because so many people say to me you must learn java but I'm already complete python basic level know I'm confused plz help me i focus on python or i wanna switch java
I still have something unclear, if the whole input does not fit in memory, and you are processing it parallel, and adding the compliments in the list, when we reach towards the end (while merging) it will still be big enough not to work on a single computer, what am I missing? Is it that the merged array would be built and stored in a distributed manner?
You are merging only the (hash) sets of values. If the values are limited, then your set will be small enough to fit in. I believe that's what he said.
They really out here asking for masterclass resumes and for you to have found the meaning of life only to hit you with a basic 2sum problem at the actual interview.
Are they trying to send message to the candidates to feel more comfortable while having the Coding interview? And encourage them to ask questions if they are not clear what they are going to solve?
def checking_pairs(a_list, a_sum): array_len = len(a_list) temp = 0 new_array = [] while temp < array_len-1: if (a_list[temp] + a_list[temp+1]) == a_sum: new_array.append([temp, temp+1]) temp += 1 if len(new_array): print(f"Array index/es which sum:{a_sum} are: {new_array}") else: print("There are not any single value pair which form the asking sum {a_sum}.") array_list = input("Write any numbers separated by space.: ") array_list = array_list.split() map_object = map(int, array_list) array_int_list = list(map_object) # print(array_int_list) sum_of_pair = int(input("Enter the sum you want from pair.: ")) # print(sum_of_pair) checking_pairs(array_int_list, sum_of_pair) "Because the problem is not looking that big." I am still in the learning so please guide if I have done something wrong here. Like if you are looking for pairs which is equals to the sum then can't we just start adding the next index value?
In the loop we can subtract the value like :-( sum - value ) and then find the output in before Position. if it found it return true and if not then false. In this case we not need to store any data.
def checkSum(myList, s): start, end = 0, -1 for x in range(len(myList)): k = myList[start]+myList[end] if k == s:return True else: if k > s:end -= 1 elif k < s:start += 1 return False print(checkSum([1, 4, 4, 5], 8)) #did that in 2 minutes in python, before he writes the code...!
Hello 🤗, I am a student studying in class 11 with arts stream. I am thinking that can I be a part of Google if I am arts stream student. My aim is to get job in Google. Can I get it or not? Please respond 🤗🤗 ..i want to know. Which degree will be best for me to get job in Google. Actually, I am a student from India. From class 6 my aim is to be a part of Google. This present year, I had passed out class 10 board exams. Before getting results my choice was to choose Science stream but I had opted Arts because science marks was poor. In other subjects like English I scored 81% and in social science I scored 89%. My mood was totally bad that I can't get job in IT companies 😣. But I have seen that the people who are working in Google have said that anyone from any stream can get job in Google, but you must have creative skills and many more. I just asking one question please reply can I get job in Google? Hope you will reply sir.
100% you can get a job in Google!!...No degree matters to get into google. First learn basics of some of programming languages (C,C++, Python,Go,etc).Then, select any one of that suites for you. Then, learn all the concepts with side by side implementation.Then,move on to data structures and algorithms and also develope a problem solving ability in mathematics.it helps in buliding a logic in code.Then, Constantly practice!... practice!... And Never give up!..you will definitely get a job into google. i am also non CSC students. After my graduation I fixed my mind to get into product based IT company like Google. So,now i am learning programming from one year before and till continuing.Now, ihave learnt all basics in C++ programming language .Now i am going to move on to Oops concepts and DSA. Keep going!. We will achieve our goal... 🌠
I know its been a year since the posting of the video, but I have a question regarding your code which I hope you would explain it to me. First, I like the way you solved this problem. This is really clever solution. second, My Question is: why do you need ( != comp.end ) part? Since you are checking before inserting, its always going to check only the previously added complements. Thanks for posting the video anyway.
It's a particular characteristic of the unordered_set structure in C++. He's not comparing to the last element in the container; "comp.end" in this case returns an iterator to the element following the last element in the current container context. This is necessary as unordered_set::find(int value) will either return an iterator to the value if found, or if it doesn't exist, the iterator to the "past-the-end" element following the end of the current container, which coincidentally is the same "location" as unordered_set::end(). It's a standard check to ensure that the currently searched value is indeed inside the current container context.
well it is one of the most important things in coding. everything is an algorithm and understanding data structures just allow you to make codes faster and more efficient
At time =15m44s, I want to know about complexity of line ------ if(comp.find(value)! ----- As I implement same in C, When I compare/Find like function as ----comp.find(value) --- Complexity of this step becomes N i.e. for finding element in compliment array, so total complexity becomes N^2 in worst case , average it less than N^2.
@@DavidGUSC actually, performing a search in a hashset will always be O(1). A hash table only gets slower (to O(n)) if there are repeating elements in the same key. They talked about not needing to use a key; therefore, using a hashset instead of hashtable. Since repeating elements are not listed, we will not have a situation where there are multiple values associated with the same key. The drawback is that the hashset will not record how many instances of the same element is present in the data set. This is exactly why he was pondering about repeating values in the data set before settling on comparing the current value with the complement of everything the program has already seen.
another checking possibility to reduce time complexity: if the asked sum is even and the adding numbers should be (even and even) or (odd and odd) if the asked is odd the adding numbers should be (even and odd)
I didn't understand something about the solution to "throwing in the wrench." How is it better than the first solution (brute force where for each element, you check each other element). He says it's linear, but I don't see that. You loop n times through the for loop, but in each iteration, you have to find an element in comp. To find whether a value is in comp, you need to check each element of comp. So the time complexity would surely be O(sum(r from r=1 to n)) = O(n^2). Unless I'm misunderstanding something about how unordered_set and how comp.find(value) works (I don't really know how they work at all, but I don't see how the complexity of comp.find(value) wouldn't depend on the length of comp)
finding an element in comp is linear time because it is a hash set. to learn more search "why is hash look up constant time" This fast input and retrieval/searching is always O(1) in a hash set/table/dictionary. Since hashing uses a hash function, you don't have to check each element in comp. It will point you directly to it based on the hash function. You can also search up videos on what a hash function is to learn more. Vote Bernie 2020.
I haven't watched video yet, just problem. First idea I am having to solve it is, looping through all the numbers in array, then using binary search to find the needed matching pair to make 8, if any. This will be O(nlogn). Let's how I did. Will continue watching video now.
It's not about how many languages you know it's about how you think of any problem. So language would not be the problem to get a job in google. try to solve the coding problems.
First of all, HTML is not a programing language and second thing in google server there are a lot of data how to write code so they don't care about the information you have they only care about how you going to solve a real-world problem....but it is a good thing, at the age of 14 you learn a lot focus on logic building and algorithms.
I'm asking this VERY seriously: Is this a joke??? I'm learning programming for no more than one year now, and I solved it as he's final result maybe 5 minutes into this video. So regarding my question, is this really the level required for Google? Is that in general considered a high-level programming?
@@michellefanter4671 Did not.. Everyone wants work experience.. I'm sending resumes multiple times a week.. Everywhere I hear companies that says "no previews experience needed" but when I send the resume they answer otherwise.
@@gigos2 You should gain experience through personal projects. Look for intern positions. If questions like these are easy for you, then you should pass the technical reviews :)
@@michellefanter4671 I understand what you're saying, but the reason I'm automatically get passed is just because I have now work experience. That's all that matters to everyone. I have no doubts I can pass any job interview.
I don't think He would take such a long amount of time its just a matter of 2 min for someone who is a intermediate even LOL he is pretending to be slow LOL
Really helpful video. This reminds me of the classic Two Sum problem on LeetCode. Since we are told a pair of numbers equals a target sum, we can say that x + y = target. And solving for y (complement of x), we see that y = target - x. Therefore, we can just walk through the input sequence and for every element, insert it into a hash set while performing a lookup in the hash set to see if for a given `x` value (arr[i]) we can find a `y` that satisfies x + y = target.
When she said she was gonna throw a wrench into the mix I felt the pain lol.
2016: 2 sum
2022: solve the travelling salesman problem in polynomial time 😭
Yeah, interviews are much much harder than this now. Honestly, if you were asked 2 sum today (which you probably will not be), and it took you just as long to solve as in this video, with all the same dialog and clarifying questions etc, you will probably be rejected along with pissing the interviewer off. All LC easies should be trivial for anyone looking to break anywhere into Big Tech.
Such a nice video. Very well conducted by both.
Great job googlers! Keep em coming please :)
def array_sum(array):
sum = 0
for element in array:
sum += element
return sum
array1 = [0,1,5,2]
total_sum = array_sum(my_array)
print("The sum of the array is:", total_sum)
bro that's correct also, but that ain't the problem 👍
I find this valuable, thanks a lot!
in problem 1 : we can simply use map storing values and index .
Who writes the music for these videos. Hahahaha jk. It's very relaxing.
Since comp.find is logarithmic and you are repeating this for every value in data, then the actual time complexity of the function is O(N*logN). Why did they say it was linear?
Not trying to be mean or anything, but I think you may need to review how data is stored in an unordered set. From my understanding, The add function will take the integer and using something similar to a hashing function, get a unique key which is probably used to get the index in the container of the stored value. When you use the find function, it probably uses the same hashing function to get the index of the stored value. If the value isn't found, at that index, the find function goes through the rest of the container to find the value. Here are two facts for you - Average case of find is constant time complexity O(1), and worst case is linear in container size O(n) which can be found at the bottom of the page here: www.cplusplus.com/reference/unordered_set/unordered_set/find/
The worst case of using this function is O(n) so if for all n values in data we have an O(n) time complexity for the find function, the solution will have an O(n^2) time complexity. However, that is highly unlikely seeing as even a basic hashing algorithm with a relatively small prime number can prove to yield O(1) time complexity more often than not. I hope this helps you to learn why they said it was linear! I have a phone interview coming up and I'm hoping to learn and help as many people as I can along the way.
I have a long way to go... But this is a motivation
The Question answer is simple but think was google don't need answer its need efficient code that should be run that things make harder to do 😊😊
Well The Question goes like this I suppose:
lets say
(python 3)
lst = [1,2,3,4,5,6]
for i1 in lst:
i2 = 8 - i1
if i2 in lst:
print(i1, i2)
we get the pairs
this is too slow of an algorithm.
Smart
a small problem with empty data: data.size() is unsigned int, after minus one, it will become extremely big, you have to convert it to int first.
I want to apply for Job
Thanks for the upload
Very intense, super interesting. Also, fun problem!
Hallo Google I am india for student the following URL and to join to google jobs for student......
Edge case: negative integers
great video. thanks
And binary had confirmed with asking decimals !
Such a nice video :)
I loved it !
OMG! i can only do sorting!!! even odd!
Lovely!
18:11 exciting blackboard eraser fall
How much math do we actually have to know for this software programming becz like fuc i hate math and i love computer
Depends. For data science, game development, A LOT of high level maths knowledge is essential.
For web/app development, depends on what you're working on. In general, not very much. Although, the mindset is pretty much the same.
I could be calculating some integral, or I could be designing a complex architecture for data flow in my webapp, in both cases I feel like I'm solving very similar problems. In both cases, you'll be running through a lot of alternatives in your mind, and quickly choosing the best ones to work with. Problem-solving is what computer science is all about.
For this problem specifically, since there will only be an addition of two number, all you need to do is to subtract one elements of the arrays from 8. If the result matches one of the remaining elements then the number you subtract from and the result will be the pair of two number that sums up to 8. You will only have to do this four times or the number of elements you have in an array.
can someone please tell me what does comp.end do.
I haven't been programming for long (and I only know Java), but from the api, I think that comp.end returns true once it goes past the last value in the HashSet. So the IF statement basically says: If this value in the vector equals one of the compliments in the HashSet (which means that it found a sum pair) AND we have NOT reached the end of the HashSet, the return true.
In other words, once one of the vector values matches a value in the compliment HashSet, comp.find(value) will be true and comp.end will be false. And since false != true, we will enter the IF statement.
@@58book comp.find(value) returns the index of the value in comp if the value is present, else it returns comp.end(), which is the pointer to the last element of comp(the pointer where the next value will be inserted). If value is present in comp, then comp.find(value) != comp.end(), hence the above if statement.
@@sarthakdubey4362 thank you!!
Lovely...
This is the math of common sense 😂
Nice mam or sir ✓
it's painful to watch. just use a map.
0:19
Oh okay 😊👍👍😂👌.
what language is this
lol
C++I think
I thought of a better solution than him that would work in half the time of what he is proposing.
So does this mean I can get an internship??
can you tell me what solution do you have?
@@nikhilpathania No, no he can't.
it's just a demo ques actuals ques are a bit hard than this
That noob man...
He crossed the first array 2:00 .... and then asked her if he could repeat the elements... and they are making 'example interview'
Hi @GoogleStudents
`+data[hi]`… AND… You've just invoke undefined behavior.
EDIT: Wait nevermind. My bad. Implicit conv… Well technically it's still UB. Just way earlier. Signed overflow is still ub (granted if you that large a vector you might want to rethink something. (also infinite loop but that's cheating). Still why use an int where you get a `std::vector::size_type` smh. And that while loop confuses me. (Besides being potentially wrong) I'm way too sleep deprived for that amount of questions. iterators wouldn't kill either. (So many whys)
Fix is obviously don't pass keep a `std::numeric_limits::max() + 2ULL` sized vector to the function…
Or don't have so many implicit conversations.
The answer in itself is fine though. (I'm just over sensitive to potential UB)
I realize I've got a long way to go. This gives me motivation, though.
GOOD LUCK ♥
Me TOO
well this comment is 5 years ago and I guess now you went more than half of your journey,right?
Have you achieved ur target
I need a lot of time to prepare 😅😅😅😅
I love the acting from the guy pretending to be looking for the answer. Thankfully for him he is an engineer and not an actor XD
I have a lot do now. I need to Study hard. Thanks googler, its very motivating
Thank you, lady, for inserting that 'coma' at 14:20. My world collapsed a moment before.
Awesome. Thanks for this, is really helpful. You could use a Bloom Filter instead of the hash set to save on space complexity(O(1)) as per you only need to know if the complement is NOT in the list.
Thank you guys for these amazing resources. It does make me feel less competent and ready but we can only learn hey.
I did this problem on leetcode when i was like 12yo
Thanks. But they asked me to design a spaceship instead.
For the last part of the problem, wouldn't it have made sense to do some pruning along the way for repeat complements? It would have bumped up the running time, but for a case where space seems to be the main issue, that would be a necessary sacrifice for the problem if you were to not use multiple systems, wouldn't it?
Can someone explain the scaling part to me.
19:47 “If my set fits in memory, but my whole input doesn’t fit in memory then I can just process it in chunks. I chunk it, I just put it in a set, and accumulate it in the set.” -This doesn’t make sense to me. If the whole input doesn’t fit in memory, in worst case the set would contain the whole input (the case where there is no sum) sooo the set wouldn’t fit in memory either? Even if your processing the data in chunks, you would be using the same set for every chunk which doesn’t work?
I don't know if my understanding is correct or not. I think because the interviewer mentioned that the range of the value is limited, also HashSet would not contain repeated values. So the size of the HashSet would be limited and will be able to fit in the memory.
@@huili2065 thank you so much. I think you're right.
11:26 "But it's too slow for Google"
😩 just when I thought 1 + 1=2
A new for of mathematics comes
Wow great job brilliant solution. but am worried what if the set was of the form [1, 2, 2 ,4]. This algorithm seems to dual mostly on two digits that sum to the required number and not when we have multiple digits.
Harisu fanyui well that’s what the question was. No need to solve anything else than the question given to you..
well set doesn't contain repetitive values
Nice to know I would have failed in the first 30 seconds...
This question was way too easy. Literally every single google interview question i've seen so far on youtube has been so easy. Is it really this easy
I love the way in which he thinks :)
I wanna one help
I'm a AI& DS student you suggest me back end program language because so many people say to me you must learn java but I'm already complete python basic level know I'm confused plz help me i focus on python or i wanna switch java
I still have something unclear, if the whole input does not fit in memory, and you are processing it parallel, and adding the compliments in the list, when we reach towards the end (while merging) it will still be big enough not to work on a single computer, what am I missing? Is it that the merged array would be built and stored in a distributed manner?
i guess yes that's why he said it is possible when we are working in 2 or more computer and set is distributed among those computer
You are merging only the (hash) sets of values. If the values are limited, then your set will be small enough to fit in. I believe that's what he said.
They really out here asking for masterclass resumes and for you to have found the meaning of life only to hit you with a basic 2sum problem at the actual interview.
Are they trying to send message to the candidates to feel more comfortable while having the Coding interview? And encourage them to ask questions if they are not clear what they are going to solve?
def checking_pairs(a_list, a_sum):
array_len = len(a_list)
temp = 0
new_array = []
while temp < array_len-1:
if (a_list[temp] + a_list[temp+1]) == a_sum:
new_array.append([temp, temp+1])
temp += 1
if len(new_array):
print(f"Array index/es which sum:{a_sum} are: {new_array}")
else:
print("There are not any single value pair which form the asking sum {a_sum}.")
array_list = input("Write any numbers separated by space.: ")
array_list = array_list.split()
map_object = map(int, array_list)
array_int_list = list(map_object)
# print(array_int_list)
sum_of_pair = int(input("Enter the sum you want from pair.: "))
# print(sum_of_pair)
checking_pairs(array_int_list, sum_of_pair)
"Because the problem is not looking that big." I am still in the learning so please guide if I have done something wrong here.
Like if you are looking for pairs which is equals to the sum then can't we just start adding the next index value?
What if we use if -else loop to get output
In the loop we can subtract the value like :-( sum - value ) and then find the output in before Position. if it found it return true and if not then false. In this case we not need to store any data.
Great Work
This video was very helpful, thank you. Please do more videos like this.
Great video. Thanks for the tips, they're certainly helpful.
[0,1,5,2] sum=08 hence prove according to criteria
First pair you change to no 9 to 7 and give command to no and yes then click 9 error will appear
can anyone explain to me the condition in if statement ... thanks
I have a lot do .now .I need hard thanks Googler ,its very motivating
Hii
Strange question: What is the size of whiteboard in feet? 3x2?
waw at it's very good. I need additional information
l dont really understand the problem
,,1-9
interesting, i was thinking since it is sorted to start checking at the end, skipping numbers which are too large and when you get to number that is
Did commerce students get job in Google
it seems like a competitive programming problem
1x2+3+3=8 excluding √
1x2+4+2=8
def checkSum(myList, s):
start, end = 0, -1
for x in range(len(myList)):
k = myList[start]+myList[end]
if k == s:return True
else:
if k > s:end -= 1
elif k < s:start += 1
return False
print(checkSum([1, 4, 4, 5], 8))
#did that in 2 minutes in python, before he writes the code...!
LOL
Are you out of your mind
Do this
lst = [1,2,3,4,5,6]
for i1 in lst:
i2 = 8 - i1
if i2 in lst:
print(i1, i2)
we get the pairs
Only works for a sorted list as he explains
Thank You very much
Can i use Hindi language for communicate with Google recruiter
no
Hello 🤗, I am a student studying in class 11 with arts stream. I am thinking that can I be a part of Google if I am arts stream student. My aim is to get job in Google. Can I get it or not? Please respond 🤗🤗 ..i want to know. Which degree will be best for me to get job in Google. Actually, I am a student from India. From class 6 my aim is to be a part of Google. This present year, I had passed out class 10 board exams. Before getting results my choice was to choose Science stream but I had opted Arts because science marks was poor. In other subjects like English I scored 81% and in social science I scored 89%. My mood was totally bad that I can't get job in IT companies 😣. But I have seen that the people who are working in Google have said that anyone from any stream can get job in Google, but you must have creative skills and many more. I just asking one question please reply can I get job in Google?
Hope you will reply sir.
100% you can get a job in Google!!...No degree matters to get into google. First learn basics of some of programming languages (C,C++, Python,Go,etc).Then, select any one of that suites for you. Then, learn all the concepts with side by side implementation.Then,move on to data structures and algorithms and also develope a problem solving ability in mathematics.it helps in buliding a logic in code.Then, Constantly practice!... practice!... And Never give up!..you will definitely get a job into google. i am also non CSC students. After my graduation I fixed my mind to get into product based IT company like Google. So,now i am learning programming from one year before and till continuing.Now, ihave learnt all basics in C++ programming language .Now i am going to move on to Oops concepts and DSA. Keep going!. We will achieve our goal... 🌠
解题一秒钟，表演一小时
I know its been a year since the posting of the video, but I have a question regarding your code which I hope you would explain it to me. First, I like the way you solved this problem. This is really clever solution. second, My Question is: why do you need ( != comp.end ) part? Since you are checking before inserting, its always going to check only the previously added complements. Thanks for posting the video anyway.
It's a particular characteristic of the unordered_set structure in C++. He's not comparing to the last element in the container; "comp.end" in this case returns an iterator to the element following the last element in the current container context. This is necessary as unordered_set::find(int value) will either return an iterator to the value if found, or if it doesn't exist, the iterator to the "past-the-end" element following the end of the current container, which coincidentally is the same "location" as unordered_set::end(). It's a standard check to ensure that the currently searched value is indeed inside the current container context.
What I realized from interview questions is that mostly they based on data structure and algorithm. Personal thought though.
well it is one of the most important things in coding. everything is an algorithm and understanding data structures just allow you to make codes faster and more efficient
It's useful for me❤️
At time =15m44s,
I want to know about complexity of
line ------ if(comp.find(value)! -----
As I implement same in C,
When I compare/Find like function as ----comp.find(value) ---
Complexity of this step becomes N i.e. for finding element in compliment array,
so total complexity becomes N^2 in worst case , average it less than N^2.
it's not an array -- it's a hashset. bigocheatsheet.com/
But yes, worst case of a hashset could in theory lead to worse than O(1) time for find
@@DavidGUSC actually, performing a search in a hashset will always be O(1). A hash table only gets slower (to O(n)) if there are repeating elements in the same key. They talked about not needing to use a key; therefore, using a hashset instead of hashtable. Since repeating elements are not listed, we will not have a situation where there are multiple values associated with the same key. The drawback is that the hashset will not record how many instances of the same element is present in the data set. This is exactly why he was pondering about repeating values in the data set before settling on comparing the current value with the complement of everything the program has already seen.
👍
i think its easy like this
int sum= (1*2)+9-3; //i think its 8 at first 1
lol that's not a general solution
Lol what is this?..
Actually, the find() method for sets has a logarithmic lookup time, which would make the complexity O(n log n) instead of liniar.
Depends on the implementation of the set, no? Hashsets should take constant time on average for find().
std::set is binary tree - O(log n)
std::unordered_set is hash table - O(1)
another checking possibility to reduce time complexity:
if the asked sum is even and
the adding numbers should be (even and even) or (odd and odd)
if the asked is odd
the adding numbers should be (even and odd)
just a minor typo, it is comp.end() ... doesn't change the general idea but still :p
Absolutely correct! A good example of how having a typo or other very minor mistakes in your code don't actually matter in an interview.
You did a superb job, that was a real pleasure to watch. Congrats
I m coming google get ready for world best programmer👌😊
second best 😎😎
@@creeplabs 4
There can't be two same elements on the same index. Wut? What array has TWO things at ONE index?
great stuff.. thanks 🙇♂️
These questions are so easy for me..
I didn't understand something about the solution to "throwing in the wrench." How is it better than the first solution (brute force where for each element, you check each other element). He says it's linear, but I don't see that. You loop n times through the for loop, but in each iteration, you have to find an element in comp. To find whether a value is in comp, you need to check each element of comp. So the time complexity would surely be O(sum(r from r=1 to n)) = O(n^2). Unless I'm misunderstanding something about how unordered_set and how comp.find(value) works (I don't really know how they work at all, but I don't see how the complexity of comp.find(value) wouldn't depend on the length of comp)
finding an element in comp is linear time because it is a hash set. to learn more search "why is hash look up constant time" This fast input and retrieval/searching is always O(1) in a hash set/table/dictionary. Since hashing uses a hash function, you don't have to check each element in comp. It will point you directly to it based on the hash function. You can also search up videos on what a hash function is to learn more. Vote Bernie 2020.
I haven't watched video yet, just problem. First idea I am having to solve it is, looping through all the numbers in array, then using binary search to find the needed matching pair to make 8, if any. This will be O(nlogn). Let's how I did. Will continue watching video now.
Heeey! He is doing my idea lol
i want job in google but iknow only 3 programing languages
1] java
2] php
3] html
i am 14 year young from india
It's not about how many languages you know it's about how you think of any problem. So language would not be the problem to get a job in google.
try to solve the coding problems.
HTML?!
LOL
First of all, HTML is not a programing language and second thing in google server there are a lot of data how to write code so they don't care about the information you have they only care about how you going to solve a real-world problem....but it is a good thing, at the age of 14 you learn a lot focus on logic building and algorithms.
How can you know java and not know c and c++?
I'm asking this VERY seriously: Is this a joke???
I'm learning programming for no more than one year now, and I solved it as he's final result maybe 5 minutes into this video.
So regarding my question, is this really the level required for Google?
Is that in general considered a high-level programming?
@Dexter Gomez Either the worst AI wrote this message or you're simply speaking gibberish.
Couldn't understand a single thing from your message.
This is an easy question imo
did you get a job yet?
@@michellefanter4671 Did not.. Everyone wants work experience..
I'm sending resumes multiple times a week..
Everywhere I hear companies that says "no previews experience needed" but when I send the resume they answer otherwise.
@@gigos2 You should gain experience through personal projects. Look for intern positions. If questions like these are easy for you, then you should pass the technical reviews :)
@@michellefanter4671 I understand what you're saying, but the reason I'm automatically get passed is just because I have now work experience. That's all that matters to everyone. I have no doubts I can pass any job interview.
I don't think He would take such a long amount of time
its just a matter of 2 min for someone who is a intermediate even
LOL
he is pretending to be slow
LOL