Arrays Interview Questions and Answers

Arrays are: Finite (fixed-size) - An array is finite because it contains only limited number of elements. Order -All the elements are stored one by one , in contiguous location of computer memory in a linear order and fashion Homogenous - All the elements of an array are of same data types only and hence it is termed as collection of homogenous

An array is a collection of homogeneous (same type) data items stored in contiguous memory locations. For example if an array is of type “int”, it can only store integer elements and cannot allow the elements of other types such as double, float, char etc. The elements of an array are accessed by using an index.O(

1)
O(
log n)
O(
n)
O(
n log n)
O(
n2)
O(
2n)
O(
n!)

Problem

What is the advantage of dealing with the complexity of inserting into a heap given an algorithm like quick sort handles sorting very well?

Solution

find-min (resp. find-max ), delete-min (resp. delete-max ) and insert are the three most important operations of a min-heap (resp. max-heap), and they usually have complexity of O(1) , O(log n) and O(log n) respectively if you implement a min/max-heap by a binary tree. Now suppose instead you implement a min-heap by a sorted (non-decreasing) array (The case for max-heap is similar). find-min and delete-min are of O(1) complexity if insert is not required in your application, since you can maintain a pointer p that always points to the minimum element in your array. When the minimum element is removed, you just need to move p one step to the next element in the array. Dealing with insertion in a sorted array is not trivial. Given a new element e, we can use binary search to locate its position in the array to insert it. But the point is that if you want to insert it there, you have to move a lot of old elements (can be O(n) ) around to make a vacancy for the new element to reside. This is quite inefficient for most applications. You may also choose to re-sort the array after an element is inserted, this requires O(n log n) time however. Where a heap absolutely, completely beats sorting arrays is a situation where small numbers of items are removed or added, and after each change you want to know again which is the smallest element.

In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of [key, value] pairs, such that each possible key appears at most once in the collection. Associative array can be implemented as: Hash table Self-balancing binary search tree Unbalanced binary search tree Association list

Let's look at the merge principle: Given two separate lists A and B ordered from least to greatest, construct a list C by: repeatedly comparing the least value of A to the least value of B, removing (or moving a pointer) the lesser value, and appending it onto C. when one list is exhausted, append the remaining items in the other list onto C in order. The list C is then also a sorted list. Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n) This problem will have O(n) complexity at best. Implementation: JS

function merge(a, b) {
  var result = [];
  var ai = 0;
  var bi = 0;
  while (true) {
    if ( ai < a.length && bi < b.length) {
      if (a[ai] < b[bi]) {
        result.push(a[ai]);
        ai++;
      } else if (a[ai] > b[bi]) {
        result.push(b[bi]);
        bi++;
      } else {
        result.push(a[ai]);
        result.push(b[bi]);

        ai++;
        bi++;
      }
  } else if (ai < a.length) {
    result.push.apply(result, a.slice(ai, a.length));
    break;
  } else if (bi < b.length) {
    result.push.apply(result, b.slice(bi, b.length));
    break;
  } else {
    break;
  }
}
return result;
}
Java
public static int[] merge(int[] a, int[] b) {
  int[] answer = new int[a.length + b.length];
  int i = 0, j = 0, k = 0;
  while (i < a.length && j < b.length)
  answer[k++] = a[i] < b[j] ? a[i++] : b[j++];
  while (i < a.length)
  answer[k++] = a[i++];
  while (j < b.length)
  answer[k++] = b[j++];
  return answer;
}
PY
def merge(left, right):
result = []
i ,j = 0, 0
while i < len(left) and j < len(right):
print('left[i]: {} right[j]: {}'.format(left[i],right[j]))
if left[i] <= right[j]:
print('Appending {} to the result'.format(left[i]))
result.append(left[i])
print('result now is {}'.format(result))
i += 1
print('i now is {}'.format(i))
else:
print('Appending {} to the result'.format(right[j]))
result.append(right[j])
print('result now is {}'.format(result))
j += 1
print('j now is {}'.format(j))
print('One of the list is exhausted. Adding the rest of one of the lists.')
result += left[i:]
result += right[j:]
print('result now is {}'.format(result))

return result

Linked lists are preferable over arrays when:

1. you need constant-time insertions/deletions from the list (such as in real-time computing where time predictability is absolutely critical)
2. you don't know how many items will be in the list. With arrays, you may need to re-declare and copy memory if the array grows too big
3. you don't need random access to any elements
4. you want to be able to insert items in the middle of the list (such as a priority queue) Arrays are preferable when:
5. you need indexed/random access to elements
6. you know the number of elements in the array ahead of time so that you can allocate the correct amount of memory for the array
7. you need speed when iterating through all the elements in sequence. You can use pointer math on the array to access each element, whereas you need to lookup the node based on the pointer for each element in linked list, which may result in page faults which may result in performance hits.
8. memory is a concern. Filled arrays take up less memory than linked lists. Each element in the array is just the data. Each linked list node requires the data as well as one (or more) pointers to the other elements in the linked list. Array Lists (like those in .Net) give you the benefits of arrays, but dynamically allocate resources for you so that you don't need to worry too much about list size and you can delete items at any index without any effort or re- shuffling elements around. Performance-wise, arraylists are slower than raw arrays.

