subahjit
BAN USERA hashmap such as
HashMap<String, LinkedList<String>> anagramHaspMap
such that the key is the string which is alphabet sorting of the input strings and the linkedlist is the list of the anagrams for the String.
For example for "eat" the data will be stored as:
"aet" : "eat" -> "tea" -> "ate" -> null
so for a given input word sort it in alphabetic order and then perform a hash look up.
with no other information given in the question, I can only think of the following.
public interface Walker{
public void walk();
public void breath();
}
public interface Talker{
public void talk();
public void breath() ;
}
public class Swimmer implements Walker, Talker{
public void walk() {
System.out.println("I walk");
}
public void talk() {
System.out.println("I talk");
}
public void swim() {
System.out.println("I swim");
}
public void breath() {
System.out.println("I breath");
}
}
Code is as follows:
public class StackOnElementFrequency {
private HashMap<Integer, Stack<Integer>> countStackMap;
private HashMap<Integer, Integer> elementCountMap;
private int maxCount;
public StackOnElementFrequency() {
countStackMap = new HashMap<Integer, Stack<Integer>>();
elementCountMap = new HashMap<Integer, Integer>();
maxCount = 0;
}
public void push(int newElement) {
int count = 0;
if(elementCountMap.containsKey(newElement)) count = elementCountMap.get(newElement) + 1;
else count = 1;
elementCountMap.put(newElement, count);
if(countStackMap.containsKey(count)) countStackMap.get(count).push(newElement);
else {
Stack<Integer> stack = new Stack<Integer>();
stack.push(newElement);
countStackMap.put(count, stack);
}
if(count > maxCount) maxCount = count;
}
public int pop() {
if(maxCount == 0) {
System.err.println("Empty Stack");
return -255;
}
Stack<Integer> maxElementCountStack = countStackMap.get(maxCount);
int resultToPop = maxElementCountStack.pop();
if(maxElementCountStack.isEmpty()) {
countStackMap.remove(maxCount);
maxCount = maxCount - 1;
}
elementCountMap.put(resultToPop, elementCountMap.get(resultToPop) - 1);
if(elementCountMap.get(resultToPop) == 0) elementCountMap.remove(resultToPop);
return resultToPop;
}
}
You need the following DS:
HashMap<Integer, Stack<Integer>> countStackMap
HashMap<Integer, Integer> valueCountMap
int maxCount
For push operation:
1> Check if the element is present in valueCountMap
1a> If present then increment the count in valueCountMap and add a element (newCountOfThisElement -> Stack(newelement) in countStackMap ; if the newCountOfThisElement is present in countStackMap then (newCountOfThisElement -> Stack(newElement,.....other elements)
1a> If not present then add element in valueCountMap with count as 1 and add in countStackMap the key-value pair (1 -> stack(newElement,...old elements)
2> If the count of this new element is greater than maxCount ; increment maxCount by 1
For pop operation:
1> Return countStackMap.get(maxCount).pop()
2> Reduce the maxCount by 1 if the stack countStackMap.get(maxCount) is empty
Complexity:
push: O(1)
pop: O(1)
Please let me know for errors or corner cases
public class BiggestIntervalWithElementsInArray {
private static void sort(int[] array, int left, int right) {
int pivotIndex = left + (right - left)/2;
int i = left - 1;
int j = right + 1;
while(i <= j) {
i++;
while(array[i] < array[pivotIndex] && i < right) i++;
j--;
while(array[j] > array[pivotIndex] && j > left) j--;
if(i < j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
if(i < right) sort(array, i, right);
if(j > left) sort(array, left, j);
}
public static void printInterval(int[] arr) {
if(arr == null || arr.length == 0) {
System.err.println("Empty array");
return;
}
sort(arr, 0, arr.length-1);
for(int i = 0; i < arr.length; i++) System.out.print(arr[i] + ", ");
int maxIntervalStartIndex = 0;
int maxIntervalEndIndex = 0;
int currentIntervalStartIndex = 0;
int currentIntervalEndIndex = 0;
for(int i = 1; i < arr.length; i++) {
if(arr[i] - arr[i-1] == 1) currentIntervalEndIndex++;
else {
if(maxIntervalEndIndex - maxIntervalStartIndex < currentIntervalEndIndex - currentIntervalStartIndex) {
maxIntervalEndIndex = currentIntervalEndIndex;
maxIntervalStartIndex = currentIntervalStartIndex;
}
currentIntervalStartIndex = currentIntervalEndIndex = i;
}
}
if(maxIntervalEndIndex - maxIntervalStartIndex < currentIntervalEndIndex - currentIntervalStartIndex) {
maxIntervalEndIndex = currentIntervalEndIndex;
maxIntervalStartIndex = currentIntervalStartIndex;
}
System.out.println("Biggest Interval that has all its elements in the array is ["
+ arr[maxIntervalStartIndex] + ", " + arr[maxIntervalEndIndex] + "]");
}
}
Not sure why this solution is given -1.
My code is as follows:
public static int getNumber(int[] inputArray, int n) {
int result = 0;
if(inputArray == null || inputArray.length == 0)
System.out.println("Empty input array");
else {
int leftPointer = 0;
int rightPointer = inputArray.length - 1;
int resultPosition = 0;
if(leftPointer == rightPointer) resultPosition = leftPointer;
else {
int minimumDifference = n;
while(leftPointer < rightPointer) {
int leftDifference = Math.abs(n - inputArray[leftPointer]);
int rightDifference = Math.abs(n - inputArray[rightPointer]);
if(leftDifference <= rightDifference && leftDifference <= minimumDifference) {
resultPosition = leftPointer;
minimumDifference = leftDifference;
rightPointer--;
}
else if(rightDifference < leftDifference && rightDifference <= minimumDifference) {
resultPosition = rightPointer;
minimumDifference = rightDifference;
leftPointer++;
}
else break;
}
}
result = inputArray[resultPosition];
}
return result;
}
Sort the array O(nlogn)
Then start from the beginning scanning the array for consecutive elements.
Store the start and end index of the consecutive element sub-array and modify when a new larger sub-array is found.
At the end return the start and end index of the larget sub-daary having consecutive elements.
O(n)
So final complexity = O(nlogn + n) = O(nlogn)
Since the array is sorted, begin checking from the beginning and the end.
For each check find the difference with the number (n) and compare the absolute value of the differences.
If the left difference is more increment the left pointer.
If the right difference is more decrement the right pointer.
Store the minimum difference.
If in the next iteration, the minimum difference is more than the minimum difference so far,stop and return the last number.
@ashot
Yes all the permutations of the characters of the given word taking all the characters in a single permutation.
Then the dictionary look up.
I have assumed that the dictionary look up apis are given and we do not have to design the dictionary data structure.
Create two arrays;
One will store the input numbers.
Other array will contain the index. Inaitally {0, 1,2,3, ..}
Sort the input array and while sorting also change the index array whenever these is swap in the input array.
Now traverse both the sorted input array and the index array.
For every number check the 2 numbers after it and there original indexes in the index array.
If the indexes are such tht i < j < k. Then this is a required triplet.
Complexity is O(nlogn + n) = O(nlogn)
My bad.
The data type of root should be double.
The changed code is here
public static double getSquareRoot(int number, double precision) {
double root = number/2;
if( Math.abs(root * root - number) <= precision ) return root;
while(Math.abs(root * root - number) > precision)
root = root - (root * root - number)/(2*root);
return root;
}
Do let me know if any other issues.
- subahjit July 05, 2013All the neighbours of the pixel (x,y) selected have to be changed including the current pixel.
There are 8 neighbours for a pixel.
(x-1, y-1)
(x-1, y)
(x-1, y+1)
(x, y-1)
(x, y+1)
(x+1, y-1)
(x+1, y)
(x+1, y+1)
for all these pixels the color will be the same as the new color of the clicked pixel at (x,y)
Since the question says tags with millions of entries, it will not be possible to create a huge tree and store the entire XML file in-memory.
So may be reading the xml file in chunks will be a good option.
In the chunk read into memory, parse it token-wise and search for tags between <> brackets.
For the matching tag print all the tokens till the closing of the tag</>.
Now this single thread can be made into multi-threaded, with each thread assigned a different chunk of the file.
Store the data in the following structure:
public class LicensePlate {
private HashMap<String, LinkedList<String>> licensePlates = new HashMap<String, LinkedList<String>>();
public LicensePlate(String[] arr) {
for(String licensePlate : arr) {
String aplhabetPart = licensePlate.split("-")[0];
String numberPart = licensePlate.split("-")[1];
if(licensePlates.containsKey(aplhabetPart)) licensePlates.get(aplhabetPart).add(numberPart);
else {
LinkedList<String> numberList = new LinkedList<String>();
numberList.add(numberPart);
licensePlates.put(aplhabetPart, numberList);
}
}
}
}
private static int partition(int[] arr, int left, int right, int pivotIndex) {
int pivot = arr[pivotIndex];
//Move pivot to the end
arr[pivotIndex] = arr[right];
arr[right] = pivot;
int newIndex = left;
for(int i = left; i < right; i++) {
if(arr[i] >= pivot) {
//swap arr[i] with arr[newIndex]
int temp = arr[newIndex];
arr[newIndex] = arr[i];
arr[i] = temp;
newIndex++;
}
}
//Move pivot to its position
int temp = arr[right];
arr[right] = arr[newIndex];
arr[newIndex] = temp;
return newIndex;
}
private static int select(int[] arr, int left, int right, int n) {
if(left == right) return arr[left];
int pivotIndex = left + (right - left)/2;
int newPivotIndex = partition(arr, left, right, pivotIndex);
int newPivotDistance = newPivotIndex - left + 1;
if(newPivotDistance == n) return arr[newPivotIndex];
else if(newPivotDistance > n) return select(arr, left, newPivotIndex -1, n);
else return select(arr, newPivotIndex + 1, right, n - newPivotDistance);
}
The following optimizations can be done
1> Prime numbers apart from 2 are all odd numbers
2> To check whether a number is prime it suffices to check numbers from 2 to sqrt of number
3> Any number can be broken down to product of prime factors
So while iterating to find nth prime number over the range of numbers, we need to consider only odd numbers greater than 2 and also for any number to check if its prime we need to check if its divisible without remainder by all prime numbers less equal to square root of the number.
Please suggest if we can have further improvement.
Using Newton Raphson method.
public double getSquareRoot(int number, double precision) {
int root = number / 2;
if( Math.abs(root * root - number) <= precision ) return root;
while(Math.abs(root * root - number) > precision)
root = root - (root * root - number)/(2*root);
return root;
}
Since we do not have enough memory to store the values, we need to use external file to store the numbers.
File will store the k largest numbers.
Every time we read a number from the input file, we need to compare with the already present numbers in the output file then accordingly store or reject this number.
Complexity is O(k*n).
Can we improve the searching in the output file?
How about a circular array?
Array where after array.length -1 position we come back to position 0.
Basically using modulo operation.
For elements which are removed in those cells in the array we can have some pre-defined indentifier number to indicate empty cell.
Removal for single element will be O(1) since we can find the exact index which has to be free.
So for n elements the removal will be O(n).
Please provide suggestions on this solution.
The graph can be represented as an adjancency matrix or list of nodes with list of tuples for directed edges.
In an adjancency matrix representation, the edge direction can be stored by having 1
for adj[i][j] = 1 such tht i->j is a directed edge.
In the tuple representation, <i, j>, where i->j is a directed edge.
public class BinarySearchTree {
private class Node {
int value;
Node left;
Node right;
public Node(int val) {
value = val;
left = null;
right = null;
}
}
Node root = null;
private int keyCeiling(int key, Node currNode) {
if(currNode == null) return -1;
int ceiling = -1;
if(key == currNode.value) ceiling = currNode.value;
else if(key < currNode.value) {
ceiling = currNode.value;
int ceil = keyCeiling(key, currNode.left);
ceiling = (ceil == -1) ? ceiling : ceil;
}
else {
int ceil = keyCeiling(key, currNode.right);
ceiling = (ceil == -1) ? ceiling : ceil;
}
return ceiling
}
public void findCeiling(int key) {
if(root == null) {
System.out.println("Empty binary search tree");
return;
}
int ceilValue = keyCeiling(key, root);
if(ceilValue == -1)
System.out.println("Not found ceiling value for " + key);
else
System.out.println("Ceiling value for " + key + " is " + ceilValue);
}
}
Please let me know if I have missed out any corner cases.
- subahjit June 24, 2013Read the numbers as astring from the file.
Then iterate over the string and store in a linked list with each node of the linked list containing the digits of the number.
Now add the digits in the two linked list to get the sum in another linked list.
Need to take care of the MSD and LSD of the numbers.
Can store the linked list such that the head points ot the LSD.
Also need a carry integer.
The final result in the linked list will have to be stored in the output file.
Complexity: O(m) where m is the maximum number of digits out of the two input numbers.
@allanchaly Thanks
- subahjit October 22, 2013