DataStructures-and-Algorithms

Data Structures

Code Challenges are taken out of order in CodeFellows. First five have no code, and Implementation of Data Structures don’t aren’t required a whiteboard.

Each Challenge will have full description. The Data Structure order is Arrays, Linked List, Hashmap, Binary tree, Binary Search Tree, K-ary tree, Stacks, Queues.

Table of Contents

---

</tr>

challenge 1	challenge 2	challenge 3	challenge 4	challenge 5	challenge 6	challenge 7	challenge 8
Interview 9	challenge 10	challenge 11	challenge 12	challenge 13	challenge 14	challenge 15	challenge 16
challenge 17	challenge 18	challenge 19	challenge 26	challenge 27	challenge 28	Interview 29a	Interview 29b
challenge 30	challenge 31	challenge 32	challenge 33	challenge 34	challenge 35	challenge 36	challenge 37
challenge 39	challenge 41	challenge 44	challenge 42	challenge 43

Code Challenges

Challenge 01

Reverse an Array

• Write a function called reverseArray which takes an array as an argument. Without utilizing any of the built-in methods available to your language, return an array with elements in reversed order.
• Input: An Integer Array
• Output: Same Reversed Integer Array

Whiteboard Process

• reverse-array Whiteboarding PDF

Approach & Efficiency

• Time: O(n) because the worst case is that iteration will be through full array and Space: O(1) no extra memory is added per each to auxillary space.
• Full Code Description Markdown
• Location: ReverseArray
• Test : ReverseArrayTest

Challenge 02

Insert and Shift Array

• Write a function called insertShiftArray which takes in an array and a value to be added. Without utilizing any of the built-in methods available to your language, return an array with the new value added at the middle index.
• Input: An Integer Array
• Output: Same Integer Array
• Full Code Description Markdown

  Whiteboard Process

  insert-Shift-Array Whiteboarding

Approach & Efficiency

• Time usage is O(N) because the time taken to complete insertion of a element with existing elements involves an iteration to the end of array which is length of array + 1. Thus, O(len + 1) or O(N+1) and simplified to O(N) over time.

• Space is O(N) because I create a new array to add memory of N + 1. and add more memory.

• Location: InsertShiftArray
• Test : InsertShiftArrayTest()
• Method: insertShiftArray(ArrayList x, int toAdd)

Challenge 03

Binary Search

• this code searches for an element in array and returns the element index that matches the key. By searching using binary search, we never need to creat new memory and decreases search operations per each check.
• input: Integer array and Integer to find
• output an Integer
• Full Code Description Markdown

  Whiteboard Process

  Binary-Search Whiteboarding

Approach & Efficiency

• Space Complexity is O(1) because no new space is created due to searching features.
• Time complexity is O(log2(N)). this is because the bisection method has a pattern that searches left half or right half. To further explain, suppose N is size of array and each search operation depends on the full size of array in worst case (traverse all elements in array - 1 from i < arr.length which results in N - 1 operations). Then, traversing half of the array => N/2/2/2/2 again and again results to logorithmic properties in where time spent depends operations done to find target.
• A mathematical explaination is better explained with an example. if N (length of array) is 16 then searching until the end will be 4 - 1 times by going to half, of half, of half, of array. thus exponent represents 2^x where x represents steps taken and 2 for cutting operation in half for the sequence {2, 4, 8, 16, …, 2^x}. 2^x = size of array, but for time complexity we want to know how many operations it took to reach target. thus using inverse of exponenets (logs) result in properties log2 (size of array) = x (x is operations made). which simplifies to look log(N/2 - 1) = operations taken to find target. Finally, this looks can now be represented in O(log2(N)) by simplifying after change overtime.
• Location: InsertShiftArray
• Test : InsertShiftArrayTest()
• Method: binary-search(int []x, int target);

Challenge 04

• The code adds the sum of each row in the matrix. Then the sum is returned into a new array.
• Full Description First
• Ask the candidate to write a function to accepts an integer, and returns the nth number in the Fibonacci sequence.
• Full Description Second

  Whiteboard Process

• Sum Matrix Whiteboarding
• Fibonacci Whiteboarding
• Sum Matrix Source Code
• Sum Matrix Test
• Fibonacci Sequence Code
• Fibonacci Sequence Test

Approach & Efficiency

• add total sum in matrix :
  • the Time complexity is O(n) and space is O(1);
• fibononacci sequence :
  • Time Complexity is O(N) and Space Complexity O(1)

Challenge 05

