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.
-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