SDE - 1

Iterative implementation of strstr(): It returns a pointer to the first occurrence of Y in X or a null pointer if Y is not part of X. The time complexity of this solution is O(m.n) where m and n are the length of String X and Y, respectively.

// returns true if `X` and `Y` are the same

int compare(const char *X, const char *Y)
{
	while (*X && *Y)
	{
		if (*X != *Y) {
			return 0;
		}
		X++;
		Y++;
	}
		return (*Y == '\0');
}

	// Function to implement `strstr()` function
const char* strstr(const char* X, const char* Y)
{
	while (*X != '\0')
	{
		if ((*X == *Y) && compare(X, Y)) {
			return X;
		}
		X++;
	}
	return NULL;
}

The standard says that accessing a NULL ptr is “undefined behavior”. Undefined behavior can be anything, including:
Nothing at all - continue running the program as if nothing happened
Crashing the application
Corrupting application data

Phase 1: Lexical Analysis
Lexical Analysis is the first phase when compiler scans the source code. This process can be left to right, character by character, and group these characters into tokens.
Here, the character stream from the source program is grouped in meaningful sequences by identifying the tokens. It makes the entry of the corresponding tickets into the symbol table and passes that token to next phase.

Phase 2: Syntax Analysis
Syntax analysis is all about discovering structure in code. It determines whether or not a text follows the expected format. The main aim of this phase is to make sure that the source code was written by the programmer is correct or not. Syntax analysis is based on the rules based on the specific programing language by constructing the parse tree with the help of tokens. It also determines the structure of source language and grammar or syntax of the language.

Phase 3: Semantic Analysis
Semantic analysis checks the semantic consistency of the code. It uses the syntax tree of the previous phase along with the symbol table to verify that the given source code is semantically consistent. It also checks whether the code is conveying an appropriate meaning. Semantic Analyzer will check for Type mismatches, incompatible operands, a function called with improper arguments, an undeclared variable, etc.

Phase 4: Intermediate Code Generation
Once the semantic analysis phase is over the compiler, generates intermediate code for the target machine. It represents a program for some abstract machine. Intermediate code is between the high-level and machine level language. This intermediate code needs to be generated in such a manner that makes it easy to translate it into the target machine code.

Phase 5: Code Optimization
The next phase of is code optimization or Intermediate code. This phase removes unnecessary code line and arranges the sequence of statements to speed up the execution of the program without wasting resources. The main goal of this phase is to improve on the intermediate code to generate a code that runs faster and occupies less space.

Phase 6: Code Generation
Code generation is the last and final phase of a compiler. It gets inputs from code optimization phases and produces the page code or object code as a result. The objective of this phase is to allocate storage and generate relocatable machine code. It also allocates memory locations for the variable. The instructions in the intermediate code are converted into machine instructions. This phase coverts the optimize or intermediate code into the target language.

The system stack (a.k.a. call stack or just "the stack") is a place in memory for things that the heap doesn't cover. The system stack is more organized than the heap since it uses the stack data structure, where order matters. Also, the address of the next allocation is known at all times because of this organization. Allocated items are pushed on to the stack in a particular order and popped off when needed. Most importantly, the system stack is used to store information about subroutine calls (where it gets the name "call stack"). The stack stores parameters for the function and a return address where the program should pick up when the function is finished. It also reserves a space for a return value to be popped by the system on return. The piece of stack used by a subprogram is called a stack frame.

The direct approach would be to loop through all bits in an integer, check if a bit is set and if it is, then increment the set bit count.
Time Complexity: Θ(logn) (Theta of logn)
Auxiliary Space: O(1)
Brian Kernighan’s Algorithm can also be used here. 
This algorithm is based on the idea that subtracting 1 from a decimal number flips all the bits after the rightmost set bit(which is 1) including the rightmost set bit. 

For example : 

10 in binary is 00001010 
9 in binary is 00001001 
8 in binary is 00001000 

So if we subtract a number by 1 and do it bitwise & with itself (n & (n-1)), we unset the rightmost set bit. If we do n & (n-1) in a loop and count the number of times the loop executes, we get the set bit count. 
The number of times it loops is equal to the number of set bits in a given integer. 
 

Algorithm : 
1) Initialize count: = 0
 

2) If integer n is not zero
(a) Do bitwise & with (n-1) and assign the value back to n
n: = n&(n-1)
(b) Increment count by 1
(c) go to step 2
 

3)Else return count

Inorder traversal requires that we print the leftmost node first and the right most node at the end. 
So basically for each node we need to go as far as down and left as possible and then we need to come back and go right. So the steps would be : 
1. Start with the root node. 
2. Push the node in the stack and visit it's left child.
3. Repeat step 2 while node is not NULL, if it's NULL then pop the topmost node from the stack and print it.
4. Now move to node's right child and repeat step 1
5. Repeat the above steps while node is not NULL and stack is not empty

Floyd's algorithm can be used to solve this question.
Define two pointers slow and fast. Both point to the head node, fast is twice as fast as slow. There will be no cycle if it reaches the end. Otherwise, it will eventually catch up to the slow pointer somewhere in the cycle.
Let X be the distance from the first node to the node where the cycle begins, and let X+Y be the distance the slow pointer travels. To catch up, the fast pointer must travel 2X + 2Y. L is the cycle size. The total distance that the fast pointer has travelled over the slow pointer at the meeting point is what we call the full cycle.
X+Y+L = 2X+2Y
L=X+Y
Based on our calculation, slow pointer had already traveled one full cycle when it met fast pointer, and since it had originally travelled A before the cycle began, it had to travel A to reach the cycle's beginning! 
After the two pointers meet, fast pointer can be made to point to head. And both slow and fast pointers are moved till they meet at a node. The node at which both the pointers meet is the beginning of the loop.
Pseudocode :

detectCycle(Node *head) 
{
	Node *slow=head,*fast=head;
	while(slow!=NULL && fast!=NULL && fast->next!=NULL) 
	{

		slow = slow->next; 
		fast = fast->next->next; 

		if(slow==fast) 
		{
			fast = head;
			while(slow!=fast) 
			{
				slow = slow->next;
				fast=fast->next;
			}
			return slow; 
		}
	}
	return NULL; 
}

An interrupt is a special type of condition that occurs during the working of a microprocessor.
Microprocessor services the interrupt by executing a subroutine called interrupt service routine (ISR).
The interrupt can be given to the processor by the external signal(i.e. on external pins of a Microprocessor) or as a software interrupt or by the condition produced by the program.

Carrier Sense Multiple Access (CSMA) is a network protocol for carriertransmission that operates in the Medium Access Control (MAC) layer. It senses or listens whether the shared channel for transmission is busy or not, and transmits if the channel is not busy. Using CMSA protocols, more than one users or nodes send and receive data through a shared medium that may be a single cable or optical fiber connecting multiple nodes, or a portion of the wireless spectrum.

Working Principle
When a station has frames to transmit, it attempts to detect presence of the carrier signal from the other nodes connected to the shared channel. If a carrier signal is detected, it implies that a transmission is in progress. The station waits till the ongoing transmission executes to completion, and then initiates its own transmission. Generally, transmissions by the node are received by all other nodes connected to the channel.
Since, the nodes detect for a transmission before sending their own frames,collision of frames is reduced. However, if two nodes detect an idle channel at the same time, they may simultaneously initiate transmission. This would cause the frames to garble resulting in a collision.

Tip 1 : The cross questioning can go intense some time, think before you speak.

Tip 2 : Be open minded and answer whatever you are thinking, in these rounds I feel it is important to have opinion.

Tip 3 : Context of questions can be switched, pay attention to the details. It is okay to ask questions in these round, like what are the projects currently the company is investing, which team you are mentoring. How all is the work environment etc.