Spock
BAN USERTypical interview question from OS are -
1. What are deadlocks? Deadlock prevention, deadlock avoidance and deadlock detection.
2. What are semaphores and mutex? Difference between semaphores and mutex? Difference between semaphores and monitors?
3. What are processes? What are threads? Difference between process and thread? How threads work?
4. What is virtual memory? How is virtual memory different from RAM? What are pages? What is page fault? Different algos for page fault?
5. What is internal and external fragmentation? What is segmentation?
6. What is a kernel? What are system calls? Difference between kernel threads and user threads?
7. Use of fork() system call to create child processes.
Well a process can either be single threaded or multi threaded. By increasing the number of threads though you are increasing the parallality of the system but you are also increasing the load on the system. More number of threads means more resource utilization for the same amount of work. So until you are working on a distributed system or on a system in which you want to do a lot of parallel processing than only you shold go for multi threading. Else single thread for a process is sufficient and best.
I hope I am clear. Thank you
Here is the psudo code -
for each element x in C
find a pair A[i], B[j] from A and B such that A[i] + B[j] = -x
end
The outer loop will run for O(n) and inner loop also for O(n), so total complexity will be O(n^2).
To find a pair A[i], B[j] s.t A[i] + B[j] = k.
First make i point to the start of array A and point j to the end of array B.
check -
1. If A[i] + B[j] == k, we found our elements so just exit.
2. If A[i] + B[j] > k, we have to decrease our sum. Decrement j.
3. If A[i] + B[j] < k, we have to increase our sum. Increment i.
So this will run for O(n). Thus making the complexity of the complete method as O(n^2).
Here is the psudo code -
for each element x in C
find a pair A[i], B[j] from A and B such that A[i] + B[j] = -x
end
The outer loop will run for O(n) and inner loop also for O(n), so total complexity will be O(n^2).
To find a pair A[i], B[j] s.t A[i] + B[j] = k.
First make i point to the start of array A and point j to the end of array B.
check -
1. If A[i] + B[j] == k, we found our elements so just exit.
2. If A[i] + B[j] > k, we have to decrease our sum. Decrement j.
3. If A[i] + B[j] < k, we have to increase our sum. Increment i.
So this will run for O(n). Thus making the complexity of the complete method as O(n^2).
It will need 6 comparisons.
1. First make the array such that a[1] < a[2], a[4] < a[5] and a[1] < a[4].
a. compare a[1] and a[2]. swap if necessary.
b. compare a[4] and a[5]. swap if necessary.
c. compare a[1] and a[4]. if a[4] is smaller than a[1] then swap a[1] with a[4] and s[2] with a[5].
2. if a[3] > a[2]. if a[2] > a[4], median = min(a[2], a[5]) else median = min(a[3], a[4]).
3. if a[3] < a[2]. if a[3] > a[4], median = min(a[3], a[5]) else median = min(a[2], a[4]).
So in total 6 comparisons.
To extend it for a list of size n, use select algorithm (media of medians algorithm).
Actually it is not a RULE that a stack will always grow downwards and the heap will always grow upwards. It depends on the OS that you are using. But ya in most of the modern systems stack generally grows downwards and heap grows upwards.
In the modern system there is actually no chance of collision. If the stack is full and it tries to enter into the heap area then you will get a stack overflow error. On the other hand if heap is full then the call to "malloc()" will return null. Now it depends on the programmer to check whether malloc() returned null or not.
Hope I am clear.. :)
Here is the perfectly running code. I have used reverse function to reverse the sublist.
#include<stdio.h>
#include<stdlib.h>
struct node {
int data;
struct node *next;
};
void push(struct node **headref, int dat) {
struct node *newnode = malloc(sizeof(struct node));
newnode->data = dat;
newnode->next = *headref;
*headref = newnode;
}
void reverse(struct node **headref) {
struct node *first, *rest;
first = *headref;
if(first == NULL) {
return;
}
rest = first->next;
if(rest == NULL) {
return;
}
reverse(&rest);
first->next->next = first;
first->next = NULL;
*headref = rest;
}
void correct_list(struct node **headref) {
struct node *current = *headref;
struct node *mark1, *mark2, *root;
while(current->next != NULL && current->data < current->next->data) {
mark1 = current;
current = current->next;
}
current = mark1->next;
while(current->next != NULL && current->data > current->next->data) {
current = current->next;
}
mark2 = current->next;
current->next = NULL;
root = mark1->next;
reverse(&root);
mark1->next = root;
while(root->next != NULL) {
root = root->next;
}
root->next = mark2;
}
int main() {
struct node *root = NULL;
push(&root, 10);
push(&root, 9);
push(&root, 5);
push(&root, 6);
push(&root, 7);
push(&root, 8);
push(&root, 4);
push(&root, 3);
push(&root, 2);
push(&root, 1);
correct_list(&root);
while(root != NULL) {
printf("%d ",root->data);
root = root->next;
}
printf("\n");
system("pause");
return 0;
}
@prashant
He made the constructor of the class private. Now if any of the child class try to create an object of the base class they will not be able to do it. For the second condition (i.e we should be able to make an object of base class) he made a static function which is creating an object of the base class.
Thus both the conditions are fulfilled.
Well your code doesn't work when the power is negative (i.e for negative b). You just have to change it a little bit. Add two lines to the code and everything will be ok.
if(b%2==0)
return(temp*temp);
else {
if(b > 1) {
return(temp*temp*a);
}
else {
return ((temp * temp)/a);
}
}
Well this problem can be solved by taking a path[] array and storing all the elements in the array while moving to a particular path and as soon as we reach a leaf node just print the path array. Here is the working code.
#include<stdio.h>
#include<stdlib.h>
struct node {
struct node *left;
struct node *right;
int data;
};
struct node *newnode(int dat) {
struct node *newone = malloc(sizeof(struct node));
newone->data = dat;
newone->left = NULL;
newone->right = NULL;
return newone;
}
struct node *insert(struct node *root, int dat) {
if(root == NULL) {
return newnode(dat);
}
if(dat <= root->data) {
root->left = insert(root->left, dat);
}
else {
root->right = insert(root->right,dat);
}
return root;
}
int height(struct node *root) {
if(root == NULL) {
return 0;
}
int ldepth = height(root->left);
int rdepth = height(root->right);
if(ldepth > rdepth) {
return (ldepth+1);
}
else {
return (rdepth +1);
}
}
void arrayprint(int path[], int n) {
int i;
for(i = 0; i < n; i++) {
printf("%d ", path[i]);
}
printf("\n");
}
void printpath(struct node *root, int path[], int pathlen) {
if(root != NULL) {
path[pathlen++] = root->data;
}
if(root->left == NULL && root->right == NULL) {
arrayprint(path, pathlen);
}
else {
printpath(root->left, path, pathlen);
printpath(root->right, path, pathlen);
}
}
int main() {
struct node *root = NULL;
root = insert(root,6);
root = insert(root,4);
root = insert(root,2);
root = insert(root,5);
root = insert(root,9);
root = insert(root,8);
root = insert(root,10);
int h = height(root);
int path[h], pathlen = 0;
printpath(root,path,pathlen);
system("pause");
return 0;
}
Well this is just a simple recursion.
int check(struct node *root1, struct node *root2) {
if(root1 == NULL && root2 == NULL) {
return 1;
}
else if(root1 && root2) {
return(root1->data == root2->data && check(root1->left,root2->left) && check(root1->right,root2->right));
}
else {
return 0;
}
}
Well the binary approach is best to solve such kind of problems. Suppose you have 1000 wine bottles so you require 10 rats to test these bottles for poison (as 2^10 = 1024, with 10 rats you can check as many as 1023 bottles) and voila we are given exactly 10 rats. So just in 1 trial we can detect all the poisonous bottles. The trick is assign each rat a position. For example rat 1 will be at position 0, rat 2 will be at position 1 and so on....Let us take a shorter case in which number of bottles are only 3 since 2^1 < 3 < 2^2, we require at least 2 rats to check which of the bottles are poisonous...
Start moving from bottle 1. 1 can be represented in binary as 1 only so the rat at position 0 will take a sip from that bottle. Now 2 is represented as 10 in binary, so the rat at the position 1 will take a sip from that bottle. Now 3 is represented as 11 in binary so rats at position 0 as well as position 1 will take a sip from that bottle. Now if rat at position 1 dies it means bottle 2 was poisonous, if rat at position 0 dies it means bottle 1 was poisonous and if both rat dies it means bottle 3 was poisonous.
I think it will give you some random answer. It is checking for the element at position a[99][j] in a loop, now it depends that which element is at that memory location. If ever in the whole loop that element comes out to be smaller than k then k's value will be updated else it will print 99.
- Spock July 06, 2012Well 1,2,3,5 will show undefined behavior because of following reasons -
1. The unary operator ++ is always very ambiguous and it's precedence changes from machine to machine, so at a particular machine you just can't predict whether the a[i] will get the new or old value of i, thus this is undefined.
2. It will be an integer overflow. As you cannot increase the value of INT_MAX and try to print it with integer specifier, as it is the maximum value of int.
3. Here the width of int is 32 and you are shifting 1 left by >= width which will cause undefined behavior.
5. It is very obvious that you cannot use &arr[6] as it will be an address of just a random chunk of memory and it will always give an undefined result.
Here you are actually setting the width of the variable a as 1bit but since you have declared a as "signed" int, hence it will reserve one bit for the sign of the number. So with a variable 1 bit wide you can just store 0 or -1(as 1 will be considered -1 because 1 is used to indicate the negative sign in signed integers) hence when you try to pass value 1 to a it will actually have a value -1. To get rid of this you can declare your variable unsigned like "unsigned int a:1" will do. Or you can increase the width of a. I hope I am clear.
You can also try an example where you set the width of a as 2 and try giving it a value "2". Since the binary representation of 2 is "10", It will treat 1 as a sign bit and will store -0 or 0 as the result.
No, the matrix will be [1 1; 1 0] only. Check it for small cases.
If you raise this matrix to the power of n then the result would be [F(n+1) F(n); F(n) F(n-1)]. Since it is easy to just return the (0,0) element of the matrix, I returned F[0][0] which is actually the "(n+1)th" fabonacci number.
Another approach is to use recursion. Well to use recursion to solve this problem is a bit tricky.
Here is the code.
void reverse(struct node **headref) {
struct node *first = *headref;
struct node *rest;
if(first == NULL) {
return;
}
rest = first->next;
if(rest == NULL) {
return;
}
reverse(&rest);
first->next->next = first;
first->next = NULL;
*headref = rest;
}
Well there are actually n number of ways to reverse a linked list. One way is to simply a make an empty linked list and while traveling through the nodes of the current linked list use a push function (which is used for pushing elements in stack) to push the elements in the result linked list. Here is the code.
#include<stdio.h>
#include<stdlib.h>
struct node {
int data;
struct node *next;
};
void push(struct node **headref, int num) {
struct node * newnode = malloc(sizeof(struct node));
newnode->data = num;
newnode->next = *headref;
*headref = newnode;
}
void reverse(struct node **headref) {
struct node *current = *headref;
struct node *result = NULL;
while(current != NULL) {
push(&result, current->data);
current = current->next;
}
*headref = result;
}
int main() {
struct node *head = NULL;
push(&head,1);
struct node *tail;
tail = head;
int i;
for(i = 2; i <= 5; i++) { //Here we are making a linked list {1,2,3,4,5} with head pointing to 1.
push(&(tail->next),i);
tail = tail->next;
}
reverse(&head);
while(head != NULL) { //After calling reverse the output will be printed as {5,4,3,2,1}.
printf("%d ", head->data);
head = head->next;
}
system("pause");
return 0;
}
Well the pointers are equal because they both are pointing to the same string. The above code can also be written as
char *p = "hello";
char * q = p;
Now this is clear that both p and q are "equal". But they both are at different memory locations and there address would be different. This is because the same memory location cannot be allocated to two members.
Well what you are asking is to actually find the nth fibonacci number in O(log n) time which is possible by using the dynamic programming approach. After that you can just multiply it by 2.
The matrix { {1,1,}, {1,0} } when raised to the power of n will give the (n+1)th fibonacci number at its (0,0) position.
Here is the working code to find the nth fibonacci number in O(log n) time -
void multiply(int F[2][2], int M[2][2])
{
int x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
int y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
int z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
int w = F[1][0]*M[0][1] + F[1][1]*M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
void power(int F[2][2], int n)
{
if( n == 0 || n == 1)
return;
int M[2][2] = {{1,1},{1,0}};
power(F, n/2);
multiply(F, F);
if( n%2 != 0 )
multiply(F, M);
}
int fib(int n)
{
int F[2][2] = {{1,1},{1,0}};
if(n == 0)
return 0;
power(F, n-1);
return F[0][0];
}
int main()
{
int n = 9;
printf("%d", fib(9));
getchar();
return 0;
}
Well it visited IIIT Allahabad too.
- Spock September 20, 2012