Channel: Gaurav Sen

Category: Education

Tags: interview preparationdata structuregooglesegment treeinterviewssoftware interviewgoogle interviewgaurav sencoding interviewgoogle hard problemprogramminghard problemalgorithmcompetitive programming

Description: Is competitive programming necessary for a Google interview? This problem has a prerequisite of segment trees, which is a popular data structure for range query problems. The data structure was until recently considered a hard concept to master. In this Google coding interview, we solve the problem of reconstructing an permutation array from a derivative. We find a brute force solution and an in-place space optimized solution before the final solution with segment trees. 00:00 Intro 00:20 Problem definition 02:08 Brute force 02:52 In-place solution 05:15 Time complexity analysis 05:44 Part 2 - Use auxiliary space 07:07 Final Solution 10:37 Time complexity 11:11 Conclusion If you'd like me to look into an interesting problem, let me know at contact@interviewready.io Are you preparing for system design interviews? get.interviewready.io It's the best place to learn system design in-depth. You can use the coupon code of 'earlybird' to get a 20% discount 🔥 AlgoWorkout playlist: youtube.com/playlist?list=PLMCXHnjXnTnvWapjXuYL4Bp7oEQKBQPce You can follow me on: Instagram: instagram.com/applepie404 LinkedIn: linkedin.com/in/gaurav-sen-56b6a941 Quora: quora.com/profile/Gaurav-Sen-6 Twitter: twitter.com/gkcs_ Github: github.com/coding-parrot #Google #Interview #CompetitiveProgramming