yankeson2013
BAN USER- 0of 0 votes
AnswersSome questions about how to write a immutable class.
- yankeson2013 in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer - 1of 1 vote
AnswersWrite code to decode strings. For example, String str = "3[a2[bd]g4[ef]h]", the output should be "abdbdgefefefefhabdbdgefefefefhabdbdgefefefefh".
My solution is as follows.
- yankeson2013 in United Statespublic class StringDecoder { public static void main(String[] args){ String s = "3[a2[bd]g4[ef]h]"; System.out.println(decode(s)); } public static String decode(String s){ if(s == null || s.length()==0) return s; int indexOfFirstNumber = findIndexOfFirstNumber(s); int indexOfFirstBracket = findIndexOfFirstBracket(s); int indexOfClosingBracket = findIndexOfClosingBracket(s, indexOfFirstBracket); if(indexOfFirstNumber == -1) return s; String subStr1 = s.substring(0, indexOfFirstNumber); String subStr2 = decode(s.substring(indexOfFirstBracket+1, indexOfClosingBracket)); String subStr3 = decode(s.substring(indexOfClosingBracket+1, s.length())); int duplicates = Integer.parseInt(s.substring(indexOfFirstNumber, indexOfFirstBracket)); StringBuilder sb = new StringBuilder(); sb.append(subStr1); while(duplicates>0){ sb.append(subStr2); duplicates--; } sb.append(subStr3); return sb.toString(); } public static int findIndexOfFirstNumber(String s){ int index = -1; for(int i=0; i<s.length(); i++){ char c = s.charAt(i); if(c>=47 && c<=58){ index = i; break; } } return index; } public static int findIndexOfFirstBracket(String s){ int index = -1; for(int i=0; i<s.length(); i++){ char c = s.charAt(i); if(c=='['){ index = i; break; } } return index; } public static int findIndexOfClosingBracket(String s, int indexOfBracket){ int index = -1; int numberOfBracket = 1; for(int i=indexOfBracket+1; i<s.length(); i++){ char c = s.charAt(i); if(c == '[') numberOfBracket++; if(c==']'){ numberOfBracket--; if(numberOfBracket==0){ index = i; break; } } } return index; } }
| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm
public class BiaryTreeValidator {
public static void main(String[] args) {
String[][] inTuples= {{"a", "b"}, {"b","c"},{"a","d"},{"c","e"}, {"e", "a"}};
Map<String, Node> map = new HashMap<>(); //create map from name to node
Set<String> children = new HashSet<>(); //create set for child nodes
boolean valid = true;
for(int i=0; i<inTuples.length; i++) {
String pName = inTuples[i][0];
String cName = inTuples[i][1];
Node pNode = map.get(pName);
if(pNode==null) {
pNode = new Node(pName);
map.put(pName, pNode);
}
Node cNode = map.get(cName);
if(cNode==null) {
cNode = new Node(cName);
map.put(cName, cNode);
}
if(pNode.getLeft()!=null && pNode.getRight()!=null) {
System.out.println(pName+" already has 2 children, so cannot add "+cName);
valid = false;
}else {
if(pNode.getLeft()!=null) {
if(pNode.getLeft().getName().equals(cName)) {
System.out.println(cName + " already exists in "+pName);
valid=false;
}else {
if(isCycled(pNode, cName)) {
System.out.println("cycled");
valid = false;
}else {
pNode.setRight(cNode);
cNode.setParent(pNode);
children.add(cName);
}
}
}else if(pNode.getRight()!=null) {
if(pNode.getRight().getName().equals(cName)) {
System.out.println(cName + " already exists in "+pName);
valid = false;
}else {
if(isCycled(pNode, cName)) {
System.out.println("cycled");
valid = false;
}else {
pNode.setLeft(cNode);
cNode.setParent(pNode);
children.add(cName);
}
}
}else {
if(isCycled(pNode, cName)) {
System.out.println("cycled");
valid = false;
}else {
pNode.setLeft(cNode);
cNode.setParent(pNode);
children.add(cName);
}
}
}
}
//remove all child nodes from map.
Iterator<String> itr1 = children.iterator();
while(itr1.hasNext()) {
String cName = itr1.next();
map.remove(cName);
}
if(map.size()>=2) {
System.out.println("Has more roots than expected.");
valid = false;
}
if(valid) {
Set<String> keys = map.keySet();
Iterator<String> itrX = keys.iterator();
while(itrX.hasNext()) {
Node root = map.get(itrX.next());
System.out.println(printNodes(root).toString());
}
}
}
static boolean isCycled(Node n, String cName) {
if(n==null) return false;
if(n.getName().equals(cName)) return true;
return isCycled(n.getParent(), cName);
}
static StringBuffer printNodes(Node root) {
StringBuffer sb = new StringBuffer();
if(root != null) {
sb.append("(").append(root.getName());
if(root.getLeft()!=null) sb.append(printNodes(root.getLeft()));
if(root.getRight()!=null) sb.append(printNodes(root.getRight()));
}
sb.append(")");
return sb;
}
static class Node{
private String name;
private Node parent;
private Node left;
private Node right;
public Node(String name) {
this.name = name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
}
1) Get the combinations of input array's indices, for example: (0, 1), (1, 2), (1, 2, 3), (0, 1, 2, 3, 4)....
2) Then multiply the elements pointed by the indices combination.
3) remove duplicates, ...
public class MultiplyAllNumbers {
public static void main(String[] args) {
int[] ip = { 1, 2, 3, 4 };
Set<Integer> origins = new HashSet<Integer>();
for(int i=0; i<ip.length; i++){
origins.add(ip[i]);
}
Set<Integer> op = new HashSet<Integer>();
int length = ip.length;
for(int i=2; i<=length; i++){
Set<Set<Integer>> set = getCombinationOfMNumbersFromN(i, length);
Iterator<Set<Integer>> itr = set.iterator();
while(itr.hasNext()){
int product = 1;
Set<Integer> subSet = itr.next();
Iterator<Integer> subItr = subSet.iterator();
while(subItr.hasNext()){
product = product*ip[subItr.next()];
}
if(!origins.contains(product)){
op.add(product);
}
}
}
System.out.println(op);
}
// get m different numbers from (0, 1, ..., (n-1)).
public static Set<Set<Integer>> getCombinationOfMNumbersFromN(int m, int n) {
Set<Set<Integer>> resultSet = new HashSet<Set<Integer>>();
getCombinationOfMNumbersFromN(m, n, 1, -1, resultSet, null);
return resultSet;
}
/**
*
* @param m
* @param n
* @param index
* is the index of element in current set, from 1 to m.
* @param preNumber
* is the previous number added to current set.
* @param resultSet
* @param currentSet
*/
private static void getCombinationOfMNumbersFromN(int m, int n, int index,
int preNumber, Set<Set<Integer>> resultSet, Set<Integer> currentSet) {
if (index == (m + 1)) {
Set<Integer> set = new HashSet<Integer>(); // Java pass object by
// reference, so need
// create a new object
// to store the data.
set.addAll(currentSet);
resultSet.add(set);
return;
}
for (int i = preNumber + 1; i < (n - m + index); i++) {
if (index == 1)
currentSet = new HashSet<Integer>();
currentSet.add(i);
getCombinationOfMNumbersFromN(m, n, index + 1, i, resultSet,
currentSet);
currentSet.remove(i);
}
}
}
public class ConvertToTree {
public static void main(String[] args){
ConvertToTree convertor = new ConvertToTree();
List<Node> nodeList = new ArrayList<Node>();
Node node4 = new Node(4, 2);
Node node5 = new Node(5, 2);
Node node2 = new Node(2, 1);
Node node6 = new Node(6, 3);
Node node7 = new Node(7, 3);
Node node3 = new Node(3, 1);
nodeList.add(node7);
nodeList.add(node3);
nodeList.add(node6);
nodeList.add(node5);
nodeList.add(node4);
nodeList.add(node2);
Map<Integer, NodeTree> map = new HashMap<Integer, NodeTree>();
for(Node node : nodeList){
int pId = node.parentId;
int cId = node.nodeId;
NodeTree nt1 = new NodeTree(pId);
NodeTree nt2 = new NodeTree(cId);
nt1.children.add(nt2);
convertor.addNodeTreeToMap(map, nt1);
}
NodeTree nt = convertor.mergeNodeTree(map);
System.out.println(nt);
}
public void addNodeTreeToMap(Map<Integer, NodeTree> map, NodeTree nt){
NodeTree nodeTree = map.get(nt.nodeId);
if(nodeTree != null){
nodeTree.children.addAll(nt.children);
}else{
Set<Integer> keys = map.keySet();
Iterator<Integer> itr = keys.iterator();
boolean added = false;
while(itr.hasNext()){
NodeTree nodeTree1 = map.get(itr.next());
NodeTree nodeTree2 = nodeTree1.findNodeById(nt.nodeId);
if(nodeTree2 != null){
nodeTree2.children.addAll(nt.children);
added = true;
break;
}
}
if(!added) map.put(nt.nodeId, nt);
}
}
public NodeTree mergeNodeTree(Map<Integer, NodeTree> map){
if(map.size()==1){
Set<Integer> keySet = map.keySet();
Integer key = keySet.iterator().next();
return map.get(key);
}
List<Integer> keys = new ArrayList<Integer>(map.keySet());
boolean[] merged = new boolean[keys.size()];
for(int i=0; i<keys.size(); i++){
if(merged[i]) continue;
for(int j=i+1; j<keys.size(); j++){
if(merged[j]) continue;
NodeTree nt1 = map.get(keys.get(i)).findNodeById(map.get(keys.get(j)).nodeId);
NodeTree nt2 = map.get(keys.get(j)).findNodeById(map.get(keys.get(i)).nodeId);
if(nt1!=null){
nt1.children.addAll(map.get(keys.get(j)).children);
merged[j] = true;
}else if(nt2!=null){
nt2.children.addAll(map.get(keys.get(i)).children);
merged[i]=true;
break;
}
}
}
for(int i=0; i<merged.length; i++){
if(merged[i] == true){
map.remove(keys.get(i));
}
}
return mergeNodeTree(map);
}
}
class NodeTree{
int nodeId;
List<NodeTree> children;
public NodeTree findNodeById(int id){
if(this.nodeId == id) return this;
if(this.children==null || this.children.size()==0) return null;
for(NodeTree tree : children){
NodeTree targetTree = tree.findNodeById(id);
if(targetTree!=null) return targetTree;
}
return null;
}
public NodeTree(int nodeId) {
this.nodeId = nodeId;
this.children = new ArrayList<NodeTree>();
}
public int getNodeId() {
return nodeId;
}
public void setNodeId(int nodeId) {
this.nodeId = nodeId;
}
public List<NodeTree> getChildren() {
return children;
}
public void setChildren(List<NodeTree> children) {
this.children = children;
}
}
class Node{
int nodeId;
int parentId;
public int getNodeId() {
return nodeId;
}
public void setNodeId(int nodeId) {
this.nodeId = nodeId;
}
public int getParentId() {
return parentId;
}
public void setParentId(int parentId) {
this.parentId = parentId;
}
public Node(int nodeId, int parentId) {
this.nodeId = nodeId;
this.parentId = parentId;
}
}
public class DivisionToEpsilon {
public static void main(String[] args){
int epsilon = 3;
double d1 = 2.223456;
double d2 = 2.1;
System.out.println(d1/d2);
DoubleWithEpsilon doubleWithEpsilon = new DoubleWithEpsilon(epsilon);
DoubleWithEpsilon result = doubleWithEpsilon.divid(d1, d2);
System.out.println(result);
}
}
class DoubleWithEpsilon{
int epsilon;
int whole;
int fraction;
public DoubleWithEpsilon(int epsilon){
this.epsilon = epsilon;
}
public DoubleWithEpsilon(int epsilon, double doubleNumber){
this.epsilon = epsilon;
if(doubleNumber<1){
this.whole=0;
}else{
this.whole = (int) doubleNumber;
}
int powerE=1;
for(int i=0; i<epsilon; i++){
powerE = powerE*10;
}
int powerE1 = powerE*10;
double tempDouble = doubleNumber-this.whole; //get the fraction from double.
int tempInt0 = (int)(tempDouble*powerE); //get the fist epsilon digits from fraction.
int tempInt1 = (int)(tempDouble*powerE1); // get the fist epsilon+1 digits from fraction.
int tempInt = tempInt1-tempInt0*10; //get last digit of tempInt1.
if(tempInt<5){ //Round fraction of original double based on tempInt
this.fraction = tempInt0;
}else{
this.fraction = tempInt0+1;
}
if(this.fraction>=powerE){
this.fraction = 0;
this.whole = this.whole+1;
}
}
public DoubleWithEpsilon divid(double d1, double d2){
DoubleWithEpsilon doubleWithEpsilon = new DoubleWithEpsilon(this.epsilon, d1/d2);
return doubleWithEpsilon;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(this.whole).append(".");
if(this.fraction<10){
sb.append("00").append(this.fraction);
}else if(this.fraction<100){
sb.append("0").append(this.fraction);
}else{
sb.append(this.fraction);
}
return sb.toString();
}
}
import java.util.Stack;
public class StringCompressor {
public static void main(String[] args){
StringCompressor compressor = new StringCompressor();
String s = "ABCBCEBCBCEBCBCEG";
String compressedStr = compressor.compress(s);
System.out.println("compressed String: "+compressedStr);
String decompressedStr = compressor.decompress(compressedStr);
System.out.println("decompressed String: "+decompressedStr);
}
public String compress(String originalString){
return compress(originalString, 1);
}
//Using recursion. Every recursion, the length of duplicate string increases by 1
//until the half length of result of last recursion.
private String compress(String originalString, int lengthOfDuplicates){
if(lengthOfDuplicates >= (originalString.length()/2+1)) return originalString;
StringBuffer sb = new StringBuffer();
String duplicateStr = originalString.substring(0, lengthOfDuplicates);
int occurence = 1;
for(int i=lengthOfDuplicates; i<=(originalString.length()-lengthOfDuplicates); i++){
String subStr = originalString.substring(i, i+lengthOfDuplicates);
if(subStr.equals(duplicateStr)){
occurence++;;
i = i+lengthOfDuplicates-1; //i points to the last index of duplicate string.
}else{
if(occurence == 1){
sb.append(duplicateStr.substring(0, 1));
duplicateStr = duplicateStr.substring(1)+originalString.charAt(i);
//i points to the last index of duplicate string.
}else{
sb.append(occurence+"["+duplicateStr+"]");
duplicateStr = subStr;
occurence = 1;
i = i+subStr.length()-1; //i points to the last index of duplicate string.
}
}
if((originalString.length()-i-1)<lengthOfDuplicates){ //test the length of remaining string.
if(occurence==1){
sb.append(duplicateStr);
}else{
sb.append(occurence+"["+duplicateStr+"]");
}
sb.append(originalString.substring(i+1));
break;
}
}
return compress(sb.toString(), lengthOfDuplicates+1);
}
public String decompress(String compressedString){
Stack<DecompressWrapper> stack = new Stack<DecompressWrapper>();
stack.add(new DecompressWrapper());
for(int i=0; i<compressedString.length(); i++){
if(isNumber(compressedString.charAt(i))){
int occurence=0;
while(isNumber(compressedString.charAt(i) )){
occurence = occurence*10+(compressedString.charAt(i)-48);
i++;
}
DecompressWrapper wrapper = new DecompressWrapper();
wrapper.setOccurence(occurence);
stack.add(wrapper);
i--;
}else if(compressedString.charAt(i)=='['){
continue;
}else if(compressedString.charAt(i)==']'){
DecompressWrapper wrapper1 = stack.pop();
DecompressWrapper wrapper2 = stack.peek();
int occ = wrapper1.getOccurence();
String dup = wrapper1.getDuplicates().toString();
while(occ>0){
wrapper2.getDuplicates().append(dup);
occ--;
}
}else{
DecompressWrapper wrapper = stack.peek();
wrapper.getDuplicates().append(compressedString.charAt(i));
}
}
return stack.pop().getDuplicates().toString();
}
private boolean isNumber(char c){
if(c>=48 && c<=57) return true;
return false;
}
private class DecompressWrapper{
private StringBuffer duplicates;
private int occurence;
public DecompressWrapper(){
this.duplicates = new StringBuffer();
}
public DecompressWrapper(StringBuffer duplicates, int occurence) {
this.duplicates = duplicates;
this.occurence = occurence;
}
public StringBuffer getDuplicates() {
return duplicates;
}
public void setDuplicates(StringBuffer duplicates) {
this.duplicates = duplicates;
}
public int getOccurence() {
return occurence;
}
public void setOccurence(int occurence) {
this.occurence = occurence;
}
}
}
My solution will give this result:
compressed String: A3[2[BC]E]G
decompressed String: ABCBCEBCBCEBCBCEG
Any optimization is welcome.
How to compress "ABCBCEBCBCEBCBCE" to "A3[2[BC]E]"?
- yankeson2013 February 09, 2017First we need find the index of the natural number in the stream. In the given example, the index of n is n-1.
/**
*
* @param initialIndex: the index of some element in the original series of natural numbers.
* @param operations: int array to hold the operation.
* @param indexOfOperation: index of the target operation.
* @param indexOfCurrentOperation: the current operation in recursive computation.
* The initial value is 0; final value is indexOfOperation;
* this value increases by 1 in each recursion.
* @return
*/
public boolean isAlive(int initialIndex, int[] operations, int indexOfTargetOperation, int indexOfCurrentOperation){
if(indexOfCurrentOperation > indexOfTargetOperation) return true;
int operation = operations[indexOfCurrentOperation];
if((initialIndex+1)%operation == 0){
System.out.println("die in operation: "+operation);
return false;
}
//index of the surviving element in new array after the operation
initialIndex = initialIndex-(initialIndex+1)/operation;
indexOfCurrentOperation++;
return isAlive(initialIndex, operations, indexOfTargetOperation, indexOfCurrentOperation);
}
public class ComputeSum {
private final char[] cArr = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
public static void main(String[] args){
ComputeSum cs = new ComputeSum();
int[] series = cs.createSeries();
for(int i=0; i<26; i++){
System.out.print(series[i]+" ");
}
System.out.println();
System.out.println(cs.sum("ABCD", series));
String shortestString = cs.createShortestString(200, series);
System.out.println(shortestString);
}
public int[] createSeries(){
int[] series = new int[26];
series[0] = 1;
for(int i=1; i<26; i++){
series[i] = series[i-1]*2+(i+1);
}
return series;
}
public int sum(String input, int[] series){
int res = 0;
for(int i=0; i<input.length(); i++){
res = res+series[input.charAt(i)-65];
}
return res;
}
public String createShortestString(int bigInt, int[]series){
StringBuffer sb = new StringBuffer();
int remain = bigInt;
for(int i=25; i>=0; i--){
if(remain < series[i]) continue;
int n = remain/series[i];
for(int j=0; j<n; j++) sb.append(cArr[i]);
remain = remain%series[i];
}
return sb.toString();
}
}
Felipe Cerqueira! The initial lists should be sorted? I have tried your code with different orders, but it failed.
- yankeson2013 February 06, 2017O(n^2)
public class ShortestSubstringWithAllAlphabets {
public static void main(String[] args){
String oStr = "aabbccba";
char[] cArr = {'a', 'b', 'c'};
String subStr=null;
int min = Integer.MAX_VALUE;
for(int i=0; i<oStr.length(); i++){
for(int j=i+cArr.length-1; j<oStr.length(); j++){
String sStr = oStr.substring(i, j+1);
if(containAll(sStr, cArr)){
if(sStr.length()<min){
subStr = sStr;
min = sStr.length();
}
break;
}
}
}
System.out.println(subStr+": "+min);
}
public static boolean containAll(String str, char[] cArr){
boolean containAll = true;
Set<Character> cSet = new HashSet<Character>();
for(int i=0; i<str.length(); i++){
cSet.add(str.charAt(i));
}
for(int j=0; j<cArr.length; j++){
if(!cSet.contains(cArr[j])) return false;
}
return containAll;
}
}
Not clear about the question. Could you please give an example?
- yankeson2013 January 23, 2017
- yankeson2013 October 17, 2018