Coding Challenges from Internet

Here are some of the coding challenge questions I found from the internet.

Maximal Square

Have the function MaximalSquare(strArr) take the strArr parameter being passed which will be a 2D matrix of 0 and 1's, and determine the area of the largest square submatrix that contains all 1's. A square submatrix is one of equal width and height, and your program should return the area of the largest submatrix that contains only 1's. For example: if strArr is ["10100", "10111", "11111", "10010"] then this looks like the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

For the input above, you can see the bolded 1's create the largest square submatrix of size 2x2, so your program should return the area which is 4. You can assume the input will not be empty.

Hard challenges are worth 15 points and you are not timed for them.

Sample Test Cases

Input:new string[] {"0111", "1111", "1111", "1111"}

Output:9

Input:new string[] {"0111", "1101", "0111"}

Output:1

My solution in c# Console App:

1. MaximalSquare_solution.cs

2. Multi-threading version: MaximalSquare_multithreaded_solution.cs.txt

In the program, some threads stop when the list is empty; some threads are still running, in progress of inserting new workloads into the list. When the list is added with new workloads, relaunch the stopped threads by redeclare them and start again.

Reference Question

https://www.coderbyte.com/editor/guest:Maximal Square:Csharp

---

Minimum transactions

There are people living in a neighborhood. When in debt, neighbors borrow money from each other to clear their debts. A neighbor has already borrowed money from another neighbor for times to clear a debt.

All the neighbors want to clear what they owe each other. Their plan is to clear their debts in such a way that the total number of transactions is minimized because the fee per transaction is very high. For example, if the person pays the person dollars, then the amount of this particular transaction is X. 

You are required to minimize the sum of the transaction amount.

Input format

· First line: Two integers n and m

· Next m lines: Three integers v_i, u_i, and w_i which means that the u_i^th person has lent the v_i^th person w_i amount of dollars

Output format

Print only one integer that represents the minimum sum of the transaction amount.

Constraints

It is guaranteed that v_i and u_i are distinct.

Sample input

2 3
1 2 10
1 2 3
2 1 5

Sample output

8

Sample Input

4 3

1 2 3

1 4 4

2 4 3

Sample Output

7

My Solution

Sequential steps to minimize the transactions

1. Combine all the debts with the same borrower in a debtor as one debt.

2. Remove cross borrowing transactions: debtor #1 borrow money from debtor #2; vice versa, debtor #2 also borrow money from debtor #1. In such case, we can offset the debts amount, reduce them into one transaction instead of two transactions.

3. Transferring the debts to another debtors: a debtor #3 borrow money from a person #1; at the same time this debtor #3 lend money to another debtor #2. That’s mean a fraction or more of the loan the debtor #3 borrowed, he lends to another debtor. Hence, we can transfer fraction or more of the loan from debtor #3 to debtor #2. Debtor #2 will directly bear the loan without need to go through debtor #3. Thus, reducing the cash flow.

Case 1

Case 2

Case 3

4. After all the minimization steps, all people will be identified discretely as either net debtors or net borrowers, and they will not be acting both roles.

My solution in c# Console App:

1. Minimum transactions_solution.cs.txt Transactions_File.txt Transactions_File1.txt Transactions_File2.txt Transactions_File3.txt Transactions_File4.txt

Reference Question

https://www.hackerearth.com/practice/basic-programming/implementation/basics-of-implementation/practice-problems/algorithm/debts-429c5441/

---

Determine the maximum value of any non-empty subsequence in the given array using the given formula

You are given an array A that contains N elements and an integer K that represents the value of a non-empty subsequence B₁, B₂,…, B_m of A is defined as

(B₁ ^ K) ^ (B₂ ^ K) ^ … ^ (B_m ^ K) * gcd(B₁, B₂,…, B_m) (where ^ is the XOR operator).

Determine the maximum value of any non-empty subsequence in the given array.

For example, if the elements of array A is [2, 4, 6] and K is 6, then the maximum value is achieved you select the subsequence [2, 4]. In this case, the value of the subsequence will be

((2 ^ 6) ^ (4 ^ 6)) * gcd(2, 4) = 6 * 2 = 12.

Note: A sequence b is a subsequence of a sequence a if b can be obtained from a by deleting several (possibly zero) elements. For this question, assume that if the sequence has a single element, then the gcd is the element itself.

Input format

· First line: N integers A₁, A₂,…, A_n (1 ≤ Ai ≤ 10⁵) that denote the elements of the array

· Second line: Integers K (K ≤ 10⁵)

Output format

Print the maximum value of any non-empty subsequence of the given array.

Sample Input	Sample Output
3 4 6 3	30

Explanation

In the given example it is clear that when we chose the subsequence containing only 6, we get the maximum value. Here gcd of elements in subsequence is 6 and K is 3. So, value = (6 ^ 3) * (6) = 5 * 6 = 30.

My solution in C# Console App:

XOR_GCD_formula_Subsequences_MaxOutput_2.txt GCDvalueSource_1.txt GCDvalueSource_2.txt

Reference Question

https://www.hackerearth.com/problem/algorithm/max-value-6e9e14bc/description/

---

Find a Mother Vertex in a Graph

Find the Mother vertex in a directed graph. A mother vertex in a graph G = (V,E) is a vertex v such that all other vertices in G can be reached by a path from v.

There can be more than one mother vertices in a graph. We need to output anyone of them.

Graph 6

Graph 7

My solution in C++ Console App:

Find Mother vertex in a directed graph by using shortest path derivation.

1. Each node takes turn to become root node, derive traveling paths from root node to all the other nodes.

2. After the derivation, check do all the nodes have paths to the current root node. If yes, the current root node is the Mother Vertex.

edges with path weight: FindMotherVertexInGraph1.cpp graph6_1.txt graph7_1.txt

edges without path weight: FindMotherVertexInGraph2.cpp graph6_2.txt graph7_2.txt

Reference Question

https://www.geeksforgeeks.org/find-a-mother-vertex-in-a-graph/

Edit date: 19 Jan 2020