RS
BAN USERThe first clue is "store them as you wish" which implies that space usage is not material.
Second clue is given a index get the state of bulb which says the operation of returning state should be O(1) i.e. a constant and hence the choice of storage is an array.
Third clue is given the start and end of the bulb list toggle state of bulbs. This is the trickiest of all since it is asking you to find an efficient way of list traversal (and not necessarily contiguously stored). Using a singly link list from start to end, traversal cost is O(n). A smarter way could be to do this in O(logn) hint think of a AVL ;-)
A possible solution could be to use an alternate representation of the number say in a exponent form say m^n.
Once the representation is done then you can multiply arbitrary number of such numbers by doing exponent addition with common base for ex:
(2^a)*(2^b)*(2^c)*....*(2^z) = 2^(a+b+c+...+z)
Lets assume each element in node is represented as -
struct node {
int data;
struct node *next;
};
Given a list you can clone it with the above structure -
void cloneList(struct node *src, struct node **dest)
{
struct node *start = src;
struct node *element = NULL;
if (src == NULL) {
// empty list
*dest = NULL;
return;
}
element = createNode(src->data);
*dest = element;
src = src->next;
while (src) {
printf("Element created %d\n", src->data);
element->next = createNode(src->data);
if (element == NULL) {
// alloc failure, free list and return empty clone list
destroyList(*dest);
*dest = NULL;
break;
}
src = src->next;
if (src == start) {
// circular list
element->next->next = *dest;
break;
}
element = element->next;
}
return;
}
Test cases would be -
1. validListClone(list)
Expected output should produce a copy. Validate using the number of elements in source and destination should match
2. emptyListClone(NULL);
Expected output should produce a empty list
3. circularListClone(list);
Expected output should to produce a circular list with last node of the cloned list pointing to the first element of the cloned list and not the original list.
As the "secondary" in the question suggests and it is assumed that it is slower than primary memory it is shown here with example that large page tables can be written to secondary storage and hence has the potential of being slower.
Most often primary memory is referred to as DRAM and secondary memory is the disk with a magnitude higher in access times. When an application has demands on more memory in DRAM operating systems will take some of the unused memory (LRU) and write its contents into disks and then provide that space to the calling application. All of this is done in the context of the memory access request. when the original process who owned the memory tries to access it again then the memory subsystem performs a page fault leading to the handler in reading the contents of memory from secondary storage into primary and then completing the request to application. It maybe noted that this process of page fault does add to the additional latency in accessing memory. The aspect of performance penalty will be observed when the number of page faults are frequent enough that the operating system is constantly in the process of reading and writing contents to secondary storage i.e. a imbalance in system resources due to the application demand on the available resources.
Consider the list of integers as {a,b,c,d,e,f}
Iterate through sum set -
1) first level sum set which is a list of adjacent elements -
{a+b,b+c,c+d,d+e,e+f}
2) second level sum set is derived by using a combination of the original list and first level sum set -
{a+b-b-c+2c, b+c-c-d+2d, c+d-d-e+2e, d+e-e-f+2f}
also rewritten as
{a+c,b+d,c+e,d+f}
3) third level sum set -
{a+c+b+d-b-c,b+d+c+e-c-d,c+e+d+f-d-e}
also rewritten as
{a+d,b+e,c+f}
4) fourth level sum set -
{a+d+b+e-b-d,b+e+c+f-c-e}
also rewritten as
{a+e,b+f}
5) fifth level sum set -
{a+e+b+f-b-e}
also rewritten as
{a+f}
and you will see that it is no longer O(n^2)
You have a valid point. The test case of cloning a malformed list is required.
- RS August 10, 2016The correctness in expected output is ambiguous -
a) clone fails as soon as it detects a loop and returns NULL
b) clone completes by detecting the loop and returns a malformed list
c) clone completes by detecting and removing the loop in the cloned copy (source is read only).
What is required to be done is supplement the function to detect malformed list.