DSA Mock Interview

Question 1

How might you determine the efficiency of an algorithm?

Answer 1

Determined by the Big O notation

Question 2

Why is the Big O Notation important?

Answer 2

So that we can have the code as smooth as possible. Speed is important.

Question 3

What categories of complexities are described in Big O Notations

Answer 3

Time complexity: How long code will take to execute as data increases

Space complexity: How much space is needed and how efficiently it is used

More space = less time and the other way around

Question 4

What is O(1)

Answer 4

O(1) = Constant Time

examples:
- setting a variable once
- performing a calculation
- determining if an integer is even or odd

Basically a flat line on a graph. Easy to plan for.

Question 5

What is O( n )

Answer 5

O( n ) = Linear Time

examples:

• basic non-nested for loops
• finding smallest or largest item in an unsorted array

Basically a 45 degree line on graph, still easy to plan for, scaling probably won’t run away from you.

Question 6

What is O( n^2 )?

Answer 6

O( n^2 ) = N squared

• basic nested for loops, bubble sort, insertion sort.

Starts to get harder to plan for as data sets increase dramatically.

Question 7

What is O( log n )

Answer 7

O( log n ) = Log N (Logarithmic Time)

• binary search - when you can easily eliminate large sections of data on each iteration.

Means that scaling large data sets won’t dramatically increase the output time.

Question 8

Describe 3 differences between a linked list and an array

Answer 8

LINKED LIST:

• Non-contiguous space requirement.
  e. i. Data doesn’t HAVE to be in same space on disk.
• Can be more efficient for memory allocation. Easier to resize.
• Can be less efficient for caching (not contiguous)
• No “find by index” feature, so accessing individual elements can be slower
• Easier to add elements (insert nodes) to various positions within list.

ARRAY:

• Must be in same contiguous disk space.
• Harder to resize. Also, increasing length may require moving the array in memory to a larger space.
• Better caching - all addresses are contiguous
• Fast access for reading when searching by index
• Harder to insert new elements to front and within the array as you then have to shift existing elements after the new element is added.

Question 9

What’s the difference between a Binary Tree and a Binary Search Tree

BST: All left descendants are less than or equal to node, and all right descendants are greater than node.

Answer 9

BST (Binary Search Tree): All left descendants are less than or equal to node, and all right descendants are greater than node

Question 10

Q: describe the 3 types of BST traversal:

25

/ \

10 32

Answer 10

In-order (from the smallest number to the biggest) (ex: 10, 25, 32)

Visit left branch, then current node, then right branch. Visits all nodes in ascending order on a BST.

Pre-order (looks like the ““ sign) (branches first, node last) (ex: 10, 32, 25)

Visits left branch, then right branch, then current node. Root node is always last visited. Useful for language processors

Question 11

Q: Algorithms for searching through arrays and trees

Answer 11

Linear search
Binary search
Depth-first search
Breadth-first search

Question 12

Linear search

Answer 12

Look through an array one-by-one until you find what you are looking for

Question 13

Binary search

Answer 13

Narrow it down by always guessing in the middle of the range

Question 14

Depth-first search

Answer 14

Traverse as far as you can down the tree before back-tracking

e.i. check if a person related to a past royal relative has the right to be a king

Question 15

Breadth-first search

Answer 15

Search works across the rows of a tree (the top row will be handled first, then the second row, and so on)

e.i check if multiple people from the same generation are part of the royal family

Question 16

Q: Array sorting methods

Answer 16

Merge sort
Bubble sort
Quick sort
Selection sort
Insertion sort
Heap sort
Bucket (bin) sort

Question 17

Merge sort

Answer 17

• DIVIDE THE UNSORTED LIST INTO N SUBLISTS, each containing 1 element (a list of 1 element is considered sorted).
• repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Question 18

Bubble sort

Answer 18

REPEATEDLY SWAPPING the adjacent elements if they are in wrong order.

Question 19

Quick sort

Answer 19

• DIVIDE AND CONQUER algorithm. It creates two empty arrays to hold elements less than the pivot value and elements greater than the pivot value, and then recursively sort the sub arrays. There are two basic operations in the algorithm, swapping items in place and partitioning a section of the array.

Question 20

Selection sort

Answer 20

• REPEATEDLY FINDING THE MINIMUM ELEMENT (considering ascending order) from unsorted part and putting it at the beginning

Question 21

Insertion sort

Answer 21

• Begin at the left-most element of the array and invoke Insert to INSERT EACH ELEMENT ENCOUNTERED INTO ITS CORRECT POSITION.
• The ordered sequence into which the element is inserted is stored at the beginning of the array in the set of indices already examined.

Question 22

Heap sort

Answer 22

• Involves preparing the list by first TURNING IT INTO A MAX HEAP (a complete Binary Tree represented as an array)
• then repeatedly swaps the first value of the list with the last value, decreasing the range of values considered in the heap operation by one, and sifting the new first value into its position in the heap.

Question 23

Bucket (bin) sort

Answer 23

• sorting algorithm that works by DISTRIBUTING THE ELEMENTS OF AN ARRAY INTO A NUMBER OF BUCKETS.
• each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm.
• sort each non-empty bucket.

Question 24

Q: What are the arrays sorting methods by speed

Answer 24

The slowest is selection, then bubble, then insertion, then shell, then merge, then heap, then quick, then quick3

Question 25

Q: What is faster than a bubble sort?

Answer 25

Insert, Shell, Heap, Merge, Quick and Quick3

Question 26

Possible coding challenge

Answer 26

Create an algorithm for counting how many times a word appears in a document.

Question 27

Computational Complexity

Answer 27

O(1) - constant time
O(log n) - logarithmic time
O(n) - linear time