Lab126 Interview Question for Software Engineer / Developers


Country: United States




Comment hidden because of low score. Click to expand.
1
of 1 vote

Clarification question #1: The arrays you were given are sorted. Ask the interviewer if the function will always be operating on already-sorted arrays or not, since that is a very obvious opportunity for optimization.

Clarification #2: Can the arrays have duplicates of the same value? If they do, should the intersection contain unique values? For example, if each array has 3 copies of the number 7, should the intersection array also have 3 copies of 7, or just one 7? I've assumed the latter in my examples, but either case is a valid real-world problem.

I wrote two functions in C# to find the intersections.

The function with Presorted in the name only works if it's given arrays of ints that are already sorted in ascending order. It doesn't validate that they are sorted, because I didn't want to confuse the intersection code with validation code, so this version simply returns incorrect results if given unsorted arrays. This version runs quicker than the other, because it takes advantage of knowing the arrays are sorted, looping only as many times as the length of the longer array. Loop does min(n,m) iterations, for Time complexity: O(n)

In the function with Unsorted in the same, the arrays need not be sorted. The smaller of the two arrays is copied into a HashSet, and the larger array is looped over. Any element in the larger array that is already in the HashSet is pushed into a new HashSet that is the scratch space for the results. I used the HashSet here because the arrays we have are unsorted, so this gives an O(1) way to be sure we're not putting duplicates into the output. if you clarified that duplicate values are not expected in the input arrays, or preservation of duplicates is desired in the output, you could save some memory and use a temp array here just as is done in the Presorted function. At the end of the function, the result HashSet is copied into the return value array. The intersection is not sorted, the values are in the order they are encountered in the larger of the 2 arrays.

static void Main( string[] args )
		{
			int[] arr1 = { 10, 9, 8, 2, 7, 6, 5, 4, 3, 2, 1 };
			int[] arr2 = { 2, 2, 3, 5, 6, 9 };
			int[] intersection;

			/*
			 * Test of version that can handle unsorted arrays
			 */ 
			ArrayIntersectionUnsorted( arr1, arr2, out intersection );
			PrintArray( intersection );

			/*
			 * Test of version optimized for already-sorted arrays
			 */ 
			Array.Sort( arr1 );
			Array.Sort( arr2 );
			ArrayIntersectionPresorted( arr1, arr2, out intersection );
			PrintArray( intersection );
		}

		static void ArrayIntersectionPresorted( int[] arr1, int[] arr2, out int[] intersection )
		{
			int i = 0;
			int j = 0;
			int count = 0;

			// Make temporary array the size of the smaller input array
			int[] tempArray = new int[Math.Min( arr1.Length, arr2.Length )];


			while ( i < arr1.Length && j < arr2.Length )
			{
				if (arr1[i]==arr2[j])
				{
					// Record the value that is common to both arrays
					tempArray[count++] = arr1[i];
					++i;
					++j;

					// Skip over duplicates of the value we just found
					while ( i < arr1.Length && arr1[i] == arr1[i - 1] ) ++i;
					while ( j < arr2.Length && arr2[j] == arr2[j - 1] ) ++j;
				}
				else if ( arr1[i] < arr2[j] )
				{
					++i;
				}
				else
				{
					++j;
				}
			}

			// Copy results from temporary array to return value array
			// which is only as large as is necessary
			intersection = new int[count];
			Array.Copy( tempArray, intersection, count );

		}

		static void ArrayIntersectionUnsorted( int[] arr1, int[] arr2, out int[] intersection )
		{
			int[] smallerArray = ( arr1.Length <= arr2.Length ) ? arr1 : arr2;
			int[] largerArray = ( arr1.Length <= arr2.Length ) ? arr2 : arr1;

			HashSet<int> table = new HashSet<int>( smallerArray );
			HashSet<int> result = new HashSet<int>();

			for ( int i = 0; i < largerArray.Length; ++i )
			{
				if ( table.Contains( largerArray[i] ) && !result.Contains(largerArray[i]) )
				{
					result.Add( largerArray[i] );
				}
			}

			intersection = new int[result.Count];
			result.CopyTo( intersection );
		}

		static void PrintArray( int[] array )
		{
			if ( array.Length > 0 )
			{
				for ( int i = 0; i < array.Length - 1; ++i )
				{
					Console.Write( array[i] + "," );
				}
				Console.WriteLine( array[array.Length - 1] );
			}
			else
			{
				Console.WriteLine( "Empty array." );
			}
		}

