Google Interview Flashcards
Why is inserting into arrays linear time complexity
Adding to the end of arrays is simple, but at the beginning, which is the worse-case scenario requires reassigning memory address to each piece of data.
Is searching an array linear or constant time
Linear. Requires starting at index = 0 and checking each index for that value
Is deletion linear or constant
Linear. Need to actually find value to delete, in the case index is not known, and removing that value and adjusting the other indexes in response.
What differentiates sets from arrays
Sets don’t allow duplicate values. Inserts are slower since a search has to be performed prior. Search, shift, and insert.
What are some of the advantages/disadvantages of ordered arrays
Search is more optimized, but slower insert times. Always have to conduct a search for inserts so less efficient.
What is a limitation to using binary search
Can only be performed on sorted arrays.
What are the advantages to binary search
Scales well. Number of steps to sort are greatly reduced.
What are some of the steps in performing a binary search
Always choose middle index and check value. Adjust bounds once you’ve established target is less than or greater than middle
What are we quantifying with BigO notation
Quantifying time and space complexity of algorithms for the worst case scenario.
What is the time complexity of bubble sort
Quadratic. Requires nested loops.
What are the major steps behind bubble sort.
Sort each element by comparing one element to the next.
Whats a strategy for finding duplicates in arrays using linear space and linear time?
Use a hash set to record numbers previously seen. Can also use a hash map to record count of a value, but that will require 2N time complexity.
What is the strategy behind selection sort
For each index, record the lowest value that was found in the array. Still produces quadratic time.
What is the strategy behind insertion sort
In best case, sorting algorithm that is linear but quadratic in worst case. Compare each additional element with the sorted sub list.
Review the answer here*
Suppose the first k elements are ordered from least to greatest, even though these elements are not necessarily in their final positions with respect to the entire array.
Move the (k+1)th element left (via repeated swaps) until the first (k+1) elements are ordered from least to greatest.
Repeat until done.
Strategy behind counting sort
Create a count array and have it correspond to the count of that element to its respective index position. So if 2 appears twice in an unsorted array then the count array will have a number 2 and the 2nd index position. This adds quite a bit of space complexity (2N).
What are the advantages of hash tables
In average case scenarios, it’s a constant time for all the major operations. The hashed key values corresponds to a specific memory cell location to store the value data.
What are stacks good for
Great for handling temporary data. Good for memory and linters. Constant time for all operations besides searching
What are some constraints for stacks
Data can only be inserted at the end (top). Data is only read from the top. And data can only be read from the top. (Last in first out)
What are queues used for
Good for asynchronous requests. Processes, printers.
Constraints for queues
Data is only added to the tail and removed/read from the head (FIFO).
Steps for quick sort
Done using recursion! First need to partition array. Set a pivot in a proper place. Treat arrays to left and right of pivot points as their own arrays. Recursively repeat the first two steps. When there is only a subarray with one element left, that is when the base case is reached.
n log(n) time complexity
How are linked lists stored in memory
Unlike arrays, they are not stored in contiguous cells, but spread out. So computer doesn’t need to find large amounts of contiguous cells. Each node references another node at a memory location.
How do linked lists perform for the major functions
Linear for reads and searches. Constant for inserts at beginnings unlike arrays, but linear for adding to the end. Same goes for delete.
What are linked lists best used for
If you’re deleting a lot of data it is superior.
What are the advantages to using a doubly linked lists
Contains an extra pointer, so don’t have to traverse the entire list when deleting to find the previous node, can just look at the previous pointer.
Advantages of a binary tree
Maintains order, has fast lookups deletions and insertions (log complexity). Good for hierarchal relationships (file directories).
When to use a binary tree
When there are lots of changes to your data. But need an evenly balanced tree otherwise it can become linear complexity.
What do graphs specialize in
Relationships. Conveys how data is connected. Weighted edges can signify relationships, distances, etc.
Which data structure does a breadth first search employ
Uses a queue that keeps track of which vertices to process next.
Advantage of BFS
Finds shortest path to a node, but it requires more memory than DFS
Advantage of DFS
Requires less memory, but doesn’t find the shortest direct path to a node
Ways to increase FE performance
Want to reduce JS load times since JS files are most expensive resources. Can try to compress/minify JS files to reduce size of code. Be mindful of the JS libraries you’re importing. Evaluate code for code complexity. Serve JS assets through a CDN.
Which web protocol does HTTP primarily use
TCP/IP port 80 or 443
What does 400 status code sequence indicate
Client errors
What are the content entity headers for
Provides info on the structure and encoding size of message body
What were the benefits from HTTP/1.1 parallel connections
Allows browser to make up to 6 parallel connections to download separate assets from a site. This reduces network load, CPU time, and congestion on network.
Whats required to enable Secure HTTP on a web server
Need a working digital certificate deployed on the server. These certs are issues by CA and contains info like issuer, algorithm used for cert, public key info. Clients will verify server certs in the SSL handshake process.
What are some of the private HTTP caches options
Confined to browser and is directed by cache-control http headers. Server can attach expiration dates to each document. No-cache header will allows for caching, but requires server validation on each request. “no-store” directs client not to store document. There are many other cache directives too
Public caching methods
Deploy caching proxies between client and server that will check if content exists locally, otherwise will fetch from server. Also, will perform freshness checks based on age headers.
Discuss the 3 part process of the TCP handshake.
- Client wants to establish a connection with server (SYN)
- Server responds with ACK (acknowledgement)
- Client sends back ACK.
Sequence numbers or sent back and forth to keep track of which packets have been sent over and if any were deleted or out of order.
Advantages/Disadvantages of UDP
Less latency, but some packets can be lost or received out of order
Steps of SSL/TLS handshake
- Client “hello” message with cryptographic info to server.
- Server “hello” message with cert and public key.
- Client verifies cert and sends key to server.
- Client sends credentials
- Server verifies credentials
- Client sends a finished signal.
- Server sends finished signal.
Encyprted communication can now take place. SSL relies on TCP to send these packets.
Features of HTTP/2
Multiplexing is a method in HTTP/2 by which multiple HTTP requests & responses can be sent/received asynchronously via a single TCP connection, thereby reducing latency
Multiplexing is the heart of HTTP/2 protocol.
Minimizes protocol overhead by efficient compression of HTTP header fields.
Support for request prioritization and server push. Client can provide preference to stream. Servers can push info that can be cached in anticipation of a request it thinks it’ll receive.
What is the medium for network communication for computers
Network interface cards. All computers will communicate via their NIC cards
What uniquely identifies a machine on a network
MAC address
What are the steps the browser takes when I enter something into the URL
Loads the resource
Parses the HTML returned
Creates DOM tree
Creates render tree - DOM and CSSOM trees are combined to form the render tree.
Layout of render tree: computing the exact position and size of each object.
Paints: takes in the final render tree and renders the pixels to the screen.
What are the components of a browser
UI Browser Engine: Moderator between UI and rendering engine Rendering engine: Mainly parses HTML Networking (DNS and HTTP calls) JS compiler Data persistence
What benefit did AJAX provide
Allows browser to be updated asynchronously by exchanging small amounts of data with server behind the scenes. No page reloads
What are iFrames used for
Embeds another document w/in an HTML document
Can insert content from another source, like ads
Can also employ AJAX to update its content
What are DNS servers used for
Serves to resolve the common names and IP Addresses
Who provides DNS servers
Typically ISPs. Primary and secondary servers are configured on your router when connecting to ISP using DHCP.
Which DNS server maintains master list of domain names and associated IPs
Root
How can malware affect DNS retrieval
It can change your DNS server settings to look up wrong hosts and take you to malicious sites.
What is OpenDNS
Software provided by CISCO that can redirect requests from bad sites to a blocked page.
Where are domains registered
With a registrar
What are some examples of top level and 2 level domains
Top level: .com, .org, .edu
Second level: google, yahoo, etc.
What is DNS cache poisoning
Diverts internet traffic from legitimate servers to fake ones. By altering entries in DNS records if other servers gather info from other DNS servers then they will be affected too
Strategies behind Great Firewall of China
DNS poisoning: Manipulates DNS lookups
Block access to IP
URL filtering
Deep packet inspection: Look into unencrypted packets
Can send reset packets to keep computers from being able to communicate
What are some vertical scaling strategies
Increase RAM, CPU power, L2 cache, SSD capacity. Any way to throw additional resources at the problem
Horizontal scaling
Increase server capacity by deploying more instances. Utilize load balancers to split traffic evenly amongst servers. LBs can attach which IP it directed traffic to in order to maintain continuous session.
Caching to increase performance
Can do it at the DB query level so if the same query appears the same data will be returned.
Data replication/redundancy
Have a master DB that you write to and updates additional slaves. Ensures that if a master DB goes down, data won’t be lost.
How availability zones lead to performance upgrade
Spread out your data centers and allows for geography based load balancing
CDNs
Distributed network of servers that ties to lower load times. Can be used to store HTML, JS, CSS, multimedia content. It’s not a web host however. It can lower load times, bandwith, and increases reliability.
Troubleshooting: What to do if server is down
Use ping tool to check status/response time of a server
Traceroute: trace and map the route data packets take when they travel from point A to B.
Network monitoring software that consistently checks the status of servers and can check the resources of these machines
Troubleshooting: slow site performance
DNS issues
Servers are running slow
Code performance (Can use New Relic to check on this)
No load balancers
Periodic traffic spikes
Failing to optimize bandwith usage: compressed multimedia files
Unoptimized dbs: no indexing, no sql caching
