MakerSquare Masters Prerequisite Self-Assessment

Prior to entering the MakerSquare Masters beta program a student should be able to implement a linked list, tree, graph, stack, queue, array, basic sorting algorithms and a hash table in JavaScript. If a student can answer the following questions then they are ready for this program. Once you are ready, continue your application by scheduling an interview using the link below.

Schedule an Interview

Linked List

• Implement a linked list with the methods addElement() and findElement(value). The addElement() method adds a node to the tail of a linked list. The findElement(value) checks to see if a node with some value is in the linked list.
• Create a method to find the length of a singly linked list. The length of a singly linked list is simply how many nodes it has.
• Create a method to find the length of a circular linked list.

Trees

• What is the worst-case time complexity of depth-first tree search?
• What’s the difference between breadth first traversal (i.e, pre-order) and depth first traversal (i.e., level-order)?
• Implement a breadth-first filter on a tree class. This method should filter out elements in a tree in breadth-first order.

Graph

• Can you devise a method on a graph that removes a node?
• Implement a graph with the methods addNode() and connectNodes().
• Implement a graph using an adjacency list and another using an adjacency matrix.

Stack

• Implement a method that pushes onto a stack.
• Implement a method that pops off of a stack.
• Devise a method on a stack called getSize() that computes how many elements are currently in the stack.

Array

• What is the time complexity for retrieving the value of the nth indexed element in an array?
• How are the elements in an array typically stored in memory?
• Suppose you are given a multidimensional array of the form: var multidimensionalArray = [ [1, 2, 3], [4, 5, 6], [6, 7, 8] ]. How would you access the element with the value 5?
• What is the average-case time complexity of finding the maximum value in an array of integers?

Queue

• Implement a queue.
• Write a method to enqueue to a queue. Write a method that dequeues.
• Use a queue to create a breadth-first selection method on a tree. This method would traverse a tree in breadth-first order, filtering out values as it traversed.

Hash Table

• What is the time complexity for looking up a value in a hash table?
• What role does a hash function play in accessing and inserting elements in a hash table?
• Solve the Two Sum problem using a hash table. The ‘Two Sum’ problem is as follows: given an array of integers, return the largest sum of any two numbers in the input array.
• What is the main characteristic of a good hash function? Hint: This characteristic will prevent needless collisions in a hash table.

Sorting

• Implement bubble sort, insertion sort, merge sort and quick sort.
• What are the worst-case time complexities of these algorithms?

Fundamental JavaScript

• When is a new local scope created in JavaScript?
• Do you know the difference between the four major object instantiation patterns in JavaScript? They are the functional, functional shared, prototypal and pseudoclassical instantiation patterns?
• How and when does one use the keyword this?
• Know how to use apply, call and bind.

Resources for Review

If you need to brush up on any of these topics then we recommend the following preparatory resources:

1. This WikiBook covers all of the data structures mentioned above.
2. Introduction to Algorithms by Leiserson, Stein, Rivest and Cormen (3rd Edition) is the canonical text on algorithms and data structures.
   • This text covers:
     • Linked Lists on pages 236-240
     • Graphs in Chapter 22
     • Stacks on pages 232-234
     • Queues on pages 234-235
     • Hash Tables on pages 256-259 & 262-264
3. For an accessible introduction to linked lists see this blog post.
4. A introduction to graphs can be found here.
5. For a highly intuitive discussion of sorting algorithms this site is particularly useful.