

<!DOCTYPE html>
<!--[if IE 8]><html class="no-js lt-ie9" lang="en" > <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js" lang="en" > <!--<![endif]-->
<head>
  <meta charset="utf-8">
  
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  
  <title>Interview Material &mdash; PantsNotes 1 documentation</title>
  

  
  

  

  
  
    

  

  
  
    <link rel="stylesheet" href="_static/css/theme.css" type="text/css" />
  

  

  
    <link rel="top" title="PantsNotes 1 documentation" href="index.html"/>
        <link rel="next" title="&lt;no title&gt;" href="TODO-protocols.html"/>
        <link rel="prev" title="&lt;no title&gt;" href="TODO-encryption.html"/> 

  
  <script src="_static/js/modernizr.min.js"></script>

</head>

<body class="wy-body-for-nav" role="document">

  <div class="wy-grid-for-nav">

    
    <nav data-toggle="wy-nav-shift" class="wy-nav-side">
      <div class="wy-side-scroll">
        <div class="wy-side-nav-search">
          

          
            <a href="index.html" class="icon icon-home"> PantsNotes
          

          
          </a>

          
            
            
              <div class="version">
                1
              </div>
            
          

          
<div role="search">
  <form id="rtd-search-form" class="wy-form" action="search.html" method="get">
    <input type="text" name="q" placeholder="Search docs" />
    <input type="hidden" name="check_keywords" value="yes" />
    <input type="hidden" name="area" value="default" />
  </form>
</div>

          
        </div>

        <div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="main navigation">
          
            
            
                <ul class="current">
<li class="toctree-l1 current"><a class="current reference internal" href="">Interview Material</a><ul>
<li class="toctree-l2"><a class="reference internal" href="#questions">Questions</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#google-glassdoor">Google Glassdoor</a></li>
<li class="toctree-l3"><a class="reference internal" href="#facebook-glassdoor">Facebook Glassdoor</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="#study-topics">Study Topics</a></li>
<li class="toctree-l2"><a class="reference internal" href="#design">Design</a></li>
<li class="toctree-l2"><a class="reference internal" href="#coding-questions">Coding Questions</a><ul>
<li class="toctree-l3"><a class="reference internal" href="#id1">Google Glassdoor</a></li>
<li class="toctree-l3"><a class="reference internal" href="#id2">Facebook Glassdoor</a></li>
<li class="toctree-l3"><a class="reference internal" href="#general">General</a></li>
</ul>
</li>
<li class="toctree-l2"><a class="reference internal" href="#quickies">Quickies</a></li>
</ul>
</li>
<li class="toctree-l1"><a class="reference internal" href="TODO-rdbms.html">Relational Databases</a></li>
<li class="toctree-l1"><a class="reference internal" href="algorithms.html">Algorithms</a></li>
<li class="toctree-l1"><a class="reference internal" href="bootprocess.html">Boot Process</a></li>
<li class="toctree-l1"><a class="reference internal" href="cassandra.html">Cassandra</a></li>
<li class="toctree-l1"><a class="reference internal" href="dynamo.html">Dynamo</a></li>
<li class="toctree-l1"><a class="reference internal" href="filesystems.html">Filesystems</a></li>
<li class="toctree-l1"><a class="reference internal" href="kafka-public.html">Kafka</a></li>
<li class="toctree-l1"><a class="reference internal" href="linux-internals.html">Linux Internals</a></li>
<li class="toctree-l1"><a class="reference internal" href="networking.html">Networking</a></li>
<li class="toctree-l1"><a class="reference internal" href="rabbithole.html">Rabbit Hole</a></li>
</ul>

            
          
        </div>
      </div>
    </nav>

    <section data-toggle="wy-nav-shift" class="wy-nav-content-wrap">

      
      <nav class="wy-nav-top" role="navigation" aria-label="top navigation">
        <i data-toggle="wy-nav-top" class="fa fa-bars"></i>
        <a href="index.html">PantsNotes</a>
      </nav>


      
      <div class="wy-nav-content">
        <div class="rst-content">
          





<div role="navigation" aria-label="breadcrumbs navigation">
  <ul class="wy-breadcrumbs">
    <li><a href="index.html">Docs</a> &raquo;</li>
      
    <li>Interview Material</li>
      <li class="wy-breadcrumbs-aside">
        
          
            <a href="_sources/TODO-interview.txt" rel="nofollow"> View page source</a>
          
        
      </li>
  </ul>
  <hr/>
</div>
          <div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
           <div itemprop="articleBody">
            
  <div class="section" id="interview-material">
