Programming Interview Questions

1) Given an integer x and a sorted array a of N distinct integers, design a linear-time algorithm to determine if there exists two distinct indices i and j such that a[i] + a[j] == x
http://stackoverflow.com/questions/11928091/linear-time-algorithm-for-2-sum

2) Find the starting node of the linked list cycle
http://stackoverflow.com/questions/2936213/explain-how-finding-cycle-start-node-in-cycle-linked-list-work
Using this diagram. Let
i = m + p.n + k - m
2i = m + q.n + k - m

k = (q - 2p).n    i.e. a multiple of cycle length

Now, let
k - m + x = n
Then,
k = (q - 2p -1).n + k - m + x
m = (q - 2p -1).n + x

So, if two pointers start at the beginning of the list and the meeting point and move the same number of steps, they will meet at the starting node of the cycle.

3) Given a string find all its permutations:

#include <stdio.h>
#include <string.h>
void perm(char * base, int * res, int pos)
{
int i,j;
for (i = 0; i < strlen(base); i++){
 for (j = 0; j < pos; j++)
   if (i == res[j])
      break;
 if (j==pos){
    res[pos] = i;
    if (pos+1 != strlen(base))
      perm(base, res, pos + 1);
    else{
      for (j = 0; j < strlen(base); j++)
         printf("%c",base[res[j]]);
      printf("\n");
      return;
    }
 }
}
}
int main(){
int i;
char str[10];
int res[10];
printf("Enter a string: ");
scanf("%s",str);
for (i = 0; i < strlen(str); i++)
{
res[0] = i;
perm(str, res, 1);
}
return 0;
}

4) Counting inversions in a array:
http://stackoverflow.com/questions/337664/counting-inversions-in-an-array

5) Find the element appearing more than n/2 times in an array in O(n) time.
http://keithschwarz.com/interesting/code/?dir=majority-element

6) Find the median of two sorted arrays
http://www.youtube.com/watch?v=_H50Ir-Tves

7) Each node of a linked list is of struct data type

struct node {
    struct node *next;
    struct node *what;
    void *data;
};

what is a pointer to a random node in the list. Duplicate the list in O(N) time without using any extra space.

http://stackoverflow.com/questions/1924741/deep-copy-linkedlist-without-destroying-original-list-and-extra-storage-space-u/1924968#1924968

8) Given an array of size N, find the sub-sequence of elements of size L in the array which has the maximum sum in O(N) time.

http://stackoverflow.com/questions/7861387/maximum-contiguous-subsequence-sum-of-at-least-length-l