• Create a linked list and implement Insert, includes, toString
• Full Description

  Whiteboard Process

  No white board for creating a linked list. Feature Task 1: Node class that has data type and pointer to itself. Feature Task 2: Implement Linked list that includes, inserts, and modify a toString method.

Approach & Efficiency

this insert adds to the beginning of the list: Time O(1), Space O(1).

Includes method checks the list : Time O(N), Space O(1)

• Location: linkedlist()
• Test : linklistTest()

API

• no api was used for this.

Challenge 6

Singly Linked List - appends, insertBefore, insertAfter

• Created a singly linked list that appends, insertBefore, insertAfter.
• Full Description

Approach & Efficiency

• appends adds to the last. I use tail pointer so time here is O(1),
• insert before time complexity is O(N).
• insert after is O(N)
• space is O(N) for all methods to create a temp node with new data.

API

• no api was used for this.

• code challenge 6 location
• code challenge 6 test

Challenge 7

Challenge Summary

• Linked list return the value of the node length - k in linkedlist.

Whiteboard Process

No white board needed for process on today’s lab. it seemed straight forward. especially iteratively.

Approach & Efficiency

I solved it just subtracting the length - k and the time complexity is O(n) space O(1)

Full Description

Solution

running libraryTest will run tests. or create a static main and call the function in main.

• code location
• code challenge test

Challenge Summary - 08

• merges unsorted linked lists and uses iteration.
• Full Description

  Whiteboard Process

Approach & Efficiency

• O(n + m) for time complexity since we are iterating two arrays and space complexity of O(1)

  Solution

  

• code location
• code challenge test

Challenge 09

Challenge Summary

• 9a reverse a linked list and return the reversed list
• 9b check if linked list is a palindrome
• Full Description 9a
• Full Description 9b

  Whiteboard Process

• Whiteboard 09a reverse list
• Whiteboard 09a reverse list

  Approach & Efficiency

• 9a time O(N) space O(1)
• 9b time O(N) and space O(1)

Challenge 10

Stacks and Queues - 10

• adds a stack using lifo to pop and push, and a queue using enqueue and dequeue method
• Full Description
• code challenge 10 - stack
• code challenge 10 - queue

Approach & Efficiency

• Time is O(n^2) since we use two loops for each data structure implementing a pop, push, enqueue, dequeue.
• Space is O(1) because we use memory to create nodes

  API

• no api used

Challenge Summary - 11

• Pseudo Queue using Stacks to implement
• Full Description

  WhiteBoard Process

  -

  Approach & Efficiency

• O(2N^2) using iteration and using pre implemented code, traversing to the end of the stack to remove an item takes N time. However, adding on T1 will have to use two loops
• the first loop will call on another function using pop() and Push() to t2, then inversely add popped items back to t1 from t2.
• time is still O(N) by creation of new memory
• Code Challenge 11 - PseudoMerge

Challenge 12

Challenge Summary - 12

• Pseudo Queue using Stacks to implement the Animal Class
• Code Challenge 12
• Full Description

  WhiteBoard Process

  

  Approach & Efficiency

• O(2N^2) using iteration and using pre implemented code, traversing to the end of the stack to remove an item takes N time. However, adding on T1 will have to use two loops
• the first loop will call on another function using pop() and Push() to t2, then inversely add popped items back to t1 from t2.
• time is still O(N) by creation of new memory
• Code Challenge 12 - Animal
• Code Challenge 12 - AnimalShelter

Code Challenge 13

Challenge Summary

• Write a function called validate brackets
• Full Description
• Arguments: string
• Return: boolean representing whether or not the brackets in the string are balanced

  WhiteBoard Process

  -

  Approach & Efficiency

• I created three different algorithms. a bit more effiecient than the other.
• the final Validate is O(N) and Space O(N)
• using a search algorithm is always traversing to N (length N is dependant on our String passed in thus {1+2+…+N-1})

• since I use only iteration, then O(N) because loop breaks out if N < N-1. thus, O(N) + cO(1) .

• Code Challenge 13(1) - ValidateParenthesis
• Code Challenge 13(2) - ValidateParenthesis
• Code Challenge 13(3) - ValidateParenthesis

Code Challenge 14

Challenge Summary

• Find the max value in node of the Queue
• Full Description

  WhiteBoard Process

  -

  Approach & Efficiency

• data structure only uses one iteration implemented by another function O(N). However, the wrapper function to push will
• do O(1) operations
• therefore, it is O(N) and recreating new nodes is O(N) space

