Software Engineering

Question 1

Abstract Class

Answer 1

Intentionally incomplete class definition; has some members declared ‘abstract’ and children must implement them; objects cannot be created

Question 2

Encapsulation

Answer 2

Implementation should be completely separate from the interface

Question 3

Child Class

Answer 3

A class that extends another class

Question 4

Aggregation

Answer 4

has-a relationship; contained object can survive without the container

Question 5

Immutable

Answer 5

A value that cannot be changed

Question 6

Inheritence

Answer 6

Ability of a class to duplicate its parent’s members

Question 7

Instance

Answer 7

An object that has been created from a class

Question 8

Interface

Answer 8

Supplies definition for methods - kind of like a .h file

Question 9

Composition

Answer 9

is-a relationship; contained object cannot survive without the container

Question 10

Polymorphism

Answer 10

Allows a child class to be used anywhere a method requires the parent class

Question 11

Private

Answer 11

Only the class itself can read/write

Question 12

Protected

Answer 12

Only the class itself and children can read/write

Question 13

Public

Answer 13

Anything can read/write

Question 14

Uses-A

Answer 14

Relationship between objects that call methods and use member variables of other objects

Question 15

Object Based vs Object Oriented

Answer 15

Object based has no inheritence

Question 16

Association

Answer 16

One object uses another but does not own it

Question 17

Virtual member

Answer 17

Expected to be implemented in subclasses

Question 18

Function Overloading vs Overriding

Answer 18

Overloading has different parameters, Overriding has same signature but different implementation

Question 19

Priority inversion

Answer 19

Medium priority task preempts a high priority task

Question 20

Hash Table

Answer 20

Use a mathematical function to take the key and transform it to the domain of an array; resolve collisions by Chaining or OpenAddressing (use an array and fill in empties nearby)

Question 21

Linked List

Answer 21

Elements chained together using pointers

Question 22

Queue

Answer 22

Uses a linked list, FIFO

Question 23

Stack

Answer 23

Uses a linked list, LIFO

Question 24

Heap

Answer 24

Nearly complete binary tree where parent >= child; Heapify (maintain heap structure, O(lg n)); BuildHeap (creates heap from array, O(n)); HeapSort (sorts array in place, O(n lg n)); ExtractMax O(lg n); Insert O(lg n)

Question 25

Binary Search Tree

Answer 25

Left Child < Parent <= Right Child

Question 26

Red-Black Tree

Answer 26

Balanced Binary Search Tree uses colors

Question 27

Graph

Answer 27

Set of vertices and edges (with possible directions and weights)

Question 28

Bubble Sort

Answer 28

Iterate and swap pairs, iterate again on one less item, etc -- O(n^2)

Question 29

Selection Sort

Answer 29

Iterate and select the smallest, then second smallest, etc -- O(n^2)

Question 30

Insertion Sort

Answer 30

Cascade items successively into place - Best O(n) if already sorted; Worst O(n^2)

Question 31

Merge Sort

Answer 31

Recursively split on a pivot then merge the arrays back up into sorted order - O(n lg n)

Question 32

Heap Sort

Answer 32

Builds a heap then exchanges elements to push down O(n lg n) - NOT STABLE

Question 33

Quicksort

Answer 33

Split into two arrays (greater than pivot, less than pivot) and recurse - worst case O(n^2), best case O(n lg n)

Question 34

Counting Sort

Answer 34

Only for integers with known maximum; count the occurences of 1s, 2s, etc - O(n)

Question 35

Radix Sort

Answer 35

Uses another stable sort on each digit - O(n)

Question 36

Bucket Sort

Answer 36

Uses equal size buckets across [0, 1) - O(n)

Question 37

Coffman Condition 1

Answer 37

Mutual exclusion - a resource can't be shared

Question 38

Coffman Condition 2

Answer 38

Resource holding - a process is holding one resource and is requesting more

Question 39

Coffman Condition 3

Answer 39

No preemption - the process itself must release resources

Question 40

Coffman Condition 4

Answer 40

Circular wait - the processes are waiting on each other to release resources

Question 41

Dynamic Programming

Answer 41

Optimizing the solution based on the data - ex. Multiplying matrices in a different order

Question 42

Breadth First Search

Answer 42

Finds the minimum distances from one source to all edges O(V+E)

Question 43

Depth First Search

Answer 43

Marks up the graph

Question 44

Pre/Post/In Order Traversal

Answer 44

Pre = N L R, In = L N R, Post = L R N

Question 45

Topological Sort

Answer 45

Performs DFS to get order of dependencies

Question 46

NP-Complete

Answer 46

Cannot be completed in polynomial time (exponential)

Question 47

Memory segmentation

Answer 47

Data - initialized variables, BSS - uninitialized variables, Heap - area for dynamic allocation, Stack - function calls and automatic variables

Question 48

Semaphore vs Mutex

Answer 48

Mutex same as binary semaphore. Mutex tracks the owner process that locked it

Question 49

Rendezvous

Answer 49

Used in multi-threading to pause a thread until other threads reach a certain execution point

Question 50

Race Condition

Answer 50

Output is dependent on the sequence or timing of threads

Question 51

Interprocess Communication Methods

Answer 51

Shared memory, file system, pipe, socket

Question 52

Singleton

Answer 52

Only one instance of a class exists

Question 53

How inheritance looks on class diagram

Answer 53

Arrow from derived to base with solid line and unfilled head

Question 54

Two-way association on class diagram

Answer 54

solid line with multiplicity on each side and member names on opposite sides

Question 55

One-way association on class diagram

Answer 55

Skeleton arrow with solid line pointing to class that is known about

Question 56

Aggregation on class diagram

Answer 56

Skeleton arrow container to contained with unfilled diamond on container

Question 57

Composition on class diagram

Answer 57

Skeleton arrow container to contained with filled diamond on containter