learner
BAN USER
- 0of 0 votes
AnswersDesign a Restaurant Reservation system.
- learner in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Object Oriented Design System Design
@codeAddict: not necessarily. If there is some other mechanism available for protection then paging won't be required. In fact since we have infinite memory, a process need not change its location in the memory. Then even the older protection methods such as base and limit register can be used.
- learner January 04, 20131) if value == node.data then break
2) if(value < node.data )
a. if node is a right child of its parent and value is less than parent.data , move to parent
else
move to left subtree of the node
3) if(value > node.data)
a. if node is a left child of its parent and value is greater than parent.data, move to parent
else
move to right subtree of the data
4) continue until node is null or node.data == value
this would find a path whether the value exits in the subtrees of the node or anywhere else.
void findPath(Node node, int value) {
if(node == null )
throw new RtE();
while(node != null) {
System.out.println(node.data);
if (node.data == value)
return;
boolean isLeftChild = false, isRightChild = false;
Node parent = node.parent;
if(parent != null) {
if( parent.left == node)
isLeftChild = true;
else
isRightChild = true;
}
if( value < node.data) {
if(isRightChild && value < parent.data)
node = parent;
else
node = node.left;
} else {
if(isLeftChild && value > parent.data )
node = parent;
else
node = node.right;
}
}
}
Paging provides 3 things :
1) creates illusion that each process has infinite memory by moving pages to and from disk
2) eliminates external fragmentation thereby saving space
3) memory protection among processes.
If there is infinite memory, 1) and 2) won't be a matter of concern.
However 3) would still be required.
So paging would be required for protection.
- Consider the two paths as two linked lists
- find the length of both the lists and get the difference in length
- move the pointer of longer list by the difference and add every node to the path
- move pointers to both the lists till they meet and add nodes to respective paths
- if the meeting point is root add root to both the paths
- display the paths
void printPath (Node node1, Node node2) {
if(node1 == null && node2 == null)
return ;
int len1 = 0, len2 = 0;
Node temp = node1;
while(temp != null) {
temp = temp.parent;
++len1;
}
temp = node2;
while(temp != null) {
temp = temp.parent;
++len2;
}
StringBuffer path1 = new StringBuffer();
StringBuffer path2 = new StringBuffer();
if(len1 > len2 ) {
for(int i = 0; i < len1 - len2 ; i++) {
path1.append(node1.data);
node1 = node1.parent;
}
}else {
for(int i = 0; i < len2 - len1 ; i++) {
path2.append(node2.data);
node2 = node2.parent;
}
}
while(node1 != node2) {
path1.append(node1.data);
path2.append(node2.data);
node1 = node1.parent;
node2 = node2.parent;
}
if(node1 == root) {
path1.append(root.data);
path2.append(root.data):
}
System.out.println(path1.toString());
System.out.println(path2.toString());
}
- If root is equal to M , root is answer return root
- if root is less than M, M cannot fit in root , move to right
- if root is greater than M, root can be the best fit , save root, move left
Integer getBestFit ( Node root, int M){
if(root == null)
return null;
Node lastBestFit = null;
while(root != null) {
if(root.data == M)
return root.data;
if(root.data < M)
root = root.right;
else{
lastBestFit = root;
root = root.right;
}
}
if(lastBestFit == null)
return null;
return lastBestFit.data;
}
- Create a hashmap of <element, count> pairs from the first array.
- Iterate through the second array and find matching elements.
- If the count of the matching element is greater than 0, print the element and
decrease the count in the map by 1.
static void commonElements(int[] arr1, int[] arr2){
HashMap<Integer, Integer> countMap = new HashMap<Integer, Integer>();
for(int e : arr1){
if(countMap.containsKey(e)){
int count = countMap.get(e);
countMap.put(e, count + 1);
}else{
countMap.put(e , 1);
}
}
for(int e : arr2){
if(countMap.containsKey(e)){
int count = countMap.get(e);
if(count > 0){
System.out.println(e);
countMap.put(e , count - 1);
}
}
}
}
int findLastOccurrence(int[] arr, int num){
int i = 0;
int index = 0;
while(arr[index] <= num) {
index = 1 << i;
++i;
}
int left = index/2 ;
int right = index;
while(left < right){
int mid = (left + right)/2;
if(arr[mid] == num){
if( (arr[mid + 1] )!=num){
return mid;
}else{
left = mid + 1;
}
}else if(arr[mid] < num){
left = mid + 1;
}else{
right = mid - 1;
}
}
Open Chat in New Window
Could you please explain how dequeu would help in getting min and max elements for the last k days ?
- learner February 26, 2015