Given an array A[n] such that A[i+1] = A[i]+1 OR A[i]-1, and a number k, can you determine in most efficient way whether k is present in A[n] or not?

bool findElement(int a[], int length, int expectedNum)
{
	int i = 0;
	while(i < length)
	{
		if(a[i] == expectedNum)
			return true;
		else
		{
			int diff = abs(expectedNum - a[i]);
			i = diff + i;
		}
	}
	return false;
}

Maths – Problem solving shortcuts

Here is a pdf of all must-know shortcuts for solving math puzzles/problems

https://docs.google.com/file/d/0BwBNB2MLLRV7VHlFZlcxdThRSWc/edit?usp=sharing

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
}

Interview Question: Data Structure for Tic-Tac-Toe

Odinlake

Got this recently:

How would you design a data structure for the game Tic Tac Toe? The main objective is to provide: A method, as efficient as possible, for checking the board to see if there is a winner.

View original post 372 more words

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