The following implementations are most common: Stack backed by a singly-linked list. Because a singly-linked list supports

O(
1) time prepend and delete-

first, the cost to push or pop into a linked-list-backed stack is also

O(
1) worst-case. However, each new

element added requires a new allocation, and allocations can be expensive compared to other operations. The locality of the linked list is not as good as the locality of the dynamic array since there is no guarantee that the linked list cells will be stored contiguously in memory. Stack backed by a dynamic array. Pushing onto the stack can be implemented by appending a new element to the dynamic array, which takes amortised

O(
1) time and worst-case
O(
n) time. Popping from

the stack can be implemented by just removing the last element, which runs in worst-case

O(
1) (or
amortised
O(
1) if you want to try to reclaim unused space). In other words, the most common
implementation has best-case
O(
1) push and pop, worst-case
O(
n) push and
O(
1) pop, and amortised
O(
1) push and
O(
1) pop.

Arrays will always be laid out in memory using consecutive storage locations. Most languages model arrays as contiguous data in memory, of which each element is the same size. Let's say we had an array of int's:

[0: 10][32: 20][64: 30][96: 40][128: 50][160: 60]
Each of these elements is a 32-bit integer, so we know how much space it takes up in memory (32 bits). And we

know the memory address of the pointer to the first element. It's trivially easy to get to the value of any other element in that array: Take the address of the first element (the compiler knows the array to start at memory cell x) Take the offset of each element (its size in memory) Multiply the offset by the desired index Add your result to the address of the first element It always takes one multiplication, one add operation and one fetch of an element from a know location.

A sparse array is an array of data in which many elements have a value of zero. This is in contrast to a dense array, where most of the elements have non-zero values or are “full” of numbers.

0 3 5 0 0 0 0 9 0 0 For example consider representing a very large 2D matrix of values, where most of the values are 0. The most straightforward representation would be a very large two dimensional array of integers. This straightforward approach has a few limitations however. If the matrix we are reperesenting is very large, it requires a large quantity of memory to store, even if the number of non-zero elements is small. A better way of representing a sparse martrix would be to only store the values that are non-zero, in such a way that iterating through the rows or columns of non-empty elements is relatively fast.

A sorted array is an array data structure in which each element is sorted in numerical, alphabetical, or some other order, and placed at equally spaced addresses in computer memory. Time complexity of operation on a sorted array: Algorithm Average Worst case

Space O(n) O(n)
Search O(log n) O(log n)
Insert O(n) O(n)
Delete O(n) O(n)

The major advantage is that search times are much faster than in an unordered array. You can apply Binary Search

O(
log n) only if array is sorted.

The disadvantage is that insertion takes longer because all the data items with a higher key value must be moved up to make room. Deletions are slow in both ordered and unordered arrays because items must be moved down to fill the hole left by the deleted item. Ordered arrays are therefore useful in situations in which searches are frequent, but insertions and deletions are not

In programming, when you have a collection of similar items, each with an item number, the collection is called an array, and the item number is called a subscript. The dimensionality of an entire array is the number of subscripts you need to give in order to address a single element. In ruby (for example) this is represented by::

[n]
# One Dimension
[n][o]
# Two Dimensions
[n][o][p]
# Three Dimensions
[n][o][p][q]
# Four Dimensions

Problem

Example: ((()())(())) should be accepted but ())() should be rejected.

Solution

Initialize a counter at zero. Whenever you see ( , increase it by one, and whenever you see ) , decrease it by one. Accept if the counter was always nonnegative and ended up at zero. Since counter is always between −1 and n , only

O(
log n) bits (note it is not
O(
1) ) are needed to store it. So I don't think we can do
O(
1) space.

Problem

Find an algorithm/write pseudocode with high performance for a stack with only two operations, pop() and

push() .

### Solution
Space (not time) efficient. You could:

1. Define two stacks beginning at the array endpoints and growing in opposite directions.
2. Define the third stack as starting in the middle and growing in any direction you want.
3. Redefine the Push op, so that when the operation is going to overwrite other stack, you shift the whole middle stack in the opposite direction before Pushing. You need to store the stack top for the first two stacks, and the beginning and end of the third stack in some structure. Above you may see an example. The shifting is done with an equal space partitioning policy, although other strategies could be chosen depending upon your problem heuristics. the middle stack could be implemented using an alternating sequence for subsequent pushes. The resulting stack structure will be something like: Elem 6 | Elem 4 | Elem 2 | Elem 0 | Elem 1 | Elem 3 | Elem 5

In this case, you'll need to store the number n of elements on the middle stack and use the function:

f[n_] := 1/4 ( (-1)^n (-1 + 2 n) + 1) + BS3

to know the next array element to use for this stack. Although probably this will lead to less shifting, the implementation is not homogeneous for the three stacks, and inhomogeneity (you know) leads to special cases, more bugs and difficulties to maintain code.

In programming, when you have a collection of similar items, each with an item number, the collection is called an array, and the item number is called a subscript. The dimensionality of an entire array is the number of subscripts you need to give in order to address a single element. In ruby (for example) this is represented by::

