Software Flashcards Preview

Job hunt > Software > Flashcards

Flashcards in Software Deck (77):

What is Big O notation used for?

Used to classify algorithms according to how their running time or space requirements grow as the input size grows.


What is the Big O runtime when the count of a search space halves each time?

O(log n)


What is the Big O runtime of sorting a string of length n?

O(n log n)


What is the Big O runtime of Radix sort?

O(nw) where w is the word length of the buckets


What is the algorithm for Radix sort?

Sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value


What is the Big O runtime of Merge sort?

O(n log n)


What is the algorithm for Merge sort?

  • First divide the list into n elements
  • Then compare each element with the adjacent list to sort and merge the two adjacent lists
  • Finally all the elements are sorted and merged


What is the Big O runtime of Heap sort?

O(n log n)


What is the algorithm for Heap sort?

  • Divides its input into a sorted and an unsorted region
  • Iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region
  • A heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C.[1] The node at the "top" of the heap (with no parents) is called the root node.
  • A heap is not a sorted structure and can be regarded as partially ordered.


What is the Big O runtime of quick sort?

O(n log n) through O(n^2)


What is the algorithm for quick sort?

  1. Pick an element, called a pivot, from the array.
  2. Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.


What is the Big O runtime of bubble sort?



What is the algorithm for bubble sort?

Repeatedly step through the list to be sorted, compare each pair of adjacent items and swap them if they are in the wrong order


What is a Binary Search Tree?

Node descendants ordering: all left <= node < all right descendants


What is an efficient way of looking up strings, step by step?

  • Tries (prefix trees)
  • n-ary tree where characters are stored at each node
  • Each path may represent a word
  • * nodes indicate complete words


What are some methods for searching a graph?

BFS, DFS, bidirectional search


What are some structures for defining a graph?

  • Graph - collection of nodes and edges between some of them, optionally directed
  • Adjacency list - Graph with all nodes, nodes with all adjacent nodes
  • Adjacency matrices - matrix of booleans for: are these two nodes connected?


What is a shortcut to calculate the sum of 1 to N?

(N * (N + 1) ) / 2


What is the formula for the unique permutations of N?



What is the formula for the unique permutations of K from N?



What is the formula for the order-ignorant combinations of K from N?



What is Dijkstra’s algorithm?

  • Algorithm for finding the optimal path on a weighted graph
  • BFS
  • Cumulative score, stop if node has been visited with better score
  • Always move visitor with lowest score


How would you calculate the Nth Fibonacci number?

  • Recursively, with memoization
  • Or for loop, tracking last two numbers


What does a recursive binary search look like?

arr, start, end => yes, or re-target


Given an array with integers 0 to N except one, find the missing number

Sum the list, compare to: (N * (N + 1) )/2 the difference is the number


Given an array with integers 0 to N except two, find the missing numbers

Getting the sum and sum of squares, then use quadratic equation


Continuous median: find and maintain the median value as random numbers are passed to a method

Max heap, min heap, current median


What are the SOLID design principles?

  • SRP – Single Responsibility Principle
  • OCP – Open/Closed Principle - open for extension, but closed for modification
  • LSP – Liskov Substitution Principle - replaceable with instances of their subtypes
  • ISP – Interface Segregation Principle - many client-specific interfaces are better than one general-purpose interface
  • DIP – Dependency Inversion Principle - depend upon abstractions, [not] concretions


What are the two forms of the quadratic equation?

  • ax^2 + bx + c = 0
  • x = (-b +/- sqrt(b^2 - 4ac)) / 2a


What are the three variable forms in ES6+?

  • var - function-scope
  • let - block-scope, mutable
  • const - block-scope, immutable


What are the differences between an ES6 inline function and an arrow function?

Arrow functions re-use the contextual this at time of definition where functions use the execution context for this.


What are the useful bits of the ES6-native Promise API?

  • new Promise((resolve, reject) => {})
  • .then, .catch, .finally
  • Promise.all, Promise.race, Promise.resolve


