Facebook Interview Question for SDE1s


Country: United States




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

We just want to find the duplicates. We can walk on the array and put every element in the the corresponding index. If we find two elements in same position, we insert them into a set<in> as the final results.
O(1) Space, O(n) time

int main()
{
// 	std::vector<int> inp = {4, 2, 0, 5, 2, 0, 1} ;
	std::vector<int> inp = {1, 2, 3, 0, 0, 1, 3, 6, 6,6};
	
	//It is only for holding output
// You can print the results instead of inserting here.
	std::set<int> res; 
	for(int i = 0; i < inp.size(); i++){
	    if(inp[i] == i) continue;
	    
	    if(inp[inp[i]] == inp[i]) res.insert(inp[i]);
	    else{
	        auto temp = inp[inp[i]];
	        inp[inp[i]] = inp[i];
	        inp[i] = temp;
	        i--;
	    }
	    
	}
	for(set<int>::iterator it = res.begin(); it != res.end(); it++)
	    cout << *it << " ";
	
	return 0;
}

I should add that if you don't want to even reserve space for the output variable, you can print the duplicates as soon as you see them first. But in order to not print them more than once, after printing any duplicated, we can make them to -1 and be sure that we will not print them twice.

- IB May 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I can look at it as a kind-of directed graph, where each vertex has only one node, to another vertex. So if array is w/o dups, visually, graph will contain only circles - 1 or more.
For example array 2, 1, 3, 0, 4
contains
2 -> 3(which is a[2]) -> 0(which is a[3]) -- 2 again (circle completed)
and 1 (which is primitive circle itself) and 4 (primitive circle as well)
But when array has dups, there will be node which has two or more incoming edges. For example
2 0 3 4 2
has circle 2 -> 3 -> 4 -> 3 again, so 3 has two incoming edges - from a[0] and a[4]
what we have to do, is to run through array like it was graph and track a situation when we visited neither first (node of circle), nor new node.
Here is approx code (i use magic digits <0 not to use additional storage for nodes)

public List<int> getRepeated(int[] input) {
    var result = new List<int>();
    for(int i = 0; i < input.Length; i++) {
        // this node was visited as part of other circle
        if(input[i] < 0) continue;
        int nextIdx = i;
        var nextIdx = input[nextIdx];
        // start new circle marking its head with -2
        input[nextIdx] = -2;
        while (true) {
            // we return to head, circle complete, we should start a new circle
            if (input[nextIdx] == -2) {
                input[nextIdx] = -1;
                break;
            } else {
                // this node was already visited as a part of another circle
                if(input[nextIdx] < 0) {
                    result.Add(input[i]);
                    break;
                } else {
                    // mark current node as visited
                    var current = nextIdx;
                    nextIdx = input[nextIdx];
                    input[current] = -1;
                }
            }
        }
    }
    return result;
}

- Michael.Karn.Ivanov May 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@azam. not sure if your logic works. in your example array, the returned list will be 1,2,3. Whereas it should only be 2

- gator May 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Store counts inside the array itself. For instance, you could assign values outside the prescribed value range (I chose negative numbers for convenience):

from numpy.random import randint
n = 13
a = randint(n, size=n)
print a

for j in a:
    a[j % n] += n

for i, j in enumerate(a):
    if j > n:
        print i

- Kristian Holsheimer May 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@IB that is not O(1) space

- Chris May 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK

It is O(1) space, you can print the results instead of putting them into a set. The set is only for holding the final results.

- IB May 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

with two passes:
1. iterate over all elements so that a[a[i]%n] = a[a[i]%n]%n + n
2. iterate a second time and if you face a[i] > n print i
note, n <= MAX_INT / 2, it's O(1) space and O(n) time, but there are two passes

it sais to do it with one pass:
1. iterate over all elements so that v=a[i], j=v%n
if a[j] < n: a[j] = a[j] + n
if n =< a[j] < 2n: a[j] = a[j] + n, print j

now n must be <= MAX_INT / 3 otherwise it won't work

