Steve Yegge's phone screen questions

yegges-phone-screening-questions.rb

https://sites.google.com/site/steveyegge2/five-essential-phone-screen-questions

# Area Number One: Coding
  # 1. Write a function to reverse a string.
  echo -e a\\nab\\nabc\\nabcdef© | ruby -lne 'puts $_.reverse'

  # 2. Write function to compute Nth fibonacci number
  seq 0 10 | ruby -ne '
  a, b = 0, 1
  $_.to_i.times { a, b = a+b, a }
  puts a'

  # 3. Print out the grade-school multiplication table up to 12x12
  ruby -e '
  rows = 1.upto(12).map do |y|
   1.upto(12).map { |x| x * y }
  end
  format = rows.last.map { |n| "%-#{n.digits.size}d" }.join(" ")
  puts rows.map { |row| format % row }'

  # 4. Write a function that sums up integers from a text file, one int per line
    # using `seq` instead of making a file:
    seq 10 | awk '{ sum += $0 } END { print sum }'

    # but if you really want it to be read in from a file:
    seq 10 > inputs && ruby -e 'puts File.readlines("inputs").map(&:to_i).sum'

    # and if they value efficiency over brevity:
    seq 10 > inputs && ruby -e 'puts File.foreach("inputs").reduce(0) { |sum, line| sum + line.to_i }'

  # 5. Write function to print the odd numbers from 1 to 99
  seq 99 | ruby -ne 'print if $_.to_i.odd?'

  # 6. Find the largest int value in an int array
  ruby -e '
  ints = 10.times.map { rand 1000 }
  p ints: ints
  p largest: ints.max'

  # 7. Format an RGB value (three 1-byte numbers) as a 6-digit hexadecimal string
  ruby -e 'puts "%02x"*3 % ARGV.map(&:to_i)' 255 0 17

# Area Number Two: Object-Oriented Programming
  # a) Terminology
    # The candidate should be able to give satisfactory definitions for a random selection of the following terms:
    # class, object (and the difference between the two)
    objects store data, classes store methods that operate on that data

    # instantiation
    allocate memory for an object and set its class pointer to the instantiated class
    
    # method (as opposed to, say, a C function)
    a function that depends on `self` or `this` (or w/e your lang calls it)

    # virtual method, pure virtual method
    IDK, this is some Java shit. My guess would be something like a method that
    comes from an interface and doesnt know how the things it uses are implemented

    # class/static method
    Method you call on a class instead of its instance
    (in Ruby, the difference between dot and hash, eg `File.open` and `File#open?`)
    
    # static/class initializer
    Again, some Java shit... guessing: a constructor method since in Java you do
    like `new String([104, 101, 108, 108, 111], 0, 5)` which calls a static method
    named `Sring` in the `String` class.
    
    # constructor
    Method that configures an object after its been instantiated. In Ruby, `initialize`
    
    # destructor/finalizer
    Method that cleans up any resources an object owns when it gets garbage collected
    (eg releasing file handles, freeing memory, etc) Pretty sure you can define these
    in Ruby, but usually anything which would do that is defined in a library in C code.
    
    # superclass or base class
    The place you continue searching, if you cant find the method youre looking for in this class
    
    # subclass or derived class
    Classes that will inherit this class methods
    
    # inheritance
    A way to share methods by creating a linked list of classes to search in
    
    # encapsulation
    Hiding implementation details behind an interface
    
    # multiple inheritance (and give an example)
    When you can have multiple class pointers... no idea how ties are broken. C++
    
    # delegation/forwarding
    Implementing a method by calling that method on some other object
    
    # composition/aggregation
    Accomplish functionality by calling methods on other objects instead of `this` / `self`
    
    # abstract class
    More Java shit. A class that can be inherited from, but not instantiated,
    becuase it lacks certain implementation details.
    
    # interface/protocol (and different from abstract class)
    A description of a set of methods (maybe other stuff, too, IDK).
    Used to appease the type system (eg allows you to convince the type system
    that your object can be used by things that receive objects implementing an
    interface). IDK the difference, probably an interface cant configure memory
    (not sure what thats called in Java, but like adding a property or attribute
    or something like that)
    
    # method overriding
    When a subclass shadows a method it inherits
    
    # method overloading (and difference from overriding)
    When a method has multiple signatures (this DNE in Ruby, people approximate
    it by reflecting on args and doing different things, but IME, code turns out
    better if you dont coddle your callers like that)

    Difference: In overriding, the methods exist in different classes,
    in overloading, they exist on the same class.
    
    # polymorphism (without resorting to examples)
    When different types of objects can be used by the same piece of code.

    # is-a versus has-a relationships (with examples)
    is-a: you inherit your functionality, has-a: you talk to instance variables that implement parts of your functionality

    # method signatures (what's included in one)
    argument types and return type
    
    # method visibility (e.g. public/private/other)
    I dont remember in Java, but in Ruby:
    public: anyone can call this method
    private: this method can be called as long as theres no receiver (hence its called on self)... IIRC, there might be some exceptions around this I would need to do some experiments and get back to you
    protected: this method can be called by other instances of this class.

  # b) OO Design
    Uhm.. Im punting on almost all of these. I just dont write code this way.
    They want to say like "Design a deck of cards that can be used for different card game applications"
    I have no idea, you have to show me how you want to use it and then I can
    tell you want I would do, but this problem description is way too open ended.

    # 4. Design an OO representation to model HTML.
    Node = Struct.new :name, :attributes, :children
    Node.new 'div', {class: 'primary'}, [Node.new('a', {href: "/"}, ["home"])]

