Question: Samsung, Most Recent Questions from Online Assessments, August 2022
0
Entering edit mode

# Question 1

Wildcard Matching

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

• '?' Matches any single character.
• '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Constraints:

• 0 <= s.length, p.length <= 2000
• s contains only lowercase English letters.
• p contains only lowercase English letters, '?' or '*'.

Examples:

Input 1:

s = "aa", p = "a"

Output 1:

false

Explanation:

"a" does not match the entire string "aa".

Example 2:

Input 2:

s = "aa", p = "*"

Output 2:

true

Explanation:

'*' matches any sequence.

Input 3:

s = "cb", p = "?a"

Output 3:

false

Explanation:

'?' matches 'c', but the second letter is 'a', which does not match 'b'.

# Question 2

## Maximum Subset Sum

Given an integer array nums, find the subarray which has the largest sum and return its sum.

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

Examples:

Input 1:

nums = [-2,1,-3,4,-1,2,1,-5,4]

Output:

6

Explanation:

[4,-1,2,1] has the largest sum = 6.

Input 2:

nums = [1]

Output 2:

1

Input 3:

nums = [5,4,-1,7,8]

Output 3:

23

## Overlapping Trees

Given two binary trees, you have to overlap Tree 2 over Tree 1.

Example

Tree 1: 4, 5, 6, 1, Null, 4, Null

Tree 2: 7, -2, -6, Null, 5, 4, 3

Output:

7, -2, -6, 1, -5, 4 ,3

## Question 4

Shifting Homes

Homes are aligned in a row. In any given row, maximum half of the homes are occupied. In a season, people got infected and all must vacate homes to move to unoccupied homes. Movements are sequential and not parallel (i.e one home completes the movement, then only the second home starts). To reduce the overall time taken, it's better to move to a nearby empty room than a farther one. i'th home to j'th home movement results in abs(j-i) distance. Minimize the overall distance covered by the time all infected home completes the movement to unoccupied homes.

Input : n = no of homes String s denoting occupied and unoccupied homes(1 = occupied, 0 = unoccupied)

Example:

Input

n = 4

"1001"

Output:

2

## Question 5

A string S of length N has to be reconstructed from 2(start, end)+k substrings(random length). Start substring is a prefix of S and end substring is a suffix of S. These substrings can be overlapping each other from right, left or both sides with minimum of 4 characters.

Example:

Input

abcde123, de123xyz, 3xyzpqr

Output :

abcde123xyzpqr

## Burst Balloon

There are n balloons and n bullets and each balloon is assigned with a particular number (point).

Whenever a particular balloon is shot the no of points increases by

1. The multiplication of point assigned to balloon on left and that of right side.
2. Point assigned to left if no right exists
3. Point assigned to right if no left exists.
4. The point assigned to itself if no other balloon exists.

You have to output the maximum no of points possible.

Input

``````1 2 3 4
``````

Output

``````20
``````
1
Entering edit mode

# Approach

This is a standard problem, usually done by Kadane's algorithm.

Following are the steps for Kadane's algorithm:

• Initialise a maxSoFar to -infinity and currentMax to 0
• maxSoFar contains answer till now, and currentMax is the sum for the current subarray
• Iterate over the array, add ai to currentMax
• If currentMax > maxSoFar, maxSoFar=currentMax
• If currentMax < 0 , we don't need to take the previous subarray, hence set currentMax = 0.

# C++ Code

``````int maxSubarraySum(vector&lt;int&gt; a)
{
int n=a.size();

int maxSoFar=-1e9,maxEndingHere=0;

for(int i = 0;i &lt; n;i++)
{
maxEndingHere=maxEndingHere+a[i];

maxSoFar=max(maxSoFar,maxEndingHere);

maxEndingHere=max(maxEndingHere,0ll);
}

return maxSoFar;
}
``````
1
Entering edit mode

# Solution - Q1

This is a well known dynamic programming problem which uses the idea of string matching DP.

## Approach

• Let dp(i,j) = true if sub-string s[ i...n-1] matches with sub-pattern p[ j...m-1] , else false.
• We can define a recursive relation to find solution for this state using other precomputed states.
• dp(i,j) is true if any of the following below cases satisfies.
• Case 1 : if s[i] == p[j] , then dp(i,j) will be surely true if dp(i+1,j+1) is true.
• Case 2 : if p[j] == '?' , then dp(i,j) will be surely true if dp(i+1,j+1) is true.
• Case 3 : if p[j] == '*' , we have the following possibilities.
• Case 3.1 : Match current character and extend , check if dp(i+1,j) is true
• Case 3.2 : Match current character with '*' and end , check if dp(i+1,j+1) is true.
• Case 3.3 : Match zero characters , check if dp(i , j+1) is true
• Base cases:
• BC1 : If both pointers have reached the end. ( string has successfully matched with pattern)
• BC2 : if string pointer has reached the end , and pattern hasnt ended . (if remaining pattern contains only '*' , return true. Else false.)
• BC3 : pattern has ended , but string hasnt ended ( return false as this is an incomplete match )

### Code

