Facebook Interview Question
SDE1sCountry: United States
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;
}
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
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]
*/
}
}
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;
}
}
@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;
}
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]));
}
}
}
//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;
}
//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;
}
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])
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])
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;
}
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
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;
}
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;
}
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);
}
}
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;
}
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
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