Actually this O(1) space is a bit of a lie, while it is true in terms of bytes,
it uses unused bits to store occurrences.

in java:

public class RepeatingNumbers {
    public List<Integer> findRepeat(int[] input) {
        ArrayList<Integer> res = new ArrayList<>();
        int n = input.length;
        if(n > Integer.MAX_VALUE / 3) throw new IllegalArgumentException("input.length");
        for(int i =0; i < input.length; i++) {
            int j = input[i] % n;
            if(input[j] < n) {
                input[j] = input[j] + n;
            } else if(input[j] >= n && input[j] < 2*n) {
                input[j] = input[j] + n;
                res.add(j);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new RepeatingNumbers().findRepeat(new int[]{4,2,0,5,2,0,1}));
        System.out.println(new RepeatingNumbers().findRepeat(new int[]{1,2,3,0,0,1,3,6,6,6}));
        /*  Output
            [2, 0]
            [0, 1, 3, 6]
         */
    }
}

- Chris May 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is working for me.

//var repAr = new int[] { 1, 2, 3, 0, 0, 1, 3, 6, 6, 6 };
            var repAr = new int[] { 8, 3, 1, 7, 1, 6, 5, 6, 3 };
            var repList = findRepItemsinFixedRange(repAr);
            Console.WriteLine($"Given Items: {string.Join(",", repAr)}");
            Console.WriteLine($"Repeated Items: {string.Join(",", repList)}");
        

        private static HashSet<int> findRepItemsinFixedRange(int[] repAr)
        {
            var repList = new HashSet<int>();
            for (int indx = 0; indx < repAr.Length; indx++)
            {
                if (repAr[valDecode(repAr[indx])] < repAr.Length)
                    repAr[valDecode(repAr[indx])] = valEncode(repAr[valDecode(repAr[indx])]);
                else
                    repList.Add(valDecode(repAr[indx]));
            }
            for (int indx = 0; indx < repAr.Length; indx++)
                repAr[indx] = valDecode(repAr[indx]);

            return repList;

            int valEncode(int val)
            {
                ////abs encode - WON"T WORK FOR ZERO VALUE
                //return -val;
                return val + repAr.Length;
            }
            int valDecode(int val)
            {
                ////abs decode - WON"T WORK FOR ZERO VALUE
                //return Math.Abs(val);
                if (val >= repAr.Length)
                    return val - repAr.Length;
                return val;
            }
        }

- syam.bollu May 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@IB, no, it will repeat already printed duplicates that's why you use a set and not a list ...
however, the approach is cool!!

int main()
{
	std::vector<int> inp = {4, 2, 0, 5, 2, 0, 1} ;
	//std::vector<int> inp = { 1, 2, 3, 0, 0, 1, 3, 6, 6 };

	for (int i = 0; i < inp.size(); i++) {
		if (inp[i] == i || inp[i] == -1) continue;

		if (inp[inp[i]] == inp[i]) {
			std::cout << inp[i] << " ";
			inp[i] = -1;
		} else {
			std::swap(inp[inp[i]], inp[i]);
			i--;
		}
	}
	return 0;
}

- Chris May 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@ChrisK
In this case, I wanted to say that we can mark the duplicates by -1, and then saw your code. sounds cool.

- IB May 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This will do it in constant memory. We are using the source array to mark if we have visited the number before or not.

package algorithms;

public class FindRepeatingNums {

	public static void main(String[] args) {
		int[] arr = {1,3,0,2,1,4,5,3,3,0};
		findRepeatingNums(arr);
	}
	
