anshuman101
BAN USERSuppose we have two integer
int i1 = 9890780787890
int i2 = 8908908
Size of integer in Java is 4 bytes.
The standard Java integer data types are:
byte 1 byte -128 to 127
short 2 bytes -32,768 to 32,767
int 4 bytes -2,147,483,648 to 2,147,483,647 (- 2.14 Billion and -2.14 Billion)
long 8 bytes -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807
How can concatenate these two.
Approach 1
Simple, No big deal .. one way is use String and sum this two.
Mean time is
Mean: 052
Approach 2
Multiplying the first one with 10X where X is number of zeros and sum.
Mean with this approach is
Mean 1490
import java.util.Random;
import java.util.Timer;
public class FastestIntConcatenation {
private static Timer timer ;
private static long mean;
private static int iterationCnt=1;
private static long timeCalculator(int i1, int i2, int approachFlag)
{
long startTime = System.nanoTime();
if(approachFlag == 1) approach1(i1, i2);
if(approachFlag == 2) approach2(i1, i2);
//if(approachFlag == 3) approach3(i1, i2);
long endTime = System.nanoTime();
long diff = endTime - startTime;
mean = (mean * iterationCnt + diff) /(iterationCnt + 1);
iterationCnt = iterationCnt + 1;
//System.out.println(("Diff:" + diff + ", mean:" + mean));
return mean;
}
private static String approach1(int i1, int i2)
{
return i1 + "" + i2;
}
private static void approach2(int a, int b)
{
long temp = b;
while (temp > 0) {
temp /= 10;
a *= 10;
}
a += b;
//System.out.println(a);
}
public static void main(String[] args) {
timer = new Timer();
int i1 = 23232;
int i2 = 1313213;
Random r = new Random();
//approach2(i1, i2);
for (int i = 0; i < 1000; i++) { i1 = r.nextInt(); i2 = r.nextInt();
System.out.println("Mean 0" + timeCalculator(i1, i2,0)); }
System.out.println("Approach 2 Starts");
for (int i = 0; i < 1000; i++) { i1 = r.nextInt(); i2 = r.nextInt();
System.out.println("Mean 1" + timeCalculator(i1, i2,1)); }
}
}
Optimized solution using Bucket sort based approach. The integer includes negative integer as well.
For example, if the array is [3, 5, 2, -4, 8, 11] and the sum is 7, your program should return [[11, -4], [2, 5]] because 11 + -4 = 7 and 2 + 5 = 7.
My approach
/**
* Approach 1: Print all the subset and find the matching sum
* Approach 2: Apply subset sum problem which 0(cnt * a.length)
* Approach 3: 0(n) how is it possible. Bucket sort based logic
*/
Approach 3 implementation is here
public class TwoSumProblem {
private static void findTwoSum(int[] a, int cnt)
{
int[] b = new int[100];
for(int i = 0 ; i < a.length ; i++)
{
b[a[i] + 50] = b[a[i] + 50] + 1;
}
int t1 = 0;
for(int i = 0 ; i < a.length ; i++)
{
if(b[a[i] + 50] == 1 && b[cnt - a[i] + 50] == 1 && cnt - a[i] + 50 != a[i] + 50)
{
b[a[i] + 50] = b[a[i] + 50] - 1;
b[cnt - a[i] + 50] = b[cnt - a[i] + 50] - 1;
t1 = cnt - a[i];
System.out.println("Pair is " + a[i] + " and " + t1);
}
}
}
public static void main(String[] args) {
int[] a = {3, 5, 2, -4, 8, 11} ;
findTwoSum(a, 7);
}
}
Stack is the right data structure for thsos
- anshuman101 February 12, 2020Basic check
public boolean checkBloodRelation(Person p1, Person p2)
{
if(p1 == null || p2 == null)
return false
if(this.isBloodRelated(p1,p2)) return true;
return(checkBloodRelation(p1.momid, p2.momid)||checkBloodRelation(p1.momid, p2.dadid)||checkBloodRelation(p1.dadid, p2.momid)||checkBloodRelation(p1.dadid, p2.dadid));
}
public boolean isBloodRelated(Person p1, Person p2)
{
if (p1==p2 || p1.momid==p2.momid || p1.dadid == p2.dadid)
return true;
else
return false;
}
Server Set = {s1, s2, ... sn}
Data almost evenly distributed
Take a random number r1 from any server and broadcast to all the servers.
Each server partition their dataset into two parts
where => partition 1 > r1 and parition 2 < r1
For each set get the size of partition1 and partition2
S1=> p11 and p12
S1=> p21 and p22
.
.
Sn=> pn1 and pn2
Location of mediam = sum (P11,P12...pn1,pn2)/2 = k
if sum(pi1) < k then k k - sum(pi1)-k
Functionality of Web Crawler
1. List of website to be crawled.
2. All the pages crawled should be stored.
3. Defined frequency for different type of web sites - New websites should be crawled frequenty
4. Consider robot.txt to determine what should not be crawled
5. Understand if there is any change in the page, if so recrawl.
6. Parse and persist.
Need a Queue for BST kind of experience.
Datastructure
1. Set : Key is hash of URL, value is parsed content
2. Zset: Key as hash of URL and timestamp
Queue - FIFO. Will check if content is available in Set, if no then it will store in the Set along with Zset.
Technique
- Bloom filter for determining if the page is not present in the storage. This is OOB in Redis.
- For page modification, rely on modification time, MD5 etc. this can be persisted as a separate set.
A Hash in redi
Apply Bucket Sort on first K elements only for both the sorted array.
- anshuman101 February 24, 2020Iterate through the bucket from 1 -- k to get the kth mean.
Assumption: Memory is not an issue and bucket array can be very high.