Practo Interview Question for SDE-2s


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 )

- NoOne January 10, 2017 | Flag Reply
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 )

- NoOne January 10, 2017 | Flag Reply
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))

- srterpe January 10, 2017 | Flag Reply
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";
  }
}

- steephen January 11, 2017 | Flag Reply
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,
}

- tjcbs2 January 13, 2017 | Flag Reply
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)

- maxximus February 17, 2017 | Flag Reply
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.

- teji.catia February 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

How about this Java code? Comments are welcomed... O(NM)

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);
			}
			list.add(numbers);
		}
		
		List<Pair> pairs = new LinkedList<Pair>();
		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) {
					pairs.add(new Pair(i,j));
					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);
		}
	}
}

- Anonymous January 11, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More