Google Interview Question
InternsCountry: United States
Interview Type: Phone Interview
This is an Objective-C solution in O(n) time and O(1) space, since the integers in the array are not greater than the size of the array we can use them as an index of the same array and mark each number in index as negative and then if we found that X number is already negative that is a duplicate number
-(void)findDuplicatesInArray:(NSMutableArray *)array{
for(int i = 0; i < [array count]; i++){
int temp = abs([array[i] intValue]);
if([array[temp] intValue] >= 0){
array[temp] = [NSNumber numberWithInt:-abs([array[temp] intValue])];
}
else{
NSLog(@"%i", abs([array[i] intValue]));
}
}
}
1. Let a[i] be the value of an element in the array: 0 <= a[i] <= n and n be the #elements in a
2. k = #bits to represent 0..n: k = ceiling(log2(N))
3. m = #bits of the datatype, e.g. 32
4. if k < m: we have at least n bits we can use to store some information
5. let value(i) be the value of a[i] that only uses k bits: value(i): a[i]&((1<<k)-1)
so we can iterate over the array and extract the value of a[i] = value(i)
if a[i] != value(i) that is a dublicate we have found a dublicate
if not store in a[value(i)] = value(i) + (1<<(k+1)) (or value(i) + n, or anything like this...)
following thoughts are important:
1) this is theoretically not O(1) space but practically it is O(1) space: why, it uses bits that are allocated but not used
2) since the array is modified, it might be a good idea to revert the change in the array after finding a dublicate, especially if the function name does not imply modifications of the array
3) even if you do redo the changes, the array will temporarily be changed, so in production, this
will have side effects if concurrent access to the array happens.
this given we can do:
// returns -1 if no dublicate was found
int getAnyDublicate(vector<int>& a)
{
int result = -1;
if(a.size() <= 1) return result;
int k = static_cast<int>(log2(a.size() - 1) + 1.0);
assert(k < numeric_limits<unsigned int>::digits);
unsigned int datamask = (1 << k) - 1;
unsigned int seenmask = (1 << (k + 1));
for(int e : a)
{
int v = e & datamask;
if(a[v] & seenmask != 0) { result = v; break; }
a[v] |= seenmask;
}
for(int& e : a) e &= datamask; // revert all changes
return result;
}
int[] findDuplicates(int[] intArray){
int arrLength = intArray.length;
byte[] duplArr = new byte[arrLength];
int dupCount = 0;
for(int index=0; index<arrLength; index++ ){
if( duplArr[intArray[index]-1] == 1) {
duplArr[intArray[index]-1] = 2;
dupCount++;
}
else if( duplArr[intArray[index]-1] == 0){
duplArr[intArray[index]-1] = 1 ;
}
}
int[] dupOutputArr = new int[dupCount];
int outputArrIndex = 0;
for(int index=0; index<arrLength; index++ ){
if(duplArr[index] == 2){
dupOutputArr[outputArrIndex] = index+1;
outputArrIndex++;
}
}
return dupOutputArr;
}
int[] findDuplicates(int[] intArray){
int arrLength = intArray.length;
byte[] duplArr = new byte[arrLength];
int dupCount = 0;
for(int index=0; index<arrLength; index++ ){
if( duplArr[intArray[index]-1] == 1) {
duplArr[intArray[index]-1] = 2;
dupCount++;
}
else if( duplArr[intArray[index]-1] == 0){
duplArr[intArray[index]-1] = 1 ;
}
}
int[] dupOutputArr = new int[dupCount];
int outputArrIndex = 0;
for(int index=0; index<arrLength; index++ ){
if(duplArr[index] == 2){
dupOutputArr[outputArrIndex] = index+1;
outputArrIndex++;
}
}
return dupOutputArr;
}
int[] findDuplicates(int[] intArray){
int arrLength = intArray.length;
byte[] duplArr = new byte[arrLength];
int dupCount = 0;
for(int index=0; index<arrLength; index++ ){
if( duplArr[intArray[index]-1] == 1) {
duplArr[intArray[index]-1] = 2;
dupCount++;
}
else if( duplArr[intArray[index]-1] == 0){
duplArr[intArray[index]-1] = 1 ;
}
}
int[] dupOutputArr = new int[dupCount];
int outputArrIndex = 0;
for(int index=0; index<arrLength; index++ ){
if(duplArr[index] == 2){
dupOutputArr[outputArrIndex] = index+1;
outputArrIndex++;
}
}
return dupOutputArr;
}
// Time: O(n)
// Space: O(1)
std::vector<int> arrayDuplicates(std::vector<int> &A)
{
std::vector<int> ret;
int processedMarker = A.size();
for (int i=0; i<A.size(); i++) {
if ( A[i] != i ) {
int newIndex;
while( A[i] != i ) {
if (A[i] == processedMarker || A[newIndex] == processedMarker )
break;
if (A[newIndex] == A[i]) {
ret.push_back(A[i]);
A[newIndex] = processedMarker;
A[i] = processedMarker;
break;
}
swap(A[i], A[newIndex]);
}
}
}
return ret;
}
// Time: O(n)
// Space: O(1)
// It will not work if there are values in array < 0
// 0 case is handled fine
std::vector<int> arrayDuplicates(std::vector<int> &A)
{
std::vector<int> ret;
int processedMarker = A.size();
for (int i=0; i<A.size(); i++) {
if ( A[i] != i ) {
int newIndex;
while( A[i] != i ) {
newIndex = A[i];
if (A[i] == processedMarker || A[newIndex] == processedMarker )
break;
if (A[newIndex] == A[i]) {
ret.push_back(A[i]);
A[newIndex] = processedMarker;
A[i] = processedMarker;
break;
}
swap(A[i], A[newIndex]);
}
}
}
return ret;
}
int main()
{
vector<int> A{0,2,1,1,1,1,0,2};
auto V = arrayDuplicates(A);
for (auto v : V) {
cout << v << endl;
}
return 0;
}
public int missing(int[] arr){
if(arr == null || arr.length == 0){
throw new IllegalArgumentException();
}
for(int i = 0; i < arr.length; i++){
while(arr[i] != i){
int dest = arr[i];
if( dest < arr.length && arr[dest] != dest){
swap(i,dest,arr);
}else{
break;
}
}
}
for(int i = 0; i < arr.length; i++){
if(arr[i] != i){
return i;
}
}
}
private void swap(int a, int b, int[] arr){
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
Why not to consider sorting? In c# Sort is in-place.
1. Sort
2. Iterate through sorted array and return first duplicate.
Will handle 0 negative cases
public class Duplicate
{
public int? GetDuplicate(int[] arr)
{
Array.Sort(arr);
int el_prev = arr[0];
for (int i=1; i< arr.Length; i++)
{
if (el_prev == arr[i]) return el_prev;
el_prev = arr[i];
}
return null;
}
}
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int duplicate(vector<int>& integers) {
unordered_map<int, int> visited_elements;
unordered_map<int, int>::const_iterator locate;
for(register size_t i = 0; i < integers.size(); ++i) {
if((locate = visited_elements.find(integers[i])) == visited_elements.end()) {
visited_elements[integers[i]] = i;
} else {
return integers[i];
}
}
}
int main() {
vector<int> my_vec = {1, 2, 3, 2, 4};
int repeated_integer = duplicate(my_vec);
cout << "Repeated integer: " << repeated_integer << endl;
return 0;
}
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int duplicate(vector<int>& integers) {
unordered_map<int, int> visited_elements;
unordered_map<int, int>::const_iterator locate;
for(register size_t i = 0; i < integers.size(); ++i) {
if((locate = visited_elements.find(integers[i])) == visited_elements.end()) {
visited_elements[integers[i]] = i;
} else {
return integers[i];
}
}
}
int main() {
vector<int> my_vec = {1, 2, 3, 2, 4};
int repeated_integer = duplicate(my_vec);
cout << "Repeated integer: " << repeated_integer << endl;
return 0;
}
Not sure if negative elements are also considered here. But, if we don't have them, then we can use 'negative sign' to keep track of the elements in the array.
- amitexam November 08, 2016