CareerCup

First time answering a question here so someone please step in and let me know if this can be improved upon.

Should be O(n + m).

I used standard Java Lists, but time complexity should be the same iterating through a more traditional Linked List.

public static int biggestCommonInteger(List<Integer> a, List<Integer> b) {
	Set<Integer> set = new HashSet<Integer>();
	int biggestNum = Integer.MIN_VALUE;

	for(Integer i : a) set.add(i);
	for(Integer j : b) {
		if(set.contains(j)) {
			if(j > biggestNum)
				biggestNum = j;
		}
	}

	return biggestNum;
}

Given lists: L1 and L2, bool bfound = false, int Val = L2[0]
1. Iterate over L1 and add its items to a hash table (hash set)
2. Now, start iterating over second list L2
    if the L2[i] is present in the hash table {
		if (false == bfound) {
			Val = L2[i];
			bfound = true;
		}
		else { // we already got a value stored in the "Val"
			if (L2[i] > Val)
				Val = L2[i];				
		}
	} 	
    else // // not found in the hash set
        continue iterating;
        
    if bfound
        print the value

How about this :

int FindGreatestCommonInteger(std::list<int> lista,std::list<int> listb){

	int nGCI = numeric_limits<int>::min();
	int nMax = numeric_limits<int>::min();
	int nUpperBound = min(lista.size(),listb.size());
	for(int idx=0;i<nUpperBound;idx++)
	{
		nMax = max(lista[idx],listb[idx]);
		nGCI = max(nGCI,nMax);
	}
	int nNewUpperBound = max(lista.size(),listb.size());
	for( ;nIdx < nNewUpperBound;nIdx++){
	 int nVal = (lista.size() == nNewUpperBound) ?lista[nIdx]:listb[nidx];
	 nGCI = max(nGCI,nVal);
	}
	return nGCI;
}

This would perform the operation in O(m) time which is equivalent to the size of the largest array.

I see two approaches for doing this:
Approach 1:
1) Merge and sort the two lists
2) find duplicate from the list
lets say n are the sum of length of two lists, then space complexity is O(n) and time complexity - O(n log n) for sorting and O(n) for search

Approach 2:
1) Construct a Max heap to store the elements of the smallest list.(m -no of elems - O(m log m))
2) Search for elements from the second list in the max heap and flag the duplicate elements - n - no of elements n >= m O(n/2 log m)
3) Remove elements one by one from the max heap to find an element with a flag - O(1)

class Node{
public static void main(String[] args){

int arr1[] = {1, 2, 3, 4, 5};

int arr2[] = {2, 3, 4, 6, 6};

int max = 0;
outerloop:
for(int i=arr1.length-1;i>=0;i--){

for(int j=arr2.length-1;j>=0;j--){

if(arr1[i] == arr2[j]){
max = arr1[i];

break outerloop;
}
}
}
System.out.println(max);
}
}

We can do it in O(n) where n represents the length of the largest list:
1.Iterate through the first list to find the largest value, say v1
2. Iterate through the second list to find its largest value, say v2
2.

return v1>v2?v1:v2

can making heap will do?
MaxHeapify both list. Revome max element
from both. They are equal then exit.
else remove Max element whose prev max element
is smaller.

Here's an O(n) approach where n is the largest element in either of the two arrays/lists

int maxVal=INT_MIN;
for(i=0;i<N;i++)
  t[a[i]]=1;
for(i=0;i<M;i++)
{
  if(t[b[i]]==1 && b[i]>maxVal)
     maxVal=b[i];
}
delete [] t;
return maxVal;

This is going to be a theoretical answer exploring all the posibilities comparing the time and space complexities which you should discuss with the interviewer to make a tradeoff

Naive : pick every elem from list1 and find in list 2. Update max_found along the way O(n*m)
Best : Using O(min(n,m)) space feed smaller list into hash. Check list 2 elems 1 by 1 and find if in hash. time : O(n+m)
In between :
when you say in between only thing that comes to mind is AlogB kind time complexity. Cases :
1) So lets say I sort 1 list. Now I can search the second list item using binary search in sorted list , but wait! since its a list, binary search is not possible (unless you have a skip list). So searching can be list 2 elemenst one buy one {space = O(1), time = O(nlogn)+O(m*n))}
2) Or sort 1 list and make a 'Balanced' BST of it, so that you can binary search on hit.
{space = O(n), 'worst' time = O(nlogn)+O(mlogn)}
3) Sort both the lists in descending order. Use two pointes and traverse linearly both of them increasing the pointer which points to larger number.
{space = O(1), time = O(2*nlogn)+O(n+m))}

So the best approach will be to use hash or 3)

the major task here is to find the no in the array.
step :-
1)hash one of the array
2)start from initial of array 2 and go till end.
3)while traversal check the value if > previous max && value is not in hash then skip that value.ifpresent then update the max_common_interger.
proceed in this way you can get the desire answer.

the major task here is to find the no in the array.
step :-
1)hash one of the array
2)start from initial of array 2 and go till end.
3)while traversal check the value if > previous max && value is not in hash then skip that value.ifpresent then update the max_common_interger.
proceed in this way you can get the desire answer.