``````string str , pat;
int dp[2001][2001];
int dfs(int i , int j){
//BASE CASE
if(i == str.size() &amp;&amp; j == pat.size())return 1;
if(i == str.size() &amp;&amp; j != pat.size()){
if(pat[j]=='*')return dp[i][j] = dfs(i , j+1);
else return dp[i][j] = 0;
}
if(i != str.size() &amp;&amp; j == pat.size())return 0;
if(dp[i][j] != -1)return dp[i][j];

int val = 0;
// Case 1 : string matches with pattern , move both pointers ahead.
if(str[i] == pat[j])val |= dfs(i+1 , j+1);
// Case 2 : Match '?' with the string pointer , move both pointers ahead.
if(pat[j] == '?')val |= dfs(i+1 , j+1);
// Case 3 : Match '*' with zero or more string pointers.
if(pat[j] == '*'){
val |= dfs(i+1,j);
val |= dfs(i+1,j+1);
val |= dfs(i , j+1);
}
return dp[i][j] = val;
}
``````
1
Entering edit mode

Solution-Q3

Approach

Step 1: Generate the binary trees from the input.

Step 2: Merge the binary trees.

• Traverse recursively.
• If subtree of Tree 2 is null, then node will be the subtree of Tree 1 as it is.
• If both the values exist, then value will be the value of Tree 2. Then traverse recursively in both the subtrees and repeat the procedure.

Step 3: Decompose the binary tree back into array format.

Here are the required function codes:

``````node* overlapTrees(node* r1, node* r2) {

if(r2 == nullptr)
return r1;

if(r1 == nullptr) {
return r2;
}

r2 -&gt; left = overlapTrees(r1 -&gt; left, r2 -&gt; left);
r2 -&gt; right = overlapTrees(r1 -&gt; right, r2 -&gt; right);

return r2;
}

vector &lt;int&gt; flattenTree(node* root) {
node* cur = root;
vector &lt;int&gt; tree;
queue &lt;node*&gt; q;
q.push(root);
if(cur != nullptr) {
tree.push_back(root -&gt; val);
} else {
tree.push_back(0);
}
while(!q.empty()) {

if(cur -&gt; left == nullptr &amp;&amp; cur -&gt; right == nullptr) {
q.pop();
continue;
}

if(cur -&gt; left != nullptr) {
tree.push_back(cur -&gt; left -&gt; val);
q.push(cur -&gt; left);
} else {
tree.push_back(0);
}

if(cur -&gt; right != nullptr) {
tree.push_back(cur -&gt; right -&gt; val);
q.push(cur -&gt; right);
} else {
tree.push_back(0);
}

q.pop();
if(!q.empty()) {
cur = q.front();
}
}

return tree;
}

node* tree_create(int* arr, int n){
queue &lt;node*&gt; q;
int i = 1;
bool l = true;
node* root = new node(arr[0]);
node* cur = root;
q.push(cur);

while(!q.empty() &amp;&amp; i &lt; n){
if(l) {
l ^= 1;

if(arr[i] != 0) {
cur -&gt; left = new node(arr[i]);
q.push(cur -&gt; left);
} else {
cur -&gt; left = nullptr;
}

} else {
l ^= 1;

if(arr[i] != 0) {
cur -&gt; right = new node(arr[i]);
q.push(cur -&gt; right);
} else {
cur -&gt; right = nullptr;
}

q.pop();
if(!q.empty()) {
cur = q.front();
}
}

i++;
}

return root;
}
``````
0
Entering edit mode

Question 4

`overview:`

• N Houses are there in a line, of which m<=N/2 are occupied (denoted by 1) by a family
• All Families have to move to a house which was not occupied initially.
• Movements are sequential, only one family can move at a time.
• The time taken to move house number `i` to house number `j` is equal to `abs(i-j)`

`Solution (O(N^2)):`

• Basic greedy idea: if family `i1` moves to `j1` and family at family at `i2` moves to `j2`, and `i1 &lt; i2` , then `j1 &lt; j2`
• There are only two possibilities `j1` is in between `i1` and `i2` , or `j1` is after `i2`
• As the diagram below shows, in both cases `j1 &lt; j2` gives a lower time'
• All arrays below are `1 indexed`
• Now find the indices of houses with and without families and store them in array `occupied[]` and `empty[]` respectively
• Size of `occupied[]` = `K`
• `occupied[i]` = index of 'i^th' occupied house
• Size of `empty[]` = `L`
• `empty[ij` = index of 'j^th' empty house
• Find distance between every empty and occupied house , store it in `dist[][]`
• `Dist[i][j]` = Distance between `i^th` occupied house and `j^th` empty house .
• Size of `Dist[][]` = `K*L`
• Define `dp[i][j]` = minimum time taken for movement of all families residing till `i^th` occupied house to a empty house such that family on the `i^th` occupied house moves to a empty house on or before `j^th` empty house
• `Initialization:`
• all `dp[i][j] = INF`
• `dp[1][1] = dist[1][1]`
• `dp[1][j] = min(dp[1][j-1],dist[1][j])`
• `Updation:`
• `dp[i][j] = min(dp[i][j-1],dp[i-1][j-1]+dist[i][j])`
• `final answer:`
• ANS = min of all `dp[K][i]` , `1 &lt;= i &lt;= L`