SDE - Intern

The basic idea of this approach is to iterate through all the possible pairs of indices and check if duplicate elements exist satisfying the given constraint in the problem statement. 

Consider the following steps:
Create a loop and start traversing the given array/list using a variable ‘i’ such that 0 <= i < ‘N’.
In a nested loop, start traversing the array/list using a variable ‘j’ such that 0 <= j < i and for each pair of (i, j) check:
If | i - j | <= ‘K’ and ARR[i] = ARR[j], then duplicate elements with given constraint exist in the array/list, therefore return “Yes”.
Else, return false.
Time Complexity
O(N^2), where ‘N’ is the number of elements in the given array/list.

Since we are trying to consider every pair of indices in the given array/list. So the overall time complexity will be O(N^2).
Space Complexity
O(1)
Since we are not using any extra space other than the few variables. So the overall space complexity will be O(1).
code: 
bool containsNearbyDuplicates(vector &arr, int k)
{
// Start traversing the array.
for (int i = 0; i < arr.size(); i++)
{
for (int j = 0; j < i; j++)
{
// Check if current pair satisfies the condition.
if (abs(i - j) <= k && arr[i] == arr[j])
{
return true;
}
}
}

return false;
}

Approach:
Make use of the stack. Traverse the string and push the current character in the stack if it is an opening brace. Else pop from the stack. If it is the corresponding starting brace for the current closing brace, then move to the next character of the string otherwise, return false.
If after complete traversal, if the stack is empty, then the string is balanced else, it is not balanced.

Algorithm:
Declare a character stack.
Now traverse the string.
1- If the current character is a starting bracket ( ‘(’ or ‘{’ or ‘[’ ), then push it to stack.
2- If the current character is a closing bracket ( ‘)’ or ‘}’ or ‘]’ ), then pop from stack, and if the popped character is the matching starting bracket, then fine 
else parenthesis is not balanced.
After complete traversal, if there is some starting bracket left in the stack, then “not balanced”.
Otherwise, the string is balanced.
Time Complexity
O(N), Where ‘N’ is the length of the string.
The traversal of the string is done only once. Hence, the O(N) time complexity.
Space Complexity
O(N), Where ‘N’ is the length of the string.
As the maximum stack size reaches the length of the string, thus the O(N) space complexity.

Code:
bool isValidParenthesis(string s) 
{ 
// Make an inbuilt stack.
stack st; 
char x; 

// Traversing int 's'.
for (int i = 0; i < s.length(); i++) 
{ 
if (s[i] == '(' || s[i] == '[' || s[i] == '{') 
{ 
// Push the element in the stack .
st.push(s[i]); 
continue; 
} 

if (st.empty()) 
{
return false; 
}

// Store the top element.
x = st.top(); 
st.pop(); 

// Check for opening braces in stack of corresponding closing braces.
switch (s[i]) { 
case ')': 

if (x == '{' || x == '[') 
{
return false; 
}
break; 

case '}': 

if (x == '(' || x == '[') 
{
return false; 
}
break; 

case ']': 

if (x == '(' || x == '{')
{
return false;
}
break; 
} 
}

We can create a new array of integers. As soon as we find a non-zero element, we can directly insert it into our new array. After that, we can insert all the left zero’s. 
We can easily calculate the number of left zeroes as :
Size of original array = size of new array + number of zero’s (since we only took non-zero elements.

Algorithm : 
Initialise a non-zero pointer with 0 value.
Start traversing the array until we reach the end,
If a non-zero element is found, insert it in new array. Else,
If a zero element is found, just continue.
After we reach the end, total number of zero’s will be original array size - new array size.
Insert these many zeros into new array.
Time Complexity
O(N)
Since we are maintaining two pointers, and as soon as a non-zero pointer reaches the end, we stop. So the maximum numbers we are visiting is ‘N’ therefore complexity is O(N)
Space Complexity
O(N) 
Since we are creating a new array.

Code:
void pushZerosAtEnd(std::vector &arr) {
int zptr = -1;
int nzptr = -1;
int n = arr.size();
for (int i = 0; i < n; i++) {
if (arr[i] == 0) {
zptr = i;
break;
}
}

if (zptr == -1) {
return;
}

for (int i = zptr + 1; i < n; i++) {
if (arr[i] != 0) {
nzptr = i;
break;
}
}

if (nzptr == -1) {
return;
}

while (nzptr < n) {
// Swapping.
int tmp = arr[zptr];
arr[zptr] = arr[nzptr];
arr[nzptr] = tmp;

zptr++;
while (nzptr < n && arr[nzptr] == 0) {
nzptr++;
}
}
}

Tip: Clear B+ Tree concepts in Data Structures.

Answer: c. Internal node

Step 1: Traverse the linked list starting from the head node.
Step 2: Keep track of the previous, current, and next nodes as you iterate through the list.
Step 3: At each node, update the next pointer to point to the previous node instead of the next node.
Step 4: Move to the next node and continue the process until you reach the end of the list.
Step 5: Once the end of the list is reached, update the head pointer to point to the last node (which was originally the tail).
Step 6: Return the head pointer as the new head of the reversed linked list

Tip 1 : Be confident.
Tip 2 : Be prepared for scenario-based questions like - what you will do in case of conflict.

Tip 1:Strengths: "I'm good at organizing things and getting tasks done efficiently. Also, I enjoy working with others and am pretty good at communicating ideas."
Tip 2: Weaknesses: "Sometimes I can be too focused on details, which can slow me down a bit. I'm working on finding a balance between being thorough and keeping things moving smoothly."

Tip 1 : Tell the truth.
Tip 2 : Be positive.