Goldman Sachs Interview - The Tree Question | Part II
ฝัง
- เผยแพร่เมื่อ 8 มิ.ย. 2019
- ✅New TH-cam Account - Developer Bhaiya 👉🏻bit.ly/developer-bhaiya-youtube Rachit, an ex-Software Engineer@Microsoft talks about his Software Interview Experience with Goldman Sachs.
algoexpert.io/rachit
Use "rachit" as coupon code to get 30% off.
Tree Traversal Trick: • If you fear Tree Trave...
Github Code: github.com/rachitiitr/DataStr...
Github Code 2: github.com/rachitiitr/DataStr...
Goldman Sachs - Part I: • Goldman Sachs Intervie...
AlgoExpert has video solutions to 70 coding problems, covering all the important topics generally asked in Coding Interviews.
I recommend AlgoExpert for Interview Prep + DailyCodingProblem.
dailycodingproblem.com/rachit to get interview questions being asked in firms like Microsoft, Google and Amazon. It's FREE and super cheap if you want the solutions as well (totally worth it).
Cracking Coding Interview in 3 Months: • How Beginners Can Crac...
🔥 SUBSCRIBE AND HIT BELL ICON TO CHECK MORE OF MY CONTETNT 🔥
th-cam.com/users/RachitJain?sub_con...
/ rachitjain2095
/ rachitiitr
AlgorithmsWithRachitJain
/ rachitiitr
================
Important Playlists:
================
Check my channel for guided content.
You can also check all playlists at / @rachitjain
MyProgrammingBlog
===============
Programming Blog ► rachitiitr.blogspot.com
Github ► github.com/rachitiitr/DataStr...
MyProgrammingProfiles:
===================
CodeForces ► www.codeforces.com/profile/rac...
CodeChef ► www.codechef.com/users/rachitiitr
![Fc ครับ ขอแนะนำให้รู้จักกับ "น้องเปียโน" l [Nickynachat]](http://i.ytimg.com/vi/HQU6Q_IYTLo/mqdefault.jpg)
All necessary links in video description. Hope this was fun to watch.
thank you so much dude
Sir Would Java be of less use in future because of growing use of Python in web dev, data science, ML, AI and
Growing Use of KOTLIN, DART flutter in Android dev side? If it is not so plz do explain in detail the advantages of Java and it's uses in comparison to python
Hey you have mentioned this question in your own video, data structure and algo, 29 Sep 2018 at 10:30.
You are following ur own video😂😂😂
Sir, gsoc vs research internship (for better resume for placements)????
What about another solution where you store the values of the tree in a hashmap and reduce the problem to finding two numbers with target sum. Time complexity becomes O(n) -> 'n' corresponds to number of elements of one tree alone.
your presentation skills have increased massively. kudos
Please make a video on your interview experience at Tower Research. If I am not wrong, Tower Research asks a lot of system design and operating systems questions. It will be good to what exactly they asked you in the interviews.
Love this video sir plz keep posting such question🤗
Thankyou that's very informative keep going!!
Awesome Work Rachit, Thanks!
Really good work !!!
Highly Appreciate ur work !!!!
goosebumps !!!! when u just shifted the whole problem from bst to arrays 1 Awesome brother :) great motivation
you deserve a like for this ingenious solution. Really Cool
I hope i become a matured programmer like you someday 🤠, awesome video , thankx for sharing ur experience
This is a beautiful solution rachit! Keep up the good work
Rachit, you genius, I've been trying to figure out a generalized solution for iterative traversals for days now, and you just do it in minutes, that too in an interview -- god _/\_
Thanks!
love this video sir,,could u make a video on how to become purple in cf.(strategy,practice,approach). that will be very helpful.thanks
brilliant idea, rachit. I think you took inspiration from graph colouring in dfs. Amazing thought process.
That iterative inorder traversal 🤩🤩🤩damn you really slayed
ahh a version of two sum problem with binary search trees!!!👌
Bhaiya, please make a video on, how interviewers sometimes try to trap the candidates and how constantly they keep giving hints to test our understanding and the boxes which we have to tick for the selection!
you could also use unordered map for storing the inorder traversal values.
The Video Quality is Increased
Thank You Sir
Please Can You make A Solution Video for this DP problem
(Hoping for Help Editorial is not given at codeforces)
Sir Could you please make a video explaining the resources you use to learn or enhance your skills about languages
The space complexity is still O(n). The actual struggle is to make it O(logn) in case of balanced tree. It can be done using dfs+stack.
There is an iterative version of Inorder Traversal without even using stack - "Morris Inorder Traversal"
for problem 2nd , I think we can do this by hashmap with maximum time complexity of 2n(n=total element of smaller array)..
please reply
Can we do it this way?
We can store all the nodes from the first tree in an unordered map. Then we simply go over the nodes of the second tree and see if sum-node exists in unordered map. This way it would take O(n+m) time complexity
@Shivansh Sharma Yup, but for set insert or retrieval would take log(n). For unordered map it's O(1). Maybe we can use unordered set if it's there in stl
thanks and congratulations 🥳
Great work bhaiya!
Thanks
I think the reason they asked you to solve it iteratively, is because maybe they wanted you to implement something like an iterator for binary search tree. And then you would not need extra space. One forward iterator on left most node of first BST and one backward iterator on the right most node of the second BST. Then you could have used this two pointer technique for getting answer in O(1) space.
I didn't know GS asks such easy questions
Sir what was the package that you're offered?
The number of views on this video can give a basic idea of the amount of competition out there! Whopping 35k!!
rachit bhai , leetcode ke medium / hard problems par video banana agar time mile to. bahut learning milati hai usse.
Sir Would Java be of less use in future because of growing use of Python in web dev, data science, ML, AI and
Growing Use of KOTLIN, DART flutter in Android dev side? If it is not so plz do explain in detail the advantages of Java and it's uses in comparison to python
Wouldn't storing all keys of 1 tree in a hashmap and then checking for target-x exists in the map(where x are the nodes in the other tree) be a better approach? The time comp would be the same as your method i.e O(m+n) but the space comp would be better(O(n) as opposed to O(m+n) in the inorder method)
you could just use a hash of the smaller bst and check if 30-x exist in there, that will take less space and u get it done quicker.
Please provide dp questions also..
I too used the same approach
Damn man!! 😎
Hashmap could be used instead of two pointer method ?
I was wondering , could not you use hashing with target-element , from the first tree and use to look up while traversing the second one ?
Hashing doesn't always guarantee O(1) searching...worst case can be O(n) which makes overall worst case complexity O(n²)...two pointer technique guarantees overall O(n) complexity.
Where GS makes use of BST ?
I was thinking
Arrays.sort both arrays and then try sum..
get inorder if both and we ll get two sorted arrays and we can take two ptrs initially pointing to beginning of both arrays and accordingly to get the sum
Did the interviewer gave you any hints during the course of time you were solving the problem?? Please do reply sir
Hi brother, can you please tell from where did you learnt advance c++ programming including STL ?
Can we use binary search as the array is sorted
You could had done this also. Since height is the issue and we know it's a BST. We do inorder traversal and using this make AVL out of it. Doing Inorder is order of n and making AVL also in this case is order of n so total time complexity would had been o(n+m) + lg term. What do you think?
Any tips to get our resume shortlisted for interviews for companies like Goldman Sachs or D.E. Shaw? I've not studied from any of the IITs or NITs but completed my Engineering from a normal EAMCET college. Does educational background matters to get our resume shortlisted?
awsome
Can we also do like in the first tree find the max value and min value
_max = 30 - min from 1st tree
_min = 30 - max from 1st tree
In secondtree check root node with _min and _max.
3 cases - both on left or right subtree
One on left and other on right
Then it's cake, I hope so....
Recursion is just a game of function stack.
So to convert from recursion to iteration, just understand how the working of a function stack, and implement a normal stack the same way using itertation.
it's not everytime that easy to convert the recursion to iteration using stack. try to do tower of hanoi problem iteratively you'll understand
@@charan775
Yeah i absolutely know. Its very difficult to convert it but the basic behind the conversion lies on the function call stack. I just meant this.
@@raghavkakar8092 yeah that's right.
Sir what should be roadmap for me as i am in my summer vacations after 2nd year and i am not quite good in comp. programming and what should be my approach towards it.
Do CP as much as possible follow gaurav's and rachit sir video,As well as try hand on some project's you won't get the free time again.Try to make notes specially for the approaches and data structure you use for solving problems, that really help me in my prep!!!
one thing is Goldman asks heavily maths problems(gfg has a collection) and Probability is a must to be well versed with .
I guess we could also simply the traverse the trees and store the values in two different hash sets. It would be easy from there on. Is that a good solution??
complexity would be more though.
O(N+M) for traversing the trees
And then O(max(NlogM,MlogN)) for searching through hash sets.
do you charge for personal interview/coaching ??
It is simple wih hashing
Hi Rachit. I am also an Electrical Engineer but from a state govt college and have no experience in programming other than the basics of python. Can I venture into the software engineer carrer? Is it worth it now p s. I already have a experience in FMCG sector
What's wrong in 2 pointer technique...it's doing in O(M+N).??..any other technique in less than this time complexity?
Is this problem there in leetcode premium?
I find recursive solution to be very much simple rather than iterative approach !
You make problems look easy.
Appreciate your efforts that you put for us. Keep it up bro
Thanks
How do i get job at big product based companies , i'm not from any IIT, NIT, etc . I am from tier 5 college. How?
Hey Rachit, its great you have cracked Goldman Sachs interview. Are you still want to apply to Goldman ?
Can we use hashmap to find 30-x from the second bst?
Yes I think we could use the hashmap or hashset. First, we had to create a hashset from one bst and then search for the value from other bst.
Space complexity would be o(n)
And time complexity would be o(m) or o(log m) or o(log n)
Hey Rachit I want to add paid english captions for your videos.can we talk on FB? Or email??
Instead of converting to array first, couldn't you just put two pointers at root of each tree and move first pointer left and the second pointer right and in next time move first pointer right and second pointer left looking for the target sum
why not use a hashmap and traverse the first tree to store the 30-x in the hashmap/hashset and then start traversing the next tree
Do engineering colleges teach all this to CS students ? I mean , I had never heard of 2 pointer technique before !
I doubt they teach it, but what do I know I am from Electrical
@@RachitJain Hello sir , since you r from electrical , does iit give practical knowledge for electrical engineering students or just it is like studying theoretically ? What practical knowledge we will get for electrical engineering in IIT ?
can I apply to such companies and get selected , when I have no experience in IT industry , and already graduated from some xyz college in 2016.
Ofcourse. you just need to crack these rounds
Plz reply this query
CAN WE SOLVE THIS ALGORITHM USING PYTHON?
Any algorithm can be implemented in any programming language.
Try doing it in brainfuck
This question is on geeksforgeeks
Tell me about any analytical que...that ask Goldman sach
Please provided also in hindi.
Is it really worth to purchase Algo expert thing? It's saying only 70 algorithms
It's only $49 dollars after discount. Thanks for the coupon code Rachit
now they are 75. they are basically base problems... base to any other problem
I can solve first 2 to 3 problems in Codechef, sometimes only first 2. 😥
Atleast you could solve 2 problems. You know what i mean...
Ye pura question k saare method mujhe malum thee pr phir bhi I have no confidence in coding😅
FYI
Rachit is from Electrical and not CS background
*Legend*. Which one do you prefer, Codewars or CodeChef?
Why did he take Electrical engineering when he wants to be in CS.
I have an interview with Goldman Sachs tomorrow and I don’t know how to do any of this 😃😁
Rachit I used your promo code but when I go to the payment portal card gets declined I tried 2-3 cards more but problem pertained...then I contacted algoexpert via mail but they didn't responded .so If you could help ,then please convey them to add method like UPI,paytm would be helpful for indian customers to pay with ease!!
I will look into this.
Btw video was awesome the way you used iteration on tree ...quite helpful loved this video 👌
Gaurav sen also publicizing this website 😂😂
Rachit, I still didn't get you in two pointer technique. I knew that technique, but I think that will works only in one array. Let me give you some example case in which that your idea of two pointer approach fails. Let consider an array of [3,7] and [7,2] and the sum is 10. Your technique will fail, but there exists a pair
The second array should be sorted as well. Its not compulsory that you got to use this technique on one array. In this case, I can safely apply two pointer technique.
@@RachitJain I got you bro🤝💯🔥
This question is super easy rofl, just use a hashtable to store one of the trees, and you will get O(N) runtime and O(N) space.
How s=18 come. Please reply 😭😭
S is input... whatever the s is we need to find two nodes that add up to S
30-x from the unordered_set O(1) time
So does it mean just O(N)? Vow
do you mean unordered_map?
Hey was it on campus or off campus?
Off
@@RachitJain and how do you find referrals ......like through friends or through random searching at LinkedIn for refferrrals / recruiters?
@@tarushiarora8628 already have a video on my channel to talk about this
What was the offer ?
Really want to know that
Goldman pays 22 lakes to freshers from our college. So with experience like Rachit it must be quite high.
If they are paying in lakes, I am happy with just one.
Sir can u make a video regarding questions asked on operating systems
@@RachitJain Lol.
2:15 yeah this was my first intuition.
learn new technique two pointer. usualy i use hashmap to find sum of pair heheh
When I tried to Buy the course in AlgoExpert it says only 15% discount. But you said in the video 30%. Can you please check once?
No coupon exists for 30% anymore from 1st November. Last few of my videos do mentioned about it.
4:04 oh !.
what was that beautiful number you got.
Don't go with Rachit's suggestion and buy AlgoExpert. It is total crap. I am sure he has been paid to advertise for it. I bought it and the problems are too simple and nowhere close to real interview problems.
ANOTHER APPROACH:- Traverse the first tree and insert
(target_sum - element) into a unordered_set and then traverse the 2nd tree and check if the element is in the set if it is then print it and (target_sum - element) and break.
Time complexity - O(m+n)
Extra space - O(min(m,n))