Makarand
BAN USERpackage com.home.careercup;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;
/*
50050055555555555510 base 10 =
11011110010001000101001101001111111110001100100100011100011 base 2
*/
public class NumberStreamModulo {
public static void main(String[] args) {
String stream = "11011110010001000101001101001111111110001100100100011100011";
List<Character> list = stream.chars().mapToObj(x -> Character.valueOf((char) x)).collect(Collectors.toList());
isDiv5(list.stream());
}
static void isDiv5(Stream<Character> s) {
final int[] res = new int[]{0};
final StringBuilder sb = new StringBuilder();
s.forEach(d -> {
sb.append(d);
int bv = Character.valueOf(d) - Character.valueOf('0');
res[0] = res[0] * 2 + bv;
res[0] = res[0] % 5;
System.out.printf("%s is %s divisible by 5%n", sb.toString(), res[0] == 0 ? "" : "NOT");
});
}
}
package com.home.careercup;
public class GreatJailEscape {
public static void main(String[] args) {
System.out.println(countJumps(7, 5,2,7,8,9,12,13,14,15));
System.out.println(countJumps(7, 5,2,4,4,4,4,4,4,4));
}
/*
if up (x) <= down (y) then escape is possible if all the walls are of height <= up.
Also, after scaling a wall successfully - a jump may be required to jump down the wall.
This jump is not added to this count
*/
static int countJumps (int N, int up, int down, int ...walls){
if ( up <= down) {
//verify if all walls have heights <=up
for (int i = 0; i <walls.length ; i++) {
if (walls [i] > up) throw new RuntimeException("no escape");
}
return N; /* N should be same as walls.length */
}
int jumps = 0;
for (int i = 0; i <N ; i++)
jumps+=jumpcount (walls [i], up, down);
return jumps;
}
/* it my be possible to simplify the below using Math.ceil */
static int jumpcount ( int h, int up, int down){
int j;
if (h<= up) {
j= 1;
}else {
j= h / (up-down) + (h% (up-down) > 0 ? 1 :0);
}
System.out.printf("wall height=%d, up=%d, down=%d, jumps=%d %n", h, up, down, j);
return j;
}
}
package com.home.careercup;
public class Doubleton {
private Doubleton() {
}
private static int call = 0;
private static Doubleton[] instances = new Doubleton[]{
new Doubleton(), new Doubleton()
};
public static Doubleton getInstance() {
return instances[call++ % 2];
}
public static void main(String[] args) {
Doubleton d1 = Doubleton.getInstance();
Doubleton d2 = Doubleton.getInstance();
for (int i=0;i<10;i++){
if ( i%2 ==0)
System.out.println(d1 == Doubleton.getInstance());
else
System.out.println(d2 == Doubleton.getInstance());
}
}
}
/*
Mix all Ei and Si
Sort this Mix (ascending)
now scan this sorted E/S list
Let visitors=0
for every E encountered: visitors +=1
for every S encountered: visitors -=1
If there is a pair (consecutive <E,S> with the same time stamp, you can drop this tuple ).The visitor count is going to remain the same
Now you have a timeline tagged with #visitors on site and
for any time T in the query, you can read out the visitor value
*/
package com.home.careercup;
public class DecodeCFNString {
public static void main(String[] args) throws Exception {
String in = "9_r4_brbrbr_3b2rb_b2r2br_r2b3rb";
char[][] result = decode(in);
for (char[] s : result) {
System.out.println(s);
}
}
static char[][] decode(String cfn) throws Exception {
char[][] result = new char[6][7];
char[] code = cfn.toCharArray();
StringBuilder sb = new StringBuilder();
int expand = 0;
for (char c : code) {
if (expand > 0) {
for (; expand > 0; expand--)
sb.append(c);
continue;
}
switch (c) {
case 'r':
sb.append(c);
break;
case 'b':
sb.append(c);
break;
case '_':
sb.append(c);
break;
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
case '0':
expand = (int) c - '0';
break;
default:
throw new Exception("invalid cfn string, found char " + c);
}
}
// now we need to end up with a 7*6 length char string
if (sb.toString().length() != 7 * 6) throw new Exception("invalid cf string");
final String rs = sb.toString();
for (int i = 0, start = 0, end = 7; end <= 42; i++, start = end, end += 7) {
result[i] = rs.substring(start, end).toCharArray();
}
for (char[] s : result) {
validate(s);
}
return result;
}
private static void validate(char[] s) {
//TODO:
//throw exception if the validation does NOT succeed
// for example there may be a digit that is placed
// such that the number of spaces to its right does
// not justify its value
return;
}
}
/*
I was tempted to try paper and pencil calculations on these records
I got a slightly different answer than what is suggested here.
*/
// c->b : 132, 827, 585 (1544)
// b->w : 751
// w->c : 877, 548 (1425)
// c->w : 157, 904 (1061)
// b->c : 976
// w->b : 872
// becomes
// c->b : 568
// w->b : 121
// w->c : 364
// reduced to
// w->c : 485
// c->b : 689
// reduced to
// c ->b: 204
// so chase pays bofa 204 ?? is this correct ?
package com.home.careercup;
import java.util.*;
/**
* N lines ( vertically and horizontally) can form a N -1 x N -1 grid.
* <p>
* Also, using combinatorics we know how many squares are there in a
* M-1 x N-1 grid.
* it is sum ( M-1 x N-1 + M-2 x N-2 + .. +1 x1 )
* But, I did not find any way (formula) to determine number of squares destroyed
* (of various sizes) when sides/segments in (inside) the grid are destroyed
* <p>
* Edges are stored using a flyweight pattern
*
* @version 1.0
*/
public class MatchStickProblemSolver {
public static void main(String[] args) {
final int N = 4, M = 4;
MatchStickProblemSolver solver = new MatchStickProblemSolver();
List<Square> squares = solver.gridFill(new int[]{0, 0}, M, N);
System.out.println(squares);
int totalSquares = squares.size();
int totalSides /*edges*/ = Edge.edgeCount();
System.out.println("total edges created=" + totalSides);
System.out.println("total squares created=" + totalSquares);
Edge[] remove = new Edge[]{
Edge.of(new int[]{1, 0}, new int[]{1, 1}), // h 2,1
Edge.of(new int[]{2, 0}, new int[]{2, 1}), // h 3,1
Edge.of(new int[]{1, 1}, new int[]{2, 1}), // v 2,2
Edge.of(new int[]{2, 1}, new int[]{3, 1}), // v 2,3
};
int squaresDestroyed = 0;
for (Square s : squares) {
for (Edge e : remove) {
if (s.containsEdge(e)) {
squaresDestroyed++;
System.out.printf("Removal of Edge %s dissolves %s%n", e, s);
break; // important
}
}
}
System.out.println("destroyed squares " + squaresDestroyed);
int remainingSquares = totalSquares - squaresDestroyed;
System.out.println("Squares remaining " + remainingSquares);
/*
** sample output ** for input grid 3x3 ( M=N=4)
total edges created=24
total squares created=14
destroyed squares 9
Squares retained 5
*/
}
/**
* @param left co-ordinates of left top corner
* @param M number of vertical lines
* @param N number of horizontal lines
* @return all squares of all possible sizes
*/
List<Square> gridFill(int[] left, int M, int N) {
List<Square> result = new ArrayList<>();
for (int s = 1; s <= Math.min(M - 1, N - 1); s++)
for (int x = left[0]; x + s <= M - 1; x++)
for (int y = left[1]; y + s <= N - 1; y++)
result.add(Square.of(new int[]{x, y}, s));
return result;
}
static class Edge {
int[] e1;
int[] e2;
static Edge of(int[] a, int[] b) {
Edge e = new Edge();
e.e1 = a;
e.e2 = b;
cache.putIfAbsent(e, e);
return cache.get(e);
}
static int edgeCount() {
return cache.size();
}
;
private static Map<Edge, Edge> cache = new HashMap<>();
@Override /* auto generated */
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Edge)) return false;
Edge edge = (Edge) o;
if (!Arrays.equals(e1, edge.e1)) return false;
return Arrays.equals(e2, edge.e2);
}
@Override /* auto generated */
public int hashCode() {
int result = Arrays.hashCode(e1);
result = 31 * result + Arrays.hashCode(e2);
return result;
}
@Override
public String toString() {
return "E{" +
"" + Arrays.toString(e1) +
"," + Arrays.toString(e2) +
'}';
}
}
static class Square {
int[] left;
int[] right;
List<Edge> edges = new ArrayList<>();
int size;
static Square of(int[] left, int[] right) {
Square q = new Square();
q.left = left;
q.right = right;
q.size = Math.abs(left[0] - right[0]);
q.populateEdges();
return q;
}
static Square of(int left[], int size) {
return Square.of(left, new int[]{left[0] + size, left[1] + size});
}
/**
* adds all the edges that form the sides of this square shape
*/
private void populateEdges() {
if (edges.size() > 0) return; /* safety check */
int[] left = this.left;
int size = this.size;
// add horizontal segments for sides
for (int row : new int[]{left[0], left[0] + size})
for (int j = left[1]; j < left[1] + size; j++)
edges.add(Edge.of(new int[]{row, j}, new int[]{row, j + 1}));
// add vertical segments for sides
for (int col : new int[]{left[1], left[1] + size})
for (int j = left[0]; j < left[0] + size; j++)
edges.add(Edge.of(new int[]{j, col}, new int[]{j + 1, col}));
}
boolean containsEdge(Edge e) {
for (Edge f : this.edges) {
if (f.equals(e)) return true;
}
return false;
}
@Override
public String toString() {
return "Square{" +
"left=" + Arrays.toString(left) +
", right=" + Arrays.toString(right) +
", size=" + size +
", edge count=" + edges.size() +
", edges=" + edges +
"}\n";
}
}
}
// the idea is to add the push-ed item to the queue and then rotate the queue
package com.home.careercup;
import java.util.LinkedList;
import java.util.Queue;
public class StackWithQueue <T>{
private Queue <T> q = new LinkedList<>();
void push (T e) {
q.offer(e);
if (q.size() > 1){
for (int i = 0; i <q.size() -1 ; i++) {
q.offer(q.remove());
}
}
}
T pop (){
return q.isEmpty() ? null : q.remove();
}
public static void main(String[] args) {
StackWithQueue <String> stack = new StackWithQueue<>();
for (String s: new String [] {"a", "b", "c", "d"}){
stack.push(s);
}
String pop =null;
while ( null !=(pop = stack.pop())){
System.out.println(pop);
}
}
}
// insertion sort can also work well for partially sorted arrays. Below, is a technique that
// uses k -sized min heaps
/**
*
* @param a a k-sorted array, each element is at most k spaces away from its final position after sorting
* @param k value of k, k<= array size
* @return fully sorted array
*/
static int [] ksort(int[] a, int k) {
final int windowSize = k + 1;
if (a.length < windowSize) throw new IllegalArgumentException();
PriorityQueue<Integer> q = new PriorityQueue<>();
int i = 0, j = 0;
//first k + 1 items are put in heap
for (; i < windowSize; i++) q.add(a[i]);
// we extra elements from the heap and add them to sorted array
// for each item lost from the heap, one is added to the heap from the
// unsorted part of the array
for (; i < a.length; i++, j++) {
a[j] = q.poll();
q.add(a[i]);
}
// the right edge of window k+1 elements has merged with the right
// end of the array. There are no more elements to add. We delete
// elements from the heap till it is empty
while (!q.isEmpty()) {
a[j++] = q.poll();
}
return a;
}
//Re-submitting with small change in main (). Main should call findHops()
package com.home.careercup;
/**
* High performance chess apps use bit operations for determining knight attacks.
* Below is sample code snipped from some chess programming material. It demonstrates
* a flood fill algo for determining knight attacks ( and the distance between source
* and destination ). This is similar to bfs (but very fast with bit operations)
* It is possible to find the shortest paths for knights from source to dest by using
* lookup tables.
* There are 64 values of source. For each source the shortest path to each of the
* other target values (64) cam be precomputed offline and fed into code.
*/
public class KnightDistance {
public static void main(String[] args) {
// 0, left bottom corner of chess board
// 35, D5
KnightDistance kd = new KnightDistance();
int d= kd.findHops(0, 35);
System.out.println(d); // prints 3
}
// flood fill all attack position for all knights on board
// some bit magic
long attacks(long bb) {
long l1 = (bb >> 1) & 0x7f7f7f7f7f7f7f7fL;
long l2 = (bb >> 2) & 0x3f3f3f3f3f3f3f3fL;
long r1 = (bb << 1) & 0xfefefefefefefefeL;
long r2 = (bb << 2) & 0xfcfcfcfcfcfcfcfcL;
long h1 = l1 | r1;
long h2 = l2 | r2;
return (h1<<16) | (h1>>16) | (h2<<8) | (h2>>8);
}
int distance(long b1 /* source */, long b2 /* target */) {
int d = 0;
while ((b1 & b2) == 0) {
b1 = attacks(b1);
d++; // hop count increment
}
return d;
}
// utility method to translate from human readable board position
// to bit position on chess board
int findHops(int a, int b) {
return distance(1L << a, 1L << b);
}
}
package com.home.careercup;
/**
* High performance chess apps use bit operations for determining knight attacks.
* Below is sample code snipped from some chess programming material. It demonstrates
* a flood fill algo for determining knight attacks ( and the distance between source
* and destination ). This is similar to bfs (but very fast with bit operations)
* It is possible to find the shortest paths for knights from source to dest by using
* lookup tables.
* There are 64 values of source. For each source the shortest path to each of the
* other target values (64) cam be precomputed offline and fed into code.
*/
public class KnightDistance {
public static void main(String[] args) {
// 0, left bottom corner of chess board
// 35, D5
KnightDistance kd = new KnightDistance();
int d= kd.distance(0, 35);
System.out.println(d); // prints 3
}
// flood fill all attack position for all knights on board
// some bit magic
long attacks(long bb) {
long l1 = (bb >> 1) & 0x7f7f7f7f7f7f7f7fL;
long l2 = (bb >> 2) & 0x3f3f3f3f3f3f3f3fL;
long r1 = (bb << 1) & 0xfefefefefefefefeL;
long r2 = (bb << 2) & 0xfcfcfcfcfcfcfcfcL;
long h1 = l1 | r1;
long h2 = l2 | r2;
return (h1<<16) | (h1>>16) | (h2<<8) | (h2>>8);
}
int distance(long b1 /* source */, long b2 /* target */) {
int d = 0;
while ((b1 & b2) == 0) {
b1 = attacks(b1);
d++; // hop count increment
}
return d;
}
// utility method to translate from human readable board position
// to bit position on chess board
int findHops(int a, int b) {
return distance(1L << a, 1L << b);
}
}
//java 8
public class MatchPatternOnDictionary {
public static void main(String[] args) {
MatchPatternOnDictionary w= new MatchPatternOnDictionary ();
List<String> dict= Arrays.asList( new String [] {"cat", "rat", "mat", "apple", "boy", "bat"});
final String pat =".at";
Predicate<String> f = w.predicateFilter(pat);
List <String> result = dict.stream().filter(f).collect(Collectors.toList());
System.out.println(result);
System.out.println("total matches "+ result.size());
}
Predicate<String> predicateFilter (String pat) {
return (x)-> Pattern.compile(pat).matcher (x).matches ();
}
}
package com.home.careercup;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class RandomBinaryTree {
public static void main(String[] args) {
RandomBinaryTree w = new RandomBinaryTree();
Node tree = w.randomBinaryTree(9);
w.visitInOrder(tree);
/*
7[int] 5[leaf] 15[int] 8[leaf] 16[int] 3[leaf] 6[int]
1[leaf] 4[int] 0[root] 17[int] 13[leaf] 18[int] 11[leaf]
14[int] 9[leaf] 12[int] 2[leaf] 10[int]
*/
}
/** crude in-order visit impl */
private void visitInOrder(Node tree) {
if (tree == null) return;
visitInOrder(tree.left);
StringBuilder s=new StringBuilder();
if (tree.d==0){
s.append(0+"[root] ");
}else if ( tree.left== null && tree.right== null){
s.append(tree.d+"[int] ");
}else {
s.append(tree.d+"[leaf] ");
}
System.out.print (s.toString());
visitInOrder(tree.right);
}
/**
* Generate binary tree with n internal nodes and n+1 leaf nodes
* <p>
* We start with a minimal tree with a root and two leaves.
* Next we choose one of the leaves and then add two branches to it
* We continue choosing leaves (randomly) and adding branches till
* we have n+1 leaf nodes
*
* @param n
* @return
*/
Node randomBinaryTree(int n) {
List<Node> nodeList = new ArrayList<>();
int nodeIndex = 0;
Node root = Node.of(nodeIndex++);
Node firstLeaf = Node.of(nodeIndex++);
Node secondLeaf = Node.of(nodeIndex++);
root.left = firstLeaf;
root.right = secondLeaf;
nodeList.add(firstLeaf);
nodeList.add(secondLeaf);
Random random = new Random();
while (nodeList.size() < n + 1) {
int nextInternalNodeIndex = random.nextInt(nodeList.size());
Node internalNode = nodeList.get(nextInternalNodeIndex);
internalNode.left = Node.of(nodeIndex++);
internalNode.right = Node.of(nodeIndex++);
nodeList.remove(nextInternalNodeIndex);
nodeList.add(internalNode.left);
nodeList.add(internalNode.right);
}
return root;
}
static class Node {
int d;
Node left, right;
static Node of(int v) {
return new Node(v);
}
Node(int v) {
this.d = v;
}
}
}
package com.home.careercup;
/**
* The problem essentially boils down to finding the lowest common ancestor (LCA)
* node. Now we need to find the number of turns on the path leading from
* one node to the LCA and then to the other node. Note, there is a possibility
* that the LCA node for a pair of nodes can be one among the pair itself
*/
import java.util.*;
/*
_______3______
/ \
___5__ ___1__
/ \ / \
6 2 0 8
/ \
7 4
*/
public class FindTurnsOnPathBetweenTwoNodes {
final Node root = Node.of(3);
public static void main(String[] args) {
FindTurnsOnPathBetweenTwoNodes g = new FindTurnsOnPathBetweenTwoNodes();
int turns = g.turns(Node.of(6), Node.of(7));
System.out.println("turns =" + turns);
}
int turns(Node a, Node b) {
List<Edge> an = findPath(root, a);
List<Edge> bn = findPath(root, b);
ListIterator<Edge> ai = an.listIterator();
ListIterator<Edge> bi = bn.listIterator();
while (ai.hasNext() && bi.hasNext()) {
Edge t1 = ai.next();
Edge t2 = bi.next();
if (t1.equals(t2)) {
ai.remove();
bi.remove();
} else {
ai.previous();
bi.previous();
break;
}
}
// construct path ( node list)
List<Node> path = new ArrayList<>();
for (int i = 0; i < an.size(); i++) {
path.add(an.get(i).start);
if (i == an.size() - 1)
path.add(an.get(i).end);
}
Collections.reverse(path);
for (int i = 1; i < bn.size(); i++) {
path.add(bn.get(i).start);
if (i == bn.size() - 1)
path.add(bn.get(i).end);
}
//print path
for (Node n : path) {
System.out.println(n.v);
}
Edge.Direction earlier = Edge.Direction.NONE;
int turns = 0;
while (ai.hasNext() || bi.hasNext()) {
Iterator<Edge> itr = ai.hasNext() ? ai : bi;
if (!itr.hasNext()) break;
Edge e = itr.next();
turns = e.d == earlier ? turns : ++turns;
earlier = e.d;
}
return --turns; /* disregard first turn */
}
// return mock paths for this example
private List<Edge> findPath(Node root, Node b) {
if (root.v == 3 && b.v == 6)
return new ArrayList<>(Arrays.asList(Edge.of(3, 5, Edge.Direction.LEFT),
Edge.of(5, 6, Edge.Direction.LEFT)));
if (root.v == 3 && b.v == 7)
return new ArrayList<>(Arrays.asList(
Edge.of(3, 5, Edge.Direction.LEFT),
Edge.of(5, 2, Edge.Direction.RIGHT),
Edge.of(2, 7, Edge.Direction.LEFT)
));
return Collections.emptyList();
}
// boiler plate Node and Edge declarations
static class Node {
Node(int v) {
this.v = v;
}
static Node of(int v) {
return new Node(v);
}
@Override
public boolean equals(Object obj) {
Node other = (Node) obj;
return this.v == other.v;
}
int v;
Node left, right;
}
static class Edge {
enum Direction {LEFT, RIGHT, NONE}
Node start, end;
Direction d;
static Edge of(int start, int end, Direction d) {
Edge e = new Edge();
e.start = Node.of(start);
e.end = Node.of(end);
e.d = d;
return e;
}
@Override
public boolean equals(Object obj) {
Edge other = (Edge) obj;
return other.start.equals(this.start) &&
other.end.equals(this.end) &&
other.d == this.d;
}
}
}
package com.home.careercup;
/*
To support age range query - parse all records and maintain age counts
in array where a [i] = c if there are c people of age i in input.
For a query with age range [q,r], we can now sum up values
a[q], a[q+1] .. a[r-1], a[r].
It is a good idea to curate the input age range before applying to the
array.
*/
public class AgeRangeQuery {
static int MAX_AGE=99;
static int[] ageData = new int[MAX_AGE +1];
public static void main(String[] args) {
Person[] persons = megaParse();
for (Person p : persons) {
if (p.age < 100) ageData[p.age]++;
}
int ranges[][] = new int[][]{
{11, 44},
{33, 55},
{71, 81},
{91, 100},
{98, 100}
};
for ( int [] range: ranges){
System.out.println(rangeCount(range [0], range [1]));
}
}
static int rangeCount(int age1, int age2) {
int low, high;
if (age1 <= age2) {
low = age1;
high = age2;
} else {
low = age2;
high = age1;
}
// finally adjust ranges
low = ( low <0) ? 0: low;
high = (high> MAX_AGE) ? MAX_AGE: high;
int result = 0;
for (int i = low; i <= high; i++) result += ageData[i];
return result;
}
private static Person[] megaParse() {
return new Person[]{
new Person(1), new Person(2), new Person(9),
new Person(11), new Person(12),
new Person(33), new Person(44),
new Person(55),
new Person(60),
new Person(71),
new Person(81),
new Person(91) //etc
};
}
static class Person {
public Person(int age) {
this.age = age;
}
String name;
int age;
// etc
}
}
import networkx as nx
""" For each tuple (a, b) in the input add nodes 'a' and 'b' and an edge
(b, a) to the directed graph. Next, do a toplogical sort on the graph
after removal of cycles ( and the edges that form the cycle)
"""
g = nx.DiGraph()
# example 1
# deps =[['master', 'ubuntu'], ['numpy', 'master'], ['tensorflow', 'numpy']]
# example 2
#deps = [ ['p', 'n'], ['n', 'p'], ['t', 'u']]
# example 3
deps = [['b', 'c'], ['c', 'd'], ['a', 'b'], ['d', 'e'], ['e', 'c'], ['f', 'g']]
for dep in deps:
g.add_edge(dep[1], dep[0])
try:
cycle = nx.find_cycle(g)
nodes = set()
for edge in cycle:
nodes = nodes | {edge[0]}
nodes = nodes | {edge[1]}
for n in nodes:
g.remove_node(n)
except:
print('error')
finally:
pass
ordering = nx.topological_sort(g)
print(ordering)
# python 3.6.x
"""
Assume a word list of length N where every word has width W
for i in [0..W-1]
- rotate each word in the list by i
- sort the list of words
- compare consecutive words in the sorted list
- assume the pair of words being compared as tuple (u, v)
- if the distance between u and v =1
- add (u,v ) as edge to a graph
let Networkx now find a shortest path from any u to any v
note: the distance between words = D when they differ in D char positions
"""
from operator import itemgetter
import networkx as nx
rotate = lambda s, t: s[len(s) - t:len(s)] + s[0:len(s) - t]
apartby1 = lambda s1, s2: 1 == len([i for i in range(len(s1)) if s1[i] != s2[i]])
g = nx.Graph()
dict = ["SAT", "PAN", "RAT", "PAT", "DAM"]
g.add_nodes_from(dict)
for t in range(3):
tdict = []
for word in dict:
tdict.append([word, rotate(word, t)])
sorted(tdict, key=itemgetter(1))
for w in tdict:
for wn in tdict[1:len(tdict)]:
if apartby1(w[1], wn[1]):
print(" edge {} -> {}".format(w[0], wn[0]))
g.add_edge(w[0], wn[0])
try:
result = nx.shortest_path(g, "SAT", "PAN")
print("path of len {} found, {}".format(len(result), result))
except:
print ("no path found")
public class HexToDecimal {
public static void main(String[] args) {
System.out.println(convertFromHex("36F9BFB3"));
}
static int convertFromHex(String str) {
char[] s = str.toUpperCase().toCharArray();
int digit, result = 0, i = (s[0] == '0') && s[1] == 'X' ? 2 : 0;
for (; i < s.length; i++) {
char c = s[i];
if (c >= '0' && c <= '9') {
digit = c - '0';
} else if (c >= 'A' && c <= 'F') {
digit = 10 + c - 'A';
} else {
throw new IllegalArgumentException("not hex");
}
try {
result =
Math.addExact(Math.multiplyExact(16, result),
digit);
} catch (Exception e) {
throw new IllegalArgumentException("overflow", e);
}
}
return result;
}
}
package com.home.careercup;
public class PrintMatrixSpirallyUsingRecursion {
/**
* Write a logic to print the elements of 2D matrix in a spiral way?
* <p>
* for eg if int[][] matrix = {{1,2,3,4}{5.6,7,8}{9, 10, 11,12}};
* The output should be 1 2 3 4 8 12 11 10 9 5 6 7
* The interviewer asked me to implement a recursive algorithm.
*
* @param args
*/
public static void main(String[] args) {
//example 1
int[][] m = new int[][]{
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
//example 2
int[][] m1 = new int[][]{
{1, 2, 3, 4, 5},
{16, 17, 18, 19, 6},
{15, 24, 25, 20, 7},
{14, 23, 22, 21, 8},
{13, 12, 11, 10, 9},
};
PrintMatrixSpirallyUsingRecursion printer = new PrintMatrixSpirallyUsingRecursion();
printer.printMatrix(m, new int[]{0, m.length - 1},
new int[]{0, m[0].length - 1}, Direction.LEFT_RIGHT);
System.out.println();
printer.printMatrix(m1, new int[]{0, m1.length - 1},
new int[]{0, m1[0].length - 1}, Direction.LEFT_RIGHT);
System.out.println();
}
enum Direction {
DEFAULT, LEFT_RIGHT, TOP_DOWN, RIGHT_LEFT, DOWN_TOP;
}
/*
Imagine a big block of soft material (rectangular).
You will take slices from this material where thickness
of slice is 1 row or 1 column
Take Ninja sword and cut off the top part from LEFT to RIGHT ( SLIIIIICE!).
Next cut slice on the right side from TOP to BOTTOM ( SLIIIIICE!)
Next cut slice from BOTTOM from RIGHT TO LEFT ( SLIIIIICE!)
Next cut slice from left side from BOTTOM to top ( SLIIIIICE!)
Repeat till there is NOTHING left
*/
void printMatrix(int[][] m, int[] rowRange, int[] colRange, Direction d) {
if (rowRange[1] - rowRange[0] < 0) return;
if (colRange[1] - colRange[0] < 0) return;
Direction next = Direction.DEFAULT;
switch (d) {
case LEFT_RIGHT:
for (int x = rowRange[0], y = colRange[0]; y <= colRange[1]; y++)
System.out.printf("%d ", m[x][y]);
rowRange[0]++;
next = Direction.TOP_DOWN;
break;
case TOP_DOWN:
for (int x = rowRange[0], y = colRange[1]; x <= rowRange[1]; x++)
System.out.printf("%d ", m[x][y]);
colRange[1]--;
next = Direction.RIGHT_LEFT;
break;
case RIGHT_LEFT:
for (int x = rowRange[1], y = colRange[1]; y >= colRange[0]; --y)
System.out.printf("%d ", m[x][y]);
rowRange[1]--;
next = Direction.DOWN_TOP;
break;
case DOWN_TOP:
for (int x = rowRange[1], y = colRange[0]; x >= rowRange[0]; --x)
System.out.printf("%d ", m[x][y]);
colRange[0]++;
next = Direction.LEFT_RIGHT;
break;
case DEFAULT:
throw new RuntimeException("invalid direction");
}
printMatrix(m, rowRange, colRange, next);
}
}
Scan text and for each word store in a list the positions it was found. Sort this list for each word. Assume we need to find the distance between w and v in the original text. The problem then boils down to finding the pair (a,b) where a is from the position list for w and b is from the position list of v. The pair where the difference abs (a-b) is minimum can be easily found. (O(n log n )
- Makarand September 05, 2017