Code Challenge 15

Challenge Summary - 15

• Create a Node and BinaryTree and Binary Search tree that adds and displays preorder, post order, and inorder.
• Full Description

  WhiteBoard Process

  -

  Approach & Efficiency

• data structure only uses one recursive call which O(N). However, some implelmentation using finding and searching takes two recursive calls.

• therefor, it is O(2N) which is O(N)

• Code Challenge 15 - Tnode
• Code Challenge 15 - BinaryTree
• Code Challenge 15 - BinarySearchTree

Code Challenge 16

Challenge Summary

• Find the maximum value stored in the tree. You can assume that the values stored in the Binary Tree will be numeric
• Full Description

  WhiteBoard Process

  

Approach & Efficiency

• data structure only uses one iteration implemented by another function O(N). However, the wrapper function to push will
• do O(1) operations
• therefore, it is O(N) and recreating new nodes is O(N) space
• Code Challenge 16 - maxValue()

Code Challenge 17

Challenge Summary

• add to a list by using BreadthFist traversal
• Full Description

  WhiteBoard Process

  

• Full Description

Approach & Efficiency

• data structure only uses one iteration implemented by another function by dequeue we getO(N).
• The traversal by going through the tree to place on the queue is also O(n) since we go throught the entire tree.
• therefore, it time O(N^2) and recreating new nodes is O(N) space
• Code Challenge 17 - BreadFirst()

Contributors

• Jason Wilson

Code Challenge 18

Challenge Summary

• Write a function called fizz buzz tree
• Full Description
• Arguments: k-ary tree
• Return: new k-ary tree

  WhiteBoard Process

  

Approach & Efficiency

• data structure only uses one iteration implemented by another function by dequeue we getO(N).
• The traversal by going through the tree to place on the queue is also O(n) since we go throught the entire tree.
• therefore, it time O(N^2) and recreating new nodes is O(N) space
• Code Challenge 18 - FizzBuzz()
• Code Challenge 18 - KaryTree
• Code Challenge 18 - KaryTree

  Contributors

• Jason Wilson

Code Challenge 19

Challenge Summary

• Find the sum of all the odd numbers in a binary search tree.
• Full Description
• Any of the traversals (depth or breadth) will work for this

  WhiteBoard Process

  

Approach & Efficiency

• data structure only uses recursion implemented to get through the worst all children. we get O(N).
• no new nodes are created.
• therefore, it time O(N) and recreating new nodes is O(1) space
• Code Challenge 19 - SumAll
• Code Challenge 19 - SumAllTest

  Contributors

Code Challenge 26 - Insertion Sort

Challenge Summary

• sort an unsorted array using insertion sort algorithm
• Full Description

  WhiteBoard Process

• 
• Coded Algorthm
• Test Algorthm

Approach & Efficiency

• Insertion sort asserts everything before the key element is sorted. then traverses the sorted portion and inserts at element where key is > then before element and > then after element replacing the key with the data at replaced element location.
• this process happens over and over.
• thus, this process uses two loops to iterate. one for iterating N elements and the other to travers sorted portion of array.
• next we have constant time variables and nothing new is created.
• thus, the time complexity Big O is O(N^2) and worst space complexity is O(1)
• 

  Contributors

Code Challenge 27 - Merge Sort

Challenge Summary

• sort an unsorted array using merge sort algorithm
• Full Description

  WhiteBoard Process

• 
• Coded Algorthm
• Test Algorthm

Approach & Efficiency

• the process of this code is to create new arrays left and right. then after reaching n amount of arrays
• this process happens over and over.
• then after all is split, into an individual array, the sorting process happens. this takes length of n times for worst case.
• thus, this process uses N amount of space and we also have N time taken as the recusive call unwinds to compare elements.
• thus, the time complexity Big O is O(N*logn) and worst space complexity is O(N)

  Contributors

Code Challenge 28 - Quick Sort

Challenge Summary

• sort an unsorted array using Quick sort algorithm
• Full Description

  WhiteBoard Process

• 

  Approach & Efficiency

  Time O(N^2) Space O(1)

Code Challenge 29

Challenge Summary

• sort an unsorted array using merge sort algorithm
• Full Description 29a
• sort an unsorted array using quicksort algorithm
• Full Description 29b

  WhiteBoard Process

• 
• 
• Coded Algorthm 29a
• Test Algorthm 29a

  Approach & Efficiency

  Contributors

Challenge Challenge 30 - Hashtables Abstract Data Type

