Day2: FAQ Interview questions – Coding

This is 2nd Day, where I have covered few major areas to cover most of the FAQ questions during the coding interview.
Feel free to ask questions in the comments (If any).

Programs:

1. Majority of an element
2. FizzBuzz problem.
3. Evaluating a postfix expression.
4. Calculating a Column number by column title\ column header.
5. Find Palindrome of a string by ignoring special characters.
6. Delete adjacent duplicates from a string.

Majority of an element :

• Majority of an element is possible if the majority of numbers are more than 50%
• If majority is not 50% then function should return -1.
• Simple logic
  if( cap == num )
  count++
  else
  count —
  if(count == 0)
  {
  cap = num;
  count=1;
  } check for majoirty greater than n/2.
• alternative approach: sort and return middle element.

int getMajorityElement(vector &vec)
{
   int cap = vec.at(0);
   int count = 1;

   for (int num : vec)
   {
       if (cap == num)
       {
           count++;
       }
       else
       {
           count--;
           if (count == 0)
           {
               cap = num;
               count = 1;
           }
       }
   }

   int count2 = 0;
   for (int num : vec)
   {
       if (num == cap)
           count2++;
   }

   if (count2 > vec.size() / 2) return cap;
   else
   return -1;
}

2. FizzBuzz problem.

For each number multiple of 3 will replace with FIZZ, if the number is of multiple of 5 then replace those numbers with BUZZ and if the number is of multiple of 3 & 5 then replace numbers with FIZZBUZZ.

Example:

Multiple of 3 = FIZZ

Multple of 5 = BUZZ

Multiple of 3 & 5 = FIZZBUZZ

vector<string> FizzBuzz(int N)
{
	vector<string> tempVec;
	for (int i = 1; i <= N; i++)
	{
		if (i % 3 == 0 && i % 5 == 0)
			tempVec.push_back("FIZZBUZZ");
		else if (i % 3 == 0 )
			tempVec.push_back("FIZZ");
		else if (i % 5 == 0)
			tempVec.push_back("BUZZ");
		else
			tempVec.push_back(to_string(i));
	}
	return tempVec;
}

3. Evaluating a postfix expression:

Let us take 2 types of expressions:
Infix: (4+ (13/5))
PostFix: 4, 13 , 5, /, +
Evaluated Resut = 6

1. In above example, move operator out of closing bracket to generate postfix from Infix expression.
2. Explination:

• Push 4 into stack.
• push 13 into stack
• push 5 into stack
• next if / operator, hence pop last two element from stack and perform /operation on elements (operator2/ oeprator1).
• Again push back result into stack. i.e. 13/5 = 2.6 ( 2 as int push to stack) – Stack value – 4, 2
• next if + operator, hence pop last two element from stack and perform +operation on elements(operator2 + oeprator1).
• Again push back result into stack. i.e. 4+2 =6 ( 6 as int push to stack) – Stack value – 6
  

int evalutePostfixExpression(vector<string> &token)
{
	stack<int> st;
	for (int i = 0; i < token.size(); i++)
	{
		//Operator
		if (token[i] == "+" || token[i] == "-" || token[i] == "*" || token[i] == "/") 
		{
			int operand1 = st.top();
			st.pop();
			int operand2 = st.top();
			st.pop();

			if (token[i] == "+") {
				st.push(operand2 + operand1);
			}
			else if (token[i] == "-") {
				st.push(operand2 - operand1);
			}
			else if (token[i] == "*") {
				st.push(operand2 * operand1);
			}
			else if (token[i] == "/") {
				st.push(operand2 / operand1);
			}
			else
			{
				throw "Invalid operator";
			}
		}
		else //operand
		{
			st.push(atoi(token[i].c_str()));
		}
	}
	return st.top();
}

4. Calculating a Column number by column title\ column header:

Return Column number by column title.
Example: A, AA, AAA, ZY

Always start from right.

1. A – 1 (ASCII = A-64)
2. AA –
   A = 1 * 1 = 1 -> ( value of A * pow )
   A = 1 + 26 * 1 = 27 -> result + pow* value of A
3. AAA –
   A = 1
   AA = 27
   AAA = 27 + 26*26 * 1 = 703
4. ZY –
   Y – 25* 1 (value of Y * pow)
   Z – 25 + 26 * 26 = 705 ( result + value of Y * pow)

int titleToNumber(string S)
{
	int n = S.size();
	long long pow = 1;
	int ans = 0;
	for (int i = n - 1; i >= 0; i--)
	{
		ans = ans + ((S[i] - 64)*pow);
		pow *= 26;
	}
	return ans;
}

5. Find Palindrome of a string by ignoring special characters:

Finding palindrome is simple where we compare the last element with the first element until it reaches the middle. Now to ignore special characters C++ provides an API “isalnum”.

bool findPalindromeOfSentence(string A)
{
   int n = A.size();
  int start = 0;
  int end = n - 1;
  while (start <= end)
  {
      while (start < end && !isalnum(A[start])) start++;
      while (start < end && !isalnum(A[end])) end--;

      if (toupper(A[start]) != toupper(A[end])) 
          return false;
      start++;
      end--;  
  }
  return true;
}

6. Delete adjacent duplicates from a string.

This is a simplest approach to delete adjucent duplicate from a string. Here we push each charecter of a string to stack and compare with top most element.

string deleteAdjacentDuplicates(string A)
{
   stack St;
   int len = A.size();
   St.push(A.at(0));
   for (int i = 1; i < len; i++)
   {
       if (!St.empty() && A.at(i) == St.top())
       {
           St.pop();
       }
       else
       {
           St.push(A.at(i));
       }
   }

   string ans;
   while (!St.empty())
   {
       ans.push_back(St.top());
       St.pop();
   }
   reverse(ans.begin(), ans.end());
   return ans;
}