	public static void findRepeatingNums(int[] arr){
		if(arr == null || arr.length <2) return;
		for(int i=0; i<arr.length; i++){
			if( arr[Math.abs(arr[i])] >= 0)    arr[Math.abs(arr[i])] = -1 * arr[Math.abs(arr[i])] ;
			else    System.out.println(Math.abs(arr[i]));
	        }
	}
}

- King@Work May 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//requires end user to specify min and max int values allowed in nums[]
  public List<Integer> findRepeat(int nums[]) {
    Integer[] constantSpace = new Integer[10];  //expand to highest int allowed in nums[]. 
    //add translation of 'zero' to 1 + nums.length/2 to support negative integers if necessary.
    List<Integer> result = new ArrayList<Integer>();
    for (int i = 0; i < nums.length; i++) {
      constantSpace[i] = constantSpace[i] + 1;
    }    
    for (int i = 0; i < constantSpace.length; i++) {
      if (constantSpace[i] > 1) {
        result.add(nums[i]);
      }
    }        
    return result;
  }

- Anonymous May 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//requirements: end user need to specify min and max int values allowed in nums[] input. ints only cost 4 bytes of memory!
  //runs in 2n = O(n). Mem used = 4bytes * range of distinct ints that NEED to be found. And runs with Constant Space as requested.
  public List<Integer> findRepeat(int nums[]) { // aka - ifYouGotTheMemoryIGotTheTime(int howMuchMemoryYouGot[])  
    int min = -9;
    int max = 9;
    if (nums == null) {
      throw new IllegalArgumentException("input cannot be null");
    }
    int[] constantSpace = new int[19];  
    List<Integer> result = new ArrayList<Integer>();
    
    for (int i = 0; i < nums.length; i++) {
      if (nums[i] < min || nums[i] > max) {
        throw new IllegalArgumentException("Invalid input: " + nums[i] + ".  int values must be >= " + min + " and <= " + max);
      }
      int index = nums[i] + max;
      constantSpace[index] = constantSpace[index] + 1;
    }   
    
    for (int i = 0; i < constantSpace.length; i++) {
      if (constantSpace[i] > 1) {        
        result.add(i - max);
      }
    }        
    return result;
  }

- joe.jadamec May 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<int> FindDups(vector<int> &a)
{
	vector<int> dups;
	for (int i = 0; i < a.size(); ++i) {
		if (a[i] != i) {
			if (a[a[i]] == a[i]) {
				dups.push_back(a[i]);
			} else {
				if (a[i] > i) {
					swap(a[i], a[a[i]]);
					--i;
				} else {
					a[a[i]] = a[i];
				}
			}
		}
	}
	return dups;
}

- Alex May 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Some good old python:

def get_dupes(nl):
    """
    Sort original list in place, then
    go through and compare the side by side values
    Python .sort() method is O(nlogn) complexity
    get_dupes is O(n)? I think :)
    """
    # ex [1,1,3,4,5,5,6,6]
    nl.sort()
    dupes = []
    for index, number in enumerate(nl):
        # ex 0
        current = index
        # ex 1
        next = index+1
        # ex 0 >= 8 is false
        if next >= len(nl):
            break
        elif nl[current] == nl[next] and number not in dupes:
            # ex [1]
            dupes.append(number)
    # ex [1,5,6]
    return dupes

get_dupes([1,5,3,6,1,5,6,4])

- zip May 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Python 2:

def get_dupes(nl):
    """
    Sort original list in place, then
    go through and compare the side by side values
    Python .sort() method is O(nlogn) complexity
    get_dupes is O(n)? I think :)
    """
    # ex [1,1,3,4,5,5,6,6]
    nl.sort()
    dupes = []
    for index, number in enumerate(nl):
        # ex 0
        current = index
        # ex 1
        next = index+1
        # ex 0 >= 8 is false
        if next >= len(nl):
            break
        elif nl[current] == nl[next] and number not in dupes:
            # ex [1]
            dupes.append(number)
    # ex [1,5,6]
    return dupes

get_dupes([1,5,3,6,1,5,6,4])

- zipzap May 10, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why cant I Reply to a message?

- ABCD May 12, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findRepeat(A):
output = []
n = len(A)
for a in A:
if a < 0:
if A[a + n] < 0:
output.append(a + n)
else:
A[a + n] = A[a + n] - n
else:
if A[a] < 0:
output.append(a)
else:
A[a] = A[a] - n

return output

- flrf May 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findRepeat(A):
    output = []
    n = len(A)
    for a in A:
        if a < 0:
            if A[a + n] < 0:
                output.append(a + n)
            else:
                A[a + n] = A[a + n] - n
        else:
            if A[a] < 0:
                output.append(a)
            else:
                A[a] = A[a] - n
    