Challenge Summary

• Full Description
• implementing the class Hashtable

  Features:

• set
  • Arguments: key, value
  • Returns: nothing
  • This method should hash the key, and set the key and value pair in the table, handling collisions as needed.
  • Should a given key already exist, replace its value from the value argument given to this method.
• get
  • Arguments: key
  • Returns: Value associated with that key in the table
  • contains
  • Arguments: key
  • Returns: Boolean, indicating if the key exists in the table already.
• keys
  • Returns: Collection of keys
• hash
  • Arguments: key
  • Returns: Index in the collection for that key

    Challenge

• this code focuses on the data structure HashTable from scratch. it is useful to know
• how this code is implemented.

Whiteboarding

Coded Algorthm Test Algorthm

Approach & Efficiency

• one to many
• using linked list seems to be the best case for a generic case. to store in bucket.
  • Simple Unifomity - each key is equally liekly to be hashed to any slot of the table. independant of where other keys hasing.
  • analysis load factor λ is the n keys / slots in bucket and λ < 1.
• Worst case time complexity is O(N) because if all map to a single element in bucket, then searching is O(N)
  • however, adding will be added to beginning or end of list which is O(1)
• Worst case space complexity is only O(N) when adding a new value into linked list.
• universal hashing for hasing(key) - hashing(key) = a*k+b mod prime mod m where prime > Universe
  • this is best because worst case key1 != key2 is that will collide probability is 1/N which is good.

API

• I have a wrapper with no arguments that gets called for method that does things for data structure
• a toString is overriden to display contents.
• uses Hashing method to create a value with the input of key.
• Coded Algorthm
• Coded Algorthm 2
• Test Algorthm

Code Challenge 31

Challenge Summary

• Finds the first word to occur more than onece in a string
• input : String
• output : String
• Full Description 31

  WhiteBoard Process

• 
• Coded Algorthm

  Approach & Efficiency

• Time O(n) space O(N^2)

  Contributors

Code Challenge 32

Challenge Summary

• Find common values in 2 binary trees.
• Full Description 32

  WhiteBoard Process

• 
• Coded Algorthm
• Test Algorthm

  Approach & Efficiency

• Time O(N ^ 2 ) with recursion approach but O(N)
• Space O(N)

  Contributors

Code Challenge 33

Challenge Summary

• Implement a simplified LEFT JOIN for 2 Hashmaps.
• Full Description 33

  WhiteBoard Process

• 
• Coded Algorthm
• Test Algorthm

  Approach & Efficiency

  Time O(N) Space O(N)

  Contributors

Code Challenge 34

Challenge Summary

• Full Description 34a
  • Determine the most common word in a book.
• Full Description 34b
  • Determine if a string is full of unique characters
  • Stretch goal is included in code

    WhiteBoard Process

• 
• 
• Coded Algorithm 34a
• Test Algorthm 34a
• Coded Algorithm 34b
• Test Algorthm 34b

  Approach & Efficiency

• Both: Time O(N) Space O(N)

  Contributors

Code Challenge 35

Challenge Summary

• Implement a graph
  • add node
  • add edge
  • get nodes
  • get neighbors
  • size
• Full Description 35

  WhiteBoard Process

• Coded Algorthm
• Test Algorthm

  Approach & Efficiency

  -

  Contributors

Code Challenge 36

Challenge Summary

• implement breadth first graph
• Full Description 36
• Coded Algorthm
• Test Algorthm

  WhiteBoard Process

  Approach & Efficiency

  Contributors

Code Challenge 37

Challenge Summary

• sort an unsorted array using merge sort algorithm
• Full Description 37

  WhiteBoard Process

• 
• Coded Algorthm
• Test Algorthm

  Approach & Efficiency

  Contributors

Code Challenge 39

Challenge Summary

• Full Description 39

  WhiteBoard Process

  Approach & Efficiency

  Contributors

Code Challenge 41

Challenge Summary

• Full Description 41

  WhiteBoard Process

  Approach & Efficiency

  Contributors

Code Challenge 42

Challenge Summary

• sort an unsorted array using merge sort algorithm
• Full Description 42

  WhiteBoard Process

  Approach & Efficiency

  Contributors

Code Challenge 43

Challenge Summary

• Full Description 43

  WhiteBoard Process

  Approach & Efficiency

  Contributors

Code Challenge 44

Challenge Summary

• Full Description 44

  WhiteBoard Process

  Approach & Efficiency

  Contributors