{"id":3613,"date":"2023-07-24T19:51:45","date_gmt":"2023-07-24T14:21:45","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3613"},"modified":"2023-07-24T19:51:47","modified_gmt":"2023-07-24T14:21:47","slug":"painters-partition-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/painters-partition-problem\/","title":{"rendered":"Painters Partition Problem (With Solution)"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#sample-test-cases\">Sample Test Cases<\/a><\/li><li><a href=\"#approach\">Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#naive-approach\">Naive Approach:<\/a><\/li><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#dynamic-programming-approach\">Dynamic Programming Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#binary-search-approach\">Binary Search Approach<\/a><\/li><li><a href=\"#implementation\">Implementation:<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#practice-problem\">Practice Problem:<\/a><\/li><li><a href=\"#faqs\">FAQs<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-when-should-such-binary-search-approaches-be-thought-of\">Q.1: When should such binary search approaches be thought of?<\/a><\/li><li><a href=\"#q2-which-of-the-above-approaches-is-optimal-in-terms-of-complexity-analysis\">Q.2: Which of the above approaches is optimal in terms of complexity analysis?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given n paint boards, of length {a1, a2, \u2026., an}, and k painters, find the minimum time to paint all the boards, such that any painter will paint only contiguous sections of paint boards. It may be assumed that each painter takes 1 unit of time to paint 1 unit of board.<\/p>\n\n\n\n<h2 id=\"sample-test-cases\">Sample Test Cases<\/h2>\n\n\n\n<p>Input 1:<\/p>\n\n\n\n<p>n = 6, k = 3<\/p>\n\n\n\n<p>a = [10, 20, 60, 50, 30, 40]\n\n\n\n<p>Output 1:<\/p>\n\n\n\n<p>90<\/p>\n\n\n\n<p>Explanation 1:<\/p>\n\n\n\n<p>It can be observed that if each worker is placed such that they are allowed to paint at most 90 units of length, then the work can be completed in a minimum time of 90 minutes by using k = 3 workers.<\/p>\n\n\n\n<p>Input 2:<\/p>\n\n\n\n<p>n = 4, k = 2,<\/p>\n\n\n\n<p>a = [10, 20, 30, 40]\n\n\n\n<p>Output 2:<\/p>\n\n\n\n<p>60<\/p>\n\n\n\n<p>Explanation 2:<\/p>\n\n\n\n<p>The first painter will paint board {10, 20, 30} and the 2nd painter will paint board {40}, taking a total time of 60 minutes. It can be observed that this partition is optimal.<\/p>\n\n\n\n<h2 id=\"approach\">Approach<\/h2>\n\n\n\n<h3 id=\"naive-approach\">Naive Approach:<\/h3>\n\n\n\n<p>The problem can be solved naively in a recursive manner. Observe, that if we have already placed <strong>k &#8211; 1<\/strong> partitions, and we need a total of <strong>k<\/strong> partitions, then we can place the <strong>k &#8211; 1 th cut<\/strong> between the <strong>ith<\/strong> and <strong>(i + 1) th<\/strong> element where <strong>i<\/strong> lies in the range <strong>[1, n]<\/strong>.<\/p>\n\n\n\n<p>Now we need to compute the cost for this arrangement, which can be done as follows:<\/p>\n\n\n\n<ul><li>Cost of the last partition, which is equal to <strong>getSum(i, n),<\/strong> where getSum represents the sum of the elements in the range <strong>[i, j],<\/strong><\/li><li>Maximum value of cost of any partition, which is formed to the left of the k &#8211; 1 th cut.&nbsp;<\/li><li>The cost for the arrangement will be the <strong>maximum<\/strong> of the above 2 cases.<\/li><\/ul>\n\n\n\n<p>To compute the value for 2nd point, we observe that it is itself a subproblem of the original problem with <strong>k := k &#8211; 1<\/strong>. So, our recursive code itself can this subproblem as the algorithm proceeds.<\/p>\n\n\n\n<p>With the recurrence in place, we need to note our base case for the recursion which is as follows:<\/p>\n\n\n\n<ul><li>For <strong>n = 1<\/strong>, Result = a[0].<\/li><li>For <strong>k = 1<\/strong>, Result = getSum(1, n).<\/li><\/ul>\n\n\n\n<p><strong>Code \/ Implementation:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-2\">C++ Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int getSum(vector &lt; int > &amp; a, int left, int right) {\n  int sum = 0;\n  for (int i = left; i &lt;= right; i++) {\n    sum += a[i];\n  }\n  return sum;\n}\nint getMinimumTime(vector &lt; int > &amp; a, int n, int k) {\n  if (n == 1) {\n    return a[0];\n  }\n  if (k == 1) {\n    return getSum(a, 0, n - 1);\n  }\n  int minimumTime = INT_MAX;\n  for (int i = 1; i &lt;= n; i++) {\n    int partitionCost = max(getMinimumTime(a, i, k - 1), getSum(a, i, n - 1));\n    minimumTime = min(minimumTime, partitionCost);\n  }\n  return minimumTime;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-2\">Java Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static int getSum(int[] a, int left, int right) {\n  int sum = 0;\n  for (int i = left; i &lt;= right; i++) {\n    sum += a[i];\n  }\n  return sum;\n}\npublic static int getMinimumTime(int[] a, int n, int k) {\n  if (n == 1) {\n    return a[0];\n  }\n  if (k == 1) {\n    return getSum(a, 0, n - 1);\n  }\n  int minimumTime = Integer.MAX_VALUE;\n  for (int i = 1; i &lt;= n; i++) {\n    int partitionCost = Math.max(getMinimumTime(a, i, k - 1), getSum(a, i, n - 1));\n    minimumTime = Math.min(minimumTime, partitionCost);\n  }\n  return minimumTime;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-2\">Python Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def getSum(a, left, right):\n    sum = 0\n    for i in range(left, right + 1):\n        sum += a[i]\n    return sum\n\n\ndef getMinimumTime(a, n, k):\n    if n == 1:\n        return a[0]\n    if k == 1:\n        return getSum(a, 0, n - 1)\n    minimumTime = 999999\n    for i in range(1, n + 1):\n        partitionCost = max(getMinimumTime(a, i, k - 1), getSum(a, i, n - 1))\n        minimumTime = min(minimumTime, partitionCost)\n    return minimumTime<\/pre>\n\n\n\n<p><strong>Complexity Analysis:<\/strong><\/p>\n\n\n\n<ul><li>Time Complexity: Exponential<\/li><li>Space Complexity: O(1) \/\/ If recursion stack space is ignored<\/li><\/ul>\n\n\n\n<h2 id=\"dynamic-programming-approach\">Dynamic Programming Approach<\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"664\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"partial recursion tree\"  class=\"wp-image-3668 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-1024x664.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-1024x664.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-300x195.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-768x498.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-230x150.png 230w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-260x170.png 260w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-380x246.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-550x357.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-800x519.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-1160x752.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree.png 1354w\" ><\/figure>\n\n\n\n<p>Consider the partial recursion tree for n = 4, k = 3. We observe that many subproblems like (n, k) = (1, 1) are being repeatedly recalculated and redundantly resolved. For a larger recursion tree, even more such subproblems will solved for again and again. So, we can observe that this problem has some <strong>overlapping subproblems<\/strong>, as well as <strong>optimal substructure,<\/strong> which hints us that the problem can be solved with <strong><a href=\"https:\/\/www.interviewbit.com\/courses\/programming\/dynamic-programming\/\" target=\"_blank\" rel=\"noreferrer noopener\">dynamic programming<\/a><\/strong>. The DP states are <strong>DP(i, j)<\/strong> represents computing the optimal cost for putting <strong>i partitions<\/strong> for the <strong>first j elements<\/strong> in the array. The answer can be found in <strong>DP(k, n)<\/strong>. The transitions are the same as explained in the naive recursive approach. The <strong>getSum()<\/strong> function can also be optimized with the help of <strong>prefix sums<\/strong>.<\/p>\n\n\n\n<p><strong>Implementation:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-3\">C++ Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int getSum(vector &lt; int > &amp; a, int left, int right) {\n  if (left == 0) {\n    return a[right];\n  } else {\n    return a[right] - a[left - 1];\n  }\n}\nint getMinimumTime(vector &lt; int > &amp; a, int n, int k) {\n  vector &lt; int > pref(n);\n  pref[0] = a[0];\n  for (int i = 1; i &lt; n; i++) {\n    pref[i] = pref[i - 1] + a[i];\n  }\n  vector &lt; vector &lt; int >> dp(k + 1, vector &lt; int > (n + 1, 0));\n  for (int i = 1; i &lt;= n; i++) {\n    dp[1][i] = getSum(pref, 0, i - 1);\n  }\n  for (int i = 1; i &lt;= k; i++) {\n    dp[i][1] = a[0];\n  }\n  for (int i = 2; i &lt;= k; i++) {\n    for (int j = 2; j &lt;= n; j++) {\n      int minimumTime = INT_MAX;\n      for (int cut = 1; cut &lt;= j; cut++) {\n        minimumTime = min(minimumTime, max(dp[i - 1][cut], getSum(pref, cut, j - 1)));\n      }\n      dp[i][j] = minimumTime;\n    }\n  }\n  return dp[k][n];\n}<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-3\">Java Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static int getSum(int[] a, int left, int right) {\n  if (left == 0) {\n    return a[right];\n  } else {\n    return a[right] - a[left - 1];\n  }\n}\npublic static int getMinimumTime(int[] a, int n, int k) {\n  int[] pref = new int[n];\n  pref[0] = a[0];\n  for (int i = 1; i &lt; n; i++) {\n    pref[i] = pref[i - 1] + a[i];\n  }\n  int[][] dp = new int[k + 1][n + 1];\n  for (int i = 1; i &lt;= n; i++) {\n    dp[1][i] = getSum(pref, 0, i - 1);\n  }\n  for (int i = 1; i &lt;= k; i++) {\n    dp[i][1] = a[0];\n  }\n  for (int i = 2; i &lt;= k; i++) {\n    for (int j = 2; j &lt;= n; j++) {\n      int minimumTime = Integer.MAX_VALUE;\n      for (int cut = 1; cut &lt;= j; cut++) {\n        minimumTime = Math.min(minimumTime, Math.max(dp[i - 1][cut], getSum(pref, cut, j - 1)));\n      }\n      dp[i][j] = minimumTime;\n    }\n  }\n  return dp[k][n];\n}<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-3\">Python Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def getSum(a, left, right):\n    if left == 0:\n        return a[right]\n    else:\n        return a[right] - a[left - 1]\n\n\ndef getMinimumTime(a, n, k):\n    pref = [0] * n\n    pref[0] = a[0]\n    for i in range(1, n):\n        pref[i] = pref[i - 1] + a[i]\n    dp = [[0 for i in range(n + 1)] for j in range(k + 1)]\n    for i in range(1, n + 1):\n        dp[1][i] = getSum(pref, 0, i - 1)\n    for i in range(1, k + 1):\n        dp[i][1] = a[0]\n    for i in range(2, k + 1):\n        for j in range(2, n + 1):\n            minimumTime = 999999\n            for cut in range(1, j + 1):\n                minimumTime = min(\n                    minimumTime, max(dp[i - 1][cut], getSum(pref, cut, j - 1))\n                )\n            dp[i][j] = minimumTime\n    return dp[k][n]<\/pre>\n\n\n\n<p><strong>Complexity Analysis:<\/strong><\/p>\n\n\n\n<ul><li>Time Complexity: O(k * n * n)<\/li><li>Space Complexity: O(k * n)<\/li><\/ul>\n\n\n\n<h2 id=\"binary-search-approach\">Binary Search Approach<\/h2>\n\n\n\n<p>We can also use binary search to solve this problem even optimally. The key idea here is use to binary search for the minimum amount of time which will allow us to completely paint the paint boards if we use the k painters optimally.\u00a0<\/p>\n\n\n\n<p><strong>How to move the pointers in the binary search?<\/strong><\/p>\n\n\n\n<ul><li>If the <strong>current mid<\/strong> is enough to paint the paint boards by k painters, we move the right pointer to mid-1. (The right half of the search space is eliminated)<\/li><li>Else we move the left point to <strong>mid + 1. <\/strong>(The left half of the search space is omitted).<\/li><li>The process is continued till the pointers meet or overtake each other.<\/li><\/ul>\n\n\n\n<p><strong>How to check if k painters are enough for a particular mid?<\/strong><\/p>\n\n\n\n<ul><li>We can linearly traverse the array, and whenever a painter exceeds the total length of which he is allowed to paint, we assign the current paint board to the next painter in line.<\/li><li>If all the paint boards can be coloured with this traversal, then the k painters are enough for the given <strong>mid-value<\/strong>, else not.<\/li><\/ul>\n\n\n\n<h2 id=\"implementation\">Implementation:<\/h2>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int getPainters(vector &lt; int > &amp; a, int n, int k) {\n  int sum = 0, numberOfPainters = 1;\n  for (auto x: a) {\n    sum += x;\n    if (sum > k) {\n      sum = x;\n      numberOfPainters++;\n    }\n  }\n  return numberOfPainters;\n}\nint getMinimumTime(vector &lt; int > &amp; a, int n, int k) {\n  int left = * max_element(a.begin(), a.end());\n  int right = accumulate(a.begin(), a.end(), 0);\n  int result = -1;\n  while (left &lt;= right) {\n    int mid = (left + right) \/ 2;\n    if (getPainters(a, n, mid) &lt;= k) {\n      result = mid;\n      right = mid - 1;\n    } else {\n      left = mid + 1;\n    }\n  }\n  return result;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static int getPainters(int[] a, int n, int k) {\n  int sum = 0, numberOfPainters = 1;\n  for (int i = 0; i &lt; n; i++) {\n    int x = a[i];\n    sum += x;\n    if (sum > k) {\n      sum = x;\n      numberOfPainters++;\n    }\n  }\n  return numberOfPainters;\n}\npublic static int getMinimumTime(int[] a, int n, int k) {\n  int left = 0, right = 0;\n  for (int i = 0; i &lt; n; i++) {\n    left = Math.max(left, a[i]);\n    right += a[i];\n  }\n  int result = -1;\n  while (left &lt;= right) {\n    int mid = (left + right) \/ 2;\n    if (getPainters(a, n, mid) &lt;= k) {\n      result = mid;\n      right = mid - 1;\n    } else {\n      left = mid + 1;\n  }\n  }\n  return result;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def getPainters(a, n, k):\n    sum = 0\n    numberOfPainters = 1\n    for i in range(n):\n        sum += a[i]\n        if sum > k:\n            sum = a[i]\n            numberOfPainters += 1\n    return numberOfPainters\n\n\ndef getMinimumTime(a, n, k):\n    left = max(a)\n    right = sum(a)\n    result = -1\n    while left &lt;= right:\n        mid = (left + right) \/\/ 2\n        if getPainters(a, n, mid) &lt;= k:\n            result = mid\n            right = mid - 1\n        else:\n            left = mid + 1\n    return result<\/pre>\n\n\n\n<p><strong>Complexity Analysis:<\/strong><\/p>\n\n\n\n<ul><li>Time Complexity: O(n * log<sub>2<\/sub>(sum(a)))<\/li><li>Space Complexity: O(1)<\/li><\/ul>\n\n\n\n<h2 id=\"practice-problem\">Practice Problem:<\/h2>\n\n\n\n<ul><li><a href=\"https:\/\/www.interviewbit.com\/old\/problems\/allocate-books\/\" target=\"_blank\" rel=\"noreferrer noopener\">Allocate Books<\/a><\/li><li><a href=\"https:\/\/www.interviewbit.com\/old\/problems\/painters-partition-problem\/\" target=\"_blank\" rel=\"noreferrer noopener\">Painter&#8217;s Partition Problem<\/a><\/li><\/ul>\n\n\n\n<h2 id=\"faqs\">FAQs<\/h2>\n\n\n\n<h3 id=\"q1-when-should-such-binary-search-approaches-be-thought-of\"><span id=\"q-1-when-should-such-binary-search-approaches-be-thought-of\">Q.1: When should such binary search approaches be thought of?<\/span><\/h3>\n\n\n\n<p><strong>Ans<\/strong>: Whenever, there is some pattern such that there is a point before and after which the nature of the curve changes, we can use binary search to search for that point.<\/p>\n\n\n\n<h3 id=\"q2-which-of-the-above-approaches-is-optimal-in-terms-of-complexity-analysis\"><span id=\"q-2-which-of-the-above-approaches-is-optimal-in-terms-of-complexity-analysis\">Q.2: Which of the above approaches is optimal in terms of complexity analysis?<\/span><\/h3>\n\n\n\n<p><strong>Ans<\/strong>: The binary search approach is optimal both in terms of Space and Time Complexity.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given n paint boards, of length {a1, a2, \u2026., an}, and k painters, find the minimum&hellip;\n","protected":false},"author":5,"featured_media":3666,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[562],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3613"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3613"}],"version-history":[{"count":6,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3613\/revisions"}],"predecessor-version":[{"id":21899,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3613\/revisions\/21899"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3666"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3613"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3613"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3613"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}