Hope
BAN USERimport org.junit.Test;
/**
* There's a matrix. Each element in the matirx is a bit (0 or 1). Write a
* method to reverse this matrix. The matrix is stored in a one dimensional char
* array. The length of each row is given.
*
* How do you improve your solution when handling large amount of data?
*
*
* Solution: As I understood, the matrix was flatten out to character array.
* Since the length of each row is given we can calculate how much char array
* has fully been filled, we can use negation to reverse bits directly.
*
* It may be possible that the last bucket(index) in char array may not be
* filled fully so it is necessary to be taken care of separately.
*
*/
public class ReverseMatrix {
@Test
public void testReverseMatrix() {
char[] arr = { '\u1010', '\uD130', '\u2100' };
int[] lengthOfRows = { 5, 7, 6, 9, 11, 3 };
// print the matrix in binary format
StringBuilder sb = new StringBuilder();
System.out.println("Before reversing char array: ");
for (int i = 0; i < arr.length; i++) {
int myInt = (int) arr[i];
String binary = Integer.toBinaryString(myInt);
binary = String.format("%16s", binary).replace(' ', '0');
System.out.printf("%c: 0x%x, %s%n", arr[i], myInt, binary);
sb.append(binary);
}
System.out.println(sb.toString());
// reverse the matrix
reverseMatrix(arr, lengthOfRows);
sb.setLength(0);
// print the matrix in binary format
System.out.println("\nAfter reversing char array: ");
for (int i = 0; i < arr.length; i++) {
int myInt = (int) arr[i];
String binary = Integer.toBinaryString(myInt);
binary = String.format("%16s", binary).replace(' ', '0');
System.out.printf("%c: 0x%x, %s%n", arr[i], myInt, binary);
sb.append(binary);
}
System.out.println(sb.toString());
}
/**
* Time complexity: O(n)
*
* @param arr
* @param lengthOfRow
*/
public void reverseMatrix(char[] arr, int[] lengthOfRow) {
final int NUMBER_BIT = Character.BYTES * 8;
int totalLength = 0;
int i;
// get the sum of all lengths
for (i = 0; i < lengthOfRow.length; i++) {
totalLength += lengthOfRow[i];
}
// negate (reverse bits) except last index
int len = Math.min(totalLength / NUMBER_BIT, arr.length - 1);
for (i = 0; i < len; i++) {
arr[i] = (char) ~arr[i];
}
if (i < arr.length) {
int shift = NUMBER_BIT - (totalLength % NUMBER_BIT);
arr[i] = (char) ((~(arr[arr.length - 1] >>> shift)) << shift);
}
}
}
Output:
Before reversing char array:
?: 0x1010, 0001000000010000
?: 0xd130, 1101000100110000
?: 0x2100, 0010000100000000
000100000001000011010001001100000010000100000000
After reversing char array:
?: 0xefef, 1110111111101111
?: 0x2ecf, 0010111011001111
?: 0xde80, 1101111010000000
111011111110111100101110110011111101111010000000
public class UniformlyDisplayedTextWithSpace {
public static String insertSpace(String str, int length) {
int len;
if (null == str || str.length() == 0 || (len = str.length()) >= length)
return str;
StringBuilder sb = new StringBuilder();
while (len + str.length() < length) {
for (int i = 0; i < str.length() - 1; i++) {
if (Character.isAlphabetic(str.charAt(i)))
sb.append(str.charAt(i)).append(" ");
else
sb.append(str.charAt(i));
}
sb.append(str.charAt(str.length() - 1));
str = sb.toString();
sb.setLength(0);
}
return str;
}
@Test
public void testInsertSpace() {
String str = "driver";
String newStr = insertSpace(str, 30);
System.out.println(newStr);
}
}
As far as I understand, the question is about converting a recursive function to iterative one to eliminate stack overflow for large amount of input.
public class MyFolder<T, U> implements Folder<T, U> {
public U fold(U u, Queue<T> ts, Function2<T, U, U> function) {
if (u == null || ts == null || function == null)
throw new IllegalArgumentException();
while(!ts.isEmpty()) {
u = function.apply(ts.poll(), u);
}
return u;
}
}
Yes, definitely. It could be partial. Depends on the contraints/requirements of your application, there might be cases that a search query may return huge number of ad IDs. In order not to fill up in-memory cache quickly, we use pagination. By using pagination, two other parameters are by default introduced to system. (limit and offset [naming can be different]) [limit: # of elements that returns from query at a time (ad ID's in this case), offset: from where you want to continue to search]
Having said that, lets talk about it on an example now.
<HOST>/search?q="Comedy"&offset=0&limit=25 => this will return the first 25 ad IDs from this search query
<HOST>/search?q="Comedy"&offset=25&limit=25 => this will return next 25 ad IDs for the same search query.
(Think about offset and limit are automatically populated by UI)
These two queries will stay in the cache as separate entries. Whenver the same search query is requested, the same result will be delivered.
Question comes when the result of search query will be changed in the cache in case it has been accessed all the time; in other words LRU hasn't discarded it for a long time.
To cover this scenario, I'd add TTL (Time to Live) feature as well to the above solution that I provided earlier. A single TTL can be used globally or TTL per search query entry. Let's think about using global TTL. Let's say we want our customers to see new ads that are added to system right away. We can keep created time per search query entry in the cache and after certain TTL we can easily invalidate the search result and remove it from the cache. [removeEldestEntry is good place to do this] When the same search query is requested again, the new result of the query will be populated into cache and it will be used for the period of next TTL.
Implementation of LRU (least recently used) cache
package cache;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public final class LRUCache {
private final Map<String, List<Long>> map;
private final int capacity;
private final float loadFactor = 0.75f;
public LRUCache(int capacity) {
this.capacity = capacity;
map = Collections
.synchronizedMap(new LinkedHashMap<String, List<Long>>(
this.capacity, loadFactor, true) {
private static final long serialVersionUID = 1L;
@Override
protected boolean removeEldestEntry(
Map.Entry<String, List<Long>> eldest) {
return size() > capacity;
}
});
}
public List<Long> get(String key) {
return map.get(key);
}
public void put(String key, List<Long> value) {
map.put(key, value);
}
public void remove(String key) {
map.remove(key);
}
public Collection<Map.Entry<String, List<Long>>> getValues() {
return map.entrySet();
}
}
Just kept the size of cache small for the simplicity. But over time, there would be more readers then writers to the cache. If we have multiple readers to read the cache at the same time (as long as allowed by locking process), then the performance of cache would increase. Therefore, we can either choose to use ConcurrentHashMap (lock-striping) or ReentrantReadWriteLock as coded below.
package cache;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;
public final class EfficientLRUCache {
private final Map<String, List<Long>> map;
private final int capacity;
private final float loadFactor = 0.75f;
private final ReadWriteLock lock = new ReentrantReadWriteLock();
private final Lock readLock = lock.readLock();
private final Lock writeLock = lock.writeLock();
public EfficientLRUCache(int capacity) {
this.capacity = capacity;
map = new LinkedHashMap<String, List<Long>>(
this.capacity, loadFactor, true) {
private static final long serialVersionUID = 1L;
@Override
protected boolean removeEldestEntry(
Map.Entry<String, List<Long>> eldest) {
return size() > capacity;
}
};
}
public List<Long> get(String key) {
readLock.lock();
try {
return map.get(key);
} finally {
readLock.unlock();
}
}
public void put(String key, List<Long> value) {
writeLock.lock();
try {
map.put(key, value);
} finally {
writeLock.unlock();
}
}
public void remove(String key) {
writeLock.lock();
try {
map.remove(key);
} finally {
writeLock.unlock();
}
}
public Collection<Map.Entry<String, List<Long>>> getValues() {
readLock.lock();
try {
return map.entrySet();
} finally {
readLock.unlock();
}
}
}
However, if we choose to use ConcurrentHashMap, we lose LRU capacility that comes handly with LinkedHashMap.
- Hope September 26, 2014package binarytree;
import java.util.ArrayDeque;
import java.util.Deque;
import org.junit.Assert;
import org.junit.Test;
public class BinaryTreeHeightNonRecursive {
/**
* Calculates height for binary tree using stack
*
* @param root
* the root node of binary tree
* @return height of tree
*/
public int height(Node<Integer> root) {
if (root == null)
return 0;
Deque<NodeWrapper<Integer>> stack = new ArrayDeque<>();
int height = 0;
NodeWrapper<Integer> wrapper = new NodeWrapper<>(root, height);
stack.push(wrapper);
while (!stack.isEmpty()) {
NodeWrapper<Integer> current = stack.pop();
if (height < current.height) {
height = current.height;
}
Node<Integer> left = current.node.left;
if (left != null) {
wrapper = new NodeWrapper<>(left, current.height + 1);
stack.push(wrapper);
}
Node<Integer> right = current.node.right;
if (right != null) {
wrapper = new NodeWrapper<>(right, current.height + 1);
stack.push(wrapper);
}
}
return height;
}
@Test
public void testHeight() {
Node<Integer> node = new Node<>(10);
node.left = new Node<>(8);
node.right = new Node<>(13);
node.left.left = new Node<>(5);
node.left.right = new Node<>(9);
node.right.right = new Node<>(17);
node.right.right.right = new Node<>(19);
int height = height(node);
Assert.assertEquals(3, height);
}
/**
* Wrapper class for Node to keep height
*
* @param <T>
*/
public class NodeWrapper<T> {
Node<T> node;
int height;
public NodeWrapper(Node<T> node, int height) {
this.node = node;
this.height = height;
}
}
/**
* Wrapper class for BTreeNode to keep height
*
* @param <T>
*/
public class BTreeNodeWrapper<T> {
BTreeNode<T> node;
int height;
public BTreeNodeWrapper(BTreeNode<T> node, int height) {
this.node = node;
this.height = height;
}
}
/**
* Calculates height for n-ary tree using stack
*
* BTree is used for an example
*
* @param root
* the root node of BTree
* @return height of tree
*/
public int height(BTreeNode<Integer> root) {
if (root == null)
return 0;
Deque<BTreeNodeWrapper<Integer>> stack = new ArrayDeque<>();
int height = 0;
BTreeNodeWrapper<Integer> wrapper = new BTreeNodeWrapper<>(root, height);
stack.push(wrapper);
while (!stack.isEmpty()) {
BTreeNodeWrapper<Integer> current = stack.pop();
if (height < current.height) {
height = current.height;
}
BTreeNode<Integer>[] children = current.node.children;
for (int i = 0; i < children.length; i++) {
if (children[i] != null) {
wrapper = new BTreeNodeWrapper<>(children[i],
current.height + 1);
stack.push(wrapper);
}
}
}
return height;
}
@Test
public void testHeightBTree() {
BTreeNode<Integer> node = new BTreeNode<>(3, false);
node.keys = new Integer[] { 10 };
node.children[0] = new BTreeNode<>(3, false);
node.children[0].keys = new Integer[] { 5 };
node.children[2] = new BTreeNode<>(3, false);
node.children[2].keys = new Integer[] { 13 };
node.children[0].children[2] = new BTreeNode<>(3, true);
node.children[0].children[2].keys = new Integer[] { 9 };
node.children[2].children[2] = new BTreeNode<>(3, false);
node.children[2].children[2].keys = new Integer[] { 17 };
node.children[2].children[2].children[2] = new BTreeNode<>(3, true);
node.children[2].children[2].children[2].keys = new Integer[] { 19 };
int height = height(node);
Assert.assertEquals(3, height);
}
}
package binarytree;
public class Node<T> {
T value;
Node<T> left;
Node<T> right;
public Node(T value, Node<T> left, Node<T> right) {
this.value = value;
this.left = left;
this.right = right;
}
public Node(T value) {
this(value, null, null);
}
public String toString() {
return "[Node:[value: " + this.value + "]]";
}
}
package binarytree;
import java.lang.reflect.Array;
public class BTreeNode<T> {
T[] keys;
BTreeNode<T>[] children;
int t; // number of keys
boolean isLeaf;
@SuppressWarnings("unchecked")
public BTreeNode(int t, boolean isLeaf){
this.t = t;
this.isLeaf = isLeaf;
keys = (T[])Array.newInstance(Object.class, 2*t -1);
children = new BTreeNode[2*t];
}
}
package queue;
import java.util.LinkedList;
import java.util.Queue;
import org.junit.Assert;
import org.junit.Test;
public class StackWithQueue<T> {
Queue<T> queue1;
Queue<T> queue2;
public StackWithQueue() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
// retrive all elements from queue1 except last one
// retrieved elements are stored in queue2
public T pop() {
T result = null;
while (queue1.size() > 1) {
queue2.offer(queue1.poll());
}
result = queue1.poll();
// swap two queues so that next push can add elements in order
Queue<T> temp = queue1;
queue1 = queue2;
queue2 = temp;
return result;
}
// push items to queue1 first
public void push(T value) {
queue1.offer(value);
}
}
package queue;
import org.junit.Assert;
import org.junit.Test;
public class StackWithQueueTest {
@Test
public void testStack() {
int[] arr = {1, 2, 3, 4};
StackWithQueue<Integer> stack = new StackWithQueue<>();
for (int i=0; i<arr.length; i++) {
stack.push(arr[i]);
}
Assert.assertEquals(4, stack.pop().intValue());
stack.push(5);
Assert.assertEquals(5, stack.pop().intValue());
Assert.assertEquals(3, stack.pop().intValue());
Assert.assertEquals(2, stack.pop().intValue());
Assert.assertEquals(1, stack.pop().intValue());
}
}
Regarding the second part of question:
public boolean isValidSequence(int[] a) {
int i = 0;
int j = 1;
int value = 0, repeat = 0, current = 0;
while (i < a.length && j < a.length) {
value = a[i];
repeat = a[j];
current = a[++j];
while (repeat > 0) {
if (value != current) {
return false;
}
value = a[++i];
repeat--;
}
j++;
}
return true;
}
Repjoyjerraj, Android test engineer at ASAPInfosystemsPvtLtd
I am a sales manager .I'm responsible for leading and coaching a team of salespeople. A sales manager's ...
RepSydneyLevy, Area Sales Manager at 247quickbookshelp
I am a highway patrol officerIn the highway patrol is the part of the police force within a particular state ...
RepJe suis Kirsten. Je travaille dans un magasin en tant que responsables de la chaîne d'approvisionnement pour promouvoir la ...
RepNatalieLutz, Applications Developer at Absolute Softech Ltd
Pitch trending story topics and continually look for ways to push breaking and/or viral stories forward with new angles ...
Repalinehchavez, SHOT 1500 NIGHT 5000 Call girls in Munirka Metro 9711794795 at Apple
Hi, I am Aline From New York USA. I am working as a Real estate rental agent in an Energy ...
Repgradyjvierra, Animator at Alliance Global Servies
Je suis Grady de Phoenix USA. Je travaille en tant que technicien de laboratoire clinique dans la société Samuels Men ...
Repethelynfrose, Computer Scientist at 247quickbookshelp
Hello, I am Ethelyn and I live in Lake Worth, USA. I am working as a Dog Trainer and Dog ...
Repritahmixon, Analyst at ADP
Hi, I am a physiotherapy to help people handle everyday problems. I also assist peoples who have issues caused by ...
Replisachndi, Backend Developer at Adjetter Media Network Pvt Ltd.
I am the manager of health services. I work in managing medical and health services in hospitals, community health institutions ...
- Hope December 27, 2014