Given an array of length N containing integers between 1 and N, determine if it contains any duplicates in O(n) time complexity and O(1) space complexity

Since we cannot use extra space, take advantage of the fact that the array has elements only from 1 to n
and there are n elements in the array(index ranges from 0 to n-1)
So if 1 occurs make value at 0th index negative
if 2 occurs make the value at 1st index negative
if n occurs make the value at n-1th index negative
So if the same number occurs again then the value at that number index will be found negative already and
voila !Thus we found a way finding repeating number.
Algorithm
traverse the list for i= 0 to n-1 elements
{
check for sign of A[abs(A[i])] ;
if positive then
make it negative by A[abs(A[i])]=-A[abs(A[i])];
else // i.e., A[abs(A[i])] is negative
this element (ith element of list) is a repetition
}

Given a 10GB file of integers and a RAM that can hold only 4GB values, how would you sort the integers in the file.

Divide the file in 3 parts(3.5 GB+3.5 GB+3 GB,(each part must be less than  4GB )) and sort each chunk using any O(nlogn) sorting algo(as it is less than 4GB we can apply any in-place sorting algo). once each chunk of file sorted, bring 1GB of each chunk in memory, so it’ll occupy 3GB(1+1+1), now sort this 3GB data(by 3-way merge sort).

When executing the merge function select the minimum element add that in remaining 1GB, and while selecting this number, bring the first number from remaining  set from the corresponding chunk to replace it, finally write sorted 1GB to secondary storage.

Example:

let say we divide file in three chunk A,B,C and after sorting individully, content of these parts is like: A{12,18,20,25,33,35,37},B{8,13,14,40,41,45,47},C{2,15,50,70,72,75,78}.
Now suppose in memory, we have {12,18,20,25} {8,13,14,40} {2,15,50,70} respectively from A,B,C. now we’ll select 2 from C’s part as its minimum, so put this in remaining 1GB and replace 2 in memory by an element of chunk C. i.e. insert 72 in C’s part in memory.. next replace 8 by 41 and so on.. we are maintaining a min heap.

source:careercup.com

implement your own sizeof() operator

Define a macro as shown in line 3 in the code

#include<iostream>
using namespace std;
#define mysizeof(data) (char*)(&data+1)-(char*)(&data)

int main(){

char arr[]={1,2,3};
int arr1[]={1,2,3};
cout<<mysizeof(arr);
cout<<endl<<mysizeof(arr1);
}

output:

3

12

suppose memory location for arr1[] starts with 2000, then arr1[]+1 will point to 2012 and not 2004.
This is because arr1[] is referring to the complete array and hence arr1[]+1 will refer to a memory location just next to the last element of the array.
So, the output with mysizeof(arr1) gives you 12

source:careercup,com

 

write a method power(a,n) that computes power of number a in O(logn)

Time complexity: O(logn)

Since the problem gets divided into half in each stage of recursion the time complexity is O(logn)

	#include<iostream>
	using namespace std;
	long long int power(long long int a,long long int n){
	long long int halfpow;
	if(n==0)
	return (long long int)1;
	halfpow=power(a,n/2);
	if(n%2==0){
	return halfpow*halfpow;
	}
	else{
	return a*halfpow*halfpow;
	}
	}
	int main(){
	cout<<power(10,10);
	}

view raw power.cpp hosted with ❤ by GitHub