import java.util.*;
import java.lang.*;
import java.io.*;
class Table{
void printTable(int n){
synchronized(this){
System.out.println(n);
}
}
}
class MyThread1 extends Thread {
Table t;
MyThread1(Table t){
this.t=t;
}
public void run(){
t.printTable(5);
}
}
class MyThread2 extends Thread{
Table t;
MyThread2(Table t){
this.t=t;
}
public void run(){
t.printTable(100);
}
}
class TestSynchronizedBlock1{
public static void main(String args[]){
Table obj = new Table();
MyThread1 t1=new MyThread1(obj);
MyThread2 t2=new MyThread2(obj);
t1.start();
t2.start();
}
}
Daily Archives: January 27, 2015
Longest Common Subsequence
int lcs( char *X, char *Y, int m, int n )
{
if (m == 0 || n == 0)
return 0;
if (X[m-1] == Y[n-1])
return 1 + lcs(X, Y, m-1, n-1);
else
return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}
Longest Palindromic Subsequence
int lps(char *seq, int i, int j) // i and j are first and last character
{
// If there is only 1 character
if (i == j)
return 1;
// If there are only 2 characters and both are same
if (seq[i] == seq[j] && i + 1 == j)
return 2;
// If the first and last characters match
if (seq[i] == seq[j])
return lps (seq, i+1, j-1) + 2;
// If the first and last characters do not match
return max( lps(seq, i, j-1), lps(seq, i+1, j) );
}
Threads
class MultithreadingDemo implements Runnable{
public void run(){
System.out.println("My thread is in running state.");
}
public static void main(String args[]){
MultithreadingDemo obj=new MultithreadingDemo();
Thread tobj =new Thread(obj);
tobj.start();
}
}
class MultithreadingDemo extends Thread{
public void run(){
System.out.println("My thread is in running state.");
}
public static void main(String args[]){
MultithreadingDemo obj=new MultithreadingDemo();
obj.start();
}
}
String vs StringBuilder vs StringBuffer
String
String is immutable ( once created can not be changed )object . The object created as a String is stored in the Constant String Pool . They are thread safe.
StringBuffer
StringBuffer is mutable means one can change the value of the object . Object created through StringBuffer is stored in the heap. Each method in StringBuffer is synchronized that is StringBuffer is thread safe
StringBuilder
StringBuilder is same as the StringBuffer , that is it stores the object in heap and it can also be modified . StringBuilder is also not thread safe.
Reverse alternate K nodes in a Singly Linked List
Example:
Inputs: 1->2->3->4->5->6->7->8->9->NULL and k = 3 Output: 3->2->1->4->5->6->9->8->7->NULL.
Algo
kAltReverse(struct node *head, int k) 1) Reverse first k nodes. 2) In the modified list head points to the kth node. So change next of head to (k+1)th node 3) Move the current pointer to skip next k nodes. 4) Call the kAltReverse() recursively for rest of the n - 2k nodes. 5) Return new head of the list.
Code
struct node *kAltReverse(struct node *head, int k)
{
struct node* current = head;
struct node* next;
struct node* prev = NULL;
int count = 0;
while (current != NULL && count < k)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}
if(head != NULL)
head->next = current;
count = 0;
while(count < k-1 && current != NULL )
{
current = current->next;
count++;
}
if(current != NULL)
current->next = kAltReverse(current->next, k);
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.
struct node *reverse (struct node *head, int k)
{
struct node* current = head;
struct node* next = NULL;
struct node* prev = NULL;
int count = 0;
/*reverse first k nodes of the linked list */
while (current != NULL && count < k)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}
/* next is now a pointer to (k+1)th node
Recursively call for the list starting from current.
And make rest of the list as next of first node */
if(next != NULL)
{ head->next = reverse(next, k); }
/* prev is new head of the input list */
return prev;
}
Reverse a linked list
Iterative Method
static void reverse(struct node** head_ref)
{
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
Recursive Method
let’s say we are dealing with node 99 in the linked list image above – the Node coming after node 99 (node 37) is represented by Node 99 -> next. If we want node 37 to point back to node 99 (which is what we would want if we are reversing the nodes), then we would set the next pointer of node 37 to point back to Node 99, which in pseudocode would look like Node99 -> next -> next = Node 99.
We would also need to get rid of the pointer from node 99 to node 37 so we would have to set Node 99 -> next to NULL.
CODE
public void recursiveReverse(Node currentNode )
{
if(currentNode == NULL)
return;
if(currentNode.next == NULL)
{
head = currentNode;
return;
}
recursiveReverse(currentNode.next);
currentNode.next.next = currentNode;
currentNode.next = null; //set "old" next pointer to NULL
}
Find the largest multiple of 3
1.Sort the array in increasing order.
2.Queue q0 stores the elements which on dividing by 3 gives remainder 0.
3.Queue q1 stores the elements which on dividing by 3 gives remainder 1.
4.Queue q2 stores the elements which on dividing by 3 gives remainder 2.
5.Find the sum of all the given digits.Let it be ‘s’.
6.If s is divisible by 3,goto step 9.
7.If s when divided by 3 gives remainder 1:
Remove one item from q1.
If q1 is empty,remove two items from q2.
If q2 contains less than two elements,number is not possible.
8.If s when divided by 3 gives remainder 2:
Remove one item from q2.
If q2 is empty,remove two items from q1.
If q1 contains less than two elements,number is not possible.
9.Empty all queues into an temporary array and sort it in decreasing order.
CODE
int findMaxMultupleOf3( int* arr, int size )
{
// Step 1: sort the array in non-decreasing order
qsort( arr, size, sizeof( int ), compareAsc );
// Create 3 queues to store numbers with remainder 0, 1 and 2 respectively
Queue* queue0 = createQueue( size );
Queue* queue1 = createQueue( size );
Queue* queue2 = createQueue( size );
// Step 2 and 3 get the sum of numbers and place them in corresponding queues
int i, sum;
for ( i = 0, sum = 0; i < size; ++i )
{
sum += arr[i];
if ( (arr[i] % 3) == 0 )
Enqueue( queue0, arr[i] );
else if ( (arr[i] % 3) == 1 )
Enqueue( queue1, arr[i] );
else
Enqueue( queue2, arr[i] );
}
// Step 4.2: The sum produces remainder 1
if ( (sum % 3) == 1 )
{
// either remove one item from queue1
if ( !isEmpty( queue1 ) )
Dequeue( queue1 );
// or remove two items from queue2
else
{
if ( !isEmpty( queue2 ) )
Dequeue( queue2 );
else
return 0;
if ( !isEmpty( queue2 ) )
Dequeue( queue2 );
else
return 0;
}
}
// Step 4.3: The sum produces remainder 2
else if ((sum % 3) == 2)
{
// either remove one item from queue2
if ( !isEmpty( queue2 ) )
Dequeue( queue2 );
// or remove two items from queue1
else
{
if ( !isEmpty( queue1 ) )
Dequeue( queue1 );
else
return 0;
if ( !isEmpty( queue1 ) )
Dequeue( queue1 );
else
return 0;
}
}
int aux[size], top = 0;
// Empty all the queues into an auxiliary array.
populateAux (aux, queue0, queue1, queue2, &top);
// sort the array in non-increasing order
qsort (aux, top, sizeof( int ), compareDesc);
// print the result
printArr (aux, top);
return 1;
}
Clone a linked list with next and random pointer
ALGO
The idea is to use Hashing. Below is algorithm.
1. Traverse the original linked list and make a copy in terms of data.
2. Make a hash map of key value pair with original linked list node and copied linked list node.
3. Traverse the original linked list again and using the hash map adjust the next and random reference of cloned linked list nodes.
CODE
public class Node {
private Node next;
private Node random;
private String data;
// getters and setters omitted for the sake of brevity
}
private Node deepCopy(Node original) {
Map<Node, Node> map = new HashMap<Node, Node>();
// We scan the original list and for each Node x we create a new
// Node y whose data is a copy of x's data, then we store the
// couple (x,y) in map using x as a key.
Node x = original;
while (x != null) {
Node y = new Node();
y.setData(new String(x.getData()));
y.setNext(null);
y.setRandom(null);
map.put(x, y);
x = x.getNext();
}
// We scan again the original list and
// we set the pointers buildings the new list
x = original;
while (x != null) {
// we get the node y corresponding to x from the map
Node y = map.get(x);
// let x' = x.next; y' = map.get(x') is the new node
// corresponding to x'; so we can set y.next = y'
y.setNext(map.get(x.getNext()));
// let x'' = x.random; y'' = map.get(x'') is the new
// node corresponding to x''; so we can set y.random = y''
y.setRandom(map.get(x.getRandom()));
x = x.getNext();
}
return map.get(original);
}
Learn By Coding 