{"id":468,"date":"2019-02-02T19:19:56","date_gmt":"2019-02-03T00:19:56","guid":{"rendered":"https:\/\/resrvoir.com\/?page_id=468"},"modified":"2019-03-17T13:49:36","modified_gmt":"2019-03-17T17:49:36","slug":"bad-commit","status":"publish","type":"page","link":"https:\/\/resrvoir.com\/?page_id=468","title":{"rendered":"Bad Commit"},"content":{"rendered":"\n<p>There is a bug in your code. You&#8217;re not certain which commit number introduced the bug into the repo, but you know for certain an earlier commit number where it didn&#8217;t exist yet. A magical function, isBad(), determines if the commit is bad or not.<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"kotlin\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">func isBad(commit: Int) -> Bool<\/pre>\n\n\n\n<p>Given isBad, determine which commit introduced the bug.<br><br>For n commits, this can be solved with a binary search in O(log n). Careful not to make an off-by-one mistake and return the bad commit rather than the commit preceding it.<\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"kotlin\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">func badCommit(pastCommit: Int, currentCommit: Int) -> Int {\n  var left = pastCommit\n  var right = currentCommit\n  var mid = (left + right) \/ 2\n  \n  while (left &lt; right) {\n    if !isBad(commit: mid) {\n      left = mid + 1\n    }\n    else {\n      right = mid\n    }\n    \n    mid = (left + right) \/ 2\n  }\n  \n  return right\n}\n\nbadCommit(pastCommit: 110, currentCommit: 334)<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>There is a bug in your code. You&#8217;re not certain which commit number introduced the bug into the repo, but you know for certain an earlier commit number where it didn&#8217;t exist yet. A magical function, isBad(), determines if the commit is bad or not. Given isBad, determine which commit introduced the bug. For n [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":2,"menu_order":15,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"_links":{"self":[{"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/pages\/468"}],"collection":[{"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/resrvoir.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=468"}],"version-history":[{"count":7,"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/pages\/468\/revisions"}],"predecessor-version":[{"id":733,"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/pages\/468\/revisions\/733"}],"up":[{"embeddable":true,"href":"https:\/\/resrvoir.com\/index.php?rest_route=\/wp\/v2\/pages\/2"}],"wp:attachment":[{"href":"https:\/\/resrvoir.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=468"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}