## Practo Interview Question for SDE-2s

• 0

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is how it looks like in ZoomBA :

``````num_lists = 5
// create a list of lists
ll = list( [0: num_lists ] ) -> {
list([0:10]) -> { random(30) }
}
println ( ll )
// naive approach
pairs = join ( [0:num_lists], [0:num_lists] ) :: {
i = \$.0 ; j = \$.1
continue ( i >= j )
intersection = ll[i] & ll[j]
size( intersection ) >= 3 // that is the condition ?
}
println ( pairs )``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

A very complex - and *tries to be smart* approach. Not entirely sure if it is worth it, I would suggest - NO.

``````num_lists = 5
// create a list of lists
ll = list( [0: num_lists ] ) -> {
list([0:10]) -> { random(30) }
}
println ( ll )
// smarter approach
d = fold( ll, dict() ) -> {
for ( inx : [0:size(ll)] ){
l = ll[inx]
for ( item : l ){
if ( item @ \$.p ){
\$.p[item] += inx
} else {
\$.p[item] = set(inx)
}
}
}
\$.p
}
// find all items that existed in more than one lists
entries = select ( d ) :: {  size( \$.o.value ) >= 2  }
println ( entries )
// make pairwise
all_pairs = fold ( entries , dict() ) -> {
list_indices = \$.o.value
// create pair from values
pair = comb( list_indices , 2 )
for ( p : pair ){
k_p = str(p,',')
if  ( k_p @ \$.p ){
\$.p[k_p] += \$.o.key
} else {
\$.p[k_p] = list( \$.o.key )
}
}
\$.p
}
println ( all_pairs )
// select all entries with value length more than 2
valid_list_pairs = select ( all_pairs ) :: { size( \$.o.value ) > 2 }
println ( valid_list_pairs )``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Runtime for this is O(n x m) where `n` is the number of integers in all lists and `m` is the number of unique pairs of lists. Worst case performance is when all lists are exactly the same.

``````function hash (pair) {
return pair.join(',')
}
function pair (list) {
var i = 0
var j = i + 1
var pairs = []
for (; j < list.length; j = ++i + 1) {
while (j < list.length) {
pairs.push([list[i], list[j++]])
}
}
return pairs
}
module.exports = function (lists) {
var i = 0
var list_ids = []
for (; i < lists.length; ++i) {
list_ids[i] = i
}
var list_pairs = pair(list_ids)
var pair_map = {}
for (i = 0; i < list_pairs.length; ++i) {
pair_map[hash(list_pairs[i])] = 0
}
var elements = {}
for (i = 0; i < lists.length; ++i) {
var list = lists[i]
for (var j = 0; j < list.length; ++j) {
var element = list[j]
if (!elements[element]) {
elements[element] = [i]
} else {
var l = elements[element].length
if (elements[element][l - 1] !== i) {
elements[element].push(i)
}
}
}
}
for (var key in elements) {
if (({}).hasOwnProperty.call(elements, key)) {
element = elements[key]
if (element.length > 1) {
var pairs = pair(element)
for (i = 0; i < pairs.length; ++i) {
var pair_hash = hash(pairs[i])
pair_map[pair_hash]++
}
}
}
}
var solutions = []
for (key in pair_map) {
if (({}).hasOwnProperty.call(pair_map, key)) {
if (pair_map[key] >= 3) {
solutions.push(key)
}
}
}
return solutions

}

var solutions = module.exports([
[1, 2, 3, 4, 5, 6],
[2, 7, 4, 5],
[2, 5, 1, 11, 12],
[11, 13, 15, 12, 4, 7, 2]
])

console.log(JSON.stringify(solutions))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>