- Adam Smith November 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * 
 */
package pkg_Arrays;

import java.util.Random;
import java.util.Scanner;

/**
 * @author Aswin
 *
 */
public class Intersection {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println("Enter the max input range for both arrays: ");
		Scanner sc = new Scanner(System.in);
		int maxNum = sc.nextInt();
		System.out.println("Enter number of elements in both arrays: ");
		int elemCount = sc.nextInt();
		int[] arr1 = new int[elemCount];
		int[] arr2 = new int[elemCount];
		int[] res = new int[elemCount];
		Random rnd = new Random();
		System.out.print("arr1: ");
		for(int i = 0; i<elemCount; i++){
			arr1[i] = rnd.nextInt(maxNum);
			System.out.print(arr1[i]+" ");
		}
		System.out.println();
		System.out.print("arr2: ");
		for(int i = 0; i<elemCount; i++){
			arr2[i] = rnd.nextInt(maxNum);
			System.out.print(arr2[i]+" ");
		}
		System.out.println();
		
		boolean[] bucket = new boolean[maxNum];
		for(int k =0; k<maxNum; k++)
			bucket[k] = false;
		for(int i=0; i<elemCount; i++){
			bucket[arr1[i]] = true;
		}
		int m=0;
		
		for(int j=0; j<elemCount; j++){
			if(bucket[arr2[j]]==true){
				res[m] = arr2[j];
				m++;
			}
		}
		
		for(int k=0; k<elemCount; k++){
			if(res[k]!=0)
				System.out.print(res[k]+" ");
		}

	}

}

Time Complexity: O(m+n)
m = maxNum
n = no. of elem

- Aswinvandev November 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There are many approach to solve this problem:
- O(N^2) - brute force match between two array.
- O(nlogn) - sort both array in O(NlogN), then compare both the list, that will take O(N)
- O(N) - if array is not too big, then store contain of first array in hashmap, then iterate through the second array and check whether number is there in the hashmap or not.

- sjain November 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//For unique values in the resulting array..

using System;
using System.Linq;
class ArrayIntersection
{
    static void Main()
    {
        int[] arr1 = { 1, 3, 6, 10, 3 };
        int[] arr2 = { 2, 3, 5, 6, 3 };
        
        int[] test = arr1.Intersect(arr2).ToArray(); // Gives {3, 6}
    }
}

- JustSteppedIn November 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Objective C solution to this ,
    NSArray *interArr1 = @[@1,@3,@6,@10];
    NSArray *interArr2 = @[@2,@3,@5,@6];
    __block NSMutableArray *interFinalArray = [NSMutableArray new];
    [interArr1 enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        if ([interArr2 containsObject:obj]) {
            [interFinalArray addObject:obj];
        }
    }];

- deepak.hebbar November 17, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ solution

int* commonIntegersInArray(int *arr1, int size1, int* arr2, int size2) {
    vector<int> result;
    if (size1 == 0 || size2 == 0) {
        return &result[0];
    }
    unordered_map<int, int> array1Map;
    for (int i=0; i<size1; i++) {
        array1Map.insert(make_pair(arr1[i], arr1[i]));
    }
    
    for (int i = 0; i < size2; i++) {
        if (array1Map.find(arr2[i]) != array1Map.end()) {
            result.push_back(arr2[i]);
        }
    }
    
    return &result[0];
}

- Jay February 08, 2016 | 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