This Great Article – coupled with a slightly complex wikipedia article makes a lot of sense.

# Permutations of a string

Lets take this old question and discuss a very elegant solution to it.

For a string “ABC”, we have these permutations : “ABC,ACB,BAC,BCA,CAB,CBA”

First, lets look at this elegant code below and try to find out how it works.

```
public class Permutations {
public static void permute(String s){
permute("",s);
}
private static void permute(String prefix, String s){
System.out.println(prefix + "---"+ s);
int n=s.length();
if (n==0)
System.out.println("-------------------------------"+prefix);
else
{
for(int i=0;i<n;i++){
permute(prefix + s.charAt(i), s.substring(0,i) + s.substring(i+1,n));
}
}
}
public static void main(String[] args) {
//
permute("ABC");
}
}
```

Note that line :

System.out.println(prefix + “—“+ s);

is just to debug this.

The output is very interesting.

private method permute is called with (“”,”ABC”) first time.

`---ABC`

A---BC

AB---C

ABC---

-------------------------------ABC

AC---B

ACB---

-------------------------------ACB

B---AC

BA---C

BAC---

-------------------------------BAC

BC---A

BCA---

-------------------------------BCA

C---AB

CA---B

CAB---

-------------------------------CAB

CB---A

CBA---

-------------------------------CBA

This is a good example of how recursion simplifies things.

# Longest increasing subsequence

Longest Increasing Subsequence has been a classic Dynamic Programming problem. O(N^2) has been around for a while but more interesting is the following O(n log n) solution.

For example : We have sequence : 1,8,2,7,3,6,4,5 which has the longest increasing subsequence : 1,2,3,4,5. How to arrive at this in O(n log n) ?

# Reverse Linked Lists – phew!

I am not really a fan of this question but it seems to be quite a favorite question during technical interview. So, lets discuss reversing a linked-list problem at length.

Basically there are two methods of reversing a linked list – iterative and recursive. Lets discuss the iterative method :

**Logic:** Iterate trough the linked list. In loop, change next to prev, prev to current and current to next.

```
private static void reverseIterative()
{
Node prev=null;
Node current= head;
Node next=null;
while(current != null)
{
next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
}
```

This is simple and has the following complexity :

Time Complexity: O(n)

Space Complexity: O(1)

The recursive method needs a bit of thinking – lets visualize our problem first.

The logic looks like this :

1) Divide the list in two parts – first node and rest of the linked list.

2) Call reverse for the rest of the linked list.

3) Link rest to first.

4) Fix head pointer

# Reverse a Linked List in groups of given size

Given a linked list, write a function to reverse every k nodes (where k is an input to the function).

**Example:**

Inputs: 1->2->3->4->5->6->7->8->NULL and k = 3

Output: 3->2->1->6->5->4->8->7->NULL.

Inputs: 1->2->3->4->5->6->7->80->NULL and k = 5

Output: 5->4->3->2->1->8->7->6->NULL.

**Algorithm: reverse(head, k)**

1) Reverse the first sub-list of size k. While reversing keep track of the next node and previous node. Let the pointer to the next node be next and pointer to the previous node be prev.

2) head->next = reverse(next, k) /* Recursively call for rest of the list and link the two sub-lists */

3) return prev /* prev becomes the new head of the list (see the diagrams of iterative method of this post) */

```
class ReverseKLL
{
static class Node
{
int data;
Node next;
Node(int data)
{
this.data = data;
next =null;
}
}
public static Node head = null; //Create head node
//Recursive Reversal of a group of k elements
//1. Reverse the first sub-list of k element and keep track of next and previous nodes
//2. head.next = reverse(next,k ) - recursively call this function on sub-groups
//3. return prev - prev becomes new next
private static Node reverse(Node node, int k)
{
Node current = node;
Node next= node, prev=null;
int count = 0;
//reverse first k elements
while(current != null && count < k)
{
next = current.next;
current.next = prev;
prev = current;
current=next;
count ++;
}
//next is now pointer to k+1th node. Recursively call reverse
//for the list starting from that point
if (next!=null)
{
node.next = reverse(next,k);
}
//prev is the new head
return prev;
}
//utility methods
//push a node in the ll
private static void push(int data)
{
Node newnode= new Node(data);
newnode.next = head;
head = newnode;
}
public static void printList(Node node)
{
while (node != null)
{
System.out.println(node.data);
node = node.next;
}
}
public static void main(String args[])
{
ReverseKLL kll = new ReverseKLL();
kll.push(8);
kll.push(7);
kll.push(6);
kll.push(5);
kll.push(4);
kll.push(3);
kll.push(2);
kll.push(1);
kll.printList(head);
head=kll.reverse(head, 3);
System.out.println("===========================");
kll.printList(head);
}
}
```

# Intersection of two Arrays

Very simple algorithm but somehow interviewers love this. So, here it is:

For example, if the input arrays are:

arr1[] = {1, 3, 4, 5, 7}

arr2[] = {2, 3, 5, 6}

Then your program should print Intersection as {3, 5}.

**Algorithm**:

For Intersection of two arrays, print the element only if the element is present in both arrays.

1) Use two index variables i and j, initial values i = 0, j = 0

2) If arr1[i] is smaller than arr2[j] then increment i.

3) If arr1[i] is greater than arr2[j] then increment j.

4) If both are same then print any of them and increment both i and j.

**Code:**

```
a1 = [1,3,4,5,7]
a2 = [2,3,5,6]
i,j = 0,0
#Get length of the larger array as the count
count = (max(len(a1), len(a2)))
for x in range(0,count):
if (a1[i] a2[j]):
j = j+1
elif (a1[i] == a2[j]):
print a1[i]
i = i+1
j = j+1
```

# Group all anagrams

Given a set of words in a dictionary, write a program to group all words which are anagrams of each other in to sets.

input: “bat”, “tar”, “xyz” , “tab”, “tar” output:[[“bat”, tab”], [“tar”, rat”],”xyz” ]

The simpler logic would be to :

- Use some sort of a hash structure
- Sort all words alphabetically and use the sorted word as the key
- If the key is found, keep on adding the original word to the ‘value’ list of strings

# Mastering Programming Interview Questions

http://courses.csail.mit.edu/iap/interview/materials.php – Pure Gold

also, a must read – http://news.ycombinator.com/item?id=1633892

# Phone Interview Silverbullet

Steve Yegge talks about the difficulties of a phone interview.

# Card Shuffle.

Write a program to shuffle an pack of cards in the most efficient way. This question can be asked in several flavors.

Knuth Shuffle / Fisher-Yates Shuffle(Modified version by Durstenfeld) algorithm is the answer to all the trick questions. So how does this algorithm work ? Continue reading