Last Updated on April 14, 2022 by Ria Pathak
1. Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?
Solution is to copy the data from the next node to the node to be deleted and delete the next node. Something like following.
struct Node * temp = node_ptr - > next;
node_ptr - > data = temp - > data;
node_ptr - > next = temp - > next;
free(temp);
void deleteNode(struct Node * node_ptr) {
struct Node * temp = node_ptr - > next;
node_ptr - > data = temp - > data;
node_ptr - > next = temp - > n ext;
free(temp);
}2. What are pure virtual functions in C++?
A pure virtual function (or abstract function) in C++ is a virtual function for which we don’t have implementation, in base class, we only declare it.
A pure virtual function is declared by assigning 0 in declaration.
Example of pure Virtual Function in C++:
class Base {
int x;
public:
virtual void fun() = 0;
int getX() {
return x;
}
}
// This class inherits from Base and implements fun()
class Derived: public Base {
int y;
public:
void fun() {
cout << “fun() called”;
}
};
int main(void) {
Derived d;
d.fun();
return 0;
}Output:
fun() called
3. Give real time application of stacks.
Real life examples of stack are:
- To reverse a word. You push a given word to stack – letter by letter – and then pop letters from the stack.
- An “undo” mechanism in text editors; this operation is accomplished by keeping all text changes in a stack.
Undo/Redo stacks in Excel or Word. - Language processing:
- Support for recursion
Activation records of method calls.
4. You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Write an efficient code to find the missing integer. I/P [1, 2, 4, ,6, 3, 7, 8] O/P 5
METHOD 1(Use sum formula)
Algorithm:
1. Get the sum of numbers
total = n*(n+1)/2
2 Subtract all the numbers from sum and
you will get the missing number.5. C code to find the missing number
/* getMissingNo takes array and size of array as arguments*/
int getMissingNo(int a[], int n) {
int i, total;
total = (n + 1) * (n + 2) / 2;
for (i = 0; i < n; i++)
total -= a[i];
return total;
}
/*program to test above function */
int main() {
int a[] = {
1,
2,
4,
5,
6
};
int miss = getMissingNo(a, 5);
printf("%d", miss);
getchar();
}Output: 3 Time Complexity: O(n)
There can be overflow if n is large. In order to avoid Integer Overflow, we can pick one number from known numbers and subtract one number from given numbers. This way we wont have Integer Overflow ever.
METHOD 2(Use XOR)
1) XOR all the array elements, let the result of XOR be X1.
2) XOR all numbers from 1 to n, let XOR be X2.
3) XOR of X1 and X2 gives the missing number.6. C Program for above mentioned approach
/* getMissingNo takes array and size of array as arguments*/
int getMissingNo(int a[], int n) {
int i;
int x1 = a[0]; /* For xor of all the elements in array */
int x2 = 1; /* For xor of all the elements from 1 to n+1 */
for (i = 1; i < n; i++)
x1 = x1 ^ a[i];
for (i = 2; i <= n + 1; i++)
x2 = x2 ^ i;
return (x1 ^ x2);
}
/*program to test above function */
int main() {
int a[] = {
1,
2,
4,
5,
6
};
int miss = getMissingNo(a, 5);
printf("%d", miss);
getchar();
}Output:
3
Time Complexity: O(n)
7. What is Critical Section problem?
The critical section problem is to design a protocol that ensures that no two process execute the critical section at the same time.
A solution to critical section problem must satisfy the following three requirements:
Mutual exclusion:If process is executing in its critical section , then no other processes can be executing in their critical sections.
Progress: If no process is executing in the critical section, then the decision of a process to enter a critical section cannot be made by any other process that is executing in its remainder section. The selection of the process cannot be postponed indefinitely.
Bounded Waiting:There exists a bound on the number of times other processes can enter into the critical section after a process has made request to access the critical section and before the requested is granted.
8. What are the differences between mutex and semaphores?
Semaphore is a signalling mechanism as wait() and signal() operation performed on semaphore variable indicates whether a process is acquiring the resource or releasing the resource. On the other hands, the mutex is a locking mechanism, as to acquire a resource, a process needs to lock the mutex object and while releasing a resource process has to unlock mutex object.
Semaphore is typically an integer variable whereas, mutex is an object.
Semaphore allows multiple program threads to access the finite instance of resources. On the other hands, Mutex allows multiple program threads to access a single shared resource but one at a time.
Semaphore variable value can be modified by any process that acquires or releases resource by performing wait() and signal() operation. On the other hands, lock acquired on the mutex object can be released only by the process that has acquired the lock on mutex object.
Semaphore are of two types counting semaphore and binary semaphore which is quite similar to the mutex.
Semaphore variable value is modified by wait() and signal()operation apart from initialization. However, the mute object is locked or unlocked by the process acquiring or releasing the resource.
If all the resources are acquired by the process, and no resource is free then the process desiring to acquire resource performs wait() operation on semaphore variable and blocks itself till the count of semaphore become greater than 0. But if a mutex object is already locked then the process desiring to acquire resource waits and get queued by the system till the resource is released and mutex object gets unlocked.
9. What is round robin scheduling?
Round Robin scheduling is similar to FCFS scheduling but pre-emption is added to enable the system to switch between processes.
A small unit of time called a time quantum or time slice is defined . The ready queue is treated as a circular queue , the CPU scheduler goes around the ready queue allocating the CPU to each process for a time interval of up to 1 quantum.
To implement RR scheduling , new processes are added to the tail of the ready queue which is a FIFO queue .
The scheduler picks the first process from the ready queue , sets a timer to interrupt after 1 time quantum , and dispatched the process. In case the process has CPU burst of less than 1 quantum , the process will release the CPU voluntarily.
The scheduler the proceeds to next process in the ready queue. In case the currently running process has CPU burst greater than 1 time quantum , after 1 time quantum interrupt will occur , context switch will be executed and the process will be put at the tail of the ready queue .
Given an array and a value, find if there is a triplet in array whose sum is equal to the given value. If there is such a triplet present in array, then print the triplet and return true. Else return false. For example, if the given array is {12, 3, 4, 1, 6, 9} and given sum is 24, then there is a triplet (12, 3 and 9) present in array whose sum is 24>
Solution for given question:
1) Sort the input array.
2) Fix the first element as A[i] where i is from 0 to array size – 2. After fixing the first element of triplet, generate all possible triplets and compare the sum of every triplet with the given valueC Program that returns true if there is triplet with sum equal to ‘sum’ present in A[].
bool find3Numbers(int A[], int arr_size, int sum) {
int l, r;
/* Sort the elements */
sort(A, A + arr_size);
/* Now fix the first element one by one and find the
other two elements */
for (int i = 0; i sum r--;
}
}
// If we reach here, then no triplet was found
return false;
}
/* main function */
int main() {
int A[] = {
1,
4,
45,
6,
10,
8
};
int sum = 22;
int arr_size = sizeof(A) / sizeof(A[0]);
find3Numbers(A, arr_size, sum);
return 0;
}Output:
Triplet is 4, 8, 10
Time Complexity: O(n^2)
10. Discuss Run time polymorphism vs compile time polymorphism
| S. No. | Compile time polymorphism | Run time polymorphism |
| 1. | In Compile time Polymorphism, call is resolved by the compiler. | In Run time Polymorphism, call is not resolved by the compiler. |
| 2. | It is also known as Static binding, Early binding and overloading as well. | It is also known as Dynamic binding, Late binding and overriding as well. |
| 3. | Overloading is compile time polymorphism where more than one methods share the same name with different parameters or signature and different return type. | Overriding is run time polymorphism having same method with same parameters or signature, but associated in a class & its subclass. |
| 4. | It is achieved by function overloading and operator overloading. | It is achieved by virtual functions and pointers. |
| 5. | It provides fast execution because known early at compile time. | It provides slow execution as compare to early binding because it is known at runtime. |
| 6. | Compile time polymorphism is less flexible as all things execute at compile time. | Run time polymorphism is more flexible as all things execute at run time. |
This article tried to discuss Top 10 Samsung Interview Questions. Hope this blog helps you understand the concept. If you wish to prepare for placements you can check out Placement Preparation Program