    return output

- flrf May 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findRepeat(A):

output = []

n = len(A)

for a in A:

if a < 0:

if A[a + n] < 0:

output.append(a + n)

else:

A[a + n] = A[a + n] - n

else:

if A[a] < 0:

output.append(a)

else:

A[a] = A[a] - n

return output

- flrf May 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findRepeat(A):
    output = []
    n = len(A)
    for a in A:
        if a < 0:
            if A[a + n] < 0:
                output.append(a + n)
            else:
                A[a + n] = A[a + n] - n
        else:
            if A[a] < 0:
                output.append(a)
            else:
                A[a] = A[a] - n
    
    return output

- flrf May 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findRepeat(A):
    output = []
    n = len(A)
    for a in A:
        if a < 0:
            if A[a + n] < 0:
                output.append(a + n)
            else:
                A[a + n] = A[a + n] - n
        else:
            if A[a] < 0:
                output.append(a)
            else:
                A[a] = A[a] - n
    
    return output

- Anonymous May 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use number as index and modify the numbers in place.

- Anonymous May 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about if we sort the array and figure out if any consecutive elements are same .It is better than 0(n) i.e. nlogn

- Aifra May 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Really enjoyed thinking on this problem :)
The key is that the cell values are less than n. Thus, you can use a[i] to store value i.
What I did was swapping the a[i] with the value at cell a[i] (a[a[i]]), to keep track of repetition. Here is my code:

set<int> Repeated(vector<int> a)
{
  set<int> ret;
  int i=0;
  while(i<a.size())
  {
    if(a[i]==i) i++; // go to next element
    else if(a[i] == a[a[i]]){
      ret.insert(a[i]);
      i++;
    }
    else
    {
      int temp = a[a[i]];
      a[a[i]] = a[i];
      a[i]=temp;
    }
  }
  return ret;
}


// To execute C++, please define "int main()"
int main() {
  vector<int> a = {4, 2, 0, 5, 2, 0, 1};
  vector<int> b = {1, 2, 3, 0, 0, 1, 3, 6, 6,6};
  set<int> c = Repeated(a);
  set<int> d = Repeated(b);
  for(int const & item:c)
    cout<<item<<' ';
  cout<<endl;
  for(int const & item:d)
    cout<<item<<' ';
  return 0;
}

- a.asudeh May 27, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think we can use the ‘negation’ technique here, because the elements in the list are all value of 0 to n-1,
we can use the element value as the ‘index or key’ of some other meaning (by inverting the value of the index into negative).
But usually we can use the negation when the value is more than 0 (because there is no +0 or -0).
So, I’m going to modify the list value by +1. (and we should do it in one pass.) when I invert the value.
The time would be O(n) and it ends in one pass.
The code (Python) will be as follows:

def find_repeat(nums):
    if not nums: return
        
    for i in range(len(nums)):
        index = -1
        if nums[i] >= 0:
            index = nums[i]
        else:
            index = abs(nums[i]) -1
            
        if nums[index] >= 0:
            nums[index] = -1*(nums[index] +1)
        else:
            # duplicates!
            print(index, end=" ")
            
    print("")
    
if __name__ == '__main__':
    nums1 = [4, 2, 0, 5, 2, 0, 1]
    nums2 = [1, 2, 3, 0, 0, 1, 3, 6, 6, 6]
    
    find_repeat(nums1) # 0 2
    find_repeat(nums2) # 0 1 3 6 6

- diko June 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findRepeats(arr):
    list = [];
    for i in range(len(arr)):
        arr[arr[i] % len(arr)] = arr[arr[i] % len(arr)] + len(arr);
    index=0;    
    for i in arr:
        if (i/len(arr)) > 1:
            list.append(index);
        index=index+1;         
    print arr;        
    return list;    
    
    
