More Interview Questions

Networking:

Explain what happens, step by step, after you type a URL into a browser.  Use as much details as possible.

1. Browser contacts the DNS server to find the IP address of the URL.
2. DNS server returns the IP address of the site.
3. Browser opens a TCP connection to the web server at port 80.
4. Browser fetches the html code of the page requested.
5. Browser renders the HTML in the display window.
6. Browser terminates the connection when window is closed.


Database:

1. What are different types of join?  Please explain how they differ and why certain types are better in certain conditions.

JOIN is used to combine the results of two tables.  To perform a join, each of the tables must have at least one field which will be used to find matching records from the other table.  The join type defines which records will go into the result set.


1. INNER JOIN:

Result set will contain only those data where the criteria match.

2. OUTER JOIN:

Outer join will always contain the results of INNER JOIN, however it can contain some records that have no matching record in other table.  OUTER JOINs are divided into following subtypes

2.1 LEFT OUTER JOIN or simply LEFT JOIN:

The result set will contain all the records from the left table.  If no matching records were found in the right table, then its fields will contain NULL values.

2.2 RIGHT OUTER JOIN or simply RIGHT JOIN:

Opposite of the LEFT JOIN.  It will contain all the records from the right table, and missing fields from the left table will contain NULL.

If we have two tables A and B, then we can say that statement A LEFT JOIN B is equivalent to statement B RIGHT JOIN A.

2.3 FULL OUTER JOIN

FULL OUTER JOIN combines the results of LEFT and RIGHT joins.  All records from both the tables will be part of the result set, whether matching records exists in other table or not.  If no matching record was found, then the corresponding result fields will have a NULL value.

C++

Compare and contrast Hash Table vs. STL map.

Hash Table:

In a hash table, a value is stored by applying hash function on a key.  Thus, values are not stored in a hash table in sorted order.  Additionally, since hash tables use the key to find the index that will store the value, an insert/lookup can be done in amortised O(1) time (assuming a few collisions in a hash table).  One must also handle potential collisions in a hash table.

STL Map

In STL Map, insertion of key/value pair is in sorted order of key.  It uses a treee to store values, which is why an O(log n) insert/lookup is required.  There is also no need to handle collisions.  An STL map works well for things like:

• find min element
• find max element
• print elements in a sorted order
• find the exact element or if the element is not found, find the next smallest number.

Implementation of a Hash Table

1. A good hash function is required (e.g. operation % prime number) to ensure that the hash values are uni-formally distributed.
2. A collision resolving method is also needed: chaining (good for dense table entries), probing (good for sparse table entries), etc.
3. Implement methods to dynamically increase or decrease the hash table size on a given criterion.  For example, when the [number of elements] by [table size] ratio is greater than the fixed threshold, increase the hash table size by creating a new hash table and transfer the entries from the old table to the new table by computing the index using new hash function.

What can be used instead of a hash table, if the number of inputs is small?

You can use an STL map.  Although this takes O(log n) time, since the number of inputs is small, this time is negligible.