{"id":357,"date":"2013-03-23T17:13:51","date_gmt":"2013-03-24T00:13:51","guid":{"rendered":"http:\/\/192.168.1.2\/wordpress\/?p=357"},"modified":"2013-05-13T14:48:01","modified_gmt":"2013-05-13T21:48:01","slug":"ctci-ch-1-1","status":"publish","type":"post","link":"http:\/\/cywang.no-ip.org\/wordpress\/?p=357","title":{"rendered":"CTCI: Ch. 1-1"},"content":{"rendered":"<p>\n\t<strong>Implement an algorithm to determine if a string has all unique characters.&nbsp;What if you cannot use additional data structures?&nbsp;<\/strong>\n<\/p>\n<p>\n\t<strong>\u200b<\/strong>\n<\/p>\n<p>\n\t<!--more-->\n<\/p>\n<pre class=\"brush:cpp;\">\r\n#include &lt;iostream&gt;\r\n#include &lt;string.h&gt;\r\nusing namespace std;\r\nbool checkUnique(char *str);\r\n\r\nbool checkUnique(char *str)\r\n{\r\n    \/\/ string length is less than 256\r\n    if(strlen(str) &gt; 256)\r\n        return false;\r\n    \r\n    int charArray[256] = {};\r\n    for(int i=0;i&lt;strlen(str);i++)\r\n    {  \r\n        charArray[(int)str[i]]++;\r\n        if(charArray[str[i]] &gt; 1)\r\n            return false;\r\n    }\r\n    return true;\r\n}\r\n\r\nint main(int argc, const char * argv[])\r\n{\r\n    char ch[]= &quot;qazwsxedcrfvyhnujm&quot;;\r\n    if(checkUnique(ch))\r\n        cout&lt;&lt;&quot;UNIQUE&quot;&lt;&lt;endl;\r\n    else\r\n        cout&lt;&lt;&quot;NOT UNIQUE&quot;&lt;&lt;endl;\r\n    return 0;\r\n}\r\n<\/pre>\n<p>\n\tTime Complexity: O(n)\n<\/p>\n<p>\n\tSpace Complexity: O(1)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Implement an algorithm to determine if a string has all unique characters.&nbsp;What if you cannot use additional data structures?&nbsp; \u200b<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[19,6],"tags":[],"class_list":["post-357","post","type-post","status-publish","format-standard","hentry","category-chapter-1-arrays-and-strings","category-cracking-the-coding-interview"],"_links":{"self":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/357","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=357"}],"version-history":[{"count":9,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/357\/revisions"}],"predecessor-version":[{"id":427,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/357\/revisions\/427"}],"wp:attachment":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=357"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=357"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=357"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}