print findRepeats([1, 2, 2, 1, 3]);

- undefined June 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<Integer> findRepeat(int[] input) {
        List<Integer> list = new ArrayList<>();
        int n = input.length;
        int empty = n + 1;

        for(int i = 0; i < input.length; i++) {
            if(input[i] == i || input[i] == empty) {
                continue;
            } else if(input[i] == n){
                list.add(i);
            } else {
                int index = input[i];
                int temp = input[index];

                if(index < i) {
                    if(temp == n) {
                        input[i] = empty;
                        continue;
                    } else if(temp == index) {
                        list.add(index);
                        input[index] = n;
                        input[i] = empty;
                        continue;
                    } else {
                        input[index] = input[i];
                        input[i] = temp;
                        i--;
                        continue;
                    }
                } else {
                    if(temp == n) {
                        input[i] = empty;
                        continue;
                    } else if(temp == index) {
                        input[index] = n;
                        input[i] = empty;
                        continue;
                    } else {
                        input[index] = input[i];
                        input[i] = temp;
                        i--;
                        continue;
                    }
                }

            }
        }return list;

}

- Feisal August 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<Integer> findRepeat(int[] input) {
        List<Integer> list = new ArrayList<>();
        int n = input.length;
        int empty = n + 1;

        for(int i = 0; i < input.length; i++) {
            if(input[i] == i || input[i] == empty) {
                continue;
            } else if(input[i] == n){
                list.add(i);
            } else {
                int index = input[i];
                int temp = input[index];

                if(index < i) {
                    if(temp == n) {
                        input[i] = empty;
                        continue;
                    } else if(temp == index) {
                        list.add(index);
                        input[index] = n;
                        input[i] = empty;
                        continue;
                    } else {
                        input[index] = input[i];
                        input[i] = temp;
                        i--;
                        continue;
                    }
                } else {
                    if(temp == n) {
                        input[i] = empty;
                        continue;
                    } else if(temp == index) {
                        input[index] = n;
                        input[i] = empty;
                        continue;
                    } else {
                        input[index] = input[i];
                        input[i] = temp;
                        i--;
                        continue;
                    }
                }

            }
        }return list;
    }

- Feisal August 29, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

public List<Integer> findRepeat(int nums[]){ 
	List<Integer> findList = new ArrayList<Integer>();
	List<Integer> findListFinal = new ArrayList<Integer>();
	if(nums.length() == 0) return findListFinal;

	for(int x:nums){
		if(!findList.contains(x)) findList.add(x);
		else findListFinal.add(x);
	}
}

- mp May 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

It can be done by modifying the existing array -

Points to be noted from questions-
1- Element range in the array is 0-n-1, Hence we can use the indexes to get frequency.
2- O(1) extra space and O(n) time complexity

In our approach , we will modify the existing array to get frequency.
eg. a = [1,2,3,2] n = 4
Steps-
1- We will make the changes at index ind = a[i]%n , and will make a[ind] += n . Hence after first iteration our array will become [1,6,11,6]
2- Iterate again to get the repeated elements-
we will check if arr[i]/n > 1 => i is repeating element in the array and i can be added to resultant list, e.g. a[2]/n = 2, Hence 2 is repeating 2 times

public static List<Integer> repeated(int[] a){
		ArrayList<Integer> list = new ArrayList<>();
		int n = a.length;
		for(int i=0;i<n;i++){
			int ind = a[i]%n;
			a[ind] = a[ind] + n;
		}
		
		for(int i=0;i<n;i++){
			if(a[i]/n > 1){
				list.add(i);
			}
		}
		
		
		return list;
		
		
	}

- azambhrgn May 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@gator, My Logic is working fine, There is an if condition in second loop , That will add only numbers which are occurring more than 1 to the list. Kindly check again.
I have tested with few test cases.

@All , If you are down voting some answer then better give some explanation as well.

- azambhrgn May 09, 2017 | 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