Interview question to find Triplets
You are given an integer nn and two arrays each of which is a permutation of numbers from 11 to nn. Your task is to determine the number of unordered triplets (a,b,c)(a,b,c) such that the relative ordering of (a,b,c)(a,b,c) is the same in both the arrays.
Input format
First line: A single integer TT denoting the number of test cases
For each test case:
First line: A single integer nn
Next two lines: Each line contains nn space-separated integers denoting the permutations of numbers from 11 to nn
Output format
For each test case, print the number of ordered triplets in a new line
Constraints
1≤T≤1001 \le T \le 100
1≤n≤1000001 \le n \le 100000
Sample Input1
3
1 2 3
1 2 3
Sample Output
1
ExplanationIts possible to select only one triplet in both the arrays, i.e., (1,2,3) and the relative ordering of this triplet is same in both the arrays.
Note: Your code should be able to convert the sample input into the sample output. However, this is not enough to pass the challenge, because the code will be run on multiple test cases. Therefore, your code must solve this problem statement.
Google Coding Interview Question and Answer #1: Zero Sum Triplets
Amazon Coding Interview Question Explained - Find triplets that satisfy the equation | 2020
Searching Algorithm (Q&A -11) - Find Triplets In Array With Given Sum | 3 Sum Problem
Counting the triplets
Sample input 5 4
13524
254
232
354
355
Sample output
2
1
2
6
// Sample code to perform I/O:
process.stdin.resume();
process.stdin.setEncoding("utf-8");
var stdin_input = "";
process.stdin.on("data", function (input) {
stdin_input += input; // Reading input from STDIN
});
process.stdin.on("end", function () {
main(stdin_input);
});
function main(input) {
const rtn = getTriplets(input);
process.stdout.write(rtn); // Writing output to STDOUT
}
// Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail
// Write your code here
function getTriplets(input){
let inputStr = input.toString();
let n = parseInt(inputStr.split("\n")[1]);
let firstArr = inputStr.split("\n")[2].split(" ");
let secondArr = inputStr.split("\n")[3].split(" ");
let arr1Trip = [];
let arr2Trip = [];
let count = 0;
for(let i = 0; i <= n-3; i++){
for(let j = i+1; j <= n-2; j++) {
for(let k = j +1; k <= n-1; k++) {
arr1Trip.push(firstArr[i]+''+firstArr[j]+''+firstArr[k]);
arr2Trip.push(secondArr[i]+''+secondArr[j]+''+secondArr[k]);
}
}
}
for(let i= 0; i < arr1Trip.length; i++) {
if(arr2Trip.indexOf(arr1Trip[i]) > -1) {
count++;
}
}
return count.toString();
}