Assorted algorithm questions

Question 1

What is the complexity of building a suffix tree?

Answer 1

By using Ukkonen’s algorithm it is O(n). It is linear.

Question 2

What computing resources do threads share and not?

Answer 2

Share

• memory
• file handles

Don’t share

• stack

Question 3

What are some of operating system level synchronization objects?

Answer 3

• monitors (mutual exclusive locks)
• semaphore (special case of a semaphore is a mutex)
• counting semaphores

Question 4

What is busy waiting? What is the problem with it? In what cases is busy waiting acceptable?

Answer 4

busy waiting: while(!somethingHappened()){}

Problem: consumes cpu cycles that could be better spent doing real work

When is it acceptable:

• when we know that waits are going to be small, and busy wait would be faster than trying to acquire a lock
• in a HPC (high performance computing) environment when there are a lots of CPU cores, each dedicated to a specific task, that would not do other tasks while waiting for a lock. In this case a system may perform better with spinlocks.

Question 5

Which are examples of O(n) runtime substring search algorithms?

Answer 5

Knuth-Morris-Pratt (KMP)

Boyer-Moore (uses 2 fallback tables instead of one as opposed to KMP)

Rabin-Karp (uses a rolling hash function)

Question 6

What is external sort and how does it work?

Answer 6

A way of sorting big files that are so large that they don’t fit into RAM.

Method:

• divide the files into chunks that fit in available RAM
• sort each chunk in RAM using any O(n log n) algoritm
• write each sorted chunk into disk
• do an n-way merge of the files on disk or merge them one by one

Question 7

Describe selection sort and its properties.

Answer 7

Algorithm:

Split the original array into two parts: first part is sorted, the second is not. Search for the smallest element in the unsorted list. Swap it with the first element in the unsorted list. The first element of the unsorted list becomes the last of the sorted.

Best, average and worst case performance is O(n^2).

Space complexity: O(n) total, O(1) auxillary.

Selection sort is not stable! (Uses swaps to move the next small number, which may change the order of items that are larger, if the next smallest is swapped with a large number of higher at higher index than the same at a lower)

Question 8

Describe insertion sort and its properties.

Answer 8

Algorithm:

Split the array into 2 parts: sorted and unsorted. Take the first element of the unsorted list. Swap it with the previous until it is not smaller than the element before it.

Worst case: O(n^2) (when it is sorted in descending order)

Best case: O(n) (it is already sorted)

Average case: O(n^2)

Space: O(n) + O(1) auxilarry

Question 9

On what kind of data does bucket sort work the best?

Answer 9

On uniformly distributed data. It ensures that in each bucket you end up with 1 element on average.

Question 10

Describe bucket sort.

Answer 10

Create a number of buckets (preferrably n number of buckets). Insert each item into one of the buckets based on the value (n*a[i] if a[i] is a number in range 0..1).

Sort each bucket using insertion sort. Iterate over the buckets in order and reinsert the elements into the original bucket.

Worst case: O(n^2). Best case: O(n). Average case: O(n+k) (k is the number of buckets).

Question 11

Describe Quicksort.

Answer 11

Algorithm: partition the array using a choosen pivot. Values less than the pivot are going into the first half, values greater than or equal to the pivot are on the second half. Repeat the process recursively on the two partitions.

Best case, average case: O(n log n), Worst case: O(n^2).

Space complexity worst case: O(log n)

Question 12

Is quicksort stable?

Answer 12

Depends on implementation. Usually it is not stable. There are stable versions with additional space complexity (O(n)).

Question 13

What are the benefits of quicksort over mergesort?

Answer 13

It can be parallelized, utilizing multiple CPUs, cores, threads.

Question 14

In which cases is quicksort performs worst (O(n^2))?

Answer 14

When the pivot function partitions the array into a n-1 and a 1 size array for every iteration. So it depends on the partition function also, not only in the input. For example it is not enough for the input to be sorted or reverse sorted.

Question 15

Describe merge-sort and its properties.

Answer 15

Algorithm: 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.

Worst, best, average: O(n log n)

Space complexity: O(n)

Stable sort.

Question 16

What are the advantages of merge sort?

Answer 16

Stable and efficiently uses slow-to-access media. Best for sorting linked lists.

Question 17

In what situations may selection sort be beneficial?

Answer 17

Where moving data (swapping) is more expensive than comparing them.

Question 18

Ask questions to determine which sorting algoritm is the best for a sorting problem.

Answer 18

• “What can you tell me about the data?”
• What is the distributions of the data?
• Is it sorted or not?
• What do we optimize for? Best case performance? Worst case? Average case?
• Does the input fit into memory?

Question 19

What kind of sorting would you use for sorting a mostly sorted list. (There are only a few items that are out of order).

Answer 19

Insertion sort could be a good solution. It has O(n) runtime on an already sorted list and when there are only a few out of order items, it needs only a few swapping.

Question 20

How do you compare two string in a case insensitive manner?

Answer 20

Using String.compareIgnoreCase(String other) instance method.

Question 21

What is big-endian and what is little-endian?

Answer 21

In big endian, the most significant byte is stored at the memory address location with the lowest address. This is akin to left-to-right reading order. Little endian is the reverse: the most significant byte is stored at the address with the highest address.

Question 22

What is a page fault?

Answer 22

A page fault is an interrupt (or exception) to the software raised by the hardware, when a program accesses a page that is mapped in address space, but not loaded in physical memory.

Question 23

What is trashing?

Answer 23

Thrash is the term used to describe a degenerate situation on a computer where increasing resources are used to do a decreasing amount of work.

Usually it refers to two or more processes accessing a shared resource repeatedly such that serious system performance degradation occurs because the system is spending a disproportionate amount of time just accessing the shared resource.

Question 24

What are the tipical stages of instruction pipelining in a CPU?

Answer 24

Fetch (instructions into pipeline)

Decode

Executing

Writing back (result to memory or cpu register)

Question 25

Describe quickselection algorithm.

Answer 25

Similar to quicksort. Used to return an unordered list of the kth smallest/largest element of a list of size n.

Has O(n) average time, O(n^2) worst case.

Algorithm: pick a random element from a list as a pivot. Move all elements that are larger to the right, move all smaller to the left. Depending on the place of the pivot, repeat the process on the left or right half until the pivot is at the given position (k).

Question 26

Given a string S and a list of smaller strings T. How would you effectively search S for each string in T.

Answer 26

Build a suffix tree from S. For each string in T check if it exists in the tree.