What does the top-level React rendering method look like?

ReactDOM.render(, mountNode);


What are the differences between React component props and state?

  • Props are read-only within the component
  • State can be changed within the component
  • State should only be changed through setState()


What does a functional React component look like?

function Blah (props) { return (

{ }
); }


What does a class-based React component look like?

class Blah extends React.Component {

 constructor(props) {


  this.state = { count: 0 };


 inc () {

  this.setState((prevState, props) => ({ count: prevState.count + 1 }));


 render() { return ({ }); }




What does the React component lifecycle look like?

  • Mounting
    • constructor
    • componentWillMount
    • render
    • componentDidMount - after the component output has been rendered to the DOM the first time
  • Updating
    • componentWillReceiveProps - If you need to update the state in response to prop changes (for example, to reset it), you may compare this.props and nextProps and perform state transitions using this.setState() in this method.
    • shouldComponentUpdate
    • componentWillUpdate
    • render
    • componentDidUpdate
  • Unmounting
    • componentWillUnmount - removed from the DOM


How do you configure event handlers in React components?

  • In ctor: this.handleClick = this.handleClick.bind(this);
  • You cannot return false to prevent default behavior in React. You must call preventDefault explicitly
  • function handleClick(e) { e.preventDefault(); }


How are keys used in React?

  • Keys help React identify which items have changed, are added, or are removed.
  • Keys should be given to the elements inside the array to give the elements a stable identity


How do you make a form refer to React as the single source of truth?

  • controlled components!
  • handle onChange/onSubmit events for input, select, and texture then update React state, re-render via React and value/checked prop
  • use name prop and to manage multiple inputs with one handler


How do you render the contents of a React component?



What is a React higher-order component?

  • HOCs are for reusing component logic
  • A function that takes a component and returns a new component
  • Convention: Pass Unrelated Props Through to the Wrapped Component

const EnhancedComponent = higherOrderComponent(WrappedComponent);

function withSubscription(WrappedComponent, selectData) {

 // ...and returns another component...

 return class extends React.Component {


  render() {

   // ... and renders the wrapped component with the fresh data!      

  // Notice that we pass through any additional props

 return ;


What is a React.PureComponent?

  • An enforcibly simple component, only renders, may be just a function
  • React.PureComponent implements shouldComponentUpdate with a shallow prop and state comparison


Describe the Flux pattern

  • Unidirectional data flow
  • Dispatcher, Store, Action
  • Data in a store must only be mutated by responding to an action
  • Store emits an event on data changing
  • Actions have types, are commands


What are the components of a Flux standard action?

  • type
  • payload
  • error
  • meta


Describe a Redux reducer

A pure function that takes the previous state and an action, and returns the next state WITHOUT CHANGING THE PREVIOUS STATE.


What does the interaction between action creators and the store look like?



What do React/Redux container components do that presentational components do not?

subscribe to Redux state, dispatch actions

const VisibleTodoList = connect(mapStateToProps, mapDispatchToProps)(TodoList)


What are some options for handling async Redux actions?

  • Thunks w/middleware, action creator returning a function instead of an object
    • export function fetchPosts(subreddit) {
      • return function (dispatch) {
        • dispatch(requestPosts(subreddit))
  • Promises, Sagas
  • Actions for starting, success, and failure of requests


What is React-Reselect good for?

  • Compute derived data, allowing Redux to store the minimal possible state.
  • Not recomputed unless one of its arguments changes.
  • Composable. They can be used as input to other selectors.


What are JWTs?

JSON Web Tokens define a compact and self-contained way for securely transmitting information between parties as a JSON object. This information can be verified and trusted because it is digitally signed. JWTs can be signed using a secret (with the HMAC algorithm) or a public/private key pair using RSA.

  • Signed tokens can verify the integrity of the claims contained within it, while encrypted tokens hide those claims from other parties.
  • Three parts: Header.Payload.Signature
    • xxxxx.yyyyy.zzzzz


What are ETags?

  • Entity tag
  • web cache validation
  • An ETag is an opaque identifier assigned by a web server to a specific version of a resource found at a URL
  • ETag in HTTP response header
  • If it is determined that the URL has expired (is stale), then the client will contact the server and send its previously saved copy of the ETag along with the request in a "If-None-Match” field
  • If the ETag values match, meaning that the resource has not changed, then the server may send back a very short response with a HTTP 304 Not Modified status


What is "credential stuffing?"

Re-using exposed credentials in an automated attack on other systems


What are some ways to secure a REST service?

  • Require SSL/TLS
  • Enforce access control, request limits via API keys and/or JWTs
  • Validate request input and content types
  • Prevent error messages from exposing sensitive information
  • Explicitly implement CORS
  • Do not send sensitive information in the URL


How can you protect against CSRF attacks?

  1. Check standard headers to verify the request is same origin

    1. Determining the origin the request is coming from (source origin - Origin, Referer, and Host)
    2. Determining the origin the request is going to (target origin)
  2. AND Check CSRF token

    1. Unique per user session

    2. Large random value

    3. Generated by a cryptographically secure random number generator

    4. It is then the responsibility of the server application to verify the existence and correctness of this token


What are the rules of preventing XSS?

  1. HTML escape before inserting untrusted data into HTML element content
  2. Attribute escape before inserting untrusted data into HTML common attributes
    1. Common like width, name, value, etc. This should not be used for complex attributes like href, src, style, or any of the event handlers like onmouseover
    2. &#xHH; format
  3. JavaScript escape before inserting untrusted data into JavaScript data values
    1. The only safe place to put untrusted data into this code is inside a quoted "data value."
  4. CSS escape and strictly validate before inserting untrusted data into HTML style property values
    1. You should stay away from putting untrusted data into complex properties like url, behavior, and custom
    2. You will have to ensure that URLs only start with "http" not "javascript" and that properties never start with "expression".
  5. URL escape before inserting untrusted data into HTML URL parameter values
  6. Sanitize HTML markup with a library designed for the job
  7. Prevent DOM-based XSS by using element.textContent or innerText instead of innerHtml


What's the deal with Content Security Policies? (CSP)

CSP makes it possible for server administrators to reduce or eliminate the vectors by which XSS can occur by specifying the domains that the browser should consider to be valid sources of executable scripts.

Can restrict by types of content: images, scripts, media, objects, style sheets


What is a cryptographic salt and why is it used?

  • A salt is fixed-length cryptographically-strong random value
  • Generate a unique salt upon creation of each stored credential (not just per user or system wide)
  • Scheme security does not depend on hiding, splitting, or otherwise obscuring the salt
  • Salts serve two purposes:
    • 1) prevent the protected form from revealing two identical credentials
    • 2) augment entropy fed to protecting function without relying on credential complexity. The second aims to make pre-computed lookup attacks on an individual credential and time-based attacks on a population intractable.


What are the main ways to defend against SQL injection attacks?

  • Use of Prepared Statements (with Parameterized Queries)

  • Use of Stored Procedures

  • White List Input Validation

  • Escaping All User Supplied Input

  • Enforcing Least Privilege


How does OpenID Connect differ from OAuth?

  • OpenID Connect is an authentication layer built on top of OAuth 2 (authorization)
    • Security claims
    • User identifier


What is the single most important fact about encodings?

It does not make sense to have a string without knowing what encoding it uses


How many bytes can a Unicode character be encoded as?

Between 1 (UTF-7, 8) and 6 bytes


How do you find the greatest common divisor of two numbers using Euclid's algorithm?

  • Larger number = q * smaller number + remainder
  • smaller number = q’ * remainder + remainder’
  • … until remainder = 0, leaving qx as the GCD


How do you detect browser language and indicate your content is in a specific language?

  • Browser sends Accept-Language header


What are the 5 basic ways of positioning an element in CSS?

  • static - The default position; the element will flow into the page as it normally would. The top, right, bottom, left and z-index properties do not apply.
  • relative - The element's position is adjusted relative to itself, without changing layout (and thus leaving a gap for the element where it would have been had it not been positioned).
  • absolute - The element is removed from the flow of the page and positioned at a specified position relative to its closest positioned ancestor if any, or otherwise relative to the initial containing block. Absolutely positioned boxes can have margins, and they do not collapse with any other margins. These elements do not affect the position of other elements.
  • fixed - The element is removed from the flow of the page and positioned at a specified position relative to the viewport and doesn't move when scrolled.
  • sticky - Sticky positioning is a hybrid of relative and fixed positioning. The element is treated as relativepositioned until it crosses a specified threshold, at which point it is treated as fixed positioned.


What are the characteristics of an "element" in BEM?

  • A composite part of a block that can’t be used separately from it.

  • Suffix of “__element-name”

  • An element is always part of a block, not another element (for naming, not document structure)


What are the characteristics of a "block" in BEM?

Semantically meaningful, functionally independent page component, always a CSS class: “block-name"


What are the characteristics of a "modifier" in BEM?

  • An entity that defines the appearance, state, or behavior of the block or element.

  • Suffix of “_modifier-name”

  • Modifiers can’t be used alone - include Block or Element class separately

  • Types of modifiers:

    • Boolean - “_disabled"

    • Key-value - “_theme_islands” | “_size_m"


Describe the elements of the CAP theorem (Brewer's theorem).

  • Consistency - every read receives the most recent write or an error
  • Availability - Every request receives a (non-error) response – without guarantee that it contains the most recent write
  • Partition tolerance - The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes


Describe the uses and characteristics of a Bloom filter.

  • Space-efficient system that allows you to test if an element is in a set
  • "Possibly in set" or "definitely not in set"
  • The more elements that are added to the set, the larger the probability of false positives

  • Uses sets of hashes over parts of the input to flip different sets of bits in an array - if at least one bit has not previously been flipped in the array, the tested element is not in the set


When does it make sense to use CQRS?

  • Command Query Responsibility Segregation
  • Command that performs an action, or a Query that returns data to the caller, but not both
  • Use a different model to update information than the model you use to read information
  • Separate the load from reads and writes allowing you to scale each independently. If your application sees a big disparity between reads and writes this is very handy



What is an ACID database?

  • Atomicity - each transaction be "all or nothing"

  • Consistency - any transaction will bring the database from one valid state to another

  • Isolation - the concurrent execution of transactions results in a system state that would be obtained if transactions were executed sequentially

  • Durability - once a transaction has been committed, it will remain so, even in the event of power loss, crashes, or errors


How do you prevent cookie hijacking?

  • SSL/TLS for all authenticated requests

  • Long random number or string as the session key

  • Regenerating the session id after a successful login


What does it mean to have a type be covariant? What type of types can be covariant?

  • Covariant - the subtyping relation of the simple types are preserved for the complex types (IEnumerable of Cat is a subtype of IEnumerable of Animal, OUT)

  • Read-only data types (sources)


What does it mean to have a type be contravariant? What type of types can be contravariant?

  • Contravariant - subtyping relation of the simple types is reversed for the complex types (Action of Animal is a subtype of Action of Cat, IN)

  • Write-only data types (sinks)


Describe how to use a JavaScript generator.

  • Useful in for..of loops
  • function* gen() { var optionalBackflowValue = yield 1; }
  • yield* val; to delegate from one generator to another
  • const generator = gen();
    • { value, done }
  • generator.return()
    •  If no argument is provided, the return object is the same as if .next(). If an argument is provided, it will be set to the value of the value property of the returned object.
  • generator.throw(exception)


How is a salt applied to a hashed value?

  • Append or prepend a long, cryptographically random string, called a salt, to the value before hashing
  • Salt stored separately and can be cleartext