# Area Number Three: Scripting and Regular Expressions
  # Last year my team had to remove all the phone numbers from 50,000 Amazon web page templates, since many of the numbers were no longer in service, and we also wanted to route all customer contacts through a single page.
  # Let's say you're on my team, and we have to identify the pages having probable U.S. phone numbers in them. To simplify the problem slightly, assume we have 50,000 HTML files in a Unix directory tree, under a directory called "/website". We have 2 days to get a list of file paths to the editorial staff. You need to give me a list of the .html files in this directory tree that appear to contain phone numbers in the following two formats: (xxx) xxx-xxxx and xxx-xxx-xxxx.
  For an exact match:
    ag '(?:\(\d{3}\) |\d{3}-)\d{3}-\d{4}' /website

  But really Id prob do this, b/c if they were entered by hand then they may not
  strictly follow the specified formats, this allows for whitespace in places it
  might accidentally show up, as well as a few likely variations such as omitting
  or not omitting the dash in different places:
    ag '(?:\(\d{3}\)|\d{3})\s*-?\s*\d{3}\s*-?\s*\d{4}' /website

  After looking at his solution, I'm amending mine to add leading and trailing word boundaries:
    ag '(?:\(\d{3}\)|\b\d{3})\s*-?\s*\d{3}\s*-?\s*\d{4}\b' /website

  # So let's say you've got a set of source files in C, C++, or Java. Your choice. And I want you to modify them so that in each source file, every open- and close-paren has exactly one space character before and after it. If there is any other whitespace around the paren, it's collapsed into a single space character.
  ruby -i -pe 'gsub(/ *([()] *)+/) { " #{$&.delete(" ").chars.join(" ")} " }' /path/to_file

