ashu1.220791
BAN USERSince RAM is very less than the size of file, we can't load it into memory at a time and hence we need chunk logic:
1. Let's divide file into 30-40 chunks such that at least 2 chunks can be loaded in memory at a time.
2. Load i'th chunk into memory. This chunk will contain words which will be compared with next remaining chunks, one at a time.
(a) Load next chunks one by one into memory and remove all words which also occurred in i'th chunk. After every chunk is processed like this, write it back into file at its designated position.
(b) Remove duplicate words into the i'th chunk itself and then write it back into the file as well at its designated position.
3. Repeat step 3 for all chunks until we reach EOF (end of file).
Note for step 2: Start position of next chunk to be compared with others will be the next position after end of previous updated (written into file after processing in 2(b)) chunk.
Can we use max-heap structure such that each node of the max-heap has two values -frequency and word, and the max-heap is based on the frequency value? We can read file and iterate over words such that while iterating over a word, we increment its frequency in the max-heap and then call heapify() to make sure heap structure is maintained. We can keep track of frequency of a word by using a HashMap such that it has key as word and value as pair (frequency, address to the max-heap node for that word).
- ashu1.220791 January 18, 2018To get the actual max unique string as is expected here, I am using below method:
public static String longestUniqueChars(Iterator<Character> chars) {
if (chars == null) {
return null;
}
int startUnique = 0;
int curr = 0;
int maxUniqueLength = 0;
int currUniqueLength = 0;
String uniqueString = "";
String maxUniqueString = null;
int[] lastCharIndex = new int[26];
for (int i = 0; i < 26; i++) {
lastCharIndex[i] = -1;
}
while (chars.hasNext()) {
char ch = chars.next();
uniqueString += ch;
if (lastCharIndex[ch - 'a'] == -1 || lastCharIndex[ch - 'a'] < startUnique) {
currUniqueLength++;
} else {
startUnique = lastCharIndex[ch - 'a'] + 1;
currUniqueLength = curr - startUnique + 1;
int indexOfRepChar = uniqueString.indexOf(ch);
uniqueString = uniqueString.substring(indexOfRepChar + 1, uniqueString.length());
}
if (currUniqueLength > maxUniqueLength) {
maxUniqueLength = currUniqueLength;
maxUniqueString = uniqueString;
}
lastCharIndex[ch - 'a'] = curr;
curr++;
}
return maxUniqueString;
}
Tested with following string "abcacdefghijkklabcdefghijklmnoabc" and it gave expected answer which is "abcdefghijklmno"
public static int longestUniqueChars(Iterator<Character> chars) {
if (chars == null) {
return 0;
}
int startUnique = 0;
int curr = 0;
int maxUniqueLength = 0;
int currUniqueLength = 0;
int[] lastCharIndex = new int[26];
for (int i = 0; i < 26; i++) {
lastCharIndex[i] = -1;
}
while (chars.hasNext()) {
char ch = chars.next();
if (lastCharIndex[ch - 'a'] == -1 || lastCharIndex[ch - 'a'] < startUnique) {
currUniqueLength++;
} else {
startUnique = lastCharIndex[ch - 'a'] + 1;
currUniqueLength = curr - startUnique +1;
}
if (currUniqueLength > maxUniqueLength) {
maxUniqueLength = currUniqueLength;
}
lastCharIndex[ch - 'a'] = curr;
curr++;
}
return maxUniqueLength;
}
- ashu1.220791 January 18, 2018public class MergeIntervals {
static int[][] arr1 = new int[][] { { 3, 11 }, { 17, 25 }, { 58, 73 } };
static int[][] arr2 = new int[][] { { 6, 18 }, { 40, 47 } };
static int[][] arr3 = new int[arr1.length + arr2.length][];
/**
* @param args
*/
public static void main(String[] args) {
int i = 0;
int j = 0;
int k = 0;
int[] intersectionCheckInterval = null;
boolean isActiveIndexI = false; // This will tell with which array, we
// need to check
// intersection. This is useful in else case only when we already have
// an intersection
while (i < arr1.length && j < arr2.length) {
// If there was no previously known intersection to check current
// intervals with
if (intersectionCheckInterval == null) {
intersectionCheckInterval = getIntersectingInterval(arr1[i][0],
arr1[i][1], arr2[j][0], arr2[j][1]);
// If i and j do not intersect, select smaller interval and put
// into result array
if (intersectionCheckInterval == null) {
if (arr1[i][0] < arr2[j][0]) {
arr3[k++] = arr1[i++];
} else {
arr3[k++] = arr2[j++];
}
} else {
// If i and j intersect, we move ahead in i or j based on
// which
// interval had lesser high value
if (intersectionCheckInterval[1] == arr1[i][1]) {
j++;
isActiveIndexI = false;
} else {
i++;
isActiveIndexI = true;
}
}
} else {
// If we already have an intersection then
int[] temp = intersectionCheckInterval;
if (isActiveIndexI) {
intersectionCheckInterval = getIntersectingInterval(
intersectionCheckInterval[0],
intersectionCheckInterval[1], arr1[i][0],
arr1[i][1]);
if (intersectionCheckInterval == null) {
arr3[k++] = temp;
j++;
} else {
if (intersectionCheckInterval[1] == arr1[i][1]) {
j++;
isActiveIndexI = false;
} else {
i++;
isActiveIndexI = true;
}
}
} else {
intersectionCheckInterval = getIntersectingInterval(
intersectionCheckInterval[0],
intersectionCheckInterval[1], arr2[j][0],
arr2[j][1]);
if (intersectionCheckInterval == null) {
arr3[k++] = temp;
i++;
} else {
if (intersectionCheckInterval[1] == arr2[j][1]) {
i++;
isActiveIndexI = true;
} else {
j++;
isActiveIndexI = false;
}
}
}
}
}
if (i != arr1.length && j == arr2.length) {
while(i != arr1.length){
arr3[k++] = arr1[i++];
}
} else if (i == arr1.length && j != arr2.length) {
while(j != arr2.length){
arr3[k++] = arr2[j++];
}
}
for(int p=0;p<k;p++) {
System.out.println(arr3[p][0]+":"+arr3[p][1]);
}
}
static boolean isIntersecting(int low1, int high1, int low2, int high2) {
if (low1 >= low2 && low1 <= high2)
return true;
if (low2 >= low1 && low2 <= high1)
return true;
return false;
}
static int[] getIntersectingInterval(int low1, int high1, int low2,
int high2) {
int[] intersectInterval = null;
if (isIntersecting(low1, high1, low2, high2)) {
intersectInterval = new int[2];
intersectInterval[0] = Math.min(low1, low2);
intersectInterval[1] = Math.max(high1, high2);
}
return intersectInterval;
}
}
If there are n machines and m of them are defective, we can do following procedure:
1.Label machines from #1 to #n
2.Divide them in sets with each set having m+1 machines.
If n = k*(m+1) + r then there will be k+1 sets with k having exactly m+1 machines and 1 last set having r machines. Remember that r can be at max m (max value of n%(m+1))
3.For each of the k+1 sets, get a coin from each machine from the set. Now, take a coin and do its weight comparison with all other coins. (total m comparisons).
4.If all coins are of same weight, we move to next set. If not, we may get a few coins less heavy and therefore the corresponding machines are defective. If the number of defective machines found in a set is already equal to m, we are done else move to the next set.
=>So, in the above method, we are doing in worst scenario doing max comparisons possible which equals: k*(m) + (r-1). Since, k = n/(m+1) and r = n%(m+1), we can write this in terms of n and m as follows: (n/(m+1))*m + n/(m+1) - 1
Can anyone explain the problem? What is the meaning of k contiguous row-wise elements?
- ashu1.220791 October 04, 2015Simple program to convert roman to decimal number:
#include <stdio.h>
#include <string.h>
int main() {
char input[100];
printf("\nEnter a number with roman numerals [Please ener valid number as not checking validity]: ");
scanf("%s", input);
int output;
int i = 0;
int len = strlen(input);
while(i < len){
char ch = input[i];
switch(ch) {
case 'M':
output += 1000;
break;
case 'D':
output += 500;
break;
case 'C':
//It can be taken as +100 or -100
//It will be 100 if input after this is D or M
//else
//-100
if(i+1 <= len && (input[i+1] == 'D' || input[i+1] == 'M'))
output += -100;
else
output += 100;
break;
case 'L':
output += 50;
break;
case 'X':
//It can be taken as +10 or -10
//It will be 10 if input after this is L or C
//else
//-10
if(i+1 <= len && (input[i+1] == 'L' || input[i+1] == 'C'))
output += -10;
else
output += 10;
break;
case 'V':
output += 5;
break;
case 'I':
//It can be taken as +1 or -1
//It will be 1 if input after this is V or X
//else
//-1
if(i+1 <= len && (input[i+1] == 'V' || input[i+1] == 'X'))
output += -1;
else
output += 1;
break;
}
i++;
}
printf("\nGiven number in decimal is : %d", output);
}
The number of ways to select 2 robots such that both belong to separate models are:
pC2 * 2 * 2 + pC1 * 2 * (n-2p)C1 + (n-2p)C2
if n is total number of bots and p are distinct pairs.
Let's say you have 3 item types (shirts, socks and jeans).
1. Create a hashmap of type HashMap<String, Integer>(where key is category and value is its count) each for Shirt, Sock and Jeans.
2. Now, read each input line and find out category and item type(last word is item type while other words form category). Ex. if input is "polka dot sock" then item type is sock and category is "polka dot".
3. In the corresponding hashmap, increment the value of that category entry or add the new entry for the category with value = 1 if it doesn't exist.
4. Once we've read all input lines and our hashmaps are filled, first we get all the entries of sock hashmap. If and entry has even value, output it as "<value/2>|<category_name>" but if the value is odd, output 2 lines: "<value/2>|<category_name>" and "0|<category_name>".
5. Now for other categories shirt and jeans, do this:
Get the hashmap entries and output one line each for the various categories as "<value>|<category_name>".
I hope this is correct and I haven't assumed something wrongly!
Let the side of each square be M units then area of each square is M^2 so net area of N squares is A = N*(M^2) and hence the minimum side square would be of sqrt(A) = M*sqrt(N) units side.
- ashu1.220791 August 15, 2013@rockstar: awesome approach dude!! :)
- ashu1.220791 November 10, 2012In any case it's better to sort. Need an array to store heads (M in no.) of resulting lists. Sort this array in MlogM. Now, for every original linked list (N in no.), find it's head(in logM) in just sorted heads. If found, traverse it completely to check with the original list, if they are same, add respective head to the answer.
Total time complexity: O(MlogM)+O(NlogM)+O(N*avg_no_in_merged_lists).
First do inorder traversal to get a sorted array. Now, for every element, c in array, do following : find pairs a, b such that a+b = k-c in remaining array by using a HashMap technique. Traverse remaining array and for each element, insert it in HashMap using following rules.
(1)If an element (a) is already present as key that when combined with it(b) gives k-c, then insert it as value to that key.
(2)Otherwise, insert it as key with value as INT_MIN or INT_MAX or INFINITY.
Now, the entries in the hashmap with proper values will give required pairs(key, value). Combining these with c gives triplets needed. Do this for every possible c.
Let pattern(array, p[]) be of length M and given string(array, str[]) be of length N. Now,
int findMatchingIndex(char*str, char*p)
{
int i=0, j=0;
for(i=0;i<=N-M+1;i++)
{
if(str[i]==p[i])
{
int xored=1;
for(int j=0;j<M;j++)
{
xored *= str[i+j] ^ p[j];
if(xored==0)
return i; //index of first match
}
}
}
return -1; //not found
}
that's correct!! :)
- ashu1.220791 October 30, 2012
If B matches repeated A that means B can be written as <S><A...><P> where <S> is any suffix of A including empty suffix, <A...> is A repeated some number of times including zero times and <P> is any prefix of A including empty prefix. Let len(A) = N, len(B) = M then ans is 1 (if non-empty S exists) + number of times A is repeated + 1 (if non-empty P exists):
- ashu1.220791 July 07, 2019<S> and <P> can be checked to exist in O(N*N) while individual <A> can be checked in N time and there might be at max ceil(M/N) times <A> in B.
If this pattern is not matched, return -1.