SumitGaur
BAN USERThe following code work assuming all the 1s are grouped together
//Original Matrix
int[][] originalMatrix = new int[][] { { 0, 0, 0, 0, 0, 0 },
{ 0, 1, 1, 1, 0, 0 }, { 0, 0, 0, 1, 0, 0 } };
//Two temp arrays of length derived from number of rows and cols
int[] row = new int[originalMatrix.length];
int[] col = new int[originalMatrix[0].length];
//For every element in the original Matrix
for (int i = 0; i < row.length; i++) {
for (int j = 0; j < col.length; j++) {
//If a 1 is found
if (originalMatrix[i][j] == 1) {
//Increment the corresponding row and col number
row[i] += 1;
col[j] += 1;
}
}
}
//Find the maximum value
int maxLength = -1;
for (int i = 0; i < (row.length > col.length ? row.length : col.length); i++) {
if (i < row.length) {
if (row[i] > maxLength) {
maxLength = row[i];
}
}
if (i < col.length) {
if (col[i] > maxLength) {
maxLength = col[i];
}
}
}
//Print
System.out.println(maxLength);
public class ThreeStringProblem {
public static void main(String[] args) {
String one = "spqrstrupvqw";
String two = "sprt";
String three = "q";
int minLength = Integer.MAX_VALUE;
String minLengthString = "";
// Sliding window; Start from index 0 with a window of size equivalent
// to String two and increment by one character every iteration
for (int i = 0; i < one.length(); i++) {
for (int j = i + two.length(); j <= one.length(); j++) {
// Get the subString
String subString = one.substring(i, j);
// Check if all the characters match
if (checkIfAllCharactersArePresent(subString, two, three)) {
if (subString.length() < minLength) {
minLength = subString.length();
minLengthString = subString;
}
}
}
}
System.out.println(minLengthString);
}
/**
* The method is used to check if all the characters of String two are
* present in String one but not that of String three
*
* @param first
* @param two
* @param three
* @return
*/
private static boolean checkIfAllCharactersArePresent(String first,
String two, String three) {
boolean result = true;
BitSet bitSet = new BitSet();
// Set first String
for (int i = 0; i < first.length(); i++) {
bitSet.set(first.charAt(i));
}
// Third
for (int i = 0; i < three.length(); i++) {
if (bitSet.get(three.charAt(i))) {
result = false;
return result;
}
}
// Two
for (int i = 0; i < two.length(); i++) {
if (!bitSet.get(two.charAt(i))) {
result = false;
return result;
}
}
return result;
}
}
1. Create a frequency array of size (n + 1); where n is the maximum element in input array
2. For every element i, in the input array, increment the ith index in the frequency array by
3. Sort the frequency array in reverse order (decrementing).
4. The first k elements are the most frequent elements in the input array.
int[] array = new int[] { 1, 2, 1, 1, 3, 4, 5, 3, 3, 3, 3, 3, 5, 6, 7,
2, 9, 7, 5 };
int k = 3;
Integer frequency[] = new Integer[10];
Arrays.fill(frequency, 0);
for (int i = 0; i < frequency.length; i++) {
frequency[array[i]] += 1;
}
Arrays.sort(frequency, new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
if (o1.intValue() < o2.intValue()) {
return 1;
} else if (o1.intValue() > o2.intValue()) {
return -1;
} else {
return 0;
}
};
});
for (int i = 0; i < k; i++) {
System.out.println(array[frequency[i]]);
}
public class ThreadPriority {
public static void main(String[] args) throws Exception{
//Create a countdown latch for 1 thread. (We just need to wait for 1 thread to complete)
CountDownLatch countDown = new CountDownLatch(1);
//Create two threads
Thread firstThread = new Thread(new Task(countDown));
Thread secondThread = new Thread(new Task(countDown));
//Set their names
firstThread.setName("JobOne");
secondThread.setName("JobTwo");
//Start first thread
firstThread.start();
//Wait for countdown to decrease
countDown.await();
//Start second thread
secondThread.start();
}
}
/**
* The class represents a Task.
*
* @author sgaur
*
*/
class Task implements Runnable {
CountDownLatch countLatch = null;
public Task(CountDownLatch countDown) {
countLatch = countDown;
}
@Override
public void run() {
for(int i = 0 ; i < 10000; i++){
System.out.println(i + " Running " + Thread.currentThread().getName());
}
//After the process is complete, decrement the countDown
countLatch.countDown();
}
}
The recursive solution can be written as follows:
The inputString is a StringBuilder representation of String to leverage its mutability. Initially start and end are set to 0 and 1 respectively.
private static void removeDuplicate(StringBuilder inputString, int start,
int end) {
// If input String of length 0
if (inputString.length() == 0) {
System.out.println(-1);
return;
}
// If the end has reached
if (end >= inputString.length()) {
System.out.println(inputString);
return;
}
// If start character equals the end character; remove the two
if (inputString.charAt(start) == inputString.charAt(end)) {
// removes the start character
inputString.deleteCharAt(start--);
// As a character is removed; decrement the end counter as well
end--;
// removes the end character
inputString.deleteCharAt(end--);
// decrements the start character; can be skipped as in the next
// step we are setting it to 0 to restart the whole process from
// first character so as to incorporate the scenarios where deletion
// of some characters have NOW made two consecutive characters to be
// same
start--;
start = 0;
end = 1;
// calls recursively
removeDuplicate(inputString, start, end);
} else {
// if no duplicate characters are found then increment the counters
removeDuplicate(inputString, start + 1, end + 1);
}
}
The problem is somewhat similar to finding the duplicate in a list of values. What we can do is maintain a hashSet of nodes. We will traverse the nodes one by one and will insert their references in the HashSet. If the node is already present in the hashSet we find a cycle on that node. The complexity will be O(n) for traversing the linkedList and O(1) for insertion. The pseudo code for the same will be something like:
1. Initialize HashSet<Node> hashSet = new HashSet<Node>();
2. Initialize the root to the firstElement of the list
3. while null != root do steps (a) and (b)
a) boolean addedSuccessfully = hashSet.add(root)
b) if NOT addedSuccessfully
return the root; cycle exists at root
else root = root.next ; continue with loop
As you can move right or <b>down</b> only so a cell say (i,j) can be reached from (i-1,j) or (i,j-1) i.e from its left or from its upper cell only what we'll do is, to every cell (i,j) we will add the max[(i,j-1) AND (i-1),j] this will make the value at every (i,j) cell as maximum keeping in sync with the fact that only right and downward transitions are allowed.
public class MaxEggCollectionProblem {
public static void main(String[] args) {
int[][] eggsMapping = new int[][] { { 2, 4, 8 }, { 5, 6, 3 },
{ 4, 7, 6 } };
int numberOfRows = eggsMapping.length;
int numberofColumns = eggsMapping[0].length;
printArray(eggsMapping, numberOfRows, numberofColumns);
// As you can move right or down only so a cell say (i,j) can be reached
// from (i-1,j) or (i,j-1) i.e from its left or from its upper cell only
// what we'll do is, to every cell (i,j) we will add the max[(i,j-1) AND
// (i-1),j]
// this will make the value at every (i,j) cell as maximum keeping in
// sync with the fact that only right and downward transitions are
// allowed
findMaxEggs(eggsMapping, numberOfRows, numberofColumns);
System.out.println("\n\n");
System.out.println("Max eggs collected at cell 1,2 is " + eggsMapping[1][2]);
System.out.println("Max eggs collected at cell 2,2 is " + eggsMapping[2][2]);
}
private static void printArray(int[][] eggsMapping, int numberOfRows,
int numberofColumns) {
System.out.println("===================");
// Print the array
for (int i = 0; i < numberOfRows; i++) {
for (int j = 0; j < numberofColumns; j++) {
System.out.print(eggsMapping[i][j] + "\t");
}
System.out.println("");
}
}
/**
* As you can move right or down only so a cell say (i,j) can be reached
* from (i-1,j) or (i,j-1) i.e from its left or from its upper cell only
* what we'll do is, to every cell (i,j) we will add the max[(i,j-1) AND
* (i-1),j] this will make the value at every (i,j) cell as maximum keeping
* in sync with the fact that only right and downward transitions are
* allowed
*
* @param eggsMapping
* @param numberofColumns
* @param numberOfRows
*/
private static void findMaxEggs(int[][] eggsMapping, int numberOfRows,
int numberofColumns) {
for (int i = 0; i < numberOfRows; i++) {
for (int j = 0; j < numberofColumns; j++) {
int leftWeight = -1;
int topWeight = -1;
leftWeight = (i - 1) < 0 ? 0 : eggsMapping[i - 1][j];
topWeight = (j - 1) < 0 ? 0 : eggsMapping[i][j-1];
eggsMapping[i][j] += Math.max(leftWeight, topWeight);
}
}
printArray(eggsMapping, numberOfRows, numberofColumns);
}
}
public static void main(String[] args) {
Set<String> spams = new HashSet<String>() {
{
add("blob");
add("cool");
}
};
System.out.println(checkIfSpam("bbbblllllllooooooooobbbbbbbbb", spams));
}
private static boolean checkIfSpam(String string, Set<String> spams) {
StringBuilder builder = new StringBuilder(string);
for (int i = 1; i < builder.length(); i++) {
if (builder.charAt(i) == builder.charAt(i - 1)) {
builder.deleteCharAt(i);
i--;
}
}
System.out.println(builder);
return spams.contains(builder.toString());
}
// input string
String input = "ssbbbbadnnnnnnnnnnzzy";
// create a string builder to leverage its mutability
StringBuilder stringBuilder = new StringBuilder(input.toUpperCase());
int count = 1;
// for every character starting from index 1
for (int i = 1; i < stringBuilder.length(); i++) {
// If that character is equal to the previous character
if (stringBuilder.charAt(i) == stringBuilder.charAt(i - 1)) {
// delete the current character
stringBuilder.deleteCharAt(i);
// decrement the index
i--;
// increment the count for that character
count++;
} else {
// else insert the count for previous character at current index
stringBuilder.insert(i, count);
// if the count is a double digit number move two places ahead
// else only 1 place
i += count > 9 ? 2 : 1;
// reset the count to 1 for next character
count = 1;
}
}
//insert the count for last character
stringBuilder.insert(stringBuilder.length(), count);
System.out.println(stringBuilder);
This can be achieved by overriding the put method of HashMap. Something like this will do the job:
Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>() {
@Override
public Integer put(Integer key, Integer value) {
if (!this.containsKey(key)) {
return super.put(key, value);
}
return null;
}
};
hashMap.put(1, 1);
hashMap.put(1, 2);
System.out.println(hashMap.get(1));
Good One. . !!
- SumitGaur May 13, 2014