Ajeet
BAN USERLearn & Share
Edit distance algorithm is the perfect solution for this ....
distance(a, b){
//Create an empty matrix to hold distance.
m= size of a and
n = size of b
int[][] dist = new int[m+1][n+1];
//Fill the matrix with base values
for(i = 0 to n){
dist[i][0] = i;
}
for(i = 0 to m){
dist[0][j] = j;
}
int cost = 0;
for(i from 0 to n){
for(j from o to m){
if(a[i] == b[j]){
// Both have same character so no need of any modification
cost = 0;
} else {
//Both strings have different characters so it required modification - deletion, insertion or substitution.
//Each edit operation has cost 1, because in each operation we are changing only one character.
cost = 1;
}
//Update dist matrix with appropriate modification
dist[i][j] = minimun of ( cost+dist[i-1][j-1], //Substitution
cost+dist[i-1][j], //Deletion
cost+dist[i][j-1]); //Insertion
}
}
return dist[m][n];
}
We can assume matrix with these two array... like A represents rows and B represents columns.
We need only 3rd element, it will lie in 3X3 matrix if more than 7 sums are not same(duplicate).
So first we will check in first 3X3 matrix than move to 6X6 ...9X9 .... so on.
int m = length of first array;
int n = length of second array;
MaxHeap maxHeap = new MaxHeap(3); // Max heap without duplicate, add() method will check if there is duplicate.
int maxLength = max(m,n);
for(k = 0; K < maxLength; K = K+3){
for(int i = K; (i < K+3) && (i < m); i++){
for(int j = K; (j < K+3) && (j < n); j++){
maxHeap.add(A[i]*B[j]);
if(maxHeap.size() == 3){
return maxHeap.root();
}
}
}
}
As per the assumption of this answer ....If we are sure that each line has size 3, than there will be no need to use extra space ....here is algo:
for(int i =0; i < 3; i++){
for(int i =0; i < 3; i++){
swap(a[i][j], a[2 - i][2 - j]);
}
}
But i dont think that in real business scenarios we have such kind of privileges .. :)
- Ajeet October 29, 2013I am adding both array (start from least significant digits). We need to find sum till (length -n)th element.
Example: Suppose we need to find 2nd sum ...
than we will stop after (5+1 - 2)th element and we will return it.
1 2 3 4 5
1 2 3 4 5
-------------------
- 4 6 9 0
int *AddArrays(int a[], int alen, int b[], int blen, int n)
{
int maxLen = max(alen, blen);
int *c = new int[maxLen + 1];
int acur = alen - 1;
int bcur = blen - 1;
int ccur = maxLen;
int carry = 0;
//Nth from start will be (length of sum array - N)th from end.
int nth = (maxLen + 1 - n);
while(ccur >= 0)
{ if(nth-- == 0){
return c[ccur];
}
int cur = carry;
if(acur >= 0)
cur += a[acur--];
if(bcur >= 0)
cur += b[bcur--];
c[ccur--] = cur % 10;
carry = cur/10;
}
return c;
}
If we need to maintain statistics for only a week than "Circular buffer" will be the right candidate.
It will contain 7 buckets (day, count).
As we will reach at 7th day (completed cycle), it will override first day.
And we will maintain a single global counter for "week".
Each time we will move from Sunday to Monday and will overiride Monday than we will remove its count value from the week counter.
Mon->Tue->Wed->Thu->Fri->Sat->Sun->Mon
We can easily get count for one day with O(1), and for week with O(1)
- Ajeet October 28, 2013If we need to maintain statistics for only a week than "Circular buffer" will be the right candidate.
It will contain 7 buckets (day, count).
As we will reach at 7th day (completed cycle), it will override first day.
And we will maintain a single global counter for "week".
Each time we will move from Sunday to Monday and will overiride Monday than we will remove its count value from the week counter.
Mon->Tue->Wed->Thu->Fri->Sat->Sun->Mon
We can easily get count for one day with O(1), and for week with O(1)
- Ajeet October 28, 2013Vibrator, light & pillow vibrator. To cover minimal to severely deaf.
Vibrator + Light = Normal deaf.
Pillow vibrator + Light = severely deaf.
Class Clock
Set the time.
Advance the time.
Display the time.
Class Hour indicator
Set its value
Advance its value
Display its value
Class Minute indicator
Set its value
Advance its value
Display its value
Class Seconds indicator
Advance its value
Display its value
Vibrator
Trigger
Silent
Light
On
Off
Agreed. No need to invest further time on this if we can't gain anything in terms of space or time.
But a better implementation of classic algo is always needed.... :)
Actually we study these basic algos\DS since first day of our engineerig\science courses. So we use to these basic algorithms and we never think about second option to implement it.
I am using this algo (check BST) with same complexity since last three years but never think about this way (cleaner approach). We generally so much confident about basics that we dont think necessary to google it.
But if we use a complex\advanced data structure than we give it proper time to implement it. May be due to fear of complexity.
Just sharing my personal experience ....
3 years back I implemented BST with in half day (including all unit tests to verify boundaries etc).
But to implement a Suffix Tree take more than a week - excluding algo and complexity study ... :) I was already aware what algo i have to use ....I took this much time to try implementation with different approaches ... :)
As we all know that we can use IN-Order traversing for this, without using any extra space.
But the implementation of this by Bob Dondero is simply awesome:
private boolean isBST() {
return isBST(root, null, null);
}
private boolean isBST(Node x, Key min, Key max) {
if (x == null) return true;
if (min != null && x.key.compareTo(min) <= 0) return false;
if (max != null && x.key.compareTo(max) >= 0) return false;
return isBST(x.left, min, x.key) && isBST(x.right, x.key, max);
}
Ref: leetcode.com/2010/09/determine-if-binary-tree-is-binary.html
- Ajeet October 23, 2013I am considering default implementation of Binary tree. Parent node is not given.
Using an extra class:
Pair {
Node node;
int distance; // To get upwards distance from given node = (depth - distance) .
}
Step 1. int depth = 0; // After this step it will hold depth of node.
Start from root and traverse path from root to given node (source node), and create a object of Pair(parentNode, depth++)) and add it in a Queue of size K.
If Queue is full before reaching the node (because depth can be larger than K) than remove one node from rear to make space and new node at front.
After this step Queue will hold all nodes and distance upwards at K or less distance from given node.
Queue result; //This will be output.
Step 2: Now find all upward nodes.
while (Queue ! = NULL){
Pair pair = parentQueue.dequeue();
int i = depth - pair.diatance;
if( i = K){
result.add(pair.node);
}
perfrom findKthNodesDownwards(givenNode, pair.node, K - i)
}
Step 3: Find all downward nodes.
findKthNodesDownwards(givenNode, null, K)
void findKthNodesDownwards(Node givenNode, Node node , int k)
{
if(node == NULL || givenNode == node)
return;
if( k == 0 )
{
nodes.add(node);
return ;
}
else
{
findKthNodes( node.left, k-1 ) ;
findKthNodes( root.right, k-1 ) ;
}
}
I think this is the most suitable scenario for K-Way merge. K represents the number of sorted one dimensional arrays.
Because it is NxN array, and it is row wise and column wise sorted.
Here number of sorted arrays = number of row (or we can use columns)= N
So here K will be equal to N.
Here is algorithm:
Put the minimum element of each array (each row will be treated as a array) into a min-heap.
Then, repeatedly extract the minimum element from the heap, and replacing it by inserting the next
element from the same array.
The heap will never be bigger than N elements, so each operation (either extract-min or
insert) takes O(lg N) time.
There are O(n) operations (one insert and one extract-min
for each element), so the running time is
O(MlogN): where M = total number of elements = N^2.
Reference: CLRS (2nd Ed) problem 6.5-8
If we have to count\return only number of anagrams for a string than why should we maintain words .. ?
We can use a HashMap, that will store key as a hash code (with hash collision for all anagrams - similar to my answer) and count as a value.
Each time a words occurs we will check in hashMap and just increase the count .. :)
Complexity will be O(1) to find all anagrams and space will be O(N), n = number of different anagram sets.
I will utilize hash collision to implement this. And i will use an array of prime numbers to avoid false collision.
HashTable<Integer, List<String>> dictionary;
1. Create an array of prime numbers. It can be easily generated by any random function.
//The size of this array will depend on the avilable number of character for words.
int primes[] = {2, 3, 5, 7, ...};
2. Get hascode for each word like this
int getHashCode(String str){
int hash = 31;
for(i =0 to length of str){
hash = hash*primes['a' - str.charAt[i]];
}
return hash;
}
3. Now we can create a dictionary with all given words:
//This hash table or map will maintain, integer as a key and a list of strings as a value.
//This is a standard approach to implement hash map. You can find it in any api so i am not mentioning its details here.
// You can look in to java.util.HashMap
void loadDictionary(String[] words){
for( word from words ; i = 0 to length of words) {
int hash = getHashCode(word);
List<String> anagrams = dictionary.get(hash);
if(anagrams ! = null){
anagrams.add(word);
} else
List<String> newAnagrams = new ArrayList<String>();
newAnagrams.add(word);
dictionary.put(hash, newAnagrams);
}
}
}
4. Now here is the approach to find anagrams:
int findNumberOfAnagrams(String str){
List<String> anagrams = dictionary.get(getHashCode(str));
return anagrams.size();
}
First there is no boundry defined in your question, so i did not consider that.
Second - as per the question, we are going to compress the string. It is a common requirement in business senarios. So for that if size of a character is 1 we did not make any change that.
Modified to working java code ... still i prefer pseudocode ... :)
public static char[] compress(char[] input){
int n = input.length;
if(n <= 1){
return input;
}
//Take two pointers P1 & P2
//Initialize
// P1 with 0 (position of first character in array) &
// P2 with 1 (position of second character in array)
int P1 = 0;
int P2 = 1;
int count = 1;
while(P2 < n){
if(input[P1] == input[P2]){
count++ ;
P2++;
if(P2 == n) {
//input[++P1] = (char)(count + "").charAt(0);
P1 = intToChar(count, input, P1);
input[++P1] = input[P2-1];
//This line is optional, for better output
input[P1] = '\0';
return input;
}
} else if(input[P1] != input[P2] && count > 1) {
//input[++P1] = (char)(count + "").charAt(0);
P1 = intToChar(count, input, P1);
input[++P1] = input[P2];
count = 0;
} else {
input[++P1] = input[P2++];
}
}
return input;
}
//Count can be of multiple digits
private static int intToChar(int count, char[] input, int position){
String str = count + "";
for(int i =0; i <str.length(); i++){
input[++position] = str.charAt(i);
}
return position;
}
public static void main(String[] args) {
char[] input = {'A','A','A','A','A','A','A','A','A','A','A','A','A','A','A','A','A','A','A','A','B','C','C','D','D','D'};
System.out.println(compress(input));
}
We can find median using random selection algorithm in linear time.
Actually here we are utilizing "5-random-elements method" to find a median in efficient way.
Pick 5 elements at random from
A[1..n], and set q to be their median.
What it is the probability that q is not a good pivot ?
• Let S be the elements of A[1..n] which are in the 10% smallest.
• The probability that an elements picked at random is in S is 0.1.
• q is in S only if at least 3 of the 5 elements that we pick are in S.
• The probability that this happens is
0.15 + 5•0.14 •0.9 + 10• 0.13 •0.92 =
all in S 4 in S,one not in S 2 not in S
= 0.00001 + 0.00045 + 0.00810=0.00856
• This is also the probability that q is in the 10% largest elements.
• In other words: with probability ≥98%, q is a good pivot.
Putting it together, during partition, each time that we need to find a pivot,
we use the “5 random elements” method.
With probability 98%, we find a good pivot.
The overall time that we spend on good partitions is much smaller than
the time we spent on bad partitions.
This algo can be apllied on QuickSelect or Selection algorithm.
Why down vote .. ? Did you relay try this algorithm .. ?
1. HashMap will store words as key and pointer\reference to a heap node.
2. Heap node will hold only count.
3. If a word occures and if it exists in hashMap than increase it's count, it can be at any level in heap, not necessary at root. After increasing a count of node in heap we need to maintain max heap so we execute heapify.
After the completion of input file, we will traverse heap to store\print sorted elements in decreasing order.
Note : It is a generic algorithm for any size of frequency or number if words in file.
Counting sort: Yes we can utilize that, if you are sure that frequency is smaller enough to fit in Integer's size of system.
And for counting sort you have to maintain a largest frequency.
Use two data structures - "Max heap" and "HashMap".
HashMap will contain word as a key and pointer to a node of Max heap as value. And Heap node will has only counter for frequency.
Now just read a word from the file.
Check in HashMap, if it is already there than increase it's frequency\count in heap and run heapify to maintain max heap.
If it is not in HashMap than add a new node in heap with frequency\count 1.
At end of file heap will contain ferequencies in dereasing order.
Complexity:
Time O(NlogN) - N = number of words in file
Space O(M) = M = number of unique words in file.
We can implement it using two locks, one for job1 and second one for job2.
public class ProducerConsumer {
Lock lock1 = new ReentrantLock();
Lock lock2 = new ReentrantLock();
public void job1() throws InterruptedException{
try{
lock1.lock();
// while(true){
// System.out.println("Job 1 started by " + Thread.currentThread().getName());
// Thread.currentThread().sleep(100);
// }
} catch(Exception ex){
ex.printStackTrace();
} finally {
lock1.unlock();
}
}
public void job2() throws InterruptedException{
try{
lock2.lock();
// while(true){
// System.out.println("Job 2 started by " + Thread.currentThread().getName());
// Thread.currentThread().sleep(100);
// }
} catch(Exception ex){
ex.printStackTrace();
} finally {
lock2.unlock();
}
}
//Test client
public static void main(String[] args) {
final ProducerConsumer pc = new ProducerConsumer();
Thread thread1 = new Thread(new Runnable() {
@Override
public void run() {
try {
pc.job1();
Thread.currentThread().sleep(100);
pc.job2();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}, "Thread1");
Thread thread2 = new Thread(new Runnable() {
@Override
public void run() {
try {
pc.job2();
Thread.currentThread().sleep(100);
pc.job1();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}, "Thread2");
thread1.start();
thread2.start();
}
}
It does not depends on value of X. It depends on index\place of bit 1 in X. Suppose following numbers are given .. 2, 3 4, 4. So in third iteration it will be something like ...0000011100. So in fourth iteration we can easily check with & operator that 4 is duplicate ...
0 1 = 0
1 0 = 0
1 1 = 1 - Duplicate
Looks like ...
- Ajeet October 30, 2013