{"id":602,"date":"2013-08-16T16:22:21","date_gmt":"2013-08-16T23:22:21","guid":{"rendered":"http:\/\/192.168.1.2\/wordpress\/?page_id=602"},"modified":"2013-08-16T16:22:21","modified_gmt":"2013-08-16T23:22:21","slug":"cracking-the-coding-interview","status":"publish","type":"page","link":"http:\/\/cywang.no-ip.org\/wordpress\/?page_id=602","title":{"rendered":"Cracking the Coding Interview"},"content":{"rendered":"

\n\tChapter 1. Arrays and Strings<\/strong><\/span>\n<\/p>\n

    \n
  1. \n\t\tImplement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures? [C++<\/a>]\n\t<\/li>\n
  2. \n\t\tImplement a function void reverse(char* str) in C or C++ which reverses a null-terminated string. [C++<\/a>]\n\t<\/li>\n
  3. \n\t\tGiven two strings, write a method to decide if one is a permutation of the other. [C++<\/a>]\n\t<\/li>\n
  4. \n\t\tWrite a method to replace all spaces in a string with ‘%20’. You may assume that the string has sufficient space at the end of the string to hold the additional characters, and that you are given the “true” length of the string. (Note: if implementing in Java, please use a character array so that you can perform this operation in place.)[C++<\/a>]
    \n\t\tEXAMPLE
    \n\t\tInput: “Mr John Smith ”
    \n\t\tOutput: “Mr%20John%20Smith”\n\t<\/li>\n
  5. \n\t\tImplement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the “compressed” string would not become smaller than the original string, your method should return the original string.[<\/span>C++<\/a>]<\/span>\n\t<\/li>\n
  6. \n\t\tGiven an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?\n\t<\/li>\n
  7. \n\t\tWrite an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.\n\t<\/li>\n
  8. \n\t\tAssume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i.e., “waterbottle” is a rotation of “erbottlewat”).[<\/span>C++<\/a>]<\/span>\n\t<\/li>\n<\/ol>\n

    \n\tChapter 2. Linked Lists<\/strong><\/span>\n<\/p>\n

      \n
    1. \n\t\tWrite code to remove duplicates from an unsorted linked list.
      \n\t\tFOLLOW UP
      \n\t\tHow would you solve this problem if a temporary buffer is not allowed?\n\t<\/li>\n
    2. \n\t\tImplement an algorithm to find the nth to last element of a singly linked list.\n\t<\/li>\n
    3. \n\t\tImplement an algorithm to delete a node in the middle of a single linked list, given only access to that node.
      \n\t\tEXAMPLE
      \n\t\tInput: the node c from the linked list a->b->c->d->e
      \n\t\tResult: nothing is returned, but the new linked list looks like a->b->d->e\n\t<\/li>\n
    4. \n\t\tWrite code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.\n\t<\/li>\n
    5. \n\t\tYou have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.
      \n\t\tEXAMPLE
      \n\t\tInput: (7->1->6) + (5->9->2). That is, 617 + 295.
      \n\t\tOutput: 2->1->9. That is, 912.
      \n\t\tFOLLOW UP
      \n\t\tSuppose the digits are stored in forward order. Repeat the above problem.
      \n\t\tEXAMPLE
      \n\t\tInput: (6->1->7) + (2->9->5). That is, 617 + 295.
      \n\t\tOutput: 9->1->2. That is, 912.\n\t<\/li>\n
    6. \n\t\tGive a circular linked list, implement an algorithm which returns the node at the beginning of the loop.
      \n\t\tDEFINITION
      \n\t\tCircular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
      \n\t\tEXAMPLE
      \n\t\tInput: A->B->C->D->E->C [the same C as earlier]
      \n\t\tOutput: C\n\t<\/li>\n
    7. \n\t\tImplement a function to check if a linked list is a palindrome.\n\t<\/li>\n<\/ol>\n

      \n\tChapter 5. Bit Manipulation<\/strong><\/span>\n<\/p>\n

        \n
      1. \n\t\tYou are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to insert M into N such that M starts at bit j and ends at bit i. You can assume that the bits j through I have enough space to fit all of M. That is, if M = 10011, you can assume that there are at least 5 bits between j and i. You would not, for example, have j = 3 and i = 2, because M could not fully fit between bit 3 and bit 2.
        \n\t\tEXAMPLE
        \n\t\tInput:    N = 10000000000, M = 10011, i = 2, j = 6
        \n\t\tOutput: N = 10001001100\n\t<\/li>\n
      2. \n\t\tGiven a real number between 0 and 1 (e.g., 0.72) that is passed in as a double, print the binary representation.
        \n\t\tIf the number cannot be represented accurately in binary with less than 32 characters, print “ERRIR.”\n\t<\/li>\n
      3. \n\t\tGiven a positive integer, print the next smallest and the next largest number that have the same number of 1 bits in their binary representation.\n\t<\/li>\n
      4. \n\t\tExplain what the following code does: ( ( n & (n-1) ) == 0).\n\t<\/li>\n
      5. \n\t\tWrite a function to determine the number of bits required to convert integer A to integer B.
        \n\t\tEXAMPLE
        \n\t\tInput: 31, 14
        \n\t\tOutput: 2\n\t<\/li>\n
      6. \n\t\tWrite a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, and so on).\n\t<\/li>\n
      7. \n\t\tAn array A contains all the integers from 0 to n, except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation.
        \n\t\tThe elements of A are represented in binary, and the only operation we can use to access them is “fetch the j-th bit of A[i],” which takes constant time.
        \n\t\tWrite code to find the missing integer. Can you do it in O(n) time?\n\t<\/li>\n
      8. \n\t\tA monochrome screen is stored as a single array of bytes, allowing eight consecutive pixels to be stored in one byte.
        \n\t\tThe screen has width w, where w is divisible by 8 (that is, not byte will be split across rows).
        \n\t\tThe height of the screen, of course, can be derived from the length of the array and the width.
        \n\t\tImplement a function drawHorizontalLine(byte[] screen, int width, int x1, int x2, int y) which draws a horizontal line from (x1, y) to (x2, y).\n\t<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

        Chapter 1. Arrays and Strings Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures? [C++] Implement a function void reverse(char* str) in C or C++ which reverses a null-terminated … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":598,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"class_list":["post-602","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/pages\/602","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/page"}],"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=602"}],"version-history":[{"count":1,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/pages\/602\/revisions"}],"predecessor-version":[{"id":605,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/pages\/602\/revisions\/605"}],"up":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/pages\/598"}],"wp:attachment":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=602"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}