# Area Number Four: Data Structures
  # 1) arrays - I'm talking about C-language and Java-language arrays: fixed-sized, indexed, contiguous structures whose elements are all of the same type, and whose elements can be accessed in constant time given their indices.
    #   what you use them for (real-life examples)
      uhm...
    #   why you prefer them for those examples
      they are compact, they work well with CPU caching
    #   the operations they typically provide (e.g. insert, delete, find)
      insert, delete, find, select, but really, these are all bad for this ds
      push and pop are decent, you can do enqueue and dequeue efficiently if you keep some metadata,
        you would need to have a strategy if you push more data than you have
    #   the big-O performance of those operations (e.g. logarithmic, exponential)
      insert: O(n), delete: O(N+M) where M=number of occurrences in the array, find: O(N), select: O(N^2)
      push: O(1), pop: O(1)
    #   how you traverse them to visit all their elements, and what order they're visited in
      you can access them async, eg ary[i] (because that location can be calculated in memory)
      it can be common to itarate: for(int i=0; i < ary.length; ++i) whatever(ary[i]);
    #   at least one typical implementation for the data structure
      no idea what this means
  # 2) vectors - also known as "growable arrays" or ArrayLists. Need to know that they're objects that are backed by a fixed-size array, and that they resize themselves as necessary.
    #   what you use them for (real-life examples)
      where you want an array but dont know the size
    #   why you prefer them for those examples
      IDK, man
    #   the operations they typically provide (e.g. insert, delete, find)
      same as array, but you can allocate more memory if you fill it up
    #   the big-O performance of those operations (e.g. logarithmic, exponential)
      same as array
    #   how you traverse them to visit all their elements, and what order they're visited in
      same as array
    #   at least one typical implementation for the data structure
      Vector class in Java?
  # 3) linked lists - lists made of nodes that contain a data item and a pointer/reference to the next (and possibly previous) node.
    #   what you use them for (real-life examples)
      inheritance hierarchies, theyre easier to implement than vectors,
      sooo if youre in C then you might choose them just for simplicity
    #   why you prefer them for those examples
      Nodes can share their ancestors without duplicating memory
    #   the operations they typically provide (e.g. insert, delete, find)
      push/pop, insert (meh), delete (meh), find (meh)
    #   the big-O performance of those operations (e.g. logarithmic, exponential)
      push: O(1), pop: O(1), insert: O(N), delete: O(N), find: O(N)
    #   how you traverse them to visit all their elements, and what order they're visited in
      Node* node = list->head;
      while(node) {
        whatever(node);
        node = node->next;
      }
    #   at least one typical implementation for the data structure
      :shrug:
  # 4) hashtables - amortized constant-time access data structures that map keys to values, and are backed by a real array in memory, with some form of collision handling for values that hash to the same location.
    # what you use them for (real-life examples)
      in practice, I use them where I could use a struct, b/c its super convenient.
      in theory, I use them where keys are unknown and not sequential
    #   why you prefer them for those examples
      theyre efficient, I can have non-integer keys
    #   the operations they typically provide (e.g. insert, delete, find)
      insert, delete, find
    #   the big-O performance of those operations (e.g. logarithmic, exponential)
      insert, delete, find: O(1) (assuming you can generate the hash in constant time, and depending on how you handle collisions)
    #   how you traverse them to visit all their elements, and what order they're visited in
      You generally dont, except that in Ruby, theyre implemented as both a hash and a linked list, so you can follow each item to the next item
    #   at least one typical implementation for the data structure
      I dont... like what is this even asking? Do they want me to say Symbol tables in Ruby or the `params` hash in Rails or something else? I dont get this Q
  # 5) trees - data structures that consist of nodes with optional data elements and one or more child pointers/references, and possibly parent pointers, representing a heirarchical or ordered set of data elements.
    #   what you use them for (real-life examples)
      In practice, its nearly always for ASTs
    #   why you prefer them for those examples
      uhhhhh... the "T" literally stands for "Tree"
    #   the operations they typically provide (e.g. insert, delete, find)
      prefix/infix/postfix iteration
      If the tree is sorted, tehn you can do an efficient find
      You can do insert/find/delete efficiently in some cases
    #   the big-O performance of those operations (e.g. logarithmic, exponential)
      iterate: O(N)
      sorted insert/find/delete: O(N) (assuming its also balanced)
    #   how you traverse them to visit all their elements, and what order they're visited in
      https://github.com/JoshCheek/tree_traversal_visualizer
    #   at least one typical implementation for the data structure
      abstract syntax tree
  # 6) graphs - data structures that represent arbitrary relationships between members of any data set, represented as networks of nodes and edges.
    #   what you use them for (real-life examples)
      representing a network
    #   why you prefer them for those examples
      because it *can* represent that data
    #   the operations they typically provide (e.g. insert, delete, find)
      IDK, man
    #   the big-O performance of those operations (e.g. logarithmic, exponential)
      Show me an interface and Ill tell you
    #   how you traverse them to visit all their elements, and what order they're visited in
      ugh
    #   at least one typical implementation for the data structure
      a social network
  # Weeder questions
    # 1) What are some really common data structures, e.g. in java.util?
      I dont have javadocs memorized, so... no clue
    # 2) When would you use a linked list vs. a vector?
      stack or queue: linked list, shared structure: linked list
      single data structure with efficient growth: vector
    # 3) Can you implement a Map with a tree? What about with a list?
      yes and yes, implement them with an array or vector, b/c when you map the
      hash to an index, it will be much more effficient to use contiguous memory
      (because you can just mod the hash by the size of the array/vector)
    # 4) How do you print out the nodes of a tree in level-order (i.e. first level, then 2nd level, then 3rd level, etc.)
      Tree = Struct.new :data, :left, :right
      def each(tree, q=[], &block)
        return to_enum :each, tree, q unless block
        if tree
          each nil, q<<tree, &block
        elsif q.any?
          node = q.shift
          q << node.left if node
          q << node.right if node
          block.call node.data if node
          each nil, q, &block
        end
      end
      tree = Tree.new '0',
            Tree.new('10',
              Tree.new('100'),
              Tree.new('010')),
            Tree.new('01',
              Tree.new('010'),
              Tree.new('011'))
      each(tree).to_a # => ["0", "10", "01", "100", "010", "010", "011"]
    # 5) What's the worst-case insertion performance of a hashtable? Of a binary tree?
      hash: If you bucket the keys and collide on every insertion, then O(N)
      binary tree: if youre doing BST instead of red/black tree or w/e, then
      they could all go down the same path, turning it into a crappy linked list,
      so also O(N)
    # 6) What are some options for implementing a priority queue?
      a heap (I think this is the only option, really, though it will be implemented
      as a tree, which can be stored with pointers like a linked list, or as an array,
      if it doesnt grow or vector if it does... calculate the child index by doubling
      the parent idnex and adding either 0 or 1)
  # Area Number Five: Bits and Bytes
    # Candidates should know what bits and bytes are. They should be able to count in binary; e.g. they should be able to tell you what 2^5 or 2^10 is, in decimal. They shouldn't stare blankly at you when you ask with 2^16 is. It's a special number. They should know it.
      bit: 1 of 2 values; byte: 8 bits; 0, 1, 10, 11, 100, 101, 110, 111, ...
      2^5... 32? 2^10 prob 1024 (just checked and yeah, but I don't think it's
      relevant to have that memorized)
      2^16... Honestly dont know prob 16.??K (checked: nope, its 65.5k, no idea why he thinks its special)
    # They should know at least the logical operations AND, OR, NOT, and XOR, and how to express them in their favorite/strongest programming language.
      n1 & n2 # each bit will be a 1 if both bits are 1
      n1 | n2 # each bit will be a 1 if either bit is a 1
      n1 ^ n2 # each bit will be a 1 if exactly 1 bit is a 1
    # They should understand the difference between a bitwise-AND and a logical-AND; similarly for the other operations.
      bitwise and operates on each bit in a number, logical and works on true/false
    # Candidates should know the probable sizes of the primitive data types for a standard 32-bit (e.g. Intel) architecture.
      I assume 32 bits?
    # If they're a Java programmer, they should know exactly what the primitive types are (byte, short, int, long, float, double, char, boolean) and, except for boolean, exactly how much space is allocated for them per the Java Language specification.
      not a java programmer. I know what all those types are, guesses about sizes on 32 bit arch:
      byte: byte, short: byte, int: 4 bytes, long: 8 bytes, float: 4 bytes,
      double: 8 bytes, char: byte, boolean: ...byte? (or bit, but prob byte, b/c
        CPU operations are prob inefficient if you want to work memory thats 1 bit in size)
      These sizes might change with your architecture, not sure
    # Everyone should know the difference between signed and unsigned types, what it does to the range of representable values for that type, and whether their language supports signed vs. unsigned types.
      signed types can represent negative numbers
      it cuts the magnitude of representable numbers in half (b/c half-1 of the values can be neg)
      Ruby does not have unsigned types
    # Candidates should know the bitwise and logical operators for their language, and should be able to use them for simple things like setting or testing a specific bit, or set of bits.
      and: & vs &&
      or:  | vs ||
      xor: ^ vs !=
      to operate on bits, you either have to mask (eg you can isolate the third bit with n&0b100) or shift (eg (n>>2)&1)
    # Candidates should know about the bit-shift operators in their language, and should know why you would want to use them.
      Omg, why does he care about this shit? For most ppl, its pointless trivia.
      bit shift operators are << and >>, you use them in place of multiplying
      and dividing by 2, obv /troll
    # A good weeder question for this area is:
      # Tell me how to test whether the high-order bit is set in a byte.
      n[7]==1
      # Write a function to count all the bits in an int value; e.g. the function with the signature int countBits(int x)
        def count_bits(n)
          n.to_s(2).gsub(/1/).count
        end
      # Describe a function that takes an int value, and returns true if the bit pattern of that int value is the same if you reverse it (i.e. it's a palindrome); i.e. boolean isPalindrome(int x)
        uhhhhh... I think you can calculate the high bit with like log_2(n),
        then can use n[i] to access bit i, so treat it like a string, but use
        the above calculation for the initial upper index, and 0 for the lower index,
        if low > high, return true, if bit[low] != bit[high] return false, otherwise
        increment low and decrement high
      # C/C++ programmers should know about the sizeof operator and how (and why/when) to use it. Actually, come to think of it, everyone should know this.
        not a C/C++ dev, but it tells you how many bytes a given value is (or smth
        like that, at the very least, whatever unit it uses matches malloc).
        You can use it when the size is known (eg a size you declared statically,
        not something calculated dynamically, eg based on an input value).

        Hes just wrong on the "everyone should know this" part, its specific to C,
        why should anyone know it who doesnt code in C?
      # All programmers should be able to count in hexadecimal, and should be able to convert between the binary, octal, and hex representations of a number.
        0, 1, 2, ... a, b, c, d, e, f, 10, 11, 12, ... 1a, 1b, 1c, 1d, 1e, 1f, 20, 21, 22, ...
        I could convert between them, but not on the fly. I think the trick here is that
        hex is a byte long, so 8 bits, octal is... uh... 3 bits long... nvm, I thought
        there was a trick to it, but I couldnt do it without coding or doing math on a sheet of paper