[n]
# One Dimension
[n][o]
# Two Dimensions
[n][o][p]
# Three Dimensions
[n][o][p][q]
# Four Dimensions

Dynamic array is an array that resizes itself up or down depending on the number of content. Advantage: accessing and assignment by index is very fast

O(
1) process, since internally index access is just [address
of first member] + [offset] .
appending object (inserting at the end of array) is relatively fast amortised
O(
1) . Same performance

characteristic as removing objects at the end of the array. Note: appending and removing objects near the end of array is also known as push and pop. Disadvantage: inserting or removing objects in a random position in a dynamic array is very slow

O(n/2) , as it must shift
(on average) half of the array every time. Especially poor is insertion and removal near the start of the array,

as it must copy the whole array. Unpredictable performance when insertion or removal requires resizing

There is a bit of unused space, since dynamic array implementation usually allocates more memory than

necessary (since resize is a very slow operation)
Linked List is an object that have a general structure of [head, [tail]] , head is the data, and tail is another

Linked List. There are many versions of linked list: singular LL, double LL, circular LL, etc. Advantage: fast

O(
1) insertion and removal at any position in the list, as insertion in linked list is only breaking the list,
inserting, and repairing it back together (no need to copy the tails)
Linked list is a persistent data structure (a persistent data structure is a data structure that always preserves
the previous version of itself when it is modified). This advantage allow

tail sharing between two linked list. Tail sharing makes it easy to use linked list as copy-on-write data structure. Linked lists lend themselves nicely to efficient multi-threaded implementations. The reason for this is that changes tend to be local - affecting only a pointer or two for insert and remove at a localized part of the data structure. So, you can have many threads working on the same linked list. With an array, any change that modifies the size of the array is likely to require locking a large portion of the array. Disadvantage: Slow

O(
n) index access (random access), since accessing linked list by index means you have to recursively

loop over the list. poor locality, the memory used for linked list is scattered around in a mess. In contrast with, arrays which uses a contiguous addresses in memory. Arrays (slightly) benefits from processor caching since they are all near each other Others: Due to the nature of linked list, you have to think recursively. Programmers that are not used to recursive functions may have some difficulties in writing algorithms for linked list (or worse they may try to use indexing). Simply put, when you want to use algorithms that requires random access, forget linked list. When you want to use algorithms that requires heavy insertion and removal, forget arrays.

Array uses continuous memory locations (space complexity O(n) ) to store the element so retrieving of any element will take O(1) time complexity (constant time by using index of the retrieved element). O(1) describes inserting at the end of the array. However, if you're inserting into the middle of an array, you have to shift all the elements after that element, so the complexity for insertion in that case is O(n) for arrays. End appending also discounts the case where you'd have to resize an array if it's full. Operation Average Case Worst Case

Read O(1) O(1)
Append O(1) O(1)

Insert O(n) O(n)
Delete O(n) O(n)
Search O(n) O(n)

A dynamic array is an array with a big improvement: automatic resizing. One limitation of arrays is that they're fixed size, meaning you need to specify the number of elements your array will hold ahead of time. A dynamic array expands as you add more elements. So you don't need to determine the size ahead of time.

Pros: Fast lookups. Retrieving the element at a given index takes O(1) time, regardless of the length of the array. Fast appends. Adding a new element at the end of the array takes O(1) time. Cons: Fixed size. You need to specify how many elements you're going to store in your array ahead of time. Costly inserts and deletes. You have to shift the other elements to fill in or close gaps, which takes worst- case O(n) time.

A simple dynamic array can be constructed by allocating an array of fixed-size, typically larger than the number of elements immediately required. The elements of the dynamic array are stored contiguously at the start of the underlying array, and the remaining positions towards the end of the underlying array are reserved, or unused. Elements can be added at the end of a dynamic array in constant time by using the reserved space until this space is completely consumed. When all space is consumed, and an additional element is to be added, the underlying fixed-sized array needs to be increased in size. Typically resizing is expensive because you have to allocate a bigger array and copy over all of the elements from the array you have overgrow before we can finally append our item. Dynamic arrays memory allocation is language specific. For example in C++ arrays are created on the stack, and have automatic storage duration -- you don't need to manually manage memory, but they get destroyed when

the function they're in ends. They necessarily have a fixed size:

int foo[10];
Arrays created with operator new[] have
dynamic storage duration and are stored on the heap (technically the
"free store"). They can have any size, but you need to allocate and free them yourself since they're not part of

the stack frame:

int* foo = new int[10];
delete[] foo;

Arrays and dictionaries both store collections of data, but differ by how they are accessed. Arrays providerandom access of a sequential set of data. Dictionaries (or associative arrays) provide a map from a set of keys to a set of values. Arrays store a set of objects (that can be accessed randomly) Dictionaries store pairs of objects Items in an array are accessed by position ( index) (often a number) and hence have an order. Items in a dictionary are accessed by key and are unordered. This makes array/lists more suitable when you have a group of objects in a set (prime numbers, colors, students, etc.). Dictionaries are better suited for showing relationships between a pair of objects.