Python Coding Interview Practice – Difficulty: Hard

    11
    23



    In this video I go through a hard coding interview question and discuss the problem, solution and do a full code walkthrough. This is designed to help you prepare for your coding interviews.

    Try AlgoExpert to ace your coding interviews: https://algoexpert.io/techwithtim
    Get 15% off using the code “techwithtim”

    Playlist: https://www.youtube.com/watch?v=nfOCvysoTjA&list=PLzMcBGfZo4-l73euhrUu0exrXc_1HQPV0

    ◾◾◾◾◾
    💻 Enroll in The Fundamentals of Programming w/ Python
    https://tech-with-tim.teachable.com/p…

    📸 Instagram: https://www.instagram.com/tech_with_tim
    🌎 Website https://techwithtim.net
    📱 Twitter: https://twitter.com/TechWithTimm
    ⭐ Discord: https://discord.gg/pr2k55t
    📝 LinkedIn: https://www.linkedin.com/in/tim-rusci…
    📂 GitHub: https://github.com/techwithtim
    🔊 Podcast: https://anchor.fm/tech-with-tim

    💵 One-Time Donations: https://www.paypal.com/donate/?token=…
    💰 Patreon: https://www.patreon.com/techwithtim
    ◾◾◾◾◾◾

    ⚡ Please leave a LIKE and SUBSCRIBE for more content! ⚡

    Tags:
    – Tech With Tim
    Python Tutorials
    – Coding Interview Question and Answer
    Python Coding Interview
    Python Programming Problem
    – Coding Interview

    #Python #CodingInterview #ProgrammingProblem

    source

    Previous articleTop 50 Docker Interview Questions & Answers | Frequently Asked Docker Interview Questions | Edureka
    Next articleKubernetes Full Course in 7 Hours | Kubernetes Tutorial | Kubernetes Training | Edureka

    23 COMMENTS

    1. I did solve it without sorting the array. Starting with a loop that walks through the array, if it finds both n and n+1 present then thats the beginning of a sequence and a number collection function is called. The number collection function has its own loop that keeps adding one to n, checking if its present in the array, then storing that number in an output array until there are none left in sequence.
      I guess its not O(n) because I have a loop within a loop, so its O(n squared).
      But I got it done my own way and it works great, and that feels good. ..

    2. Small optimization: we could use Hashset instead of Hashmap and delete seen values from there. We also could declare set capacity to avoid Hashset resizes during population and optimize performance:

      public int[] longestRange(int[] arr) {

      // Declare a hashset capacity of 125% mof arr.length to avoid hashset resizes and optimize performance
      Set<Integer> set = new HashSet<>((int) (arr.length / 0.75) + 1);

      // Populate hashset
      for(int element : arr) {
      set.add(element);
      }

      int left = 0;
      int right = 0;

      for(int element : arr) {

      if(!set.contains(element)) {
      continue;
      }

      int leftElement = element;
      int rightElement = element;

      while (set.contains(leftElement – 1)) {
      set.remove(leftElement);
      leftElement–;
      }
      while (set.contains(rightElement + 1)) {
      set.remove(rightElement);
      rightElement++;
      }
      set.remove(element);

      if(rightElement – leftElement > right – left) {
      left = leftElement;
      right = rightElement;
      }

      }
      return new int[]{
      left,
      right
      };
      }

    3. The trivial solution is O(n) in space (the input array) and O(n*log n) in time by sorting (O(n*log n)) the list and then simply scanning it once while remembering the longest sequence seen so far. The fancy alternative would use a hash table of all sequences seen so far, indexed by the beginning of each sequence. The top of each sequence is also indexed, with the negative length of the sequence. This is also O(n) space but should approach O(n) in time since it can be done with a single streaming pass over the input. It is similar to how I merge contour line segments generated from a triangulated lidar point cloud.

    4. Here's another linear approach in JS. It works in one pass (no pre-initialization of a hash table), but it keeps more information in the table. It's a simplified union-find

      function largestRange(arr) {
      if (arr.length === 0) return []

      const rangeMap = {} // { num => [lo, hi] }
      let largestRange = [arr[0], arr[0]]
      for (num of arr) {
      if (rangeMap[num]) continue;
      rangeMap[num] = [num,num] // init with default range

      if (rangeMap[num-1]) largestRange = union(num, num-1, rangeMap, largestRange) // union num with left
      if (rangeMap[num+1]) largestRange = union(num, num+1, rangeMap, largestRange) // union num with right
      }
      return largestRange
      }
      function union(x, y, map, range) {
      let newLo = Math.min(map[x][0], map[y][0])
      let newHi = Math.max(map[x][1], map[y][1])

      map[newLo] = [newLo, newHi] // keep endpoints of ranges up to date in map
      map[newHi] = [newLo, newHi]

      return newHi-newLo > range[1]-range[0] ? [newLo,newHi] : range // return newLargestRange
      }