Makarand
BAN USERpublic class TranslateBracketArrangement {
public static void main(String[] args) {
final String s1 = "[[]][]";
final String s2= "[][[]]";
System.out.println(process(s1, 0, s1.length() - 1));
System.out.println(process (s2, 0, s2.length()-1));
}
static String process(String s, int start, int end) {
System.out.printf("start =%d, end=%d %n", start, end);
List<String> result = new ArrayList<>();
// handle base case []
if (end == start + 1) return String.format("[%d,%d, null]", start, end);
// handle base case ""
if ( end <start+1) return "null";
// else we have [*] where * needs parsing
int p = start;
int left = 0, right = 0, p1 = p;
while (end >= p) {
switch (s.charAt(p)) {
case '[':
left++;
break;
case ']':
right++;
break;
}
p++;
if (left > 0 && right > 0 && (left == right)) {
String partial = String.format("[%d,%d,%s]", p1, p1 + left + right - 1, process(s, p1 + 1, p1 + left + right - 2));
result.add (partial);
left= right =0;
p1=p;
}
}
return result.toString();
}
}
/*
Not sure if there is a solution that will use no extra space strictly.
But, surely there is a trade off possible between speed and space.
For example you can scan
each row
each column
each sub-square
and check if the values are in range and are NOT repeated.
The validation step can be done using 9 units of extra memory
for the standard size soduku board ( which is 9x9)
In this type of check, each cell on the board will get
subjected to a check 1+ times ( 3 times ?)
*/
/*
I wanted to mention here how I have interpreted this problem!
Assume you have a valid binary tree. Take each node from this tree and
add these nodes to a list (array). This is the list the problem is talking about.
While the nodes are placed in this list - they still point to their
original left tree and right sub tree
The method should return TRUE if the list had nodes
from a valid binary tree
The method should return FALSE if the list had nodes from more
than one distinct binary tree ( forest )
The method should return FALSE if the list had nodes from a binary
tree that contained cycles ( not a tree in the first place)
*/
package something;
import java.util.*;
public class FindIfNodesInListAreFromABinaryTree {
public static void main(String[] args) {
System.out.println("== valid tree");
List<Node> tree = cleanTree();
boolean areTree = isValidTree(tree);
System.out.println(areTree); // will PRINT true
System.out.println("== forest ");
tree = twoTrees();
areTree = isValidTree(tree);
System.out.println(areTree); // will PRINT false
// tree with at last one node where node.left is pointing to
// some ancestor
System.out.println("== invalid tree, with cycle");
tree = cyclicTree();
areTree = isValidTree(tree);
System.out.println(areTree); // will PRINT true
}
private static boolean isValidTree(List<Node> listOfNodes) {
Objects.requireNonNull(listOfNodes);
if (listOfNodes.size() <= 1) return true;
Set<Node> roots = findRoots(listOfNodes);
if (roots.size() != 1) {
System.out.printf("No single root could be found, found %d roots %n", roots.size());
return false;
}
Node root = roots.iterator().next();
System.out.println("root is " + root.d);
Set<Integer> allNodes = new HashSet<>();
for (Node n : listOfNodes)
allNodes.add(System.identityHashCode(n));
Set<Integer> allNodesCheck = new HashSet<>();
// visit all nodes in possible tree and add to allNodesCheck
try {
saveIdentities(root, allNodes, allNodesCheck);
} catch (Exception e) {
System.out.println("Cycle detected..");
return false;
}
return allNodes.equals(allNodesCheck);
}
/**
* as you descend the tree do the following for each node
* if node is null return
* find hashCode of this Node object
* check that this hash exists in the list of all hashCodes
* check that this hash was NOT seen before
* add this to the list of seen hash codes
* recurse with left subtree
* recurse with right subtree
*
* @param root
* @param allNodes
* @param allNodesCheck
* @throws Exception
*/
private static void saveIdentities(Node root, Set<Integer> allNodes, Set<Integer> allNodesCheck) throws Exception {
if (root == null) return;
int h = System.identityHashCode(root);
if (!allNodes.contains(h)) throw new Exception("Node in tree not found in the list ");
if (allNodesCheck.contains(h)) throw new Exception("Possible loop ");
//we established that it is in the original list and it was not seen earlier
//we now add this node to allNodesCheck
allNodesCheck.add(h);
saveIdentities(root.left, allNodes, allNodesCheck);
saveIdentities(root.right, allNodes, allNodesCheck);
}
/**
* The root node is the one that is NOT pointed to by anyone else
*
* @param listOfNodes
* @return
*/
private static Set<Node> findRoots(List<Node> listOfNodes) {
Set<Node> allNodes = new HashSet<>();
allNodes.addAll(listOfNodes);
for (Node n : listOfNodes) {
allNodes.remove(n.left);
allNodes.remove(n.right);
}
System.out.println("size of remaining list that should contain root =" + allNodes.size());
return allNodes;
}
// == mostly boiler plate
private static List<Node> cyclicTree() {
Node n1 = Node.of(1);
Node n3 = Node.of(3);
Node n5 = Node.of(5);
Node n6 = Node.of(6);
Node n12 = Node.of(12);
Node n7 = Node.of(7);
List<Node> list = new ArrayList<>();
list.add(n1);
list.add(n3);
list.add(n5);
list.add(n6);
list.add(n12);
list.add(n7);
n1.left = n3;
n1.right = n5;
n3.left = n6;
n3.right = n12;
n5.left = n7;
n7.right = n3; // a node in RIGHT subtree is pointing to a node in the left subtree
return list;
}
private static List<Node> twoTrees() {
Node n2 = Node.of(2);
Node n7 = Node.of(7);
Node n5 = Node.of(5);
n2.left = n7;
n2.right = n5;
Node n11 = Node.of(11);
Node n15 = Node.of(15);
n11.left = n15;
List<Node> list = new ArrayList<>();
list.add(n2);
list.add(n7);
list.add(n5);
list.add(n11);
list.add(n15);
return list;
}
private static List<Node> cleanTree() {
Node n2 = Node.of(2);
Node n7 = Node.of(7);
Node n5 = Node.of(5);
Node n11 = Node.of(11);
Node n22 = Node.of(22);
Node n12 = Node.of(12);
Node n13 = Node.of(13);
Node n15 = Node.of(15);
List<Node> list = new ArrayList<>();
list.add(n2);
list.add(n7);
list.add(n5);
list.add(n11);
list.add(n22);
list.add(n12);
list.add(n13);
list.add(n15);
n2.left = n7;
n2.right = n5;
n7.right = n11;
n11.left = n22;
n5.left = n12;
n5.right = n13;
n13.left = n15;
return list;
}
private static class Node {
Node left, right;
int d;
public Node(int d) {
this.d = d;
}
public static Node of(int d) {
return new Node(d);
}
}
}
from itertools import combinations, chain #unlock python wealth
def powerset(arr):
return list (chain.from_iterable(combinations(arr, r) for r in range(len(arr)+1)))
def count (l):
print (l)
totals= [sum (tup) for tup in l]
print (totals)
return len ([t for t in totals if t ==0] )
a= [-1,-2,1,2,0]
print (f'total subsets for set {a} that sum to 0: {count (powerset(a))}')
"""
To make a pyramid
the first row will have 1 *
the second row will have 3 *
the third row will have 5 *
the N th row will have 1+3+5+7. (expand sequence to have N terms )
The sum or first n odd numbers is n*n
For forming a pyramid with N *s - N should be a perfect square
"""
import math
def isPyramidPossible (n):
root = int (math.sqrt(n))
return int (root) == n //root
def main(n):
print (f'A pyramid with {n} *s is {"" if isPyramidPossible(n) else "not"} possibe')
if (__name__== "__main__"):
for i in range (1, 100):
main (i)
"""
Assume array is in ascending order. First we check if the first
int in the list is >=0. If yes, then we square each element and
leave it in the result in the same order (trivial case)
Else we have negative values in the array.
Find position of the abs minimum in the list.
Square this value and move to the result.
Keep two pointers to the left and right of the min value found earlier.
We now compare the abs values of the values pointed to by these pointers
and square the smaller value and move it to the result. Keep doing this
till you exhaust the list
"""
def squareSortedIntArray(list):
result = []
if list[0] >= 0:
result = [i * i for i in list]
else:
m = list.index (min(list, key=abs))
result.append(list[m] * list[m])
low = m - 1
high = m + 1
#print (f"low={low}, high={high}")
while (low > -1 and high < len(list)):
if (abs(list[low]) < abs(list[high])):
result.append(list[low] * list[low])
low -=1
elif (abs(list[low]) == abs(list[high])):
v = list[low] * list[low]
result.append(v)
result.append(v)
low -=1
high += 1
else:
result.append(list[high] * list[high])
high += 1
# append rest of the list squared to the result
while ( low >-1):
result.append(list [low] * list [low])
low-=1
while ( high < len (list)):
result.append (list [high] * list [high])
high+=1
return result
def main():
list = [-5, -4, -3, -3, -3, -2, 0, 1, 2, 3, 4, 5, 6, 7, 8]
print(f"squared & sorted array of \n\t{list} \nis \n\t{squareSortedIntArray(list)}")
"""
Prints
[0, 1, 4, 4, 9, 9, 9, 9, 16, 16, 25, 25, 36, 49, 64]
"""
if (__name__ == '__main__'):
main()
#solution for part 1
from collections import Counter
def findSubsetWord ( s, words):
result = []
for word in words:
w= Counter (word)
c= Counter (s)
c.subtract(w)
# print (c)
if len ( [i for i in c.values () if i <0 ])==0:
result.append(word)
return result
def main ( input, words):
result = findSubsetWord(input, words)
print (f" The following words {result} are subset of {input}")
if __name__ == '__main__':
main ("ACRAT", ["A", "BAR", "CAR", "AAA" "ACA", "ART", "RAC",])
/* when processes run in parallel - their
bandwidth requirements add up */
List all start times and end times
Sort the list
Scan from left to right
maxBandwidth = 0
currentBandwidth =0
if start time
currentBandwidth += bandWidth for this interval
if ( maxBandwidth < currentBandwidth )
maxBandwidth = currentBandwidth
if end time
currentBandwidth -= bandWidth for this interval
if ( maxBandwidth < currentBandwidth )
maxBandwidth = currentBandwidth
print maxBandwidth
end
import java.util.ArrayList;
import java.util.List;
/*
Recursively descend into the tree. Pass a collector argument
that will store the sum for each level. Then find the minimum
level
*/
public class MinLevelSum {
public static void main(String[] args) {
Node n50 = new Node(50);
Node n6 = new Node(6);
Node n2 = new Node(2);
Node n30 = new Node(30);
Node n80 = new Node(80);
Node n7 = new Node(7);
//
n50.left = n6;
n50.right = n2;
n6.left = n30;
n6.right = n80;
n2.left = n7;
MinLevelSum work = new MinLevelSum();
List<Integer> list = new ArrayList<>();
work.findLevelSums(n50, 0, list);
System.out.printf("Min level= " + work.findMinLevelSum(list));
}
private static class Node {
Node left = null, right = null;
int data;
Node(int d) {
this.data = d;
}
}
void findLevelSums(Node n, int level, List<Integer> list) {
if (n == null) return;
while (list.size() - 1 < level)
list.add(0);
list.set(level, list.get(level) + n.data);
findLevelSums(n.left, level + 1, list);
findLevelSums(n.right, level + 1, list);
}
int findMinLevelSum(List<Integer> list) {
int minLevel = -1, min = Integer.MAX_VALUE;
for (int i = 0; i < list.size(); i++)
if (min > list.get(i))
minLevel = i;
return minLevel;
}
}
"""
return list of tuples with items in list that add to a sum
"""
def twoSum(list, sum):
s = set(list);
result = []
for i in list:
diff = sum - i
if diff in s:
result.append (tuple ([i, diff]) )
return result
list = [1, 2, 3, 4, 5, 6, 9]
result = twoSum(list, 9)
print(result)
import java.util.ArrayList;
import java.util.List;
/*
Check if two DOM Trees have the same text.
e.g. <html><p>hello</p></html>, <html><p><b>h</b>ello</p></html> should be the same text
DOMNode class definition (string tag, string text, bool isText, vector<DOMNode*> children)
*/
public class TextInDomTree {
static class DOMNode {
String tag;
String text;
boolean isText;
private List<DOMNode> children;
void addChild(DOMNode n) {
if (n == null) return;
if (children == null) children = new ArrayList<>();
children.add(n);
}
DOMNode(String tag, String text ) {
this.tag = tag;
this.text = text;
this.isText = text != null && text.length() >= 1;
}
}
public static void main(String[] args) {
//<html><p>hello</p></html>
{
DOMNode html = new DOMNode("html", "");
DOMNode p = new DOMNode("p", "");
p.addChild(new DOMNode("text", "hello"));
html.addChild(p);
StringBuilder sb = new StringBuilder();
getText(html, sb);
System.out.println(sb);
}
//<html><p><b>h</b>ello</p></html>
{
DOMNode html = new DOMNode("html", "");
DOMNode p = new DOMNode("p", "");
DOMNode b = new DOMNode("b", "");
DOMNode h =new DOMNode("text", "h");
b.addChild(h);
p.addChild(b);
DOMNode ello =new DOMNode("text", "ello");
p.addChild(ello);
html.addChild(p);
StringBuilder sb = new StringBuilder();
getText(html, sb);
System.out.println(sb);
}
}
/*
Traverse DOM tree and extract text
*/
private static void getText(DOMNode node, StringBuilder sb) {
if (node == null) return;
if (node.isText) {
sb.append(node.text);
return;
}
for (DOMNode n : node.children)
getText(n, sb);
}
}
/*
Here is a matrix 9 x 9 with above code
[47, 58, 69, 80, 1, 12, 23, 34, 45]
[57, 68, 79, 9, 11, 22, 33, 44, 46]
[67, 78, 8, 10, 21, 32, 43, 54, 56]
[77, 7, 18, 20, 31, 42, 53, 55, 66]
[6, 17, 19, 30, 41, 52, 63, 65, 76]
[16, 27, 29, 40, 51, 62, 64, 75, 5]
[26, 28, 39, 50, 61, 72, 74, 4, 15]
[36, 38, 49, 60, 71, 73, 3, 14, 25]
[37, 48, 59, 70, 81, 2, 13, 24, 35]
all rows and cols etc add to 369
*/
/*
For a matrix N X N where N is odd
take numbers 1.. N^2
Place 1 in the middle column of top row
Next number will go in one of the following positions
-- move up diagonally 1 place and place it here if this is empty
-- OR move 1 place down
Note: all position calculations are mod N
*/
public class MagicMatrix {
public static void main(String[] args) {
print(mm(9));
}
static int[][] mm(int N) {
if (N % 2 != 1)
throw new IllegalArgumentException("argument should be odd integer");
int result[][] = new int[N][N];
for (int p = 1, i = 0, j = N / 2; p < N * N + 1; p++) {
if (p == 1) {
//start in the middle column of top row
result[i][j] = p;
} else {
// move right and up diagonally
// and if that position is already full
// then move down
if (result[(N + i - 1) % N][(N + j + 1) % N] == 0)
result[i = (N + i - 1) % N][j = (N + j + 1) % N] = p;
else
result[i = (i + 1) % N][j] = p;
}
}
return result;
}
private static void print(int[][] mm) {
validate(mm);
for (int[] x : mm)
System.out.println(Arrays.toString(x));
}
private static void validate(int[][] mm) {
final int X = mm.length;
int[] rows = new int[X];
int[] cols = new int[X];
for (int i = 0; i < X; i++) {
rows[i] = 0;
for (int j = 0; j < X; j++) {
rows[i] += mm[i][j];
}
}
// System.out.println(Arrays.toString(rows));
for (int i = 0; i < X; i++) {
cols[i] = 0;
for (int j = 0; j < X; j++) {
cols[i] += mm[j][i];
}
}
//System.out.println(Arrays.toString(cols));
//TODO: add code for diagonals
final int tot = rows[0];
for (int i = 0; i < rows.length; i++) {
if (tot != rows[i]) throw new IllegalArgumentException("");
}
for (int i = 0; i < cols.length; i++) {
if (tot != cols[i]) throw new IllegalArgumentException("");
}
//etc
}
}
/* For each row and each column, first count number of white pixels.
Print out those pixels that have value 1 and also their rows and column
counts =1
*/
static void findLonely(int[][] pixels) {
final int ROWS = pixels.length;
final int COLS = pixels[0].length;
int[] r = new int[ROWS];
int[] c = new int[COLS];
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
if (1 == pixels[i][j]) {
r[i]++;
c[j]++;
}
}
}
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
if (pixels[i][j] == 1 && r[i] == 1 && c[j] == 1) {
System.out.printf("lonely pixel at %d %d %n", i, j);
}
}
}
}
/*
Reverse this string 1+2*3-20. Note: 20 must be retained as is.
Expected output: 20-3*2+1
*/
public class ReverseEquation {
public static void main(String[] args) {
final String input = "1+2*3-20";
System.out.println(new ReverseEquation().reverse(input));
//prints 20-3*2+1
}
String reverse(String s) {
BreakIterator b = java.text.BreakIterator.getWordInstance();
b.setText(s);
StringBuilder sb = new StringBuilder();
for (int end = b.last(), start = b.previous(); start != BreakIterator.DONE;
end = start, start = b.previous()) {
String w = s.substring(start, end);
sb.append(w);
}
return sb.toString();
}
}
/*
This has to be solved by using the flood-fill technique.
First pick a 'X' and flood fill to find all connected
X's and determine size. Call this area A1.
Next pick the next X. Before flood fill is done, check if
this X is in A1. If yes, then skip this X. If not, then
this X is in another disconnected area which has to be
determined. Call this area A2.
Now continue to the next X
In the end you have have areas A1, A2. .. An with sizes
S1, S2 .. Sn
Find max S
Please note that flood-fill will actually need to happen just
once for each disconnected area in the figure
*/
/*
store stock prices and timestamp both in a map and a priority queue to access.
changes during insertion and deletion should be cascaded to both the queue and the map
*/
public class StockPricesEtc {
public static void main(String[] args) {
/*TimeStamp - 1, 2, 3, 4, 5
Price - 12,34,4,1,18
*/
StockPricesEtc spe = new StockPricesEtc();
spe.put(1L,12);
spe.put(2L,34);
spe.put(3L,4);
spe.put(4L,1);
spe.put(5L,18);
System.out.println(spe.findStockPriceAtGivenTimeStamp(3L));
//Output - 4
System.out.println(spe.deleteAndGetMinimumStockPriceForToday());
//Output - 1
System.out.println(spe.findStockPriceAtGivenTimeStamp(2L));
//Output - 34
System.out.println(spe.deleteAndGetMinimumStockPriceForToday());
//Output - 4
}
private
Map<Long, Wrap> map = new HashMap<>();
private PriorityQueue<Wrap> min = new PriorityQueue<>((x, y) ->
{
double d = x.d-y.d;
return Math.abs (d )< 0.0001 ? 0 : (d < 0 ? -1 : +1);
});
class Wrap {
private Long t;
private Double d;
Wrap(Long t, Double d) {
this.t = t;
this.d = d;
}
}
void put(Long timestamp, double price) {
Wrap w = new Wrap(timestamp, price);
map.put(w.t, w);
min.offer(w);
}
Double findStockPriceAtGivenTimeStamp (Long t ) {
Wrap w = map.get(t);
return w == null ? -1.0: w.d;
}
Double deleteAndGetMinimumStockPriceForToday (){
Wrap w = min.poll();
if (w== null) return -1.0;
map.remove(w.t);
return w.d ;
}
}
/*
Let the rectangles R_0, R_1,..R_L-1 have areas
A_0, A_1,..., A_L-1
Now find a random number between 0 and (A_L-1) -1
This will determine the rectangle inside of which our chosen point will reside
For example if the random number falls in range [A3..A4-1] then
the point is inside R3
Let the sides or R3 be a and b ( not equal )
Let a' = random number in range [ 0 and a-1]
Let b' = random number in range [ 0 and b-1]
The co-ordinates of the point we want are (a', b')
*/
public class CycleFindingOverArray {
public static void main(String[] args) {
int [] F= {6,6,0,1,4,3,3,4,0};
System.out.println( hasCycle(F));
}
/*
F can be thought of as a function that maps values of its indices to itself
where each i, 0<=i<=F.length -1
Cycle detection can be done with Floyd's cycle finding method
*/
static boolean hasCycle(int[] F) {
final int len = F.length;
int slow, fast;
switch (len) {
case 1:
/* loop of single element */
return F[0] == 0;
case 2:
/* loop(s) with first two elements */
return F[0] == 1 && F[1] == 0 || F [0]==0 || F[1] ==1;
default:
/* a bigger loop */
slow = F[0];
fast = F[F[0]];
while (slow != fast && fast >= 0 && fast <= F.length - 1) {
slow = F[slow];
fast = F[F[fast]];
}
return slow == fast;
}
}
}
package com.home.careercup;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/*
This is NOT a solution with space complexity lesser than O(n)
I am watching to see if anyone posts a solution that is better than O(n) space
All solutions that use a map <word, index> already take up O(n) space inside
the index. Correct me if I am wrong.
*/
public class KGrepp {
final static String[] words = {"aaa", "bbb", "ccc", "booking", "alpha", "beta", "gamma"};
private static Map<String, List<Long>> wordLocator = new HashMap<>();
static {
build(words);
}
public static void main(String[] args) {
grep("beta", 2);
System.out.println("===");
grep("booking", 3);
}
static void build(String[] words) {
for (int i = 0; i < words.length; i++) {
final String w = words[i];
wordLocator.putIfAbsent(w, new ArrayList<>(2));
wordLocator.get(w).add((long) i);
}
}
static void grep(String w, int k) {
if (k > words.length - 1) return;
List<Long> locations = wordLocator.get(w);
if (locations == null || locations.size() == 0) return;
for (long loc : locations) {
for (long i = Math.max(0, loc - k); i <= loc; i++) {
System.out.println(words[(int) i]);
}
}
}
}
@prashant.tah why is time complexity of your solution O(nm) ? Is it not O(n) ?
You have a queue of size k+1. If the last word entering the queue was w then you drain and print the queue. Also, there is no mention of whether any words are repeated in the file.
package com.home.careercup;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
/*
Thread ordering. There are 4 threads ( instead of three required by the problem ).
First thread keeps printing 0
Second thread prints 1, 3, 5, ..
Third thread prints 0
Last thread will print 2,4,6,..
The synchronization will interleave the output to get the needed sequence
There is a Queue and condition variables to signal the queue condition.
First thread will act when queue size =0, drops a token into the queue.
Signals that queue size =1
Second thread waits till queue size =1 and then prints and then drops another token
into the queue. Signals to others that size = 2
Third thread waits till queue size =2 and then prints and then drops another token
into the queue. Signals to others that size = 3
Last thread waits till queue size =3 and then prints and then drops another token
into the queue. But size is now 4 and the queue is drained. Signals to others that
the queue size = 0. The first thread can now do its printing again.
Cycle continues .. ??
It should be trivial to implement something similar with 3 threads instead of 4.
*/
public class ThreadOrdering {
public static void main(String[] args) throws Exception {
Lock master = new ReentrantLock(true);
Condition c0 = master.newCondition(); // queue size =0
Condition c1 = master.newCondition();// queue size= 1
Condition c2 = master.newCondition();// queue size =2
Condition c3 = master.newCondition(); // queue size =3
new Thread(new Printer(0, 0, 0, master, c0, c1)).start();
new Thread(new Printer(1, 2, 1, master, c1, c2)).start();
new Thread(new Printer(0, 0, 2, master, c2, c3)).start();
new Thread(new Printer(2, 2, 3, master, c3, c0)).start();
/*
prints
0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0
16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 30 0
31 0 32 0 33 0 ..
*/
}
private static class Printer implements Runnable {
int start;
int inc;
int current, size;
Lock lock;
Condition[] conditions;
Printer(int start, int inc, int size, Lock lock, Condition... conditions) {
this.start = start;
this.inc = inc;
current = start;
this.lock = lock;
Queue<Integer> q = Printer.q;
this.size = size;
this.conditions = conditions;
}
//shared across all printer threads
static Deque<Integer> q = new LinkedList<>();
@Override
public void run() {
while (true) {
try {
lock.lock();
while (this.q.size() != size)
conditions[0].await();
synchronized (System.out) {
System.out.printf("%d ", current);
current += inc;
}
this.q.offer(1);
if (this.q.size() >= 4)
while (this.q.size() != 0)
this.q.remove();
conditions[1].signalAll();
} catch (Exception e) {
} finally {
lock.unlock();
}
}
}
}
}
package com.home.careercup;
public class InsertionSortForInversionCounting {
public static void main(String[] args) {
final int a [] = {3,3,3,3};
System.out.println(inversionCount(a));
}
/*
find number of positions any element moves forward during
sorting using selection sort.
This is not the most optimal.
Other faster ( O(n log (n)) methods are possible ( hint: divide and conquer)
*/
static int inversionCount(int arr[]) {
int n = arr.length;
int forwardMoves = 0;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
forwardMoves++;
}
arr[j + 1] = key;
}
return forwardMoves;
}
}
package com.home.careercup;
import java.util.Arrays;
public class CountingSortFor1MIntegers {
/**
* You are given an integer array n. Complete the function
* sortIntegers which takes as an argument, an integer array
* n of up to 1 million integers such that 1 <= n_i <= 10.
* for every element n_i in the array, and returns the sorted
* array. The sort does not need to occur in-place.
* Please do not call a standard sorting function like
* quicksort, you can do better. A sample input is
* {3, 1, 4, 1, 5, 9, 2, 6, 5} and the corresponding output is
* {1, 1, 2, 3, 4, 5, 5, 6, 9}.
* Constraints: i <= 10^9; 1 <= n_i <= 10
*
* @param args
*/
public static void main(String[] args) {
int [] sample = new int [] {3, 1, 4, 1, 5, 9, 2, 6, 5};
sort (sample);
System.out.println(Arrays.toString(sample));
}
/*
counting sort (in place)
*/
static void sort(int[] arr) {
int f[] = new int[11];
for (int i = 0; i < arr.length; i++) {
if (arr[i] <=0 || arr [i]>10)
throw new RuntimeException(String.format("array value out of range, index=%d, value=%d", i, arr [i]));
f[arr[i]]++;
}
for (int i = 1,j=0; i <f.length ; j+= f[i],i++) {
if (f[i] >0 )
Arrays.fill(arr,j, j+ f[i],i);
}
}
}
package com.home.careercup;
import java.util.Arrays;
public class SortSegments {
/*
For example, the string "AZQF013452BAB" will result in "AFQZ012345ABB".
The input letters will be uppercase and numbers will be between 0 and 9
inclusive.
*/
public static void main(String[] args) {
final String text = "AZQF013452BAB";//"a1b1c1d312mmm22dgfjdfgjdg245ui4ye96";//
StringBuilder sb = new StringBuilder();
for (int start = 0, end =breakIterator(text, start);
end !=-1;
start = end, end=end =breakIterator(text, start)) {
char [] ss= text.substring(start,end).toCharArray();
Arrays.sort(ss);
sb.append(ss);
}
System.out.println(sb.toString());
}
/**
* Launch search for next segment
*
* @param s search text string
* @param start index where to start looking for the next segment
* @return end index where the search for the segment ended
*/
static int breakIterator(String s, int start) {
if (start >= s.length()) return -1;
boolean check = Character.isDigit(s.charAt(start));
for (int i = start; i < s.length(); i++) {
if (!(check == Character.isDigit(s.charAt(i)))) {
return i;
}
}
return s.length() ;
}
}
import htsjdk.samtools.util.IntervalTree;
import java.time.LocalDate;
import java.time.format.DateTimeFormatter;
import java.util.Iterator;
import java.util.stream.Stream;
/*
Found an implementation of the interval tree (Samtools.github.io//htsjdk/) instead of implementing it!
Insert date intervals into an interval tree. Each date could be converted to a long or int
denoting number of days from the Epoch ( to simplify the problem).
You can query for the list of all intervals into which a particular day can drop using
the tree. You query with an interval where the lower range (day) and the upper range (day) are
the same.
*/
public class App {
public static void main(String[] args) {
final IntervalTree <String> tree = new IntervalTree<>();
DateTimeFormatter formatter = DateTimeFormatter.ofPattern("MM/dd/yyyy");
String [] [] dateIntervals = {
{"09/01/2016", "09/10/2016"},
{"09/11/2016", "09/13/2016"},
{"09/14/2016", "09/22/2016"},
{"09/15/2016", "09/16/2016"},
{"10/01/2016", "10/10/2016"},
{"10/11/2016", "10/12/2016"},
{"10/13/2016", "10/14/2016"},
{"10/15/2016", "10/16/2016"},
{"10/01/2016", "10/01/2017"},
{"10/02/2017", "10/12/2017"},
{"10/10/2016", "10/13/2016"},
{"10/10/2016", "10/15/2016"},
{"10/10/2016", "10/16/2016"},
{"10/10/2016", "10/18/2016"},
};
Stream.of(dateIntervals).forEach (r -> {
int dateLow = (int) LocalDate.parse(r[0], formatter).toEpochDay();
System.out.println(dateLow
);
int dateHigh = (int) LocalDate.parse(r[1], formatter).toEpochDay();
System.out.println(dateHigh);
System.out.println(dateLow + " " + dateHigh +" " + r[0]+ "~"+ r[1]);
tree.put (dateLow, dateHigh, r[0]+ "~"+ r[1]);
});
Iterator<IntervalTree.Node<String>> query = tree.overlappers(17085, 17085 );
while (query.hasNext()) {
System.out.println(query.next());
}
}
}
@Mahesh - I am not sure if the interviewer will be mighty pleased with this solution. I guess what they want three run () methods that behave between themselves using some synchronization mechanism ( and they should be able to go as fast as possible with no deadlocks). Using some kind of global state (as you did ) is also a solution - but surely not what they are looking for. Thanks
- Makarand September 08, 2017
- Makarand October 30, 2017