Vijay
BAN USERIt can be solved using heap data structure. The idea is to maintain a heap of 1000 largest elements while scanning through the million elements.
1. Construct a min heap using the first 1000 elements. Now the root has minimum element out of the first 1000 elements.
2. Iterate over the remaining elements one by one. Let 'item' be the element under consideration
if the item is greater than root of the heap, replace the root with the item and heapify the tree.
else continue with the next element.
At the we will have the min heap of 1000 largest elements of the list
Time Complexity : O(N)
where N is the number of elements in the list
Physically stack and heap both are allocated on RAM and their implementation varies from language, compiler and run time
Stack is used for local variables of functions and to track function calling sequences. Heap is used for allocating dynamically created variables using malloc, calloc or new.
Stack memory is freed whenever the function completes execution but the heap memory needs to be freed explicitly using delete, free or by garbage collector of the language.
Stack memory of a process is fixed size and heap is variable memory.
Stack is faster than heap as allocating memory on stack is simpler just moving stack pointer up.
In case of multi threading, each thread of process will have a different stack but all threads share single heap
Function Call :
isPalandrome(str.toLowerCase()
boolean isPalandrome(String s) {
int strLength = s.length();
if(strLength == 0 || s == null)
return false;
int start = 0;
int end = strLength - 1;
while(start < end) {
while(!isAlphabet(s.charAt(start)) && start <= end)
start++;
while(!isAlphabet(s.charAt(end)) && start <= end)
end--;
if(s.charAt(start) == s.charAt(end)) {
start++;
end--;
} else {
return false;
}
}
return true;
}
Graph data structure is useful for representing the many to many relationships.
- Vijay April 26, 2013Particularly array representation of directed graph is more suitable to store that data,
where we will use 3D array to represent the relations.
A[No.of URLs][No.of Time Stamps][2]
A[i][j][0] = 1, if URL i is accessed at time stamp j, else 0
A[i][j][1] = 1, if at time stamp j, URL i is accessed, else 0