SDE - 1

Ayush read about irreducible fractions in the school and made an expression ‘EXPRESSION’ of fraction addition and subtraction.

Note:

An irreducible fraction is a fraction in which the numerator and denominator are integers that have no other common divisors than 1.

Example: 2/3, 8/9, 0/1 are irreducible fractions, where 8/12, 9/12 are not irreducible fractions. 

Expression ‘EXPRESSION’ contains integers from '0' to '9', and characters '/', '+' and '-'.

Each fraction will be an irreducible fraction and will be in the format of ±(numerator/denominator).

Ayush does not know how to solve the expression he made, so he gave you the expression to solve. Your task is to solve the expression.

Note:

Ayush expects your answer to be an irreducible fraction, so if your answer is an integer, convert it into an irreducible fraction by putting 1 in the denominator.

For example, if your answer is "9", then print "9/1" (without quotes). 

You are given an array/list of ‘N’ integers. You are supposed to return the maximum sum of the subsequence with the constraint that no two elements are adjacent in the given array/list.

Note:

A subsequence of an array/list is obtained by deleting some number of elements (can be zero) from the array/list, leaving the remaining elements in their original order.

You have been given a Binary Tree of distinct integers and two nodes ‘X’ and ‘Y’. You are supposed to return the LCA (Lowest Common Ancestor) of ‘X’ and ‘Y’.

The LCA of ‘X’ and ‘Y’ in the binary tree is the shared ancestor of ‘X’ and ‘Y’ that is located farthest from the root.

Note :

You may assume that given ‘X’ and ‘Y’ definitely exist in the given binary tree.

For example :

For the given binary tree

LCA of ‘X’ and ‘Y’ is highlighted in yellow colour.

You are given two strings BEGIN and END and an array of strings DICT. Your task is to find the length of the shortest transformation sequence from BEGIN to END such that in every transformation you can change exactly one alphabet and the word formed after each transformation must exist in DICT.

Note:

1. If there is no possible path to change BEGIN to END then just return -1.
2. All the words have the same length and contain only lowercase english alphabets.
3. The beginning word i.e. BEGIN will always be different from the end word i.e. END (BEGIN != END).

Explain about the different Databases you have worked with. Differentiate between SQL and NoSQL databases. Discussion in detail about ACID compliance in SQL vs CAP Theorem in NoSQL. Discussion on indexing in RDBMS and the internal data structure used (B-Tree). Had a discussion about scalability in DBMS and topics such as sharding etc. Discussion on Joins in SQL and a few SQL queries.

Design a Commodity Exchange using OOPs. Also discuss in detail about the Networking Protocols that can be used in such a system (MQTT, CQRS etc.).

Error Handling Practices.
How to structure directories in React / Node (Related to my internship experience)
The interviewer made me write code to print the Nth Fibonacci numbers with error handling and input sanitization. (I was able to write a logarithmic time complexity solution using Matrix multiplication which impressed the interviewer.)

Implement a Stack Data Structure specifically to store integer data using two Queues.

There should be two data members, both being Queues to store the data internally. You may use the inbuilt Queue.

Implement the following public functions :

1. Constructor:
It initializes the data members(queues) as required.

2. push(data) :
This function should take one argument of type integer. It pushes the element into the stack and returns nothing.

3. pop() :
It pops the element from the top of the stack and, in turn, returns the element being popped or deleted. In case the stack is empty, it returns -1.

4. top :
It returns the element being kept at the top of the stack. In case the stack is empty, it returns -1.

5. size() :
It returns the size of the stack at any given instance of time.

6. isEmpty() :
It returns a boolean value indicating whether the stack is empty or not.

Operations Performed on the Stack:

Query-1(Denoted by an integer 1): Pushes an integer data to the stack. (push function)

Query-2(Denoted by an integer 2): Pops the data kept at the top of the stack and returns it to the caller. (pop function)

Query-3(Denoted by an integer 3): Fetches and returns the data being kept at the top of the stack but doesn't remove it, unlike the pop function. (top function)

Query-4(Denoted by an integer 4): Returns the current size of the stack. (size function)

Query-5(Denoted by an integer 5): Returns a boolean value denoting whether the stack is empty or not. (isEmpty function)

Example

Operations: 
1 5
1 10
2
3
4

Enqueue operation 1 5: We insert 5 at the back of the queue.
  Queue: [5]

Enqueue operation 1 10: We insert 10 at the back of the queue.
  Queue: [5, 10]

Dequeue operation 2: We remove the element from the front of the queue, which is 5, and print it.
  Output: 5
  Queue: [10]

Peek operation 3: We return the element present at the front of the queue, which is 10, without removing it.
  Output: 10
  Queue: [10]

IsEmpty operation 4: We check if the queue is empty.
  Output: False
  Queue: [10]

Why would you like to join Microsoft? Where do you see yourself in 5 years?