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) ?
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
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);
}
}
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+1Given 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 :
http://courses.csail.mit.edu/iap/interview/materials.php – Pure Gold
also, a must read – http://news.ycombinator.com/item?id=1633892
Steve Yegge talks about the difficulties of a phone interview.
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
Its been a very long time since I have been looking for a good explanation/implementation of TRIEs in Java. Unfortunately, internet is full of incomplete or too academic articles.
Finally, today I stumbled upon a very practical article : Source Uploaded here.
Find vertical sum of given binary tree.
Example:
1
/ \
2 3
/ \ / \
4 5 6 7
The tree has 5 vertical lines
Vertical-1: nodes-4 => vertical sum is 4
Vertical-2: nodes-2 => vertical sum is 2
Vertical-3: nodes-1,5,6 => vertical sum is 1+5+6 = 12
Vertical-4: nodes-3 => vertical sum is 3
Vertical-5: nodes-7 => vertical sum is 7
We need to output: 4 2 12 3 7
