Hot Topics
NVDIA Solution
Technical Round
Design a full adder with 2-1 mux.
A full adder adds binary numbers and accounts for values carried in as well as out. A one-bit full adder adds
three one-bit binary numbers, often written as A, B, and Cin; A and B are the operands, and Cin is a bit carried in
from the previous less significant stage. The full adder is usually a component in a cascade of adders, which add
8, 16, 32, etc. bit binary numbers. The circuit produces a two-bit output, output carry and sum typically
represented by the signals Cout and Sum, The one-bit full adder’s truth table is given in the next section
The value of sum is given by Sum = 2 x Cout + S.
The dataflow Boolean logic for full adder is given by
Sum(S) = A XOR B XOR Cin.
Carry(C) = (A AND B) OR (Cin AND (A XOR B)).
Where A and B are the 1-bit binary inputs to the full adder.
Identify the number of 1s in an integer is odd or even
To determine if the number of 1s in an integer is odd or even, you need to count the number of 1s in its binary representation. If the number of 1s is odd, the integer has an odd number of 1s. If the number of 1s is even, the integer has an even number of 1s.
Is there any benefit to use cache if there is read miss for every access?
No, if there is a cache miss for every access, the cache serves no purpose and its use would only add overhead without any performance improvement. The purpose of a cache is to provide faster access to frequently used data by storing a copy of the data in a small, fast memory close to the processor. If every access misses the cache, then the processor has to go to the slower main memory every time, resulting in a performance degradation instead of improvement.
There is a singly linked list of integer type, write a function that takes the head pointer, and prints the list in reverse order.
Here’s an implementation of a function to reverse print a singly linked list in C:
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
void reversePrint(struct node *head) {
if (head == NULL) {
return;
}
reversePrint(head->next);
printf("%d ", head->data);
}This implementation uses a recursive approach to traverse the linked list and print its elements in reverse order. It first calls `reversePrint` on the next node, and then it prints the data of the current node. This way, when the function returns, the elements are printed in the reverse order.
How is processor performance affected when the instruction cache hit latency increases? How do you overcome that?
Use small, simple cache
Split & multi-banked cache organization (instruction cache and data cache)
Use virtual indexing and physical tagging rather than virtual address to reduce the time caused by translations.
Use way prediction to predict the index
Pipeline the write operation, do write the word to block and cache in background
How to delete a node in a singly linked list without access to the list header?
It is not possible to delete a node in a singly linked list if you do not have access to the list header, because in a singly linked list, you need access to the previous node to update its next pointer and effectively delete a node. However, if you have access to the node to be deleted, you can change its data and next pointer in the following way:
struct node *temp = nodeToDelete->next;
nodeToDelete->data = temp->data;
nodeToDelete->next = temp->next;
free(temp);
This effectively replaces the node to be deleted with the next node, and then frees the memory of the old next node. Note that this approach modifies the list’s data and only works for singly linked lists.
Build the func f=(ab+c`)` using min mux 2:1
You can build the function f = (a * b + c')' using a 2:1 multiplexer as follows:
Implement the product of
aandbusing an AND gate.Implement the sum of
a * bandc'using an OR gate.Use the output of the OR gate as the input to the NOT gate to implement the complement of the sum.
Connect the output of the NOT gate to the select input of the 2:1 multiplexer.
Connect the inputs
a * bandc'to the data inputs of the multiplexer.Connect the output of the multiplexer to the output of the function
f.
The truth table of the function f can be represented as:
a | b | c’ | f |
|---|---|---|---|
0 | 0 | 0 | 1 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 0 |
1 | 1 | 1 | 1 |
The 2:1 multiplexer can be implemented using a combination of AND, OR, and NOT gates.
Why the cover of a gutter man hole is circular in shape?
The cover of a gutter man hole is circular in shape because of two main reasons:
It is easy to handle
It can withstand more weight and speed rather than square manhole.
You are driving on a racetrack. The first lap you averaged 60mph. How fast do you have to drive on the second lap to average 120mph on both laps?
If you averaged 60 mph on the first lap, the total time to complete the first lap is t1 = d1/60, where d1 is the distance of the first lap.
To average 120 mph on both laps, the total time to complete both laps is t2 = 2d2/120, where d2 is the distance of the second lap.
Since the distance of both laps is the same, we have d1 = d2 = d, and therefore t1 = d/60 and t2 = 2d/120.
We want to find the speed at which you have to drive on the second lap such that the total time to complete both laps is the same. Hence, we set t1 = t2 and solve for the speed v on the second lap:
d/60 = 2d/120
d/60 = d/60
So, you have to drive at 60 mph on the second lap to average 120 mph on both laps.
Given 2 unsigned ints a and b, return 1 unsigned int = a/b, rounded to nearest int without float operation
To perform integer division without using floating-point operations, you can use a bitwise operation and bit shifting. Here’s how you can round the result of the division to the nearest integer:
unsigned int divide_and_round(unsigned int a, unsigned int b) {
unsigned int quotient = a / b;
unsigned int remainder = a % b;
if (remainder * 2 >= b) quotient++;
return quotient;
}
This code calculates the quotient of a / b and the remainder of a % b. If the remainder multiplied by 2 is greater than or equal to b, it means that rounding up the quotient is closer to the true result. So the quotient is incremented by 1 to round to the nearest integer.
Complete the C function (body) that uses recursion to determine if the string is a palindrome
Here’s a C function that uses recursion to determine if a given string is a palindrome:
#include <string.h>
int is_palindrome(char *str, int start, int end) {
if (start >= end) return 1;
if (str[start] != str[end]) return 0;
return is_palindrome(str, start + 1, end – 1);
}
int is_palindrome_wrapper(char *str) {
int len = strlen(str);
return is_palindrome(str, 0, len – 1);
}
The is_palindrome_wrapper function takes the string as input, and calls the recursive function is_palindrome with the start and end indices of the string. The is_palindrome function compares the first and last characters of the string and continues recursively with the sub-string between these characters. If the first and last characters don’t match, the function returns 0. If all characters match and the start index is greater than or equal to the end index, the function returns 1, indicating that the string is a palindrome.
5 bags, each bag has some balls. 1 bag has faulty balls. There are faulty balls weighing 1.1kg and good ones weighing 1kg. There is a weighing machine. Determine in how many measurements you can find the bag with faulty balls and which bag contains it.
To determine which bag contains the faulty balls in the minimum number of weighings, you can use the binary search algorithm. Here’s how you can do it:
Weigh two bags at a time and compare their weights.
If the two bags weigh the same, it means that neither of them contain the faulty balls.
If one of the bags weighs more, it contains the faulty balls.
If you can’t determine the bag with faulty balls from the first weighing, divide the remaining bags into two sets and weigh one set against the other.
Repeat the process until you’ve determined which bag contains the faulty balls.
In this case, you will need a maximum of 4 weighings to determine which bag contains the faulty balls.
Here’s the sequence of weighings you can follow:
Weigh bags 1 and 2.
If they weigh the same, weigh bags 3 and 4.
If they weigh the same, the faulty bag is 5. If not, weigh bags 1 and 3.
If the bags weigh the same, the faulty bag is 2. If not, the faulty bag is the heavier one.
What is the format of the floating point number? What does the following code do? Does it terminate? Float f,g; f=0; do{ g=f++; } While ((f-g)!=0);
and quadruple-precision floating-point numbers.
The following code initializes a floating-point variable f to 0 and uses a do-while loop to increment f and assign the result to g. The loop continues until the difference between f and g is not equal to 0.
However, this code will not terminate because there is no limit on the number of iterations in the loop, and f can continue to increment indefinitely. The difference between f and g will never be exactly equal to 0 due to the nature of floating-point representation and the fact that not all real numbers can be exactly represented as floating-point numbers.
As a result, the loop will run indefinitely and cause an infinite loop.
Tell me ten features of C++ (that are not in C) that have nothing to do with object oriented programming.
C++ supports both procedural and object oriented programming paradigms
C++ is a superset of C
C++ supports reference variable
C++ supports bottom-up approach
C++ has 97 keywords
C++ has access modifiers
C++ has rich library
Say the program you are running has stack overflow. You want to know when and where this happens, but you don’t want to use debuggers, because they slow. How would you do this?
If you want to detect stack overflow without using debuggers, you can use the following techniques:
Modify the program to keep track of the stack usage: You can modify the program to keep track of the current stack size and compare it to the maximum stack size. If the current stack size exceeds the maximum, you can print a message indicating a stack overflow has occurred.
Use a signal handler: Stack overflow can cause a segmentation fault, which can be caught and handled by a signal handler in your program. You can set a signal handler for the
SIGSEGVsignal, which will be triggered when the program encounters a segmentationfault. In the signal handler, you can print a message indicating that a stack overflow has occurred.
Enable stack protection: Some operating systems and compilers provide mechanisms for stack protection, such as the
-fstack-protectorflag in GCC. Enabling stack protection can cause the program to crash with a specific error message if a stack overflow occurs.Inspect core dumps: If the program crashes due to a stack overflow, you can inspect the core dump generated by the operating system to determine the cause of the crash and the location of the stack overflow.
Note that these techniques may not be foolproof and may not provide the exact location of the stack overflow in all cases, but they can give you a rough idea of where the issue is happening and allow you to diagnose and fix the problem.
How to know if two linked list collide
To check if two linked lists collide, you can compare the reference/memory addresses of their corresponding nodes. If the memory addresses are the same, it means both linked lists are pointing to the same node, which indicates a collision. You can use a hash set to store the memory addresses of nodes in one linked list, and then traverse the other linked list to see if any of its nodes’ memory addresses exist in the hash set. If a match is found, it means both linked lists are colliding.
Implement a linked list structure and insert routine in C. Make it thread safe.
Here’s an example implementation of a linked list structure and insert routine in C, using a mutex for thread safety:
#include <pthread.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct LinkedList {
struct Node* head;
pthread_mutex_t lock;
};
void init(struct LinkedList* list) {
list->head = NULL;
pthread_mutex_init(&list->lock, NULL);
}
void insert(struct LinkedList* list, int data) {
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
pthread_mutex_lock(&list->lock);
if (list->head == NULL) {
list->head = newNode;
} else {
struct Node* temp = list->head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
pthread_mutex_unlock(&list->lock);
}
In this implementation, a mutex (pthread_mutex_t) is used to ensure exclusive access to the linked list structure while inserting new nodes. The pthread_mutex_lock and pthread_mutex_unlock functions are used to lock and unlock the mutex, respectively, while accessing the linked list. This ensures that multiple threads cannot modify the linked list simultaneously, avoiding race conditions.
Difference between const char * and char const *
Both const char * and char const * are used to declare a pointer to a constant character. They are equivalent and mean that the pointed character is a constant and cannot be modified through this pointer. There is no difference in their meaning or usage.
Automata Fixing