Brainscape's Knowledge GenomeTM

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


See full index

Coding Interview > Data Structures > Flashcards

Data Structures Flashcards

1
Q

Describe the format of Linked List data structure (3)

A
  • Linear data structure
  • Data is not stored in contiguous memory
  • Comprised of nodes which have a variable for the data to be stored and a pointer to the next node in the list.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Advantages of Linked List (3)

A
  • Dynamic size
  • Memory is not wasted
  • Effective insertion and deletion as data doesn’t have to move like in arrays
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Disadvantage of Linked List (3)

A
  • Using more memory per node due to having to maintain the pointer
  • O(n) access due to having to traverse list from head
  • Cache inefficient as memory is not stored in contiguous memory
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Complexity of insert/delete at beginning of Linked List

A

O(1)

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

Complexity of insert/delete at end of Linked List

A

O(n)

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

Complexity of insert/delete at given point in Linked List

A

O(n)

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

Complexity of searching/accessing Linked List by index

A

O(n)

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

Describe the format of a Stack data structure (4)

A
  • Linear data structure
  • Follows Last in First Out, access via the top of the stack
  • Can be fixed size or dynamic
  • Can be implemented with both Arrays or Linked List
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Advantages of Stack data structure (4)

A
  • Simplicity
  • Efficiency: O(1) operations
  • LIFO
  • Limited memory usage
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Disadvantages of Stack data structure (2)

A
  • Limited access: O(n)
  • Possibility of overflow if fixed size
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Common Stack operations (5)

A
  • Push
  • Pop
  • Peek
  • Size
  • isEmpty
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Complexity of insert in Stack

A

O(1)

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

Complexity of removal in Stack

A

O(1)

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

Describe the structure of Queue data structure (4)

A
  • Linear data structure
  • Follows First in First Out
  • Can be fixed size or dynamic
  • Can be implemented with both Arrays or Linked List
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Common Queue operations (5)

A
  • Enqueue O(1)
  • Dequeue O(1)
  • Peek
  • Size
  • IsEmpty
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is a Binary Search Tree?

A

A tree data structure where each node has two children and they fit a specific ordering such as:
All left children < n < all right children

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

What are the advantages of BST? (5)

A
  • Efficient searching: O(log n) time complexity
  • Ordered structure: Elements are stored in sorted order, making it easy to find the next or previous element
  • Dynamic insertion and deletion: Elements can be added or removed efficiently
  • Balanced structure: Can be balanced to maintain logarithmic height, ensuring efficient operations
  • Space efficiency
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What are the disadvantages of BST? (5)

A
  • Not self-balancing: Unbalanced BSTs can lead to poor performance
  • Worst-case time complexity: In the worst case, BSTs can have a linear time complexity for searching and insertion
  • Memory overhead: Pointers
  • BSTs can become inefficient for very large datasets
  • Limited functionality: BSTs only support searching, insertion, and deletion operations
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are the common operations for BST and their time complexities? (3)

A
  • Insert: O(log(N))
  • Delete: O(log(N))
  • Search: O(log(N))
20
Q

What are some applications of a BST? (5)

A
  • Searching: Finding a specific element in a sorted collection
  • Sorting: Sorting a collection of elements in ascending or descending order
  • Range queries: Finding elements within a specified range
  • Data storage: Storing and retrieving data in a hierarchical manner
  • Databases: Indexing data for efficient retrieval
21
Q

What is a balanced tree?

A

Tree where the left and right sub trees are some what similar so that operations are O(log(n))

22
Q

What is a complete binary tree?

A

A complete binary tree is a binary tree in which every level of the tree is fully filled, except for perhaps the last level. To the extent that the last level is filled, it is filled left to right.

23
Q

What is a full binary tree?

A

A full binary tree is a binary tree in which every node has either zero or two children.That is, no nodes have only one child.

24
Q

What is a perfect binary tree?

A

Binary tree which is both full and complete

25
Q

What is in-order traversal of a binary tree?

A

Left branch, current node, right branch. For a binary search tree, this would traverse in ascending order.

26
Q

What is pre-order traversal of a binary tree?

A

This visits the current node, before visiting its children. Root is always visited first

27
Q

What is post-order traversal of a binary tree?

A

This visits its children before, visiting the current node. Root is always visited last.

28
Q

How do you remove element from BST, what is the time complexity?

A

Replace the node to be removed with its in order successor. Finding successor is O(log(n)) time complexity

29
Q

What is a Heap data structure?

A

A Heap is a complete binary tree data structure that satisfies the heap property: for every node, the value of its children is less than or equal to its own value. Meaning the root will either hold the max or min value of data structure.

30
Q

How is a heap normally implemented? How do you get the children of an element?

A

With and array, where the left and right children are given by (2index) + 1 and (2index) + 2

31
Q

What are the advantages of Heap data structure? (5)

A
  • Efficient insert and delete operations
  • Efficient priority queue implementation
  • O(1) access to Max or Min
  • Less memory as Binary Tree is complete
  • Heapsort implementation
32
Q

What are the disadvantages of Heap data structure? (5)

A
  • Flexibility
  • Bad for searching
  • Not stable data structure
  • Memory management
  • Complexity
33
Q

What are the common operations for Heap? (4)

A
  • Insert O(log(N))
  • Delete O(log(N))
  • Min/Max O(1)
  • Heapify O(n)
34
Q

What are applications of Heaps? (5)

A
  • Priority Queues
  • Heapsort Algo
  • Memory management, memory blocks stored in Heap and used to efficient allocate it to programs
  • Graph algorithms Dijkstra’s and Kruskal’s
  • Job scheduling based on priority
35
Q

What is the algorithm for inserting an element into a Heap?

A
  • Insert at the end of the heap array and work up its parent nodes swap if it is larger. O(log(N))
36
Q

What is the algorithm for deleting the root node in Heap?

A
  • Remove the root node and replace with last element in Heap. Swap element with its largest child and move down the branch till Heap ordering is restored. O(log(N))
37
Q

What is a Graph data structure?

A

A graph is simply a collection of nodes with some edges between the nodes.

38
Q

What is a directed Graph?

A

A directed graph allows travel down its edges in one direction only.

39
Q

What is a connected Graph?

A

Where every pair of nodes has an edge between them.

40
Q

What is an acyclic Graph?

A

Graph without cycle in it.

41
Q

What are the ways to represent a graph? (2)

A
  • Adjacency List: Each node has a list of its adjacent nodes
  • Adjacency Matrix: True value in matrix[i][j] means there is a path between node i and j. This implementation can be less efficient.
42
Q

What is depth first search in terms of a Graph data structure? What is breadth first search?

A
  • Depth: Starting at the root or some other node and exploring each branch first before moving onto the next branch.
  • Breadth: Explore each neighbour first before moving a level down
43
Q

When is DFS used for a Graph?

A

When you want to visit every node, it is simpler

44
Q

When is BFS used for a Graph?

A

Normally when you want to find the shortest path between two nodes

45
Q

What is Bi-directional search for a Graph? When is it used?

A

It is used to find the shortest path between two nodes and is a breadth search starting from each node. When these collide you have found the shortest path.

Coding Interview (2 decks)

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