Term
LINKED LIST LOOP
Using a constant amount of memory, find a loop in a singly-linked list in O(n) time. You cannot modify the list in any way. |
|
Definition
Iterate with 2 pointers, one goes slow and the second goes faster.
// Best solution
function boolean hasLoop(Node startNode){
Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
if (slowNode == fastNode1 || slowNode == fastNode2) return true;
slowNode = slowNode.next();
}
return false;
} |
|
|
Term
REPEATED NUMBER
You are given a sequence S of numbers whose values range from 1 to n-1. One of these numbers repeats itself once in the sequence. (Examples: {1 2 3 4 5 6 3}, {4 2 1 2 3 6 5}). Write a program that finds this repeating number using a constant amount of memory. Now what if there are two repeating numbers (and the same memory constraint)? |
|
Definition
| sum all and extract (n-1)*n/2 |
|
|
Term
| Devise a fast algorithm for computing the number of 1-bits in an unsigned integer. If the machine supports n-bit integers, can we compute the number of 1-bits in O(log n) machine instructions? Can we compute the number of 1-bits in O(b) machine instructions where b is the number of 1-bits in the integer? |
|
Definition
static int bits_in_char [256] ;
int bitcount (unsigned int n) {
// works only for 32-bit ints
return bits_in_char [n & 0xffu]
+ bits_in_char [(n >> 8 ) & 0xffu]
+ bits_in_char [(n >> 16) & 0xffu]
+ bits_in_char [(n >> 24) & 0xffu] ;
}
Counting bits set, Brian Kernighan's way
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
v &= v - 1; // clear the least significant bit set
} |
|
|
Term
| Write code for finding number of zeros in n! |
|
Definition
function zeros(int n)
{
int count=0,k=5;
while(n>=k)
{
count+=n/k;
k*=5;
}
return count;
} |
|
|
