Interview Question Android Engineers
Country: India
Interview Type: Phone Interview
package com.eb.corealgo;
import java.util.ArrayList;
public class FindUnCommon {
public ArrayList<Integer> getUnCommon(ArrayList<Integer> list1,ArrayList<Integer> list2){
int indexOfElement=-1;
if(list1.size()==0){
return list2;
}
if(list2.size()==0){
return list1;
}
ArrayList<Integer> returnList=new ArrayList<Integer>();
//if not find form both
for(int i=0;i<list1.size();i++){
if(!list2.contains(list1.get(i))){
returnList.add(list1.get(i));
}
if(list2.contains(list1.get(i))){
indexOfElement=list2.indexOf(list1.get(i));
list2.remove(indexOfElement);
}
}
returnList.addAll(list2);
return returnList;
}
//test Application
public static void main(String args[]){
FindUnCommon un=new FindUnCommon();
ArrayList<Integer> l1=new ArrayList<Integer>();
l1.add(1);
l1.add(2);
l1.add(3);
l1.add(1);
l1.add(5);
ArrayList<Integer>l2=new ArrayList<Integer>();
l2.add(3);
l2.add(4);
l2.add(5);
l2.add(6);
l2.add(7);
System.out.println(un.getUnCommon(l1, l2));
}
}
Take both the lists as a string. Then take two frequency counters f1[10] and f2[10]. Initialise all the 10 elements of both the arrays to 0. Now traverse the two strings from left to right. Increment the counter like- f1[ a [ i ] - ' 0 ' ]++ and f2[ b[i] - '0']++. Now take a loop from 0 to 9 and check whether f1[i]==f2[i] or not. Time complexity- O(list size)*10.
Using hashmap
firstly, if we use list related api Running time will be O(mn). Because, contains() in list is O(n)
Secondly, if we use set related api it maintains only unique elements but not how many times it repeated
To solve these two things we use hash map. It contains unique elements and maintains as value how many times each element is repeated. Also, we are using linkedhashmap to preserve the order in which elements occurred
Importantly, add/contains/remove methods are O(1)
// Time : O(m+n), Space : O(max(m,n))
public static List<Integer> findUncommonElements(Integer a1[], Integer a2[]) {
if (null == a1 && null == a2) {
return null;
}
if (null == a1 || a1.length == 0)
return Arrays.asList(a2);
if (null == a2 || a2.length == 0)
return Arrays.asList(a1);
List<Integer> result = new ArrayList<>();
Map<Integer, Integer> countMap = new LinkedHashMap<>();
for (int i : a2) {
countMap.compute(i, (key, value) -> {
if (null == value)
return 1;
return value + 1;
});
}
for (int i : a1) {
if (countMap.containsKey(i)) {
countMap.remove(i);
} else {
result.add(i);
}
}
for (int key : countMap.keySet()) {
for (int i = 0; i < countMap.get(key); i++) {
result.add(key);
}
}
return result;
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace careercup
{
class Program
{
static void Main(string[] args)
{
List<int> l1 = new List<int>(){1,5,6,3,2};
List<int> l2 = new List<int>() { 1, 7, 2, 9, 5 };
IList<int> uniqueNumbers = new List<int>();
foreach (var item in l1)
{
if (!action.CheckIfElementIsPresent(item, l2)) { uniqueNumbers.Add(item);
Console.WriteLine(item);
}
}
foreach (var item in l2)
{
if (!action.CheckIfElementIsPresent(item, l1))
{
uniqueNumbers.Add(item);
Console.WriteLine(item);
}
}
Console.ReadLine();
}
}
class action
{
public static bool CheckIfElementIsPresent(int a, ICollection<int> collection)
{
return collection.Where(x => x == a).Any();
}
}
}
class Program
{
static void Main(string[] args)
{
List<int> l1 = new List<int>(){1,5,6,3,2};
List<int> l2 = new List<int>() { 1, 7, 2, 9, 5 };
IList<int> uniqueNumbers = new List<int>();
foreach (var item in l1)
{
if (!action.CheckIfElementIsPresent(item, l2)) { uniqueNumbers.Add(item);
Console.WriteLine(item);
}
}
foreach (var item in l2)
{
if (!action.CheckIfElementIsPresent(item, l1))
{
uniqueNumbers.Add(item);
Console.WriteLine(item);
}
}
Console.ReadLine();
}
}
class action
{
public static bool CheckIfElementIsPresent(int a, ICollection<int> collection)
{
return collection.Where(x => x == a).Any();
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace careercup
{
class Program
{
static void Main(string[] args)
{
List<int> l1 = new List<int>(){1,5,6,3,2};
List<int> l2 = new List<int>() { 1, 7, 2, 9, 5 };
IList<int> uniqueNumbers = new List<int>();
foreach (var item in l1)
{
if (!action.CheckIfElementIsPresent(item, l2)) { uniqueNumbers.Add(item);
Console.WriteLine(item);
}
}
foreach (var item in l2)
{
if (!action.CheckIfElementIsPresent(item, l1))
{
uniqueNumbers.Add(item);
Console.WriteLine(item);
}
}
Console.ReadLine();
}
}
class action
{
public static bool CheckIfElementIsPresent(int a, ICollection<int> collection)
{
return collection.Where(x => x == a).Any();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace careercup
{
class Program
{
static void Main(string[] args)
{
List<int> l1 = new List<int>(){1,5,6,3,2};
List<int> l2 = new List<int>() { 1, 7, 2, 9, 5 };
IList<int> uniqueNumbers = new List<int>();
foreach (var item in l1)
{
if (!action.CheckIfElementIsPresent(item, l2)) { uniqueNumbers.Add(item);
Console.WriteLine(item);
}
}
foreach (var item in l2)
{
if (!action.CheckIfElementIsPresent(item, l1))
{
uniqueNumbers.Add(item);
Console.WriteLine(item);
}
}
Console.ReadLine();
}
}
class action
{
public static bool CheckIfElementIsPresent(int a, ICollection<int> collection)
{
return collection.Where(x => x == a).Any();
}
}
}
private void solution(int[] input1, int[] input2)
{
HashMap<Integer,Integer> hm = HashMap<Integer,Integer>();
for(int i=0,int j=0;i<input1.length ||j<input2.length;i++;j++)
{
if(i<input1.length && hm.containsKey(input1[i]))
{
int count = hm.get(input1[i]);
if(count == 0 || count >0)
{
// Do nothing, its either both or only A
}
else
{
// its there in both the lists
hm.put(input1[i],0);
}
}
else
hm.put(input[i],1);
if(j<input2.length && hm.containsKey(input2[j]))
{
int count = hm.get(input2[i]);
if(count == 0 || count <0)
{
// Do nothing, its either both or only B
}
else
{
// its there in both the lists
hm.put(input2[i],0);
}
}
else
hm.put(input[i],-1);
}
Iterator it = hm.entrySet().iterator();
while(it.hasNext())
{
Map.Entry pair = (Map.Entry) it.next();
if(it.getValue()!=0)
System.out.println(it.getValue());
}
}
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;
public class UnCommonCharacters {
/**
* @param args
*/
public static void main(String[] args) {
String str1= "characters";
String str2= "alphabets";
char[] c1= str1.toLowerCase().toCharArray();
char[] c2= str2.toLowerCase().toCharArray();
Map<Character, Integer> countMap = new TreeMap<>();
for(char i : c1){
countMap.put(i, 1); // Present in 1st String
}
for(char i : c2){
if(countMap.containsKey(i)){
countMap.put(i,-1); // Common to both the strings
}
else {
countMap.put(i,2); // Present in 2nd String
}
}
for(Entry<Character, Integer> ent : countMap.entrySet())
if(!(ent.getValue() == -1)){
System.out.println(ent.getKey());
}
}
}
- NoOne October 06, 2016