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;
}

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 a stack having findMiddle operation as well, which returns middle element of stack on O(1) time.

[gist https://gist.github.com/vishnujayvel/6098074]

Move the spaces to the starting of the string in a c style string. In place within one iteration.

Start two pointers i & j from the end of the string.

a. Keep copying the character from ith location to the jth location and decrement both i & j
b. When i encounters a space, decrement i, but not j
c Repeat steps a & b until i falls of the beginning of the string.
d. Keep setting ‘space’ character at jth location and decrement j unitl j falls of the beginning of the string

source:careercup.com

Swapping every pair of nodes in a single linked list

Provided n1->n2->n3->n4->n5
in general for each pair starting with n
have a temp variable that will keep copy of reference to n.next

Consider the link list n1->n2->n3->……

and n=n1
temp=n.next             //temp=n2
n.next=n.next.next//n1.next=n1.next.next=n3

temp.next=n          //n2.next=n1

Now move n to n.next//n=n1.next=n3
Repeat the same for next pair.but we have to link previous pair with the current pair
Which will have previous pairs 2nd element ? its temp.next
So make temp.next.next=n.next

Thats it!!

 

Also you can swap the pairs by just swapping the value.That is way too simple.Look at the 2nd function
Source code:

[gist https://gist.github.com/vishnujayvel/6049904]