Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Computer Science > Google Interview > Flashcards

Google Interview Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

Why is inserting into arrays linear time complexity

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Is searching an array linear or constant time

A

Linear. Requires starting at index = 0 and checking each index for that value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Is deletion linear or constant

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What differentiates sets from arrays

A

Sets don’t allow duplicate values. Inserts are slower since a search has to be performed prior. Search, shift, and insert.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are some of the advantages/disadvantages of ordered arrays

A

Search is more optimized, but slower insert times. Always have to conduct a search for inserts so less efficient.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a limitation to using binary search

A

Can only be performed on sorted arrays.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are the advantages to binary search

A

Scales well. Number of steps to sort are greatly reduced.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are some of the steps in performing a binary search

A

Always choose middle index and check value. Adjust bounds once you’ve established target is less than or greater than middle

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What are we quantifying with BigO notation

A

Quantifying time and space complexity of algorithms for the worst case scenario.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the time complexity of bubble sort

A

Quadratic. Requires nested loops.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What are the major steps behind bubble sort.

A

Sort each element by comparing one element to the next.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Whats a strategy for finding duplicates in arrays using linear space and linear time?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the strategy behind selection sort

A

For each index, record the lowest value that was found in the array. Still produces quadratic time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the strategy behind insertion sort

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Strategy behind counting sort

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What are the advantages of hash tables

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What are stacks good for

A

Great for handling temporary data. Good for memory and linters. Constant time for all operations besides searching

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What are some constraints for stacks

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are queues used for

A

Good for asynchronous requests. Processes, printers.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Constraints for queues

A

Data is only added to the tail and removed/read from the head (FIFO).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Steps for quick sort

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

How are linked lists stored in memory

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

How do linked lists perform for the major functions

A

Linear for reads and searches. Constant for inserts at beginnings unlike arrays, but linear for adding to the end. Same goes for delete.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What are linked lists best used for

A

If you’re deleting a lot of data it is superior.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What are the advantages to using a doubly linked lists

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Advantages of a binary tree

A

Maintains order, has fast lookups deletions and insertions (log complexity). Good for hierarchal relationships (file directories).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

When to use a binary tree

A

When there are lots of changes to your data. But need an evenly balanced tree otherwise it can become linear complexity.

28
Q

What do graphs specialize in

A

Relationships. Conveys how data is connected. Weighted edges can signify relationships, distances, etc.

29
Q

Which data structure does a breadth first search employ

A

Uses a queue that keeps track of which vertices to process next.

30
Q

Advantage of BFS

A

Finds shortest path to a node, but it requires more memory than DFS

31
Q

Advantage of DFS

A

Requires less memory, but doesn’t find the shortest direct path to a node

32
Q

Ways to increase FE performance

A

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.

33
Q

Which web protocol does HTTP primarily use

A

TCP/IP port 80 or 443

34
Q

What does 400 status code sequence indicate

A

Client errors

35
Q

What are the content entity headers for

A

Provides info on the structure and encoding size of message body

36
Q

What were the benefits from HTTP/1.1 parallel connections

A

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.

37
Q

Whats required to enable Secure HTTP on a web server

A

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.

38
Q

What are some of the private HTTP caches options

A

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

39
Q

Public caching methods

A

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.

40
Q

Discuss the 3 part process of the TCP handshake.

A
  1. Client wants to establish a connection with server (SYN)
  2. Server responds with ACK (acknowledgement)
  3. 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.
41
Q

Advantages/Disadvantages of UDP

A

Less latency, but some packets can be lost or received out of order

42
Q

Steps of SSL/TLS handshake

A
  1. Client “hello” message with cryptographic info to server.
  2. Server “hello” message with cert and public key.
  3. Client verifies cert and sends key to server.
  4. Client sends credentials
  5. Server verifies credentials
  6. Client sends a finished signal.
  7. Server sends finished signal.
    Encyprted communication can now take place. SSL relies on TCP to send these packets.
43
Q

Features of HTTP/2

A

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.

44
Q

What is the medium for network communication for computers

A

Network interface cards. All computers will communicate via their NIC cards

45
Q

What uniquely identifies a machine on a network

A

MAC address

46
Q

What are the steps the browser takes when I enter something into the URL

A

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.

47
Q

What are the components of a browser

A 
UI
Browser Engine: Moderator between UI and rendering engine 
Rendering engine: Mainly parses HTML
Networking (DNS and HTTP calls) 
JS compiler 
Data persistence
48
Q

What benefit did AJAX provide

A

Allows browser to be updated asynchronously by exchanging small amounts of data with server behind the scenes. No page reloads

49
Q

What are iFrames used for

A

Embeds another document w/in an HTML document
Can insert content from another source, like ads
Can also employ AJAX to update its content

50
Q

What are DNS servers used for

A

Serves to resolve the common names and IP Addresses

51
Q

Who provides DNS servers

A

Typically ISPs. Primary and secondary servers are configured on your router when connecting to ISP using DHCP.

52
Q

Which DNS server maintains master list of domain names and associated IPs

A

Root

53
Q

How can malware affect DNS retrieval

A

It can change your DNS server settings to look up wrong hosts and take you to malicious sites.

54
Q

What is OpenDNS

A

Software provided by CISCO that can redirect requests from bad sites to a blocked page.

55
Q

Where are domains registered

A

With a registrar

56
Q

What are some examples of top level and 2 level domains

A

Top level: .com, .org, .edu

Second level: google, yahoo, etc.

57
Q

What is DNS cache poisoning

A

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

58
Q

Strategies behind Great Firewall of China

A

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

59
Q

What are some vertical scaling strategies

A

Increase RAM, CPU power, L2 cache, SSD capacity. Any way to throw additional resources at the problem

60
Q

Horizontal scaling

A

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.

61
Q

Caching to increase performance

A

Can do it at the DB query level so if the same query appears the same data will be returned.

62
Q

Data replication/redundancy

A

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.

63
Q

How availability zones lead to performance upgrade

A

Spread out your data centers and allows for geography based load balancing

64
Q

CDNs

A

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.

65
Q

Troubleshooting: What to do if server is down

A

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

66
Q

Troubleshooting: slow site performance

A

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

Computer Science (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions