SDE - 1

Brute force solution - O(N):
Step 1: Traverse the array from 0th index to n-2th index.
Step 2: At each iteration compare current element with next element.
Step 3: If they are same then continue, else return that element.
Efficient solution - O(LogN):
Step 1: Traverse the complete array 
Step 2: Take XOR of each element
Step 3: Return the resultant XOR of complete array [As XOR of whole array will return the element occuring once]

Brute force solution - O(N^4):
Step 1: Traverse the mat1 and search for x - mat1[i][j] in mat2 linearly
Efficient solution - O(N^2):
Step 1: Traverse mat2 and store all elements in hash set
Step 2: Now traverse mat1 and find occurences of x-mat1[i][j] in hashset

Brute force solution - O(N*M): 

Step 1: Traverse list1 and for each of its nodes, find that node in list2. 

Better solution - O(N+M): 

Step 1: Update the structure of the given Node class of the linked list. Add a 'visited' field to it. 

Step 2: Traverse the first list and mark all its nodes as visited = true. 

.Step 3: Now traverse the second list and if you find any node with visited = true, return that node. 

Best solution - O(N+M): 

Step 1: Traverse the first linked list (count the elements) and make it a circular linked list (Remember the last node so that we can break the circle later on). 

Step 2: Now view the problem as finding the loop in the second linked list. Thus, the problem is solved. 

Step 3: Since we already know the length of the loop (size of the first linked list), we can traverse that many nodes in the second list, then start another pointer from the beginning of the second list. We need to traverse until they are equal, which gives us the required intersection point. 

Step 4: Remove the circle from the linked list.

Using Kadane's algorithm: 

Step 1: Initialize the variables max_so_far = INT_MIN and max_ending_here = 0. 

Step 2: Run a for loop from 0 to N-1 and for each index i: 

Step 3: Add arr[i] to max_ending_here. 

Step 4: If max_so_far is less than max_ending_here, update max_so_far to max_ending_here. 

Step 5: If max_ending_here < 0, update max_ending_here = 0. 

Step 6: Return max_so_far.

Brute force solution - O(NLogN):
Step 1: Sort the given array
Step 2: Return the kth index element
Efficient solution - O(NLogK):
Step 1: Initialize a max heap (priority queue) pq.
Step 2: For each element in the array:
Step 3: Push the element onto the max heap.
Step 4: If the size of the max heap exceeds K, pop (remove) the largest element from the max heap. This step ensures that the max heap maintains the K smallest elements encountered so far.
Step 5: After processing all elements, the max heap will contain the K smallest elements, with the largest of these K elements at the top.

Step 1: Initialize three pointers prev as NULL, curr as head, and next as NULL.
Step 2: Iterate through the linked list. In a loop, do the following:
Step 3: Before changing the next of curr, store the next node => next = curr -> next
Step 4: Now update the next pointer of curr to the prev => curr -> next = prev 
Step 5: Update prev as curr and curr as next => prev = curr; curr = next;

Step 1: Define a Node struct to represent a binary tree node. 

Step 2: Define a recursive function addNodesToMap that takes a binary tree node, a level, and a reference to an unordered map, and adds the node to the vector of nodes at its level in the unordered map. This function should then recursively call itself on the left and right subtrees. 

Step 3: Define the main reverseLevelOrder function that takes the root of the binary tree as input and returns a vector containing the nodes in reverse level order. 

Step 4: Inside the reverseLevelOrder function, create an unordered map to store the nodes at each level of the binary tree. 

Step 5: Call the addNodesToMap function on the root of the binary tree with level 0 and a reference to the unordered map to populate the map with nodes. 

Step 6: Iterate over the unordered map in reverse order of the levels and add the nodes to the result vector in the order they appear in the vectors in the unordered map. 

Step 7: Return the result vector containing the nodes in reverse level order.

Tip 1: Need to explain what a thread is, how they are made in C++, and their properties.

Tip 1: Mainly, this concept ensures multiple processes access shared resources without interfering with each other and prevents the possibility of inconsistent data due to concurrent access. 

Tip 2: Provide some real-life examples if possible.