Vir Pratap Uttam
BAN USER VIR PRATAP UTTAM(8+ yrs)
virprataputtam@hotmail.com
CERTIFICATIONS
• Java EE 6 Enterprise Architect Certified Master Exam.
• Oracle Certified Expert, Java EE 6 Web Services Developer.
• Oracle Certified Expert, Java EE 6 Java Persistence API Developer.
• OCWCD(Oracle Certified Professional, Java EE 5 Web Component Developer).
• OCJP6 (Oracle Certified Java Programmer).
LANGUAGES AND TECHNOLOGIES
• JDK 1.6,JSP ,Servlet
• Multithreading (volatile, ThreadPool, Reentrant Locks, Concurrent Hashmaps, Semaphores, Cyclic Barrier, Countdownlatches, Executors Framework, Synchronization etc.)
• Data Structures(Lists, Trees, Graphs, Queues, Stacks etc.)(Problem Solving, Time complexity analysis), Algorithm
• Spring 1.2 ,Spring 3(IOC ,AOP ,Security ,Services, MVC, Web, Integration, Batch, JMS), RTDS(HSBC Owned Framework), Struts 1.3 Framework , JSF(Java Server Faces)
• Hibernate 3.1, EJB 3
• Design Patterns (Singleton, Factory, Abstract Factory, Façade, Proxy, Strategy, Visitor etc.)
• Web Services(SOAP, REST, SOA)
• Web Logic Server, Jakarta Tomcat, Web Sphere
• Quality Center 9.2, Maven
• Oracle 10g , MySQL
private static void levelOrderTraversal(BinaryTreeNode root) {
BinaryTreeNode temp;
Queue<BinaryTreeNode> q = new LinkedBlockingDeque<BinaryTreeNode>();
q.add(root);
q.add(new BinaryTreeNode(-1));
while (!q.isEmpty()) {
temp = q.poll();
if (temp.getData() == -1) {
System.out.println();
if (!q.isEmpty())
q.add(new BinaryTreeNode(-1));
} else {
System.out.print(" "+temp.getData());
if (temp.getLeft() != null)
q.add(temp.getLeft());
if (temp.getRight() != null)
q.add(temp.getRight());
}
}
}
private static void levelOrderTraversal(BinaryTreeNode root) {
BinaryTreeNode temp;
Queue<BinaryTreeNode> q = new LinkedBlockingDeque<BinaryTreeNode>();
q.add(root);
q.add(new BinaryTreeNode(-1));
while (!q.isEmpty()) {
temp = q.poll();
if (temp.getData() == -1) {
System.out.println();
if (!q.isEmpty())
q.add(new BinaryTreeNode(-1));
} else {
System.out.print(" "+temp.getData());
if (temp.getLeft() != null)
q.add(temp.getLeft());
if (temp.getRight() != null)
q.add(temp.getRight());
}
}
}
Ans : Compile time error :Cannot cast B to A
For code to run change below ...
class A
{
}
class B extends A
{
}
public class ClassTest {
public static void main(String[] args) {
B b=new B();
A a=(A) b;
System.out.println(b.getClass());
System.out.println(a.getClass());
}
}
package com.datastructure.priorityheap;
import java.util.NoSuchElementException;
class BinaryHeap
{
private static final int d = 2;
private int heapSize;
private int[] heap;
public BinaryHeap(int capacity)
{
heapSize = 0;
heap = new int[capacity + 1];
}
public boolean isEmpty( )
{
return heapSize == 0;
}
public boolean isFull( )
{
return heapSize == heap.length;
}
public void makeEmpty( )
{
heapSize = 0;
}
private int parent(int i)
{
return (i - 1)/d;
}
private int kthChild(int i, int k)
{
return d * i + k;
}
public void insert(int x)
{
if (isFull( ) )
throw new NoSuchElementException("OverFlow : Heap is full");
heap[heapSize++] = x;
heapifyUp(heapSize - 1);
}
public int findMin( )
{
if (isEmpty() )
throw new NoSuchElementException("Underflow: Heap is empty");
return heap[0];
}
public int deleteMin()
{
int keyItem = heap[0];
delete(0);
return keyItem;
}
public int delete(int ind)
{
if (isEmpty() )
throw new NoSuchElementException("Underflow Exception");
int keyItem = heap[ind];
heap[ind] = heap[heapSize - 1];
heapSize--;
heapifyDown(ind);
return keyItem;
}
private void heapifyUp(int childInd)
{
int tmp = heap[childInd];
while (childInd > 0 && tmp < heap[parent(childInd)])
{
heap[childInd] = heap[ parent(childInd) ];
childInd = parent(childInd);
}
heap[childInd] = tmp;
}
private void heapifyDown(int ind)
{
int child;
int tmp = heap[ ind ];
while (kthChild(ind, 1) < heapSize)
{
child = minChild(ind);
if (heap[child] < tmp)
heap[ind] = heap[child];
else
break;
ind = child;
}
heap[ind] = tmp;
}
private int minChild(int ind)
{
int bestChild = kthChild(ind, 1);
int k = 2;
int pos = kthChild(ind, k);
while ((k <= d) && (pos < heapSize))
{
if (heap[pos] < heap[bestChild])
bestChild = pos;
pos = kthChild(ind, k++);
}
return bestChild;
}
public void printHeap()
{
System.out.println("Heap = ");
for (int i = 0; i < heapSize; i++)
System.out.print(heap[i] +" ");
System.out.println();
}
}
public class BinaryHeapImpl
{
public static void main(String[] args)
{
BinaryHeap bh = new BinaryHeap(6);
bh.insert(3);
bh.insert(2);
bh.insert(1);
bh.insert(8);
bh.insert(5);
System.out.println("Min Element :-"+bh.findMin());
bh.printHeap();
bh.deleteMin();
System.out.println("Min Element :-"+bh.findMin());
bh.printHeap();
}
}
private static boolean canPlant(int[] plantArr, int i) {
boolean canPlant=false;
if(i==0)
{
if(plantArr[i]==0 && plantArr[++i]==0)
{
canPlant=true;
}
}
else if(i==plantArr.length-1)
{
if(plantArr[i]==0 && plantArr[--i]==0)
{
canPlant=true;
}
}
else if(i>0 && i< plantArr.length-1 )
{
if(plantArr[i]==0 && plantArr[i+1]==0 && plantArr[i-1]==0)
{
canPlant=true;
}
}
return canPlant;
}
private static void findArrayIndexMax(int[] arrMax) {
Arrays.sort(arrMax);
int output=0;
int k=0;
for(int i=arrMax.length;i>=1;i--)
{
output+=arrMax[k++]*i;
}
System.out.println("Output is :-"+output);
}
private static void levelOrderTraversal(BinaryTreeNode root) {
BinaryTreeNode temp;
Queue<BinaryTreeNode> q = new LinkedBlockingDeque<BinaryTreeNode>();
q.add(root);
q.add(new BinaryTreeNode(-1));
while (!q.isEmpty()) {
temp = q.poll();
if (temp.getData() == -1) {
System.out.println();
if (!q.isEmpty())
q.add(new BinaryTreeNode(-1));
} else {
System.out.print(temp.getData());
if (temp.getLeft() != null)
q.add(temp.getLeft());
if (temp.getRight() != null)
q.add(temp.getRight());
}
}
}
Thanks vinod.
private static void unCompressString(String s) {
char[] c = s.toCharArray();
StringBuffer str = new StringBuffer();
for (int i = 0; i < c.length; i++) {
if(Character.isDigit(c[i]))
{
int d=Character.getNumericValue(c[i]);
for(int j=0;j<d;j++)
{
str.append(c[i-1]);
}
}
}
System.out.println(str);
}
private static void unCompressString(String s) {
char[] c = s.toCharArray();
StringBuffer str = new StringBuffer();
for (int i = 0; i < c.length; i++) {
if(Character.isDigit(c[i]))
{
int d=Character.getNumericValue(c[i]);
for(int j=0;j<d;j++)
{
str.append(c[i-1]);
}
}
}
System.out.println(str);
}
private static int[] multiplyData(int[] data) {
int[] newArray=new int[data.length];
for(int i=0;i<newArray.length;i++)
{
int temp=1;
for(int j=0;j<newArray.length;j++)
{
if(i!=j)
{
temp*=data[j];
}
}
newArray[i]=temp;
}
return newArray;
}
private static int[] sortBasedOnZero(int[] arr) {
int k=0;
for(int i=0;i<arr.length;i++)
{
if(arr[i]==0)
{
int temp=arr[i];
arr[i]=arr[k];
arr[k]=temp;
k++;
}
}
return arr;
}
public class TicTacToe {
static int n = 3;
static char[][] board = new char[n][n];
private static char currentPlayer='X';
public static void main(String[] args) {
initializeBoard(n);
placeMark(0,0);
printBoard();
checkForWin();
changePlayer();
placeMark(0,1);
printBoard();
checkForWin();
changePlayer();
placeMark(1,1);
printBoard();
checkForWin();
changePlayer();
placeMark(2,0);
printBoard();
checkForWin();
changePlayer();
placeMark(2,2);
printBoard();
checkForWin();
changePlayer();
placeMark(3,0);
printBoard();
checkForWin();
changePlayer();
placeMark(3,1);
printBoard();
checkForWin();
changePlayer();
printBoard();
isBoardFull(n);
checkForWin();
}
public static void checkForWin() {
if(checkRowsForWin() || checkColumnsForWin() || checkDiagonalsForWin())
{
System.out.println("Player :-"+currentPlayer+" Won the game");
System.exit(0);
}
}
private static boolean checkRowsForWin() {
for (int i = 0; i < n; i++) {
if (checkRowCol(board[i][0], board[i][1], board[i][2]) == true) {
return true;
}
}
return false;
}
private static boolean checkColumnsForWin() {
for (int i = 0; i < n; i++) {
if (checkRowCol(board[0][i], board[1][i], board[2][i]) == true) {
return true;
}
}
return false;
}
private static boolean checkDiagonalsForWin() {
return ((checkRowCol(board[0][0], board[1][1], board[2][2]) == true) || (checkRowCol(
board[0][2], board[1][1], board[2][0]) == true));
}
private static boolean checkRowCol(char c1, char c2, char c3) {
return ((c1 != '-') && (c1 == c2) && (c2 == c3));
}
private static boolean isBoardFull(int n2) {
boolean isFull = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j]=='-') {
isFull = false;
}
}
}
return isFull;
}
private static void printBoard() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(board[i][j]+" ");
}
System.out.println();
}
}
private static void initializeBoard(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '-';
}
}
}
public static void changePlayer() {
System.out.println("Player changed");
if (currentPlayer == 'X') {
currentPlayer = 'O';
}
else {
currentPlayer = 'X';
}
}
public static boolean placeMark(int row, int col) {
if ((row >= 0) && (row < n)) {
if ((col >= 0) && (col < n)) {
if (board[row][col] == '-') {
board[row][col] = currentPlayer;
return true;
}
}
}
return false;
}
}
First check which level you are applying whether it's SDE1 or SDE2 level. Once its confirmed look for sample program in this site.
Prepare for data structure & algorithm
Practice some Design question
private static void reverse(char[] c) {
reverse(c,0,c.length-1);
int wordStart=0;
for(int i=0;i<c.length;i++)
{
if(c[i]==' ')
{
reverse(c,wordStart,i-1);
wordStart=i+1;
}
else if(i==c.length-1)
{
reverse(c,wordStart,i);
}
}
}
private static void levelOrder(BSTNode root) {
BSTNode temp;
Queue<BSTNode> q = new LinkedBlockingDeque<BSTNode>();
if (root == null)
return;
q.add(root);
while (!q.isEmpty()) {
temp = q.poll();
System.out.println(temp.getData());
if (temp.getLeft() != null)
q.add(temp.getLeft());
if (temp.getRight() != null)
q.add(temp.getRight());
}
}
private static void dfs() {
g.vertexList[0].isVisited = true;
g.displayVertex(0);
g.thStack.push(0);
while (!g.thStack.isEmpty()) {
int v=getAdjUnVisitedVertex(g.thStack.peek());
if(v==-1)
{
g.thStack.pop();
}
else
{
g.vertexList[v].isVisited=true;
g.displayVertex(v);
g.thStack.push(v);
}
}
for(int j=0;j<g.vertexCount;j++)
g.vertexList[j].isVisited=false;
}
public class TicTacToe {
static int n = 3;
static char[][] board = new char[n][n];
private static char currentPlayer='X';
public static void main(String[] args) {
initializeBoard(n);
placeMark(0,0);
printBoard();
checkForWin();
changePlayer();
placeMark(0,1);
printBoard();
checkForWin();
changePlayer();
placeMark(1,1);
printBoard();
checkForWin();
changePlayer();
placeMark(2,0);
printBoard();
checkForWin();
changePlayer();
placeMark(2,2);
printBoard();
checkForWin();
changePlayer();
placeMark(3,0);
printBoard();
checkForWin();
changePlayer();
placeMark(3,1);
printBoard();
checkForWin();
changePlayer();
printBoard();
isBoardFull(n);
checkForWin();
}
public static void checkForWin() {
if(checkRowsForWin() || checkColumnsForWin() || checkDiagonalsForWin())
{
System.out.println("Player :-"+currentPlayer+" Won the game");
System.exit(0);
}
}
private static boolean checkRowsForWin() {
for (int i = 0; i < n; i++) {
if (checkRowCol(board[i][0], board[i][1], board[i][2]) == true) {
return true;
}
}
return false;
}
private static boolean checkColumnsForWin() {
for (int i = 0; i < n; i++) {
if (checkRowCol(board[0][i], board[1][i], board[2][i]) == true) {
return true;
}
}
return false;
}
private static boolean checkDiagonalsForWin() {
return ((checkRowCol(board[0][0], board[1][1], board[2][2]) == true) || (checkRowCol(
board[0][2], board[1][1], board[2][0]) == true));
}
private static boolean checkRowCol(char c1, char c2, char c3) {
return ((c1 != '-') && (c1 == c2) && (c2 == c3));
}
private static boolean isBoardFull(int n2) {
boolean isFull = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j]=='-') {
isFull = false;
}
}
}
return isFull;
}
private static void printBoard() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(board[i][j]+" ");
}
System.out.println();
}
}
private static void initializeBoard(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '-';
}
}
}
public static void changePlayer() {
System.out.println("Player changed");
if (currentPlayer == 'X') {
currentPlayer = 'O';
}
else {
currentPlayer = 'X';
}
}
public static boolean placeMark(int row, int col) {
if ((row >= 0) && (row < n)) {
if ((col >= 0) && (col < n)) {
if (board[row][col] == '-') {
board[row][col] = currentPlayer;
return true;
}
}
}
return false;
}
}
public class TicTacToe {
static int n = 3;
static char[][] board = new char[n][n];
private static char currentPlayer='X';
public static void main(String[] args) {
initializeBoard(n);
placeMark(0,0);
printBoard();
checkForWin();
changePlayer();
placeMark(0,1);
printBoard();
checkForWin();
changePlayer();
placeMark(1,1);
printBoard();
checkForWin();
changePlayer();
placeMark(2,0);
printBoard();
checkForWin();
changePlayer();
placeMark(2,2);
printBoard();
checkForWin();
changePlayer();
placeMark(3,0);
printBoard();
checkForWin();
changePlayer();
placeMark(3,1);
printBoard();
checkForWin();
changePlayer();
printBoard();
isBoardFull(n);
checkForWin();
}
public static void checkForWin() {
if(checkRowsForWin() || checkColumnsForWin() || checkDiagonalsForWin())
{
System.out.println("Player :-"+currentPlayer+" Won the game");
System.exit(0);
}
}
private static boolean checkRowsForWin() {
for (int i = 0; i < n; i++) {
if (checkRowCol(board[i][0], board[i][1], board[i][2]) == true) {
return true;
}
}
return false;
}
private static boolean checkColumnsForWin() {
for (int i = 0; i < n; i++) {
if (checkRowCol(board[0][i], board[1][i], board[2][i]) == true) {
return true;
}
}
return false;
}
private static boolean checkDiagonalsForWin() {
return ((checkRowCol(board[0][0], board[1][1], board[2][2]) == true) || (checkRowCol(
board[0][2], board[1][1], board[2][0]) == true));
}
private static boolean checkRowCol(char c1, char c2, char c3) {
return ((c1 != '-') && (c1 == c2) && (c2 == c3));
}
private static boolean isBoardFull(int n2) {
boolean isFull = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j]=='-') {
isFull = false;
}
}
}
return isFull;
}
private static void printBoard() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(board[i][j]+" ");
}
System.out.println();
}
}
private static void initializeBoard(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '-';
}
}
}
public static void changePlayer() {
System.out.println("Player changed");
if (currentPlayer == 'X') {
currentPlayer = 'O';
}
else {
currentPlayer = 'X';
}
}
public static boolean placeMark(int row, int col) {
if ((row >= 0) && (row < n)) {
if ((col >= 0) && (col < n)) {
if (board[row][col] == '-') {
board[row][col] = currentPlayer;
return true;
}
}
}
return false;
}
}
public class TicTacToe {
static int n = 3;
static char[][] board = new char[n][n];
private static char currentPlayer='X';
public static void main(String[] args) {
initializeBoard(n);
placeMark(0,0);
printBoard();
checkForWin();
changePlayer();
placeMark(0,1);
printBoard();
checkForWin();
changePlayer();
placeMark(1,1);
printBoard();
checkForWin();
changePlayer();
placeMark(2,0);
printBoard();
checkForWin();
changePlayer();
placeMark(2,2);
printBoard();
checkForWin();
changePlayer();
placeMark(3,0);
printBoard();
checkForWin();
changePlayer();
placeMark(3,1);
printBoard();
checkForWin();
changePlayer();
printBoard();
isBoardFull(n);
checkForWin();
}
public static void checkForWin() {
if(checkRowsForWin() || checkColumnsForWin() || checkDiagonalsForWin())
{
System.out.println("Player :-"+currentPlayer+" Won the game");
System.exit(0);
}
}
private static boolean checkRowsForWin() {
for (int i = 0; i < n; i++) {
if (checkRowCol(board[i][0], board[i][1], board[i][2]) == true) {
return true;
}
}
return false;
}
private static boolean checkColumnsForWin() {
for (int i = 0; i < n; i++) {
if (checkRowCol(board[0][i], board[1][i], board[2][i]) == true) {
return true;
}
}
return false;
}
private static boolean checkDiagonalsForWin() {
return ((checkRowCol(board[0][0], board[1][1], board[2][2]) == true) || (checkRowCol(
board[0][2], board[1][1], board[2][0]) == true));
}
private static boolean checkRowCol(char c1, char c2, char c3) {
return ((c1 != '-') && (c1 == c2) && (c2 == c3));
}
private static boolean isBoardFull(int n2) {
boolean isFull = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j]=='-') {
isFull = false;
}
}
}
return isFull;
}
private static void printBoard() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(board[i][j]+" ");
}
System.out.println();
}
}
private static void initializeBoard(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '-';
}
}
}
public static void changePlayer() {
System.out.println("Player changed");
if (currentPlayer == 'X') {
currentPlayer = 'O';
}
else {
currentPlayer = 'X';
}
}
public static boolean placeMark(int row, int col) {
if ((row >= 0) && (row < n)) {
if ((col >= 0) && (col < n)) {
if (board[row][col] == '-') {
board[row][col] = currentPlayer;
return true;
}
}
}
return false;
}
}
private static void findLeader(int[] arr) {
int max=Integer.MIN_VALUE;
System.out.println("----Leaders are-----");
for(int i=arr.length-1;i>=0;i--)
{
if(arr[i]>max)
{
System.out.print(" "+arr[i]);
max=arr[i];
}
}
}
private static void reverse(char[] c) {
reverse(c,0,c.length-1);
int wordStart=0;
for(int i=0;i<c.length;i++)
{
if(c[i]==' ')
{
reverse(c,wordStart,i-1);
wordStart=i+1;
}
else if(i==c.length-1)
{
reverse(c,wordStart,i);
}
}
}
private static void reverse(char[] c, int i, int j) {
if(i>=j)
return;
for(int k=i;k<=(i+j)/2;k++)
{
char temp=c[k];
c[k]=c[i+j-k];
c[i+j-k]=temp;
}
}
private static void reverse(char[] c) {
reverse(c,0,c.length-1);
int wordStart=0;
for(int i=0;i<c.length;i++)
{
if(c[i]==' ')
{
reverse(c,wordStart,i-1);
wordStart=i+1;
}
else if(i==c.length-1)
{
reverse(c,wordStart,i);
}
}
}
private static void reverse(char[] c, int i, int j) {
if(i>=j)
return;
for(int k=i;k<=(i+j)/2;k++)
{
char temp=c[k];
c[k]=c[i+j-k];
c[i+j-k]=temp;
}
}
private static void reverse(char[] c) {
reverse(c,0,c.length-1);
int wordStart=0;
for(int i=0;i<c.length;i++)
{
if(c[i]==' ')
{
reverse(c,wordStart,i-1);
wordStart=i+1;
}
else if(i==c.length-1)
{
reverse(c,wordStart,i);
}
}
}
private static void reverse(char[] c, int i, int j) {
if(i>=j)
return;
for(int k=i;k<=(i+j)/2;k++)
{
char temp=c[k];
c[k]=c[i+j-k];
c[i+j-k]=temp;
}
}
private static int maxContigousWithoutDP(int A[], int n) {
int sumSoFar = 0, sumEndingHere = 0;
int startInd=0;
int endInd = 0;
for (int i = 0; i < n; i++) {
sumEndingHere = sumEndingHere + A[i];
if (sumEndingHere < 0) {
sumEndingHere = 0;
continue;
}
if (sumSoFar < sumEndingHere)
{
startInd=endInd;
endInd=i;
sumSoFar = sumEndingHere;
}
}
System.out.println("Start Ind & End Ind :-"+startInd+" "+endInd);
return sumSoFar;
}
private static boolean isBalanced(char[] source) {
int counter=0;
for(char c:source)
{
if(c=='{')
counter++;
else if(c=='}')
{
counter--;
if(counter==-1)
return false;
}
}
return counter==0;
}
Not sure about sparse number but below code will give no adjacent 1. Can someone check
private static void nextSparse(int x) {
for (int i = x + 1; i < Integer.MAX_VALUE; i++) {
if ((i & (i * 2)) == 0) {
System.out.println(i);
return;
}
}
}
This is just a sample code for reference......do not consider it as working code
package com.lms;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
public class LMSImpl {
static List<BookDetails> books = new ArrayList<BookDetails>();
static Map<Integer, ArrayList<BookIssueDetails>> hm = new HashMap<Integer, ArrayList<BookIssueDetails>>();
public static void main(String[] args) {
addIssueDetails();
System.out.println("Library Management System");
System.out.println("Press 1 to add Book");
System.out.println("Press 2 to issue a book");
System.out.println("Press 3 to return a book");
System.out.println("Press 4 to print the book details");
System.out.println("Press 5 to print complete issue detais");
System.out.println("Press 6 to exit");
Scanner c = new Scanner(System.in);
int choice = c.nextInt();
do {
switch (choice) {
case 1:
addBook();
break;
case 2:
issueBook();
break;
case 3:
returnBook();
break;
case 4:
printBookDetails();
break;
case 5:
printCompleteIssueDetails();
break;
case 6:
System.exit(0);
default:
System.out.println("Invalid input");
break;
}
c = new Scanner(System.in);
choice = c.nextInt();
} while (choice > 0 && choice < 6);
}
private static void printCompleteIssueDetails() {
for (Map.Entry<Integer, ArrayList<BookIssueDetails>> entry : hm
.entrySet()) {
for (BookIssueDetails b : entry.getValue()) {
System.out.println(entry.getKey() + " " + b.getBookNumber()
+ " " + b.getName() + " " + b.getNoOfBookIssued()
+ " " + b.getIssueDate() + " " + b.getReturnDate());
}
}
}
private static void printBookDetails() {
for (BookDetails b : books) {
System.out.print(b.getBookNumber() + " " + b.getBookName() + " "
+ b.getCount() + " " + b.getPrice());
}
}
private static void returnBook() {
System.out.println("Enter studentId & bookId");
Scanner c = new Scanner(System.in);
int id = c.nextInt();
int bookId = c.nextInt();
List<BookIssueDetails> bd = hm.get(id);
for (BookIssueDetails b : bd) {
if (b.getBookNumber() == bookId) {
Date issueDate = b.getIssueDate();
Date todayDate = new Date();
long diff = todayDate.getTime() - issueDate.getTime();
long diffDays = diff / (24 * 60 * 60 * 1000);
if (diffDays > 10) {
int fine = (int) (diffDays - 10);
fine = fine * 10;
System.out.println("Total Fine " + fine + " Rs.");
}
}
}
}
private static void addIssueDetails() {
BookIssueDetails bd1 = new BookIssueDetails(1,"abc",1,new Date("04/04/2015"));
BookIssueDetails bd2 = new BookIssueDetails(2,"xyz",1,new Date());
BookIssueDetails bd3 = new BookIssueDetails(3,"mn",1,new Date());
BookIssueDetails bd4 = new BookIssueDetails(4,"u",1,new Date());
ArrayList<BookIssueDetails> list1 = new ArrayList<BookIssueDetails>();
ArrayList<BookIssueDetails> list2 = new ArrayList<BookIssueDetails>();
ArrayList<BookIssueDetails> list3 = new ArrayList<BookIssueDetails>();
ArrayList<BookIssueDetails> list4 = new ArrayList<BookIssueDetails>();
list1.add(bd1);
list2.add(bd2);
list3.add(bd3);
list4.add(bd4);
hm.put(100, list1);
hm.put(101, list2);
hm.put(103, list3);
hm.put(104, list4);
}
private static void issueBook() {
System.out.println("Enter Student Id,Booknumber, name and price");
Scanner c = new Scanner(System.in);
int studentId = c.nextInt();
Scanner c1 = new Scanner(System.in);
int bookNumber = c1.nextInt();
Scanner c2 = new Scanner(System.in);
String name = c2.nextLine();
Scanner c3 = new Scanner(System.in);
String issueDate = c3.nextLine();
BookIssueDetails newIssuedBook = new BookIssueDetails();
newIssuedBook.setName(name);
newIssuedBook.setBookNumer(bookNumber);
ArrayList<BookIssueDetails> l=new ArrayList<BookIssueDetails>();
SimpleDateFormat formatter = new SimpleDateFormat("dd-MMM-yyyy");
try {
Date date = formatter.parse(issueDate);
newIssuedBook.setIssueDate(date);
} catch (ParseException e) {
e.printStackTrace();
}
List<BookIssueDetails> list = hm.get(studentId);
for (BookIssueDetails b : list) {
int value = b.getNoOfBookIssued();
newIssuedBook.setNoOfBookIssued(++value);
l.add(newIssuedBook);
if (value > 2)
System.out.println("You already issued max(2) books");
else
hm.put(studentId, l);
}
}
private static void addBook() {
System.out.println("Enter Booknumber, name and price");
Scanner c = new Scanner(System.in);
int bookNumber = c.nextInt();
String name = c.nextLine();
Double price = c.nextDouble();
BookDetails book = new BookDetails(bookNumber, name, price);
books.add(book);
}
}
package com.lms;
import java.util.Date;
public class BookIssueDetails {
private int bookNumber;
private String name;
private int totalBookAllowed = 2;
private int noOfBookIssued=0;
private Date issueDate;
private Date returnDate;
public BookIssueDetails(int bookNumber,String name,int n,Date issueDate)
{
this.bookNumber=bookNumber;
this.name=name;
this.noOfBookIssued=n;
this.issueDate=issueDate;
}
public BookIssueDetails() {
}
public int getBookNumber() {
return bookNumber;
}
public void setBookNumer(int bookNumber) {
this.bookNumber = bookNumber;
}
public int getNoOfBookIssued() {
return noOfBookIssued;
}
public void setNoOfBookIssued(int noOfBookIssued) {
this.noOfBookIssued = noOfBookIssued;
}
public Date getIssueDate() {
return issueDate;
}
public void setIssueDate(Date issueDate) {
this.issueDate = issueDate;
}
public Date getReturnDate() {
return returnDate;
}
public void setReturnDate(Date returnDate) {
this.returnDate = returnDate;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getTotalBookAllowed() {
return totalBookAllowed;
}
public void setTotalBookAllowed(int totalBookAllowed) {
this.totalBookAllowed = totalBookAllowed;
}
}
package com.lms;
public class BookDetails {
private int bookNumber;
private String bookName;
private Double price;
private int count;
public BookDetails(int bookNumber,String name,Double price)
{
this.bookNumber=bookNumber;
this.bookName=name;
this.price=price;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
public int getBookNumber() {
return bookNumber;
}
public void setBookNumber(int bookNumber) {
this.bookNumber = bookNumber;
}
public String getBookName() {
return bookName;
}
public void setBookName(String bookName) {
this.bookName = bookName;
}
public Double getPrice() {
return price;
}
public void setPrice(Double price) {
this.price = price;
}
}
package com.lms;
public class StudentDetails {
private int studentId;
private String studentName;
private String className;
public int getStudentId() {
return studentId;
}
public void setStudentId(int studentId) {
this.studentId = studentId;
}
public String getStudentName() {
return studentName;
}
public void setStudentName(String studentName) {
this.studentName = studentName;
}
public String getClassName() {
return className;
}
public void setClassName(String className) {
this.className = className;
}
}
calling------------------ isFoldable(root.getLeft(),root.getRight()));
private static BinaryTreeNode createBinaryTreeFoldable() {
// TODO Auto-generated method stub
BinaryTreeNode node1 = new BinaryTreeNode(10);
BinaryTreeNode node2 = new BinaryTreeNode(20);
BinaryTreeNode node3 = new BinaryTreeNode(20);
BinaryTreeNode node4 = new BinaryTreeNode(30);
BinaryTreeNode node5 = new BinaryTreeNode(40);
BinaryTreeNode node6 = new BinaryTreeNode(40);
BinaryTreeNode node7 = new BinaryTreeNode(30);
node1.setLeft(node2);
node1.setRight(node3);
node2.setLeft(node4);
node2.setRight(node5);
node3.setLeft(node6);
node3.setRight(node7);
return node1;
}
private static boolean isFoldable(BinaryTreeNode root1, BinaryTreeNode root2) {
if (root1 == null && root2 == null)
return true;
if ((root1 == null && root2 != null)
|| (root1 != null && root2 == null))
return false;
if (root1.getData() != root2.getData())
return false;
else
return isFoldable(root1.getLeft(), root2.getRight())
&& isFoldable(root1.getRight(), root2.getLeft());
}
private static void zigZagTraversal(BinaryTreeNode root) {
int leftToRight = 1;
BinaryTreeNode temp;
Queue<BinaryTreeNode> currentLevel = new LinkedBlockingDeque<BinaryTreeNode>();
Stack<BinaryTreeNode> nextLevel = new Stack<BinaryTreeNode>();
System.out.println("Zig Zag Traversal");
currentLevel.add(root);
while (!currentLevel.isEmpty()) {
temp = currentLevel.poll();
if (temp != null) {
System.out.print(" "+temp.getData());
if (leftToRight == 0) {
if (temp.getLeft() != null)
nextLevel.push(temp.getLeft());
if (temp.getRight() != null)
nextLevel.push(temp.getRight());
} else {
if (temp.getRight() != null)
nextLevel.push(temp.getRight());
if (temp.getLeft() != null)
nextLevel.push(temp.getLeft());
}
}
if (currentLevel.isEmpty()) {
System.out.println();
leftToRight = 1 - leftToRight;
while (!nextLevel.isEmpty()) {
currentLevel.add(nextLevel.pop());
}
}
}
}
calling------------------ isFoldable(root.getLeft(),root.getRight()));
private static BinaryTreeNode createBinaryTreeFoldable() {
// TODO Auto-generated method stub
BinaryTreeNode node1 = new BinaryTreeNode(10);
BinaryTreeNode node2 = new BinaryTreeNode(20);
BinaryTreeNode node3 = new BinaryTreeNode(20);
BinaryTreeNode node4 = new BinaryTreeNode(30);
BinaryTreeNode node5 = new BinaryTreeNode(40);
BinaryTreeNode node6 = new BinaryTreeNode(40);
BinaryTreeNode node7 = new BinaryTreeNode(30);
node1.setLeft(node2);
node1.setRight(node3);
node2.setLeft(node4);
node2.setRight(node5);
node3.setLeft(node6);
node3.setRight(node7);
return node1;
}
private static boolean isFoldable(BinaryTreeNode root1, BinaryTreeNode root2) {
if (root1 == null && root2 == null)
return true;
if ((root1 == null && root2 != null)
|| (root1 != null && root2 == null))
return false;
if (root1.getData() != root2.getData())
return false;
else
return isFoldable(root1.getLeft(), root2.getRight())
&& isFoldable(root1.getRight(), root2.getLeft());
}
private static void zigZagTraversal(BinaryTreeNode root) {
int leftToRight = 1;
BinaryTreeNode temp;
Queue<BinaryTreeNode> currentLevel = new LinkedBlockingDeque<BinaryTreeNode>();
Stack<BinaryTreeNode> nextLevel = new Stack<BinaryTreeNode>();
System.out.println("Zig Zag Traversal");
currentLevel.add(root);
while (!currentLevel.isEmpty()) {
temp = currentLevel.poll();
if (temp != null) {
System.out.print(" "+temp.getData());
if (leftToRight == 0) {
if (temp.getLeft() != null)
nextLevel.push(temp.getLeft());
if (temp.getRight() != null)
nextLevel.push(temp.getRight());
} else {
if (temp.getRight() != null)
nextLevel.push(temp.getRight());
if (temp.getLeft() != null)
nextLevel.push(temp.getLeft());
}
}
if (currentLevel.isEmpty()) {
System.out.println();
leftToRight = 1 - leftToRight;
while (!nextLevel.isEmpty()) {
currentLevel.add(nextLevel.pop());
}
}
}
}
private static void printPaths(BinaryTreeNode root, int[] path, int pathLen) {
if(root==null)
return;
path[pathLen]=root.getData();
pathLen++;
if(root.getLeft()==null && root.getRight()==null)
{
printArray(path,pathLen);
}
else
{
printPaths(root.getLeft(),path,pathLen);
printPaths(root.getRight(),path,pathLen);
}
}
private static void printArray(int[] path, int pathLen) {
int sum=0;
for(int i=0;i<pathLen;i++)
{
sum+=path[i];
System.out.print(path[i]+ "->");
}
totalsum+=sum;
System.out.println(" "+sum);
}
private static void printPaths(BinaryTreeNode root, int[] path, int pathLen) {
if(root==null)
return;
path[pathLen]=root.getData();
pathLen++;
if(root.getLeft()==null && root.getRight()==null)
{
printArray(path,pathLen);
}
else
{
printPaths(root.getLeft(),path,pathLen);
printPaths(root.getRight(),path,pathLen);
}
}
private static void printArray(int[] path, int pathLen) {
int sum=0;
for(int i=0;i<pathLen;i++)
{
sum+=path[i];
System.out.print(path[i]+ "->");
}
totalsum+=sum;
System.out.println(" "+sum);
}
private static void printPaths(BinaryTreeNode root, int[] path, int pathLen) {
if(root==null)
return;
path[pathLen]=root.getData();
pathLen++;
if(root.getLeft()==null && root.getRight()==null)
{
printArray(path,pathLen);
}
else
{
printPaths(root.getLeft(),path,pathLen);
printPaths(root.getRight(),path,pathLen);
}
}
private static void printArray(int[] path, int pathLen) {
int sum=0;
for(int i=0;i<pathLen;i++)
{
sum+=path[i];
System.out.print(path[i]+ "->");
}
totalsum+=sum;
System.out.println(" "+sum);
}
C(n)=2n!/n!(n+1)!
- Vir Pratap Uttam May 10, 2015boolean[] row = new boolean[n];
boolean[] column = new boolean[n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == 0) {
row[i] = true;
column[j] = true;
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (row[i] || column[j]) {
matrix[i][j] = 0;
}
}
}
System.out.println("Matrix After Setting zero:-");
printMatrix(matrix, n);
return matrix;
}
private static boolean isBST(BSTNode root) {
if (root == null)
return true;
if (root.getLeft() != null && findMax(root.getLeft()) > root.getData())
return false;
if (root.getRight() != null
&& findMin(root.getRight()) < root.getData())
return false;
if (!(isBST(root.getLeft())) || (!isBST(root.getRight())))
return false;
return true;
}
private static boolean isBstSame(BSTNode root1,BSTNode root2) {
BSTNode temp1,temp2;
Queue<BSTNode> q1 = new LinkedBlockingDeque<BSTNode>();
Queue<BSTNode> q2 = new LinkedBlockingDeque<BSTNode>();
if (root1 == null && root2==null)
return true;
q1.add(root1);
q2.add(root2);
while (!q1.isEmpty() && !q2.isEmpty()) {
temp1 = q1.poll();
temp2=q2.poll();
if(temp1.getData()!=temp2.getData())
return false;
if (temp1.getLeft() != null)
q1.add(temp1.getLeft());
if (temp1.getRight() != null)
q1.add(temp1.getRight());
if (temp2.getLeft() != null)
q2.add(temp2.getLeft());
if (temp2.getRight() != null)
q2.add(temp2.getRight());
}
return true;
}
private static boolean isBST(BSTNode root) {
if (root == null)
return true;
if (root.getLeft() != null && findMax(root.getLeft()) > root.getData())
return false;
if (root.getRight() != null
&& findMin(root.getRight()) < root.getData())
return false;
if (!(isBST(root.getLeft())) || (!isBST(root.getRight())))
return false;
return true;
}
private static void displayNumbersHasSum(int[] arr,int sum) {
HashMap<Integer,Integer> ht=new HashMap<Integer,Integer>();
for(int i=0;i<arr.length;i++)
{
int k=sum-arr[i];
if(ht.containsKey(arr[i]))
{
System.out.println("Numbers are :- "+k+" "+arr[i]);
}
else
{
ht.put(arr[i], 1);
}
}
}
Override the hashcode & equals method
package com.datastructure.trees;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingDeque;
public class N_aryTreeNodeImpl {
static int k = 3;
public static void main(String[] args) {
N_aryTreeNode root = createN_aryTree();
zigZagTraversal(root, k);
}
private static void zigZagTraversal(N_aryTreeNode root, int k) {
int leftToRight = 1;
N_aryTreeNode temp;
Queue<N_aryTreeNode> currentLevel = new LinkedBlockingDeque<N_aryTreeNode>();
Stack<N_aryTreeNode> nextLevel = new Stack<N_aryTreeNode>();
System.out.println("Zig Zag Traversal");
currentLevel.add(root);
while (!currentLevel.isEmpty()) {
temp = currentLevel.poll();
N_aryTreeNode[] childArr = temp.getChild();
if (temp != null) {
System.out.print(" " + temp.getData());
if (leftToRight == 1) {
for (int i = 0; i < k; i++) {
if (childArr != null && childArr[i] != null)
nextLevel.push(childArr[i]);
}
} else {
for (int i = k - 1; i >= 0; i--) {
if (childArr != null && childArr[i] != null)
nextLevel.push(childArr[i]);
}
}
}
if (currentLevel.isEmpty()) {
leftToRight = 1 - leftToRight;
while (!nextLevel.isEmpty()) {
currentLevel.add(nextLevel.pop());
}
}
}
}
private static N_aryTreeNode createN_aryTree() {
N_aryTreeNode node1 = new N_aryTreeNode(k);
N_aryTreeNode node2 = new N_aryTreeNode(k);
N_aryTreeNode node3 = new N_aryTreeNode(k);
N_aryTreeNode node4 = new N_aryTreeNode(k);
N_aryTreeNode node5 = new N_aryTreeNode(k);
N_aryTreeNode node6 = new N_aryTreeNode(k);
N_aryTreeNode node7 = new N_aryTreeNode(k);
N_aryTreeNode node8 = new N_aryTreeNode(k);
N_aryTreeNode node9 = new N_aryTreeNode(k);
N_aryTreeNode node10 = new N_aryTreeNode(k);
node5.setData(5);
node1.setData(1);
N_aryTreeNode[] childNode1 = { node2, node6, node10 };
node1.setChild(childNode1);
node2.setData(2);
N_aryTreeNode[] childNode2 = { node3, node4, node5 };
node2.setChild(childNode2);
node6.setData(6);
N_aryTreeNode[] childNode6 = { node7, node8, node9 };
node6.setChild(childNode6);
node3.setData(3);
node3.setChild(null);
node4.setData(4);
node4.setChild(null);
node5.setData(5);
node5.setChild(null);
node7.setData(7);
node7.setChild(null);
node8.setData(8);
node8.setChild(null);
node9.setData(9);
node9.setChild(null);
node10.setData(10);
node10.setChild(null);
return node1;
}
}
private static void printDLLReverse(DLLNode head) {
DLLNode current=head;
DLLNode prev=head;
while(current!=null)
{
prev=current;
current=current.getNext();
}
while(prev!=null)
{
System.out.println(prev.getData());
prev=prev.getPrevious();
}
}
BST to Circular DLL
static BSTNode prev, head;
public static BSTNode convetToCLL(BSTNode root) {
if (root == null)
return null;
convetToCLL(root.getLeft());
if (prev == null) { // first node in list
head = root;
} else {
prev.setRight(root);
root.setLeft(prev);
}
prev = root;
convetToCLL(root.getRight());
if (prev.getRight() == null) { // last node in list
head.setLeft(prev);
prev.setRight(head);
}
return head;
}
BST to Doubly Linked List
static BSTNode prevDLL, headDLL;
public static BSTNode convetToDLL(BSTNode root) {
if (root == null)
return null;
convetToDLL(root.getLeft());
if (prevDLL == null) {
headDLL = root;
} else {
prevDLL.setRight(root);
root.setLeft(prevDLL);
}
prevDLL = root;
convetToDLL(root.getRight());
return headDLL;
}
private static int maxContigousWithoutDP(int A[], int n) {
int sumSoFar = 0, sumEndingHere = 0;
for (int i = 0; i < n; i++) {
sumEndingHere = sumEndingHere + A[i];
if (sumEndingHere < 0) {
sumEndingHere = 0;
continue;
}
if (sumSoFar < sumEndingHere)
sumSoFar = sumEndingHere;
}
return sumSoFar;
}
private static int LongestIncreasingSubsequenceLength(int[] arr, int n) {
int i, j, max = 0;
for (i = 0; i < n; i++)
LISTable[i] = 1;
for (i = 0; i < n; i++) {
for (j = 0; j < i; j++) {
if (arr[i] > arr[j] && LISTable[i] < LISTable[j] + 1) {
LISTable[i] = LISTable[j] + 1;
}
}
}
for (i = 0; i < n; i++) {
if (max < LISTable[i]) {
max = LISTable[i];
}
}
return max;
}
private static int catalanNumber(int n) {
if (n == 0)
return 1;
int count = 0;
for (int i = 1; i <= n; i++) {
count += catalanNumber(i - 1) * catalanNumber(n - i);
}
return count;
}
private static BSTNode findLCA(BSTNode root, BSTNode alpha, BSTNode beta) {
while (true) {
if (((alpha.getData() < root.getData() && beta.getData() > root
.getData()))
|| ((alpha.getData() > root.getData()) && (beta.getData() < root
.getData())))
return root;
if (alpha.getData() < root.getData())
root = root.getLeft();
else
root = root.getRight();
}
}
RepGayle L McDowell, CEO at CareerCup
Gayle Laakmann McDowell is the founder / CEO of CareerCup, which provides programming interview prep for candidates interviewing with Microsoft, Google ...
- Vir Pratap Uttam October 13, 2017