1. String Manipulation

Class Replacement{
	int start;
	string before;
	string after;
}
start: start index
before: substring that is present at the star index
after: Replace the before substring with after substring.

Given a string and replacement queries. Return a string after performing all the replacements.
Ex:
Input: num foo;
replacements: [
{start: 0, before: "num", after: "number"},
{start: 4, before: "foo", after: "bar"}
]

Output: "number bar;"

MyApproach:
I discussed different approached with the interviewer. Finally, I told a concantenation approach.
For every replacement query, we do
string ans = s.subtr(0, start) + after + s.substr(start+before.size());
swap(ans,s);

And finally return s. For this to word our queries need to be sorted in decreasing order of start index.

2. Cards

A card has 4 attributes (shape, size, color, shading). You have been given 3 such cards. A set of three cards is said to be valid if for each attribute either
a. All 3 cards have same value 
b. All 3 cards have different value.
Write a funtions valid_set() that takes in a set of cards and returns if the set is valid.

Ex:
Input:
[
{1,1,2,3},
{1,2,2,3},
{1,3,2,3}
]

Output: True

Explanation:
Each card is represented as row and each attribute is represented as column. 
For the first attribute (0th column), all cards have same value. 
For second attribute(1st column), all attributes have different value. 
For third attribute (2nd column), all attributes have same value. 
For 4th attribute(3rd column), all attributes have same value.
For all the attributes, all cards either have same value or different value. So this set is valid.

As number of cards is 3 and number of attributes is 4, constant space and time solution was expected.

My Approach:
We cam simply take the input as a 3x4 matrix and traverse the matrix in column major format. We can use if-else statements to check the condition or we can also use set.

3. Cards Follow up
Given n number of cards, return 3 valid cards set if they exists. (Validity rules expained above)

As number of cards given is N, I was able to come up with a O(N*N) time and O(N) space solution. Please let me know if you come up with a better solution.

My Approach:
First I told the brute force approach with O(N*N*N) TC.
For optimizing it further, we can use two for loops for iterating over ever pair of card.
Using those two cards, try to construct the third card and check if it is present in the given arr.
We can use unordered_set to optimize the search.