1. Java pass by value or pass by reference
Java is ALWAYS pass-by-value (meaning make another new copy ).
That’s why when we change object’s value within function, the original object’s value is untouchable.
Reference:
|
Thursday, February 11, 2016
Java is ALWAYS pass-by-value Java is ALWAYS pass-by-value
Tuesday, November 24, 2015
Facebook: Print a Binary Tree Sum in Vertical Order
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.HashMap;
import java.util.TreeMap;
import java.util.Map.Entry;
import java.util.Collections;
class QueueEntry
{
TreeNode node;
int horizontalDistance;
QueueEntry(TreeNode node, int horizontalDistance)
{
this.node = node;
this.horizontalDistance = horizontalDistance;
}
}
class TreeNode
{
TreeNode left;
TreeNode right;
int val;
public TreeNode(int x)
{
this.val = x;
}
}
public class PrintVerticalLevelNodesSum {
/*
Output
1. Expected Output -
4
2
1 5 6
3 8
7
2. HashMap Output -
1,5,6,
8,3,
7,
4,
2,
3. TreeMap (key:level=>in order) Output
4,
2,
1,5,6,
8,3,
7,
4. Collections.sort() Output
4,
2,
1,5,6,
3,8,
7,
Output for sum
4,
2,
12,
11,
7
*/
public static void main(String[] arg)
{
PrintVerticalLevelNodesSum tree = new PrintVerticalLevelNodesSum();
/*
1
2 3
4 5 6 7
8
*/
TreeNode root = tree.createTree();
tree.printVerticalOrder(root);
}
public TreeNode createTree()
{
TreeNode root = new TreeNode(1);
TreeNode n1 = new TreeNode(2);
TreeNode n2 = new TreeNode(3);
TreeNode n3 = new TreeNode(4);
TreeNode n4 = new TreeNode(5);
TreeNode n5 = new TreeNode(6);
TreeNode n6 = new TreeNode(7);
TreeNode n7 = new TreeNode(8);
root.left = n1;
root.right = n2;
n1.left = n3;
n1.right = n4;
n2.left = n5;
n2.right = n6;
n4.right = n7;
return root;
}
// Main Function
public static void printVerticalOrder(TreeNode root){
if(root == null) return;
//HashMap> map = new HashMap>();
TreeMap> map = new TreeMap>();
printVerticalOrderUtilRecursive(root, 0, map);
//printVerticalOrderUtilInterative(root,0,map);
TreeMap mapSum = new TreeMap();
printVerticalOrderSumUtilRecursive(root, 0, mapSum);
// Print
System.out.println("vertical nodes :" );
for(Integer level: map.keySet()){
ArrayList tmp = map.get(level);
Collections.sort(tmp);
for(Integer value: tmp)
System.out.print(value + ",");
System.out.println();
}
System.out.println();
System.out.println("vertical sum :" );
for(Integer level: mapSum.keySet()){
int tmp = mapSum.get(level);
System.out.print(tmp + ",");
System.out.println();
}
}
//private static void printVerticalOrderUtil(TreeNode root, int level,
// HashMap> map) {
private static void printVerticalOrderUtilRecursive(TreeNode root, int level, TreeMap> map) {
// Base Case, root == null
if(root == null) return;
// Base Case, root != null
ArrayList list = (map.get(level) != null)? map.get(level): new ArrayList();
list.add(root.val);
map.put(level, list);
// Recursive
printVerticalOrderUtilRecursive(root.left, level-1, map);
printVerticalOrderUtilRecursive(root.right, level+1, map);
}
private static void printVerticalOrderUtilInterative(TreeNode root, int level, TreeMap> map)
{
if (root == null) return;
ArrayList mapEntry;
LinkedList queue = new LinkedList();
queue.add(new QueueEntry(root, level));
while (!queue.isEmpty())
{
QueueEntry entry = queue.remove();
// Base Case, root != null
mapEntry = (map.get(entry.horizontalDistance) != null)? map.get(entry.horizontalDistance):new ArrayList();
mapEntry.add(entry.node.val);
map.put(entry.horizontalDistance, mapEntry);
if (entry.node.left != null)
{
queue.add(new QueueEntry(entry.node.left, entry.horizontalDistance - 1));
}
if (entry.node.right != null)
{
queue.add(new QueueEntry(entry.node.right, entry.horizontalDistance + 1));
}
}
}
private static void printVerticalOrderSumUtilRecursive(TreeNode root, int level, TreeMap map) {
// Base Case, root == null
if(root == null) return;
// Base Case, root != null
int sum = (map.get(level) != null)? map.get(level)+root.val: root.val;
map.put(level, sum);
// Recursive
printVerticalOrderSumUtilRecursive(root.left, level-1, map);
printVerticalOrderSumUtilRecursive(root.right, level+1, map);
}
private static void printVerticalOrderSumUtilInterative(TreeNode root, int level,TreeMap map)
{
if (root == null) return;
ArrayList mapEntry;
LinkedList queue = new LinkedList();
queue.add(new QueueEntry(root, level));
while (!queue.isEmpty())
{
QueueEntry entry = queue.remove();
// Base Case, root != null
int sum = (map.get(entry.horizontalDistance) != null)? map.get(entry.horizontalDistance)+ root.val: root.val;
map.put(entry.horizontalDistance, sum);
if (entry.node.left != null)
{
queue.add(new QueueEntry(entry.node.left, entry.horizontalDistance - 1));
}
if (entry.node.right != null)
{
queue.add(new QueueEntry(entry.node.right, entry.horizontalDistance + 1));
}
}
}
}
//list can not set -1, sum
//sh-4.3$ java -Xmx128M -Xms16M PrintVerticalLevelNodesSum
//Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
// at java.util.ArrayList.rangeCheck(ArrayList.java:635)
// at java.util.ArrayList.get(ArrayList.java:411)
// at PrintVerticalLevelNodesSum.printVerticalOrderSumUtilRecursive(PrintVerticalLevelNodesSum.java:185)
// at PrintVerticalLevelNodesSum.printVerticalOrder(PrintVerticalLevelNodesSum.java:120)
// at PrintVerticalLevelNodesSum.main(PrintVerticalLevelNodesSum.java:84)
Friday, November 20, 2015
Binary Indexed Tree In 2D , 2D Binary Indexed Tree
vector<vector<int>> matrix;
int M = matrix.size(), N = matrix[0].size();
// update > > sum
// update O(1); sum O(n^2)
int M = matrix.size(), N = matrix[0].size();
// update > > sum
// update O(1); sum O(n^2)
[size=13.3333330154419px]set O(1)
[size=13.3333330154419px]sum O(n^2)
void update(int r, int c, int val) {
matrix[r][c] = val;
}
// (r1,c1) upper left, (r2,c2) bottom right
int sum(int r1, int c1, int r2, int c2) {
int res = 0;
for (int i = r1; i <= r2; ++i) {
for (int j = c1; j <= j2; ++j) {
res += matrix[i][j];
}
}
return res;
}
// sum > > update
// dp[i][j] computer sum of rectangle [0,0] --- [0,j] --- [i,0] --- [i,j]
// update O(n^2), sum O(1).
void update(int r, int c, int val) {
matrix[r][c] = val;
}
// (r1,c1) upper left, (r2,c2) bottom right
int sum(int r1, int c1, int r2, int c2) {
int res = 0;
for (int i = r1; i <= r2; ++i) {
for (int j = c1; j <= j2; ++j) {
res += matrix[i][j];
}
}
return res;
}
// sum > > update
// dp[i][j] computer sum of rectangle [0,0] --- [0,j] --- [i,0] --- [i,j]
// update O(n^2), sum O(1).
[size=13.3333330154419px]set O(n^2)
[size=13.3333330154419px]sum O(1)
vector<vector<int>> dp(M,vector(N,0));
void compute() {
dp[0][0] = matrix[0][0];
for (int j = 1; j < N; ++j) {
dp[0][j] = dp[0][j-1] + matrix[0][j];
}
for (int i = 1; i < M; ++i) {
dp[i][0] = dp[i-1][0] + matrix[i][0];
}
for (int i = 1; i < M; ++i) {
for (int j = 1; j < N; ++j) {
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i][j];
}
}
}
void update(int r, int c, int val) {
int dif = val - matrix[i][j];
for (int i = r; i < M; ++i) {
for (int j = c; j < N; ++j) {
dp[i][j] += dif;
}
}
}
int sum(int r1, int c1, int r2, int c2) {
if (r1 == 0 && c1 == 0) return dp[r2][c2];
else if (r1 == 0) return dp[r2][c2] - dp[r2][c1-1];
else if (c1 == 0) return dp[r2][c2] - dp[r1-1][c2];
else return dp[r2][c2] - dp[r1-1][c2] - dp[r2][c1-1] + dp[r1-1][c1-1];
}
// sum ~= update
// update
vector<vector<int>> dp(M,vector(N,0));
void compute() {
dp[0][0] = matrix[0][0];
for (int j = 1; j < N; ++j) {
dp[0][j] = dp[0][j-1] + matrix[0][j];
}
for (int i = 1; i < M; ++i) {
dp[i][0] = dp[i-1][0] + matrix[i][0];
}
for (int i = 1; i < M; ++i) {
for (int j = 1; j < N; ++j) {
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i][j];
}
}
}
void update(int r, int c, int val) {
int dif = val - matrix[i][j];
for (int i = r; i < M; ++i) {
for (int j = c; j < N; ++j) {
dp[i][j] += dif;
}
}
}
int sum(int r1, int c1, int r2, int c2) {
if (r1 == 0 && c1 == 0) return dp[r2][c2];
else if (r1 == 0) return dp[r2][c2] - dp[r2][c1-1];
else if (c1 == 0) return dp[r2][c2] - dp[r1-1][c2];
else return dp[r2][c2] - dp[r1-1][c2] - dp[r2][c1-1] + dp[r1-1][c1-1];
}
// sum ~= update
// update
[size=13.3333330154419px]set O(n)
[size=13.3333330154419px]sum O(n)
vector<vector<int>> dp(M,vector(N,0));
// row dp; dp[i][j] = sum_i_{k = 0}^{k = j};
void compute() {
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (j == 0) dp[i][j] = matrix[i][j];
else dp[i][j] = dp[i][j-1] + matrix[i][j];
}
}
}
void update(int r, int c, int val) {
int dif = val - matrix[i][j];
for (int j = c; j < N; ++j) {
dp[r][j] += dif;
}
}
int sum(int r1, int c1, int r2, int c2) {
int res = 0;
for (int i = r1; i <= r2; ++i) {
res += c1 == 0 ? dp[i][c2] : dp[i][c2] - dp[i][c2-1];
}
return res;
}
vector<vector<int>> dp(M,vector(N,0));
// row dp; dp[i][j] = sum_i_{k = 0}^{k = j};
void compute() {
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (j == 0) dp[i][j] = matrix[i][j];
else dp[i][j] = dp[i][j-1] + matrix[i][j];
}
}
}
void update(int r, int c, int val) {
int dif = val - matrix[i][j];
for (int j = c; j < N; ++j) {
dp[r][j] += dif;
}
}
int sum(int r1, int c1, int r2, int c2) {
int res = 0;
for (int i = r1; i <= r2; ++i) {
res += c1 == 0 ? dp[i][c2] : dp[i][c2] - dp[i][c2-1];
}
return res;
}
[size=13.3333330154419px]set O(log n)
[size=13.3333330154419px]sum O(log n)
Solution:
Lets take an example:
Given a matrix M[R][C], initially set to 0.
We have 2 operations:
1. set r,c,Value element to value.
2.range sum r1,c1,r2,c2 ; return the sum of all the elements r,c such that r1<=r<=r2, c1<=c<=c2;
This can be done using Fenwick 2D Point updation Tree.
1. Use update(r,c,Value) for 1st operation;
void update(int x , int y , int val){
int y1;
while (x <= max_x){
y1 = y;
while (y1 <= max_y){
tree[x][y1] += val;
y1 += (y1 & -y1);
}
x += (x & -x);
}
}
2. read(r1,c1,r2,c2) = read(r2,c2) - read(r2,c1-1) - read(r1-1,c2) + read(r1-1,c1-1);
int read(int x,int y){ // return sum from 1,1 to x,y.
int sum= 0;
while( x){
int y1 = y;
while(y1){
sum += tree[x][y1];
y1 -= y1 & -y1;
}
x -= x & -x;
}
return sum;
}
import java.lang.*;
public class BIT2DSumAndUpdate {
// Given an NxN matrix of positive and negative integers, write code to find the
// range sum and update matrix
// Approach#1 sum: O(n^2) time, update:O(1) time.
static int sum(int[][] matrix, int r1, int c1, int r2, int c2) {
int sum = 0;
for (int r = r1; r <= r2; ++r) {
for (int c = c1; c <= c2; ++c) {
sum += matrix[r][c];
}
}
return sum;
}
static void update (int[][] matrix, int r1, int c1, int val){
matrix[r1][c1] = val;
}
// Approach#2 sum: O(1) time, update:O(n^2) time.
static int[][] processMatrix(int[][] m) {
if (m == null) return null;
int[][] sumMatrix = new int[m.length][m[0].length];
sumMatrix[0][0] = m[0][0];
for (int j = 1; j < m[0].length;j++){
sumMatrix[0][j]=sumMatrix[0][j-1]+m[0][j];
//System.out.println(0+","+j+" - "+sumMatrix[0][j]+",");
}
for (int i = 1; i < m.length;i++){
sumMatrix[i][0]=sumMatrix[i-1][0]+m[i][0];
//System.out.println(i+","+0+" - "+sumMatrix[i][0]+",");
}
for (int i =1; i< m.length;i++) {
for (int j=1; j < m[0].length;j++){
sumMatrix[i][j] = sumMatrix[i-1][j]+sumMatrix[i][j-1]-sumMatrix[i-1][j-1]+m[i][j];
//System.out.println(i+","+j+" - "+sumMatrix[i][j]+",");
}
}
return sumMatrix;
}
static int sum2(int[][] sumMatrix, int r1, int c1, int r2, int c2) {
if (r1 == 0 && c1 == 0){
return sumMatrix[r2][c2];
}
else if (r1 == 0){
return sumMatrix[r2][c2]-sumMatrix[r2][c2-1];
}
else if (c1 == 0 ){
return sumMatrix[r2][c2]-sumMatrix[r1-1][c2];
} else {
return sumMatrix[r2][c2]-sumMatrix[r2][c1-1]-sumMatrix[r1-1][c2]+sumMatrix[r1-1][c1-1];
}
}
static void update2(int[][] matrix, int[][] sumMatrix,int r1, int c1, int val){
int diff= val - matrix[r1][c1];
for (int i = r1; i < sumMatrix.length;i++){
for (int j = c1; j< sumMatrix[0].length; j++){
sumMatrix[i][j]+=diff;
}
}
}
// Approach#3 sum: O(log n) time, update:O(log n) time.
static int[][] processMatrixTree(int[][] m) {
if (m == null) return null;
int[][] tree = new int[m.length+1][m[0].length+1];
for( int i = 1; i <= m.length;i++){
for(int j = 1; j <=m[0].length;j++){
//System.out.println(i+","+j+". sumFirst="+tree[i][j]);
updateBuilde3(tree, i, j, m[i-1][j-1]);
}
}
return tree;
}
static int sum3(int[][] tree, int r1, int c1, int r2, int c2) {
if (r1 == 0 && c1 == 0){
return getSum(tree,r2,c2);
}
else if (r1 == 0){
return getSum(tree,r2,c2)-getSum(tree,r2,c2-1);
}
else if (c1 == 0 ){
return getSum(tree,r2,c2)-getSum(tree,r1-1, c2);
} else {
return getSum(tree,r2,c2)-getSum(tree,r2,c1-1)-getSum(tree,r1-1, c2)+getSum(tree,r1-1,c1-1);
}
}
static int getSum(int[][] tree, int i, int j){
int sum = 0;
//System.out.println(i+","+j+". sumAdd="+sum);
i = i+1;
j = j+1;
int j1;
while(i > 0) {
j1 = j;
while(j1 > 0){
sum += tree[i][j1];
///System.out.println(i+","+j1+". sumAdd="+sum);
j1 -= j1 & -j1;
}
i -= i & -i;
}
return sum;
}
static void updateBuilde3(int[][] tree, int i, int j, int val){
//int diff= val - matrix[r1][c1];
int j1;
while(i < tree.length){
j1 = j;
while(j1 < tree[0].length){
tree[i][j1] += val;
//System.out.println(i+","+j1+". sumAfter="+tree[i][j1]);
j1 += (j1 & -j1);
}
i += (i & -i);
}
}
static void update3(int[][] matrix, int[][] tree, int i, int j, int val){
int diff= val - matrix[i][j];
int j1;
while(i < tree.length){
j1 = j;
while(j1 < tree[0].length){
tree[i][j1] += diff;
//System.out.println(i+","+j1+". sumAfter="+tree[i][j1]);
j1 += (j1 & -j1);
}
i += (i & -i);
}
}
//--------------------------------------
public static void main(String[]args) {
int[][] m = {
{1,-2,3,1},
{1,5,-4,1},
{1,1,0,2},
{-1,1,1,-8}};
int[][] m2 = {
{1,-2,3,1},
{1,5,-4,1},
{1,1,0,2},
{-1,1,1,-8}};
int[][] m3 = {
{1,-2,3,1},
{1,5,-4,1},
{1,1,0,2},
{-1,1,1,-8}};
long start = System.nanoTime();
int sum1_1 = sum(m,0,0,2,3);
long end = System.nanoTime();
update(m, 2,3,3);// 2->3
int sum1_2 = sum(m,0,0,2,3);
System.out.println("Time:"+(long)(end-start)+",sum=" +sum1_1+",sum2=" +sum1_2);
int[][] sumMatrix = processMatrix(m2);
long start2 = System.nanoTime();
int sum2_1 = sum2(sumMatrix,0,0,2,3);
long end2 = System.nanoTime();
update2(m2, sumMatrix, 2,3,3);// 2->3
int sum2_2 = sum2(sumMatrix,0,0,2,3);
System.out.println("Time:"+(long)(end2-start2)+",sum=" +sum2_1+",sum2=" +sum2_2);
int[][] tree = processMatrixTree(m3);
long start3 = System.nanoTime();
int sum3_1 = sum3(tree,0,0,2,3);
long end3 = System.nanoTime();
update3(m3, tree, 2,3,3);// 2->3
int sum3_2 = sum3(tree,0,0,2,3);
System.out.println("Time:"+(long)(end3-start3)+",sum=" +sum3_1+",sum2=" +sum3_2);
}
}
Subscribe to:
Posts (Atom)