int main ()
{

std::vector< std::vector<int> > lists = { {1,2,3,4,5}, {4,5,6,2,3}, {11,10,9,3,5,6,2}, {4,6,7,9}, {2,3,4,5} };

for( auto& list: lists )
{
std::sort( std::begin(list),std::end(list) );
}
std::vector<int> difference;

std::vector< std::pair<int,int> > result;
for( size_t i = 0; i < lists.size()-1 ; ++i )
{
for( size_t j = i+1; j < lists.size(); ++j )
{
std::set_intersection( std::begin(lists[i]), std::end(lists[i]),  std::begin(lists[j]), std::end(lists[j]), std::back_inserter(difference) );

if(difference.size() > 3)
{
result.push_back(std::pair<int,int>(i,j));
}
difference.clear();
}
}

for (auto& ele: result)
{
std::cout << ele.first+1 << " " << ele.second+1 <<"\n";
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N)

``````#include <vector>
#include <unordered_map>
#include <stdio.h>

void PrintOverlapping(const std::vector<std::vector<int>>& lol)
{
struct occuranceEntry
{
int lastList = -1, cnt = 0;
};
std::unordered_map<int, occuranceEntry> occurances;

for (int i = 0; i < (int)lol.size(); i++)
{
for (int j = 0; j < (int)lol[i].size(); j++)
{
occuranceEntry& e = occurances[lol[i][j]];
if (e.lastList != i)
{
e.lastList = i;
if (++e.cnt == 3)
printf("%d,", lol[i][j]);
}
}
}
}

int main()
{
PrintOverlapping({ {1, 9, 2, 4, 3},
{2, 3, 3, 5, 7},
{1, 2, 4, 7, 2},
{4, 5} }); //output = 2,4,
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Brute Force Approach: For 2 lists of length n1 and n2, finding out overlaps will take O(n1+n2). For n lists, choose 2 lists in n*(n-1)/2 ways . So final Time Complexity = O(n^3)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is what I think the Pseudo code can be:

Step 1: Count number of list and name it as as listCount
Step 2: Create an Array called arrayOfLists of HashMap<Integer,Integer> having length as listCount(each index corresponds to list index). the first Integer argument of HashMap tells the list number of overlapping list. The second Integer argument tells count about how many characters of both lists are overlapping.
Step 3: Create a Hashmap<Integer,list<Integer>> called clashMap: the first argument is number, the second is to store all overlapping lists that have this number.
Step 4: Iterate through all numbers of List one by one and put them into clashMap. If clashMap already had it, then check if present list number is already present in its list. If not add the list number in list. And also iterate this list and update arrayOfList:go to index of present list in arrayOfList and if it does not have the overlapping list, add it with count of overlapping characters as 1; otherwise increment that count.

when we have iterated through all the numbers we will have arrayOfLists telling us each list is overlapping with how many characters with which list. So we can then extract how many are overlapping with more then 3 elements.

The complexity will be O(n+k). where n is total number of elements in all list. And k is the number of Lists.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````class Pair {
int list1;
int list2;

public Pair(int l1, int l2) {
this.list1 = l1;
this.list2 = l2;
}
public String toString() {
return "{"+list1+","+list2+"}";
}
}

public class Overlapping {

public List<Pair> findOverlapping(int a[][]) {

List<Map<Integer, Integer>> list = new LinkedList<Map<Integer, Integer>>();
for(int i=0; i < a.length; i++) {
Map<Integer,Integer> numbers = new HashMap<Integer,Integer>();
for(int j=0; j < a[i].length; j++) {
numbers.put(a[i][j], 1);
}
}

for(int i=0; i < a.length; i++) {
int matches = 0;
for(int j=i+1; j < a.length; j++) {
Map<Integer,Integer> counter1 = list.get(i);
Map<Integer,Integer> counter2 = list.get(j);
for(Integer ival: counter1.keySet()) {
if(counter2.get(ival) != null)
matches++;
}
if(matches >= 3) {
break;
}
}
}
return pairs;
}

public static void main(String args[]) {
/*
* {0,1},{1,3},{2,3}
*/
int list[][] = new int[][]{
{ 1, 2, 3, 4, 4, 5, 6},
{ 2, 7, 4, 5 },
{ 2, 5, 1, 11, 12 },
{ 11, 13, 15, 12, 4, 7, 2 }
};
Overlapping pi = new Overlapping();
List<Pair> pairs = pi.findOverlapping(list);
for(Pair pair: pairs) {
System.out.print(pair);
}
}
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.