Interview Questions

Problems on search/ sort
---------------------------

Q. Design an algorithm to find the duplicates in an array.

Given an array of random integers, write an algorithm in C that removes duplicated numbers and return the unique numbers in the original array.

E.g Input: {4, 8, 4, 1, 1, 2, 9} Output: {4, 8, 1, 2, 9, ?, ?}

void rmdup(int *array, int length){
int *current , *end = array + length - 1;

for ( current = array + 1; array < end; array++, current = array + 1 ){
  while ( current < end ){
    if ( *current == *array ){
        *current = *end--;
    }
    else{
        current++;
    }
 }// while ends ... } // for ends ... } // func ends
=====================
Q. Given an array of length N containing integers between 1 to Nm determine if it contains any duplicates.

How can we efficiently find out if any of those numbers are duplicates ? To know only

The easiest approach is to make a hash table to keep track of the numbers we've seen so far.
Something like this:

Given an array A of length n,

let h ← (new hash table)
for 1 <= i <= n:
if A[i] is present in h: return A[i]
set h[A[i]] ← True
return

OR ALTERNATIVELY

let s ← array [1..n]
initialize s to all zeroes
for 1 <= i <= n:
if s[A[i]] > 0: return A[i]
set s[A[i] ← 1

IF we have constant space; no more creating hash tables and arrays on the fly

Since there are n values from 1 to n-1 with one duplicate, we can use the fact that the sum of the integers from 1 to m is (m*(m+1))/2, take the sum from 1 to n-1, subtract that from the actual sum of numbers in the array, and the result will be the duplicated number:

let s ← 0
for 1 <= i <= n:
s ← s + A[i]
return s - n*(n-1)/2

==============
Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?

int findDup (int *a, int len) { // len is 1001 here
int found, i, t;

for (i = 0; i < len; i++) {
t = a[i] > 0 ? a[i] : -a[i];

if (a[t] > 0)
a[t] = -a[t]; // use negative as a mark
else { // if it is already marked, it must be a dup!
found = t;
break;
}
}

for (i = 0; i < len; i++)
a[i] = (a[i] > 0) ? a[i] : -a[i]; // restore the array

return found;
}
===================
Q. Program to remove duplicates from a sorted array.

Q. There is a fixed size list of no, given that how to find out if an element in 2nd list (fixed size)
is present in the first list.
===================
Q. Find contiguous subarray within an given array of integers.
void maxSumSubArray( int *array, int len, int *start, int *end, int *maxSum )
{
int maxSumSoFar = -2147483648;
int curSum = 0;
int a = b = s = i = 0;
for( i = 0; i < len; i++ ) {
curSum += array[i];
if ( curSum > maxSumSoFar ) {
maxSumSoFar = curSum;
a = s;
b = i;
}
if( curSum < 0 ) {
curSum = 0;
s = i + 1;
}
}
*start = a;
*end = b;
*maxSum = maxSumSoFar;
}
===================
Q. Find the 2 numbers where the difference is minimum among the set of numbers.




3. Data Structures 
 3.a Link list problems +
    http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
 3.b - Hash
 3.c - Binary Trees
 3.d -
Miscellaneous Links
Reb-Black Tree +
http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf
http://www.cs.princeton.edu/courses/archive/fall08/cos226/lectures/10BalancedTrees-2x2.pdf
Trie Implementation Example +
http://www.cs.bu.edu/teaching/c/tree/trie/

4. Linux System

5. Ip table and NAT related info +
https://www6.software.ibm.com/developerworks/education/l-packet/l-packet-a4.pdf
http://www.linuxhomenetworking.com/wiki/index.php/Quick_HOWTO_:_Ch14_:_Linux_Firewalls_Using_iptables
http://books.google.com.sg/books?id=T8V02u2jDP0C&pg=PT152&lpg=PT152&dq=ip+packet+processing+linux&source=bl&ots=6GXbsRfLJ_&sig=q781FGrsp0twWNcB_K-ol_spFCo&hl=en&ei=QdImTs-TK8yHrAez3vSsCQ&sa=X&oi=book_result&ct=result&resnum=10&ved=0CFoQ6AEwCTgU#v=onepage&q=ip%20packet%20processing%20linux&f=false
http://www.wisdomjobs.com/e-university/linux/chapter-180-277/the-linux-tcp-ip-stack.html
http://www.ecsl.cs.sunysb.edu/elibrary/linux/network/recvpath.pdf
http://www.google.com.sg/#q=ip+packet+processing+linux&hl=en&prmd=ivnsb&ei=BtImTozqLcjVrQeflO2vCQ&start=20&sa=N&fp=97340d1897d20133&biw=1280&bih=892
http://www.cookinglinux.org/pub/netdev_docs/iprecv2.pdf

Interview questions +
http://www.mytechinterviews.com/reverse-the-order-of-words-in-a-string

http://rapidtrend.com/f/1917556/the_art_of_computer_programming_2nd_ed_vol3_donald_knuth.html

Linux +
Intruppt Handler ++
IP Packet Processing ++