Adjetter Media Network Pvt Ltd. Interview Question
Java DevelopersTeam: CRM
Country: India
Interview Type: Written Test
If I understood the question properly, here is what interviewer wants
1) Find the number of rows which have any number duplicate column(s)
2) Find the number of rows which have the specific number of duplicate column(s).
Here is how we would do it
Public static int FindDuplicateRowCount(int[][] data, int operationid, int duplicatecolumncount)
{
int duplicaterowcount = 0;
for(int i = 0 ; i < data.length;i++)
{
if(hasDuplicate(data[i],operationid, duplicatecolumncount))
{
duplicaterowcount++
}
}
return duplicaterowcount==0?-1:duplicaterowcount;
}
public static bool hasDuplicate(int[] data, int operationid, int duplicatecolumncount)
{
if((data != null) && (data.length > 1))
{
data = QuickSort(data);
int currentdataelement = data[0];
int currentduplicatecolumncount = 0
for(int j = 1; j < data.length; j++)
{
if(data[j] == currentdataelement)
{
currentduplicatecolumncount++;
while(j < data.length && data[j] == currentdataelement)
{
j++;
}
j--;
}
else
{
currentdataelement = data[j];
}
}
if((currentduplicatecolumncount > 0 && operationid == 1) || (currentduplicatecolumncount >= duplicatecolumncount && operationid == 2))
{
return true;
}
return false;
}
return false;
}
Complexity of this algorithm is O(MNLogN) in time and O(1) in space.
If we use HashSet or std::hash, we can reduce time complexity to O(MN) but the space complexity will increase to O(N).
In this case, the HashSet will be used for figuring out the duplicate elements only.
private static int findDuplicates(int[][] data, int operation, int numOfDuplicates) {
switch(operation){
case 1: return findDuplicatesOp1(data, numOfDuplicates);
case 2: return findDuplicatesOp2(data, numOfDuplicates);
default: return -1;
}
}
private static int findDuplicatesOp1(int[][] data, int numOfDuplicates) {
int count =0, result =0;
List<Integer> dupNumInRow = new ArrayList<>();
Map<Integer, Integer> rowMap = new HashMap<>();
for(int i=0;i<data.length;i++){
for(int j =0;j<data[i].length;j++){
if(rowMap.containsKey(data[i][j])){
if(rowMap.get(data[i][j])!=2){
rowMap.put(data[i][j], 2); // just to make sure this number is duplicate
count++;
}
}
else
rowMap.put(data[i][j], 1);
}
dupNumInRow.add(count);
count=0;
rowMap.clear();
}
for(int dups: dupNumInRow){
if(dups>=numOfDuplicates)
result++;
}
return result;
}
private static int findDuplicatesOp2(int[][] data, int numOfDuplicates) {
Set<Integer> uniqueValue = new HashSet<>();
Map<Integer, Integer> dupNumInCol = new HashMap<>();
for(int i = 0;i<data[0].length;i++){
for(int j = 0;j<data.length;j++){
if(uniqueValue.contains(data[j][i]))
dupNumInCol.put(i, data[j][i]);
else
uniqueValue.add(data[j][i]);
}
uniqueValue.clear();
}
int count = 0, result = 0;
for(int i=0;i<data.length;i++){
for(int j =0;j<data[i].length;j++){
if(dupNumInCol.get(j)!=null && dupNumInCol.get(j)==data[i][j])
count++;
}
if(count>=numOfDuplicates)
result++;
count = 0;
}
return result;
}
package com.test.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class DupsMakeCrazy {
public static void main(String[] args) {
int[][] data = {{1,3,5,9},{1,2,1,2},{1,4,7,9},{3,5,9,11},{20,25,20,35}};
int[][] data1 = {{1,1,2},{1,1,1},{1,2,1}};
System.out.println(findDuplicates(data1, 1, 2));
//System.out.println(FindDuplicateRowCount(data, 2, ));
}
private static int findDuplicates(int[][] data, int operation, int numOfDuplicates) {
switch(operation){
case 1: return findDuplicatesOp1(data, numOfDuplicates);
case 2: return findDuplicatesOp2(data, numOfDuplicates);
default: return -1;
}
}
private static int findDuplicatesOp1(int[][] data, int numOfDuplicates) {
int count =0, result =0;
List<Integer> dupNumInRow = new ArrayList<>();
Map<Integer, Integer> rowMap = new HashMap<>();
for(int i=0;i<data.length;i++){
for(int j =0;j<data[i].length;j++){
if(rowMap.containsKey(data[i][j])){
if(rowMap.get(data[i][j])!=2){
rowMap.put(data[i][j], 2); // just to make sure this number is duplicate
count++;
}
}
else
rowMap.put(data[i][j], 1);
}
dupNumInRow.add(count);
count=0;
rowMap.clear();
}
for(int dups: dupNumInRow){
if(dups>=numOfDuplicates)
result++;
}
return result;
}
private static int findDuplicatesOp2(int[][] data, int numOfDuplicates) {
Set<Integer> uniqueValue = new HashSet<>();
Map<Integer, Integer> dupNumInCol = new HashMap<>();
for(int i = 0;i<data[0].length;i++){
for(int j = 0;j<data.length;j++){
if(uniqueValue.contains(data[j][i]))
dupNumInCol.put(i, data[j][i]);
else
uniqueValue.add(data[j][i]);
}
uniqueValue.clear();
}
int count = 0, result = 0;
for(int i=0;i<data.length;i++){
for(int j =0;j<data[i].length;j++){
if(dupNumInCol.get(j)!=null && dupNumInCol.get(j)==data[i][j])
count++;
}
if(count>=numOfDuplicates)
result++;
count = 0;
}
return result;
}
}
package com.test.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class DupsMakeCrazy {
public static void main(String[] args) {
int[][] data = {{1,3,5,9},{1,2,1,2},{1,4,7,9},{3,5,9,11},{20,25,20,35}};
int[][] data1 = {{1,1,2},{1,1,1},{1,2,1}};
System.out.println(findDuplicates(data1, 1, 2));
//System.out.println(FindDuplicateRowCount(data, 2, ));
}
private static int findDuplicates(int[][] data, int operation, int numOfDuplicates) {
switch(operation){
case 1: return findDuplicatesOp1(data, numOfDuplicates);
case 2: return findDuplicatesOp2(data, numOfDuplicates);
default: return -1;
}
}
private static int findDuplicatesOp1(int[][] data, int numOfDuplicates) {
int count =0, result =0;
List<Integer> dupNumInRow = new ArrayList<>();
Map<Integer, Integer> rowMap = new HashMap<>();
for(int i=0;i<data.length;i++){
for(int j =0;j<data[i].length;j++){
if(rowMap.containsKey(data[i][j])){
if(rowMap.get(data[i][j])!=2){
rowMap.put(data[i][j], 2);
count++;
}
}
else
rowMap.put(data[i][j], 1);
}
dupNumInRow.add(count);
count=0;
rowMap.clear();
}
for(int dups: dupNumInRow){
if(dups>=numOfDuplicates)
result++;
}
return result;
}
private static int findDuplicatesOp2(int[][] data, int numOfDuplicates) {
Set<Integer> uniqueValue = new HashSet<>();
Map<Integer, Integer> dupNumInCol = new HashMap<>();
for(int i = 0;i<data[0].length;i++){
for(int j = 0;j<data.length;j++){
if(uniqueValue.contains(data[j][i]))
dupNumInCol.put(i, data[j][i]);
else
uniqueValue.add(data[j][i]);
}
uniqueValue.clear();
}
int count = 0, result = 0;
for(int i=0;i<data.length;i++){
for(int j =0;j<data[i].length;j++){
if(dupNumInCol.get(j)!=null && dupNumInCol.get(j)==data[i][j])
count++;
}
if(count>=numOfDuplicates)
result++;
count = 0;
}
return result;
}
}
package com.test.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class DupsMakeCrazy {
public static void main(String[] args) {
int[][] data = {{1,3,5,9},{1,2,1,2},{1,4,7,9},{3,5,9,11},{20,25,20,35}};
System.out.println(findDuplicates(data, 1, 2));
//System.out.println(FindDuplicateRowCount(data, 2, ));
}
private static int findDuplicates(int[][] data, int operation, int numOfDuplicates) {
switch(operation){
case 1: return findDuplicatesOp1(data, numOfDuplicates);
case 2: return findDuplicatesOp2(data, numOfDuplicates);
default: return -1;
}
}
private static int findDuplicatesOp1(int[][] data, int numOfDuplicates) {
int count =0, result =0;
List<Integer> dupNumInRow = new ArrayList<>();
Map<Integer, Integer> rowMap = new HashMap<>();
for(int i=0;i<data.length;i++){
for(int j =0;j<data[i].length;j++){
if(rowMap.containsKey(data[i][j])){
if(rowMap.get(data[i][j])!=2){
rowMap.put(data[i][j], 2); // just to make sure this number is duplicate
count++;
}
}
else
rowMap.put(data[i][j], 1);
}
dupNumInRow.add(count);
count=0;
rowMap.clear();
}
for(int dups: dupNumInRow){
if(dups>=numOfDuplicates)
result++;
}
return result;
}
private static int findDuplicatesOp2(int[][] data, int numOfDuplicates) {
Set<Integer> uniqueValue = new HashSet<>();
Map<Integer, Integer> dupNumInCol = new HashMap<>();
for(int i = 0;i<data[0].length;i++){
for(int j = 0;j<data.length;j++){
if(uniqueValue.contains(data[j][i]))
dupNumInCol.put(i, data[j][i]);
else
uniqueValue.add(data[j][i]);
}
uniqueValue.clear();
}
int count = 0, result = 0;
for(int i=0;i<data.length;i++){
for(int j =0;j<data[i].length;j++){
if(dupNumInCol.get(j)!=null && dupNumInCol.get(j)==data[i][j])
count++;
}
if(count>=numOfDuplicates)
result++;
count = 0;
}
return result;
}
}
- NoOne March 28, 2017