Filtering product ids

Question

As regarding the following question I have completed the code as below.

But I am curious about other effective solutions. I am also curious about if there is any solution that could be applicable by using java stream API.

It is not mandatory to keep records at int[][] matrix. Any data structure can be used.

My solution has O(n) time complexity. If you have a better to solve the question please share your solution.

For a given retailer "100" function only needs to return 4 because product 1 exists in other retailers.

Thanks.

public class InterviewQuestion {

 public static void main(String[] args) {
    int[][] itemSeller =       { {1, 100},
                                 {2, 200},
                                 {3, 300},
                                 {4, 100},
                                 {1, 200},
                                 {2, 300} };

    int target = 100;

    getUniqueProduct(itemSeller,target);

}

private static void getUniqueProduct(int[][] itemSeller, int target) {


    int count[] = new int[itemSeller.length];

    for (int i = 0; i < itemSeller.length; i++) {
        count[itemSeller[i][0]]++;
    }

    for (int i = 0; i < itemSeller.length; i++) {
        if (target == itemSeller[i][1]) {

            int item = itemSeller[i][0];
            if (count[item] > 1) {
                continue;
            } else
                System.out.println(item);
        }
    }
}
}

Answer 1

Your class is InterviewQuestion, if it is for an interview, then there's a few other things to consider, in addition to whether or not you get a reasonably efficient solution. Whilst a bad solution will probably rule you out, a non-optimal solution may be acceptable depending on other factors.

Seperation of concerns

Finding the list of unique product items seems like it's a different concern to printing the list out to the console. Rather than printing the items out directly, it would be better to return the list of items and then print them from the caller. Not only does this demonstrate that you're thinking about reuse, but it also makes the code easier to write automated tests (for a given set of inputs, you can test against the expected results).

Naming

Naming is fairly important for readability. You variable names are mostly appropriate, but a few small things. Your method getUniqueProduct doesn't return anything, which is misleading. productRetailer is a collection of mappings, rather than a single product retailer. Something like productRetailerMappings might be more descriptive. target refers to a retailer, so targetRetailer would make this clearer, otherwise given the context it might be expected that it's the targetProductId.

Consistency

Modern IDE's can auto-format your code for you. Inconsistencies suggest that either you don't use your IDE effectively, or that you lack attention to detail. Both of these are things that interviewers are going to consider. Two obvious things that stand out are sometimes there's ) { and sometimes there's ){. A missing space may seem minor, but it is noticeable. Another is blank line after at the top of the if block. Sometimes you have one, sometimes you don't.

To continue...or not

if(count[item]>1){
    continue;
}else
    System.out.println(item);

It's almost always preferable to use {} around your if/else clauses. Doing it for one side of an if, and not for the else, when they're both one-line is unnecessarily confusing. The else is also redundant in this case, since if the if is triggered, the following code won't be executed anyway, you don't need the else. Where possible you want to avoid introducing unnecessary nesting. Since there's nothing else after the println that's executed, inverting the if would also make the code cleaner, since you wouldn't need the branch condition:

if(count[item]==1) {
    System.out.println(item);
}

Constants can help readability

You're using a two dimensional array, with a fixed size. Have two constants, one for the ITEM_COUNT and one for the RETAILER_ID would help in understanding. It's not obvious from this line:

if(target == productRetailer[i][1]) {

What '1' is referring to (retailer or item).

Answer 2

The exact time complexity of your algorithm is O(2*n) since it performs two sequential iterations on the array.

I do have a slightly better performing algorithm:

1. Sort the array by the first item in the 2nd dimension array (item number)

2. iterate over the sorted array looking for items that have exactly one line that has the requested target seller.

time complexity is O(n log n) + O(n)

Note: streaming of arrays is possible with Arrays.stream()

Edit: Here is a complete solution with Java 8 streams:

private static void getUniqueProduct2(int[][] itemSeller, int target) {

    // map key is item, map value is list of 2nd dimension arrays that have this item
    Map<Integer, List<int[]>> map =
        Arrays.stream(itemSeller)
            .collect(Collectors.groupingBy(arr -> arr[0]));

    // stream on map values, looking for lists with one list-item that belongs to target seller
    // build array of items that satisfy criteria
    int[] sellerExclusiveItems =
        map.values().stream()
            .filter(list -> list.size() == 1  &&  list.get(0)[1] == target)
            .mapToInt(list -> list.get(0)[0])
            .toArray();

    System.out.println(Arrays.toString(sellerExclusiveItems));
}