<span id="interview"></span><h1>Interview Material<a class="headerlink" href="#interview-material" title="Permalink to this headline">¶</a></h1>
<p>TODO: Fix all ref links.</p>
<div class="section" id="questions">
<h2>Questions<a class="headerlink" href="#questions" title="Permalink to this headline">¶</a></h2>
<ul class="simple">
<li>What is an initrd and why is it needed?</li>
</ul>
<p>initrd stands for Initial RAM Disk. PXE/some_bootloader extracts and executes the kernel, and then the kernel can extract and mount its associated initrd. initrd provides a virtual root filesystem which contains several executables and modules that permit the real root filesystem to be mounted, or to do whatever else you&#8217;d like at that point in the boot process.</p>
<p>Nearly all of initrd&#8217;s use cases involve needing to load some needed module into the kernel in order to support a non-standard root filesystem, LVM, network drive, or RAID controller prior to full boot. You may also choose to rebuild your kernel to include necessary modules and get rid of the initrd; however, in the instances of needing to mount a network drive, run some sort of process that doesn&#8217;t need to boot fully into linux, or do some other &#8220;staging&#8221; type thing, an initrd environment is useful.</p>
<ul class="simple">
<li>Files, inodes, filesystems...how do they work? What are file descriptors?</li>
</ul>
<p><strong>Filesystems, inodes, file descriptors</strong>: Described in <span class="xref std std-ref">filesystems</span></p>
<ul class="simple">
<li>What are semaphores? What is a mutex? What&#8217;s the difference between the two?</li>
</ul>
<p>A semaphore is best described as a signaling mechanism, but could also be described as a type of lock. A semaphore is an object that contains a (natural) number, on which two modifying operations are defined. One operation, V, adds 1 to the number. The other operation, P, removes 1. Because the natural number 0 cannot be decreased, calling P on a semaphore containing 0 will block the execution of the calling process/thread until some other thread comes along and calls a V on that semaphore. You may create a semaphore with more than one &#8220;slot&#8221; available (ie: s(6)). As such, semaphores can be used to restrict acess to a certain resource to a maximum (but variable) number of processes.</p>
<p>A mutex is a locking mechanism which helps multiple tasks serialize their access to a shared resource. It&#8217;s simply some function or object you call prior to performing a block of code on some shared resource. Your first call sets a locked flag, then you run your code, and then your second call to the mutex releases the lock.</p>
<p>You might think of a semaphore or a mutex as a key to a bathroom. One key, one door works well for a mutex or a semaphore(1). But above we mentioned semaphores can count higher than one...so one key for six bathrooms. A mutex will not scale in this scenario as it would block each time 1/6 resources are used. A semaphore will allow 6 people to use the bathrooms at once, but it has no idea which bathroom is free at which time. What you end up needing is a separate mutex for each resource regardless.</p>
<p>Because of this, you should not be relying solely on semaphores for locking - in fact, you really should only be using semaphores for simple signaling. For example, have a semaphore for power button which your display subscribes to (semaPend(sem_pwr_button); //wait for signal), such that when the power button is hit, a post (V, increment, semaPost(sem_pwr_button); //send the signal)) is sent and your display thread then unblocks and performs some_code. Another use could be naive throttling: only allow 3 threads to access a database at once.</p>
<ul class="simple">
<li>How are cookies passed in the HTTP protocol?</li>
</ul>
<dl class="docutils">
<dt>The server sends one of these in its response header (square brackets optional):</dt>
<dd>Set-Cookie: &lt;em&gt;value&lt;/em&gt;[; expires=&lt;em&gt;date&lt;/em&gt;][; domain=&lt;em&gt;domain&lt;/em&gt;][; path=&lt;em&gt;path&lt;/em&gt;][; secure]</dd>
</dl>
<p>Note that &#8220;value&#8221; above is a string, and is almost always in a format like this: <strong>key=value</strong> , and is usually enforced as such.</p>
<dl class="docutils">
<dt>And if the client accepts the cookie write, it sends this in its next request header:</dt>
<dd>Cookie: name=value</dd>
</dl>
<ul class="simple">
<li>How does traceroute work?</li>
</ul>
<p>ICMP packets are sent, with the initial packet having a TTL of 0 and each consecutive packet having its TTL incremented by one. This elicits a response along each hop of a network path. The TTL count exists in the IP header.</p>
<div class="section" id="google-glassdoor">
<h3>Google Glassdoor<a class="headerlink" href="#google-glassdoor" title="Permalink to this headline">¶</a></h3>
<ul class="simple">
<li>Rank the following in terms of speed: access a register, access main memory, perform a context switch, hd seek time</li>
</ul>
<p>1 Register. 1 or 2 cycles. Smallest and fastest memory on a system. A compiler will typically allocate registers to hold values retrieved from main memory.
2 Perform a context switch (which type? assuming thread switch). 30-60 cycles best case.
3 Access main memory. NUMA local: 100 cycles NUMA remote: 300 cycles for no/normal congestion
4 HD seek time. A typical hdd needs anywhere from 2.5ms to 6.5ms to seek, depending on rotational speed (2ms=15k). Arm movement (stroke/track-to-track) takes anywhere from 0.2 to 1ms. SSD seek time is around 0.08-0.16ms</p>
<p><strong>Context Switch:</strong> The process of storing execution state of a process or thread so that execution can be resumed from the same point at a later time.</p>
<blockquote>
<div>&#8220;Context Switch&#8221; can mean several different things, including: thread switch (switching
between two threads within a given process), process switch (switching between two
processes), mode switch (domain crossing: switching between user mode and kernel mode
within a given thread), and more.</div></blockquote>
<p>Which type of context switch you&#8217;re talking about can mean a very different performance costs. For example, a context switch pausing one thread and the cpu scheduling another where each thread is not sharing memory (separate working sets) could dirty the cpu cache if there is not enough space to hold both thread&#8217;s memory or the new thread fills the cache with new data. The same is true for processes. Additionally, if two processes share the same working set of memory and one is context switched out and another is scheduled in on a different core, it does not have access to the same cache/working set without a NUMA hop or a trip to main memory.</p>
<p><a class="reference external" href="http://blog.tsunanet.net/2010/11/how-long-does-it-take-to-make-context.html">http://blog.tsunanet.net/2010/11/how-long-does-it-take-to-make-context.html</a></p>
<ul class="simple">
<li>What information is contained in a file inode?</li>
</ul>
<p><strong>Filesystems, inodes, file descriptors</strong>: Described in <span class="xref std std-ref">filesystems</span></p>
<ul class="simple">
<li>How is MTU size determined?</li>
</ul>
<p>MTU is referenced by packet (and frame) based protocols like TCP and UDP in order to determine the maximum size of packet it should construct for communication over a given interface. Something called <strong>Path MTU Discovery</strong> (PMTUD) is used in order to discover this value.</p>
<p>In IPv4, this works by setting the <em>DF</em> (don&#8217;t fragment) bit in the ip header of outgoing packets. Any device along the network path whose MTU is smaller than the packet will drop it and send back an ICMP <em>fragmentation needed</em> message containing its MTU. The source host reconfigures appropriately, and the process is repeated.</p>
<p>IPv6 works differently as it does not support fragmentation (nor the don&#8217;t fragment option). Instead, the initial packet MTU is set to the same as the source interface, and if it hits a device along the path where the packet size is too large for its MTU setting, that device drops the packet and sends back an ICMPv6 <em>Packet Too Big</em> message which contains its MTU. The source then reconfigures its MTU appropriately, and the process is repeated.</p>
<p>If the path MTU changes lower along the path after the connection is set up, the process still does its thing. If the MTU changes to a higher value, PMTUD will eventually discover this (Linux performs another PMTD check every 10 minutes by default) and increase MTU accordingly.</p>
<p>Some firewall operators will blanket deny all ICMP traffic. This means that after a TCP handshake happens and the first packet is sent out with a larger MTU than something along the link can handle, the firewall blocks the ICMP reply and you end up with a &#8220;black hole&#8221; connection where the source keeps retrying to send data and some device along the path keeps dropping it, with a blocked response. Some PMTUD attempt to infer this problem and lower MTU size accordingly, but the lack of response could also just be due to congestion.</p>
<p>Some routers may work around this issue by changing the <em>maximum segment size</em> (MSS) of all TCP connections passing through links which have an MTU lower than the ethernet default of 1500. While an MTU is concerned with the total size of a packet, MSS only determines the TCP Segment (minus TCP header) size - typical default = 536 Bytes.</p>
<p>[TCP Packet[TCP Segment[IP datagram[Data link layer Frame]]]]
[UDP Datagram[UDP Segment[IP datagram[Data link layer Frame]]]]</p>
<p>Also reference: <a class="reference internal" href="networking.html#networking-mtu"><span>Maximum Transmission Unit (MTU)</span></a></p>
<ul class="simple">
<li>Which system call returns inode information? (study all common system calls and know them)</li>
</ul>
<p><strong>Kernel - System Calls</strong>: <span class="xref std std-ref">kernel-systemcalls</span></p>
<ul class="simple">
<li>What are signals? What signal does the &#8220;kill&#8221; command send by default? What happens if the signal is not caught by the target process?</li>
</ul>
<p>Check out <a class="reference internal" href="linux-internals.html#kernel-signals"><span>Linux Signals</span></a></p>
<p>Signals are software interrupts. Kill sends a SIGTERM by default. The kernel delivers signals to target processes or process groups on behalf of an originating process, or on behalf of itself. If the originating process has the permissions to send a signal to another, the kernel forwards it on.</p>
<p>Note that processes can ignore, block, or catch all signals except SIGSTOP and SIGKILL. If a process catches a signal, it means that <em>it includes code that will take appropriate action when the signal is received</em>. If the signal is not caught, the kernel will take the appropriate action for the signal.</p>
<ul class="simple">
<li>SIGHUP hangup. Send this to a terminal and it will likely log you out. Other applications may instead use this signal as an indication to reload their configuration without terminating themselves.</li>
<li>SIGINT is sent when you ctrl-c something. It is intended to provide a mechanism for an orderly, graceful shutdown of the foreground process. Interactive shells (mysql, other) may take it to mean &#8220;terminate current query&#8221; rather than the whole process.</li>
<li>SIGQUIT signals a process to terminate and do a core dump</li>
<li>SIGSTOP suspends a processes execution. If you are experiencing some sort of intermittent socket/buffer full or backflow buildup related bug, SIGSTOP is a good way to reproduce the issue. File handles will be kept open.</li>
<li>SIGKILL is the ol&#8217; kill -9</li>
</ul>
<ul class="simple">
<li>Describe a TCP connection setup</li>
</ul>
<p>Look here: <a class="reference internal" href="networking.html#networking-tcp"><span>TCP</span></a></p>
<ul class="simple">
<li>What happens when you type &#8216;ps&#8217; (shell word splitting, searching PATH, loading dynamic libs, argument parsing, syscalls, /proc, etc. expand)</li>
</ul>
<p>A variant of &#8220;the rabbit hole&#8221; question. <span class="xref std std-ref">rabbithole</span></p>
<ul class="simple">
<li>what is the worst case time for a quicksort?</li>
</ul>
<p>O(n^2) for already-sorted lists if your pivot is the final element in the array you&#8217;re sorting, or if all elements in an array are the same. Quicksort performance generally depends on your pivot. Look here: <a class="reference internal" href="algorithms.html#id1"><span>Big O Notation</span></a></p>
<ul class="simple">
<li>What is the maximum length(depth) of a binary tree?</li>
</ul>
<p><a class="reference external" href="http://codercareer.blogspot.com/2013/01/no-35-depth-of-binary-trees.html">http://codercareer.blogspot.com/2013/01/no-35-depth-of-binary-trees.html</a></p>
<p>Max depth is <em>n</em>, ie: unlimited. The maximum depth of a binary tree is the length of the longest path.</p>
<img alt="A binary tree with depth 4" class="align-center" src="_images/compsci-binarytreedepth.png" />
<p>In this image, we can see that the left subtree has a depth of 3 while the right subtree has a depth of 1. So long as the difference in depth between two branches is no greater than 1, it is considered <em>balanced</em>. Therefore, the binary tree depicted in this image is balanced.</p>
<ul class="simple">
<li>What is the theoretical best trans-continental round-trip ping time?</li>
</ul>
<p>Light travels at just below 300,000KM/sec. Light travels through fiber around 30% slower, so 210,000KM/sec. London to NYC is about 5500KM. So, 5500/210000 = 0.026, or 26ms. Routers/switches only add microseconds of delay, so being generous, add 1ms total for both sides. So RTT = around 53ms. Verizon consistently sees 72ms between london and nyc in the real world.</p>
<ul class="simple">
<li>How do you solve a deadlock?</li>
</ul>
<p>A deadlock occurs when multiple processes/threads must acquire <em>more than one shared resource</em>, or in the case of <em>recursive/self deadlock</em> where a thread tries to acquire a lock that it is already holding. Recursive deadlocks are the most common as they are easy to program by mistake. For example, if some function calls code to some other outside module which over some path ends up calling a function in the original module which is protected by the same mutex lock, then it will deadlock. The solution for this type of deadlock is to know your code path. Avoid calling functions outside the module when you don&#8217;t know whether they will call back into the module without reestablishing invariants and dropping all module locks before making the call.</p>
<p>In the case where multiple shared resources are needing to be locked prior to performing an operation, if two or more concurrent process obtain multiple shared resources indescriminately a situation can occur where each process has a resource needed by another process. As a result, none of the processes can obtain all the resources it needs and as such all are blocked from further execution. Within a single application, deadlocks most often occur when two concurrently running threads need to lock the same two or more mutexes. The common advice for avoiding this type of deadlock is to always lock the two mutexes/resources in the same order: if you always lock mutex A before mutex B, then you&#8217;ll never deadlock.</p>
<ul class="simple">
<li>Difference between processes and threads</li>
</ul>
<p><em>Processes are the abstraction of running programs</em>: A binary image, virtualized memory, various kernel resources, an associated security context, etc. A process <em>contains</em> one or more threads.</p>
<p><em>Threads are the unit of execution in a process</em>: A virtualized processor, a stack, and program state. Threads share one memory address space, and each thread is an independent schedulable entity.</p>
<p>Put another way, processes are running binaries and threads are the smallest unit of execution schedulable by an operating system&#8217;s process scheduler.</p>
<ul class="simple">
<li>What is a socket?</li>
</ul>
<p>A socket is a way to speak to other programs using standard Unix file descriptors. When Unix programs do any sort of I/O, they do it by reading or writing to a file descriptor. A file descriptor is simply an integer associated with an open file. This file can be a network connection, a FIFO, a pipe, a terminal, a real on-disk file, or just about anything else! Read more about sockets here: <span class="xref std std-ref">linux-kernel-sockets</span></p>
<ul class="simple">
<li>What is a transaction (db)?</li>
</ul>
<p>A transaction is simply a completed operation. Read more about RDBMS+ACID or NoSQL+CAP/Other here: <span class="xref std std-ref">rdbms</span></p>
<ul class="simple">
<li>What algorithm does python&#8217;s .sort() use?</li>
</ul>
<p>Timsort! Read more here: <a class="reference internal" href="algorithms.html#algorithms-sorting"><span>Sorting Algorithms</span></a></p>
</div>
<div class="section" id="facebook-glassdoor">
<h3>Facebook Glassdoor<a class="headerlink" href="#facebook-glassdoor" title="Permalink to this headline">¶</a></h3>
<ul class="simple">
<li>What is a filesystem, how does it work?</li>
</ul>
<p>A filesystem is a method of organizing data on some form of media. Read about specific filesystems here: <span class="xref std std-ref">filesystems</span></p>
<ul class="simple">
<li>What is a socket file? What is a named pipe?</li>
</ul>
<p>Read more about sockets here: <span class="xref std std-ref">linux-kernel-sockets</span>. A named pipe is just a | that exists on a filesystem rather than only in your command line. Here are some cool things you can do with named pipes:</p>
<p>Create a pipe that gzips things piped to it and then outputs to a file:</p>
<blockquote>
<div>mkfifo my_pipe
gzip -9 -c &lt; my_pipe &gt; out.gz &amp;
# Now you can send some stuff to it
cat file &gt; my_pipe</div></blockquote>
<p>An example that is perhaps more useful is this:</p>
<blockquote>
<div>mkfifo /tmp/my_pipe
gzip &#8211;stdout -d file.gz &gt; /tmp/my_pipe # Decompress file.gz, send to my_pipe
# Now load the uncompressed data into a MySQL table:
LOAD DATA INFILE &#8216;/tmp/my_pipe&#8217; INTO TABLE tableName;</div></blockquote>
<p>So what we did here was use a named pipe in order to transfer data from one program (gzip decompressing stuff) to another (mySQL). This allowed us to write out the entire uncompressed version of file.gz before loading it into MySQL, rather than having to decompress the whole thing first.</p>
<p>(RobertL: Data written to a pipe is buffered by the kernel until it is read from the pipe. That buffer has a fixed size. Portable applications should not assume any particular size and instead be designed so as to read from the pipe as soon as data becomes available. The size on many Unix systems is a page, or as little as 4K. On recent versions of Linux, the size is 64K. What happens when the limit is reached depends on the O_NONBLOCK flag. By default (no flag), a write to a full pipe will block until sufficient space becomes available to satisfy the write. In non-blocking mode (flag provided), a write to a full pipe will fail and return EAGAIN.)</p>
<ul class="simple">
<li>What is a zombie process? How and when can they happen?</li>
</ul>
<p>When a process ends via exit, all of the memory and resources associated with it are deallocated; however, the process&#8217;s entry in the process table remains. Its process status becomes EXIT_ZOMBIE and the process&#8217;s parent is sent a SIGCHLD signal by the kernel letting it know that its child process has exited. At this point, the parent process is supposed to call a wait() in order to read the dead process&#8217;s exit status and such. After the wait() is called, the process&#8217;s entry in the process table is removed.</p>
<p>If a parent process doesn&#8217;t handle the SIGCHLD and call wait(), you end up with a zombie process. Let run wild under high load, you may run out of PIDs. To get rid of zombie processes, you may try using kill to send SIGCHLD to the parent, and if that doesn&#8217;t work, kill the parent. The zombie will become an orphan which is then picked up by init (1), who calls wait() periodically.</p>
<ul class="simple">
<li>What does user vs system cpu load mean?</li>
</ul>
<p>Read more about the user and system separation in <span class="xref std std-ref">linux-internals</span>.</p>
<ul class="simple">
<li>How can disk performance be improved?</li>
</ul>
<p>Caching, sequential reads/writes, block/stripe alignment.</p>
<ul class="simple">
<li>Explain in every single step about what will happen after you type &#8220;ls (asterisk-symbol-redacted)&#8221; or &#8220;ps&#8221; in your terminal, down to machine language</li>
</ul>
<p>Variant of <span class="xref std std-ref">rabbithole</span></p>
<ul class="simple">
<li>Suppose there is a server with high CPU load but there is no process with high CPU time. What could be the reason for that? How do you debug this problem?</li>
</ul>
<p>Might be due to something causing high IOWait and not having associated higher cpu usage. If everything else is basically idle, this is usually an indicator that the disk/controller you&#8217;re writing to is about to die. If there&#8217;s a process at something really low, like 7% or something, then it could just be pushing a lot of data to slow media and not requiring much cpu time to do it. iostat will tell you what disk is being written to, and iotop will tell youwhich process it is. If you don&#8217;t have these tools installed, look for processes that are in uninterruptible sleep:</p>
<blockquote>
<div>while true ; do ps -eo state,pid,cmd|grep &#8220;^D&#8221; ; sleep 1 ; done</div></blockquote>
<p>Anything marked with a &#8220;D&#8221; at the start are in uninterruptible sleep, or a wait state. If you see a suspicious process, cat /proc/&lt;pid&gt;/io a couple times to see its io activity. You can also check lsof to see what file handles it has open.</p>
<blockquote>
<div>cat /proc/12345/io
lsof -p 12345</div></blockquote>
<p>If you&#8217;re not seeing high IOWait, the high cpu is likely due to many very short lived processes stuck in a crash loop or doing some other thing it&#8217;s not supposed to. atop shows you all processes which have lived and died over a polling period. Alternately, Brendan Gregg has a tool called execsnoop which he built for exactly this problem. If your kernel is new enough, you can use systemtap as well.</p>
<ul class="simple">
<li>What happens when a float is cast to/from a boolean in python?</li>
</ul>
<p>If float == 0: bool = False ; else: bool = True  ? Not sure what more to say here</p>
<ul class="simple">
<li>Given a database with slow I/O, how can we improve it?
- If relational, check out <span class="xref std std-ref">rdbms</span> notes.
- Profile the thing to see where it&#8217;s slow (expand)
- indexing (expand)
- disk optimisations (expand)</li>
<li>What options do you have, nefarious or otherwise, to stop people on a wireless network you are also on (but have no admin rights to) from hogging bandwidth by streaming videos?
- discover their mac address (iwconfig wlan0 mode monitor;tcpdump), create another interface and assign their mac address as your own, make script to forever perform gratuitous ARP until offender gets annoyed at poor performance and stops using internet. (might also just be able to do arping -U ip.addre.s.s &amp; echo 1 &gt; /proc/sys/net/ipv4/ip_nonlocal_bind <a class="reference external" href="http://serverfault.com/questions/175803/how-to-broadcast-arp-update-to-all-neighbors-in-linux">http://serverfault.com/questions/175803/how-to-broadcast-arp-update-to-all-neighbors-in-linux</a>)
- If you can gain access to wifi router, ban their mac or set QoS if available
- (expand)</li>
<li>How exactly does the OS transfer information across a pipe?</li>
</ul>
<p><a class="reference internal" href="linux-internals.html#linux-internals-systemcalls"><span>System Calls</span></a>
Linux has an in-memory VFS called pipefs that gets mounted in kernel space at boot. The entry point to pipefs is the pipe(2) syscall. This system call creates a pipe in pipefs and then returns two file descriptors (one for the read end, opened using O_RDONLY, and one for the write end, opened using O_WRONLY).</p>
<p>In the case of unnamed pipes using bash, bash will call pipe(2) and get its file descriptors back, dup2 the pipe&#8217;s stdin and first program&#8217;s stdout, start up the second program and dup2 its stdin with the pipe&#8217;s stdout.</p>
<p>The &#8220;left&#8221; program writes out, and that data ends up in a 64KB (usually) sized buffer, which is immediately read by the &#8220;right&#8221; program. Once the &#8220;left&#8221; program is done writing, it closes its fd, and the listening end then gets an EOF (read(2) will return 0).</p>
<p>If the pipe is full, the write will block. If the pipe is empty, the read will block. It&#8217;s possible to create FIFOs or socket files non-blocking, which will return an error if full.</p>
<ul class="simple">
<li>What problems are you going to run into when doing IPC (pipes, shared memory structures)?</li>
</ul>
<dl class="docutils">
<dt>In computer science, &#8220;Classic&#8221; IPC problems all refer to resource contention, or synchronization and deadlock problems. These are generally solved by using semaphores and mutexes, and ensuring access to multiple mutexes is done in order.</dt>
<dd><a class="reference external" href="https://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problem">https://en.wikipedia.org/wiki/Producer%E2%80%93consumer_problem</a>
<a class="reference external" href="https://en.wikipedia.org/wiki/Readers%E2%80%93writers_problem">https://en.wikipedia.org/wiki/Readers%E2%80%93writers_problem</a>
<a class="reference external" href="https://en.wikipedia.org/wiki/Dining_philosophers_problem">https://en.wikipedia.org/wiki/Dining_philosophers_problem</a>
<a class="reference external" href="https://en.wikipedia.org/wiki/Sleeping_barber_problem">https://en.wikipedia.org/wiki/Sleeping_barber_problem</a></dd>
</dl>
<ul class="simple">
<li>What is &#8220;file descriptor 2&#8221;</li>
</ul>
<p>STDERR. fd0 is STDIN, and fd1 is STDOUT. Read more in <span class="xref std std-ref">linux-file-descriptors</span></p>
<ul class="simple">
<li>What&#8217;s the difference between modprobe and insmod?</li>
</ul>
<p>Modprobe is more intelligent than insmod. It refers to a /lib/modules/$(uname -r)/modules.dep.bin (or other depending on OS) dependency file to read available modules and their dependencies. It&#8217;ll accept the name of .ko files in /lib/modules/$(uname -r) as well. Insmod on the other hand will not do dependency resolution, and accepts paths to module files. Modprobe uses insmod to do its work once it does its more intelligent work.</p>
</div>
</div>
<div class="section" id="study-topics">
<h2>Study Topics<a class="headerlink" href="#study-topics" title="Permalink to this headline">¶</a></h2>
<ul class="simple">
<li>Brush up on RAID</li>
</ul>
<p>The RAID write hole problem can crop up when a power loss or some other event causes a disk write to be interrupted such that raid parity bits are not consistent with the data. Prevent this by using Battery Backed caches or PDUs, and/or consider storage systems that use transactional-style writes.</p>
<ul class="simple">
<li>learn the particulars of ssh</li>
<li>core system functionality such as I/O buffering</li>
<li>(googs)Prepare for Hashmap/hashtable questions</li>
<li>(googs)Understand how job scheduling is handled in the most recent iterations of the kernel</li>
</ul>
<p><span class="xref std std-ref">linux-internals-scheduling</span></p>
<ul class="simple">
<li>(googs)Know your signals</li>
</ul>
<p>See above, &#8220;What are signals?&#8221;</p>
<ul class="simple">
<li>(googs)Study up on algorithms and data structs</li>
</ul>
<p><a class="reference internal" href="algorithms.html#id1"><span>Big O Notation</span></a></p>
<ul class="simple">
<li>(googs)Study the book &#8220;Cracking the Coding Interview&#8221; for several weeks prior to interviewing. practice &#8220;whiteboarding&#8221; your code</li>
<li>(fb)Review DNS, TCP, HTTP, system calls, signals, semaphores, complete paths (ie: telnet blah.com 80), boot process (incl UEFI)</li>
<li>(fb)Refresh CCNA related knowledge, TCPDump commands (memorize syntax, memorize basic &#8220;listen&#8221;), ipv6 notes, load balancing types, load balancer failover modes &amp; how VIP mac addr changes (gratuitous/unsolicited ARP), direct routing vs NAT, jumbo frames, MTU size, fragmentation and when it can occur, what a packet looks like</li>
<li>(fb)Review systemtap, perftools, sar(sysstat), and other options</li>
<li>(fb)Write about shared file systems which are read/written to from many servers.</li>
<li>(fb)Write about distributed systems and different types of consistency models and where they are used</li>
</ul>
</div>
<div class="section" id="design">
<h2>Design<a class="headerlink" href="#design" title="Permalink to this headline">¶</a></h2>
<p>Reference stackshare.io for ideas.</p>
<ul class="simple">
<li>(googs)How would you design Gmail?</li>
<li>(googs)How do you best deal with processing huge amounts of data? (if you say map reduce, learn a ton about it)</li>
<li>(fb)Outline a generic performant, scalable system. From frontend (lb&#8217;s? or cluster-aware metadata like kafka) to backend (db&#8217;s, storage, nosql options, etc). Remember networking as well: what features does a high performance network card supply - what can it offload? What should you tweak network wise for high bandwidth connections</li>
<li>(fb)How would you design a cache API?</li>
<li>(fb)How would you design facebook?</li>
</ul>
<ol class="arabic simple">
<li>Define desired features, and split them into their own design. ie: photos, video, news feed, messenger, events</li>
</ol>
<p>Video: Use GPU&#8217;s to transcode streams to different quality levels</p>
<ul class="simple">
<li>(fb)How would you design a system that manipulates content sent from a client (eg: clean bad words in a comment post)?</li>
</ul>
<p>For the clean bad words from a comment post, I would consider splitting the words in a comment post to a list (order matters here if we are to reconstruct the sentence, so can&#8217;t sort or use a dict) and then iterating over them against a badwords hash/dict where the dict key is the badword. This would be O(n)+O(1), or an O(n) operation (this assumes that the hash function for the dict keys is sufficiently robust to make collisions uncommon, giving linear time O(1)).</p>
<p>If badwords is massive, you could consider keeping it sorted and then doing a binary search (O(log n)) against it when comparing words.</p>
<p>If the comment is huge or has many duplicate words and we want to prevent comparing them against the badwords more than once, you could consider splitting each word to a dict where the key is the word, and then doing a str.replace() on the original comment text if a badword match is found.</p>
<ul class="simple">
<li>Design the SQL database tables for a car rental database.</li>
<li>How would you design a real-time sports data collection app?</li>
<li>design a highly-available production service from bare metal all the way to algorithms and data structures. (eg: gmail, hangouts, google maps, etc.)</li>
</ul>
</div>
<div class="section" id="coding-questions">
<h2>Coding Questions<a class="headerlink" href="#coding-questions" title="Permalink to this headline">¶</a></h2>
<div class="section" id="id1">
<h3>Google Glassdoor<a class="headerlink" href="#id1" title="Permalink to this headline">¶</a></h3>
<ul class="simple">
<li>Implement a hash table</li>
</ul>
<p>dicky = {&#8216;herp&#8217;: 1, &#8216;derp&#8217;: 2, &#8216;potato&#8217;: 3}</p>
<ul class="simple">
<li>Remove all characters from string1 that are contained in string2</li>
</ul>
<dl class="docutils">
<dt>This is O(n), but inefficient as strings are immutable in python, so string1 keeps getting recreated.</dt>
<dd><p class="first">string1 = &#8220;can you still read this?&#8221;
string2 = &#8220;aeiou&#8221;
for char in string2:</p>
<blockquote>
<div>string1 = string1.replace(char, &#8220;&#8221;)</div></blockquote>
<p class="last">return string1</p>
</dd>
</dl>
<p>str.translate() in python uses C string magic, ends up being fastest at <em>removing</em> chars</p>
<dl class="docutils">
<dt>Python 2 only:</dt>
<dd>string1 = &#8220;can you still read this?&#8221;
string2 = &#8220;aeiou&#8221;
string1.translate(None, string2)</dd>
<dt>Python 3&#8217;s translate method expects a translation table (ie: dict) passed to it which contains the unicode ordinal value of a character as the key, and an associated ord, str, or None as the value. maketrans() will create this table for us. Any characters entered in the <em>third</em> argument will be mapped to None, which is what we want in this case</dt>
<dd>string1 = &#8220;can you still read this?&#8221;
string2 = &#8220;aeiou&#8221;
charTransTable = str.maketrans(&#8216;&#8217;, &#8216;&#8217;, &#8216;aeiou&#8217;)
# or
charTransTable = str.maketrans(&#8216;&#8217;, &#8216;&#8217;, string2)
string1.translate(charTransTable)</dd>
</dl>
<ul class="simple">
<li>implement quicksort. Determine its running time.</li>
<li>Given a numerym (first letter + length of omitted characters + last letter), how would you return all possible original words? E.G. i18n the numeronym of internationalization</li>
<li>Find the shortest path between two words (like &#8220;cat&#8221; and &#8220;dog), changing only one letter at a time.</li>
<li>Reverse a linked list</li>
<li>Write a function that returns the most frequently occurring number in a list</li>
<li>Do a regex to get phone numbers out of a contacts.txt file</li>
</ul>
</div>
<div class="section" id="id2">
<h3>Facebook Glassdoor<a class="headerlink" href="#id2" title="Permalink to this headline">¶</a></h3>
<ul class="simple">
<li>re-implement &#8216;tail&#8217; in a scripting language</li>
<li>Battleship game: write a function that finds a ship and return its coordinates.</li>
<li>Write a script to ssh to 100 hosts, find a process, and email the result to someone</li>
<li>or i in {1..100} ; do ssh <a class="reference external" href="mailto:user&#37;&#52;&#48;host${i">user<span>&#64;</span>host${i</a>} &#8220;ps -ef|grep blah|grep -v grep|mail -s &#8220;This is the subject&#8221; <a class="reference external" href="mailto:user&#37;&#52;&#48;myemail&#46;com">user<span>&#64;</span>myemail<span>&#46;</span>com</a>&#8221; ; done</li>
<li>Write a function to sort a list of integers like this [5,2,0,3,0,1,6,0] in the most efficient way (look up sorting algorithms)</li>
<li>Given a sentence convert the sentence to the modified pig-latin language: Words beginning with a vowel, remove the vowel letter and append the letter to the end. All words append the letters &#8216;ni&#8217; to the end. All words incrementally append the letter &#8216;j&#8217;. i.e. &#8216;j&#8217;,&#8217;jj&#8217;,&#8217;jjj&#8217;, etc... (what&#8217;s the last part mean? append j&#8217;s incrementally, what?)</li>
<li>take input text and identify the unique words in the text and how many times each word occurred. Edge cases as well as performance is important. How do you identify run time and memory usage?</li>
<li>build a performance monitoring script, adding more features and improving efficiency as you go</li>
<li>For a given set of software checkins, write a program that   will determine which part along the branch where the fault lies.</li>
</ul>
<blockquote>
<div>-So we assume we already have a list of git revisions, and once a certain revision gets hit everything after it fails
-Do a binary search in order to determine where the build starts breaking. Ie: pick the middle number, do a checkout, build, if fail then do another binary search in the middle of startrevision and failedrevision-1. If success, then do another binary search between successrevision+1 and finalrevision..etc etc. Do this until you find that failedrevision-1=a successful revision</div></blockquote>
<ul class="simple">
<li>Given a list of integers, output all subsets of size three, which sum to zero. (wtf? <a class="reference external" href="http://www.glassdoor.com/Interview/Given-a-list-of-integers-output-all-subsets-of-size-three-which-sum-to-zero-QTN_580995.htm">http://www.glassdoor.com/Interview/Given-a-list-of-integers-output-all-subsets-of-size-three-which-sum-to-zero-QTN_580995.htm</a> )</li>
<li>Given a list of integers which are sorted, but rotated   ([4, 5, 6, 1, 2, 3]), search for a given integer in the list.</li>
</ul>
<blockquote>
<div>&#8211;Think of the array as two separate lists. If number we&#8217;re searching for is less than or equal to the last number in the array (3 in this case), then cut array in half and do a binary search on just that half until number is found</div></blockquote>
<ul>
<li><p class="first">Write a frequency list generator! Do one attempt, then try to make it more efficient. Good problem to test performance with. Have it output the top 10 words or something.</p>
<blockquote>
<div><p>For above questions, elaborate on theoretical best performance. Talk about
memory vs CPU usage. Talk about whether certain system calls take more
resources than others. How long it takes to: access a register, access main
memory, perform a context switch, hd seek time</p>
</div></blockquote>
</li>
</ul>
</div>
<div class="section" id="general">
<h3>General<a class="headerlink" href="#general" title="Permalink to this headline">¶</a></h3>
<ul class="simple">
<li>re-implement nc in python</li>
<li>re-implement grep in python</li>
</ul>
</div>
</div>
<div class="section" id="quickies">
<h2>Quickies<a class="headerlink" href="#quickies" title="Permalink to this headline">¶</a></h2>
<dl class="docutils">
<dt>Make immutable, can&#8217;t delete this file:</dt>
<dd>chattr +i filename</dd>
<dt>Special file being a douche to rm? eg: $!filename, -filename, &#8216;filename-</dt>
<dd>ls -i    #list by inode
find . -inum 1234 -exec rm {} ;</dd>
</dl>
</div>
</div>


           </div>
          </div>
          <footer>
  
    <div class="rst-footer-buttons" role="navigation" aria-label="footer navigation">
      
        <a href="TODO-protocols.html" class="btn btn-neutral float-right" title="&lt;no title&gt;" accesskey="n">Next <span class="fa fa-arrow-circle-right"></span></a>
      
      
        <a href="TODO-encryption.html" class="btn btn-neutral" title="&lt;no title&gt;" accesskey="p"><span class="fa fa-arrow-circle-left"></span> Previous</a>
      
    </div>
  

  <hr/>

  <div role="contentinfo">
    <p>
        &copy; Copyright 2015, Pants.

    </p>
  </div>
  Built with <a href="http://sphinx-doc.org/">Sphinx</a> using a <a href="https://github.com/snide/sphinx_rtd_theme">theme</a> provided by <a href="https://readthedocs.org">Read the Docs</a>. 

</footer>

        </div>
      </div>

    </section>

  </div>
  


  

    <script type="text/javascript">
        var DOCUMENTATION_OPTIONS = {
            URL_ROOT:'./',
            VERSION:'1',
            COLLAPSE_INDEX:false,
            FILE_SUFFIX:'.html',
            HAS_SOURCE:  true
        };
    </script>
      <script type="text/javascript" src="_static/jquery.js"></script>
      <script type="text/javascript" src="_static/underscore.js"></script>
      <script type="text/javascript" src="_static/doctools.js"></script>

  

  
  
    <script type="text/javascript" src="_static/js/theme.js"></script>
  

  
  
  <script type="text/javascript">
      jQuery(function () {
          SphinxRtdTheme.StickyNav.enable();
      });
  </script>
   

</body>
</html>