1.
What is a sparse array?
Answer: Option 'C'
An array in which most of the elements have the same value
They are set to a default value, usually 0 or null.
2.
When do you use a sparse array?
Answer: Option 'B'
When the array has more occurrence of zero elements
3.
What is the difference between a normal(naive) array and a sparse array?
Answer: Option 'B'
A naive implementation allocates space for the entire size of the array, whereas a sparse array(linked list implementation) allocates space only for the non-default values.
4.
Choose the code which performs the store operation in a sparse array.(Linked list implementation)
public void store(int index, Object val)
{
List cur = this;
List prev = null;
List node = new List(index);
node.val = val;
while (cur != null && cur.index < index)
{
prev = cur;
cur = cur.next;
}
if (cur == null)
{
prev.next = node;
} else
{
if (cur.index == index)
{
System.out.println("DUPLICATE");
return;
}
prev.next = node;
node.next = cur;
}
return;
}
public void store(int index, Object val)
{
List cur = this;
List prev = null;
List node = new List(index);
node.val = val;
while (prev != null && prev.index < index)
{
prev = cur;
cur = cur.next;
}
if (cur == null)
{
prev.next = node;
} else
{
if (cur.index == index)
{
System.out.println("DUPLICATE");
return;
}
prev.next = node;
node.next = cur;
}
return;
}
public void store(int index, Object val)
{
List cur = this;
List prev = null;
List node = new List(index);
node.val = val;
while (cur != null && cur.index < index)
{
cur = cur.next;
prev = cur;
}
if (cur == null)
{
prev.next = node;
} else
{
if (cur.index == index)
{
System.out.println("DUPLICATE");
return;
}
prev.next = node;
node.next = cur;
}
return;
}
Answer: Option 'A'
Create a new node and traverse through the list until you reach the correct position, check for duplicate and nullity of the list and then insert the node.
5.
Which of the following performs the fetch operation?
public Object fetch(int index)
{
List cur = this.next;
Object val = null;
while (cur != null && cur.index != index)
{
cur = cur.next;
}
if (cur != null)
{
val = cur.val;
} else
{
val = null;
}
return val;
}
public Object fetch(int index)
{
List cur = this;
Object val = null;
while (cur != null && cur.index != index)
{
cur = cur.next;
}
if (cur != null)
{
val = cur.val;
} else
{
val = null;
}
return val;
}
public Object fetch(int index)
{
List cur = this;
Object val = null;
while (cur != null && cur.index != index)
{
cur = cur.index;
}
if (cur != null)
{
val = cur.val;
} else
{
val = null;
}
return val;
}
Answer: Option 'B'
You travers through the array until the end is reached or the index is found and return the element at that index, null otherwise.
6.
Choose the appropriate code that counts the number of non-zero(non-null) elements in the sparse array.
public int count()
{
int count = 0;
for (List cur = this.next; (cur != null); cur = cur.next)
{
count++;
}
return count;
}
public int count()
{
int count = 0;
for (List cur = this; (cur != null); cur = cur.next)
{
count++;
}
return count;
}
public int count()
{
int count = 1;
for (List cur = this.next; (cur != null); cur = cur.next)
{
count++;
}
return count;
}
Answer: Option 'A'
A simple ‘for loop’ to count the non-null elements.
7.
Suppose the contents of an array A are, A = {1, null, null, null, null, 10};
What would be the size of the array considering it as a normal array and a sparse array?
Answer: Option 'B'
A normal array considers null also as an element, but in the sparse array only a non-zero or a non-null element is considered.
8.
What is sparsity of a matrix?
Answer: Option 'A'
The fraction of zero elements over the total number of elements
This is the definition of sparsity(density) of a matrix.
9.
How would you store an element in a sparse matrix?
public void store(int row_index, int col_index, Object val)
{
if (row_index < 0 || row_index > N)
{
System.out.println("row index out of bounds");
return;
}
if (col_index < 0 || col+index > N)
{
System.out.println("column index out of bounds");
return;
}
sparse_array[row_index].store(col_index, val);
}
public void store(int row_index, int col_index, Object val)
{
if (row_index < 0 || row_index > N)
{
System.out.println("column index out of bounds");
return;
}
if (col_index < 0 || col+index > N)
{
System.out.println("row index out of bounds");
return;
}
sparse_array[row_index].store(col_index, val);
}
public void store(int row_index, int col_index, Object val)
{
if (row_index < 0 && row_index > N)
{
System.out.println("row index out of bounds");
return;
}
if (col_index < 0 && col+index > N)
{
System.out.println("column index out of bounds");
return;
}
sparse_array[row_index].store(col_index, val);
}
public void store(int row_index, int col_index, Object val)
{
if (row_index < 0 && row_index > N)
{
System.out.println("column index out of bounds");
return;
}
if (col_index < 0 && col+index > N)
{
System.out.println("row index out of bounds");
return;
}
sparse_array[row_index].store(col_index, val);
}
Answer: Option 'A'
Each row in a sparse matrix acts as a sparse array, hence this row with the specified col_index is the array and the specified position where the element is stored.
10.
What is the functionality of the following piece of code?
public Object function(int row_index, int col_index)
{
if (row_index < 0 || col_index > N)
{
System.out.println("column index out of bounds");
return;
}
return (sparse_array[row_index].fetch(col_index));
}
Answer: Option 'D'
The fetch method of SparseArray class is called , the row specified by row_index makes it an array and the col_index denotes the specified position.