srcnaks
BAN USER 0of 0 votes
AnswersYou given and instruction called DBNZ ( Decrement and Branch if Not Zero)
 srcnaks in 
which can be used as "DBNZ X L10".
This instruction decrement X by one and checks X, if X is not zero than branches line 10,
if it is zero than continue to next instructions.
By using DBNZ instruction implement CLEAR instruction.
CLEAR can be used as "CLEAR X" which means set X to zero.
By using DBNZ and CLEAR instructions implement NEGATE instruction
NEGATE can be used as "NEGATE X Y" which means set Y to negative of X ( Y = X) Report Duplicate  Flag  PURGE
Google Software Engineer / Developer Algorithm Assembly  1of 3 votes
Answersdesign and implement a calculater that can calculate expressions like:
 srcnaks in 
+ 2 4
* 8 ( + 7 12)
( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 )
(PS:all items are space delimetered.)
Example answers
+ 2 4 => 2 + 4 = 6
* 8 ( + 7 12) => 8 * ( 7 + 12 ) = 152
( + 7 ( * 8 12 ) ( * 2 (+ 9 4) 7 ) 3 ) => 7+8*12+2*(9+4)*7+3 = 148 Report Duplicate  Flag  PURGE
Google Software Engineer / Developer Algorithm Data Structures Problem Solving Stacks String Manipulation Trees and Graphs  2of 2 votes
Answersthere are numbers in between 09999999999 (10digits) which are assigened someone (does not matter which number assigned who)
 srcnaks in 
Write two methods called "getNumber" and "requestNumber" as follows
Number getNumber();
boolean requestNumber(Number number);
getNumber method should find out a number that did not assigened than marks it as assiged and return that number.
requestNumber method checks the number is assigened or not. If it is assigened returns false, else marks it as assiged and return true.
design a data sturucture to keep those numbers and implement those methods Report Duplicate  Flag  PURGE
Google Software Engineer / Developer Algorithm Data Structures Hash Table
public class AirportNode{
private String name;
private ArrayList<AirportNode> from = new ArrayList<AirportNode>();
private ArrayList<AirportNode> to = new ArrayList<AirportNode>();
private int longestPath = 0;
public AirportNode(String name){
this.name = name;
}
public String Name(){
return name;
}
public int LongestPathDistance(){
return longestPath;
}
public void addFrom(AirportNode n){
from.add(n);
n.updateLongestPath(this);
}
public void addTo(AirportNode n){
to.add(n);
n.addFrom(this);
}
public void updateLongestPath(AirportNode n){
if(n.LongestPathDistance()>=longestPath){
longestPath = n.LongestPathDistance()+1;
to.remove(n);
to.add(0, n);
for(AirportNode f : from)
f.updateLongestPath(this);
}
}
public AirportNode getLongestPathNode(){
return to.size() == 0 ? null : to.get(0);
}
}
public String findPath (String [] airports){
HashMap<String,AirportNode> map = new HashMap<String,AirportNode> ();
for (int i = 0 ; airports.length  2 >= i ; i += 2){
AirportNode d = null;
if(!map.containsKey(airports[i])){
d = new AirportNode(airports[i]);
map.put(airports[i],d);
}else
d = map.get(airports[i]);
AirportNode a = null;
if(!map.containsKey(airports[i+1])){
a = new AirportNode(airports[i+1]);
map.put(airports[i+1],a);
}else
a = map.get(airports[i+1]);
d.addTo(a);
}
AirportNode n = null;
for(String d:map.keySet()){
if(n == null 
n.LongestPathDistance()<map.get(d).LongestPathDistance())
n = map.get(d);
}
StringBuilder sb = new StringBuilder ();
sb.append(n.Name()) ;
while ((n = n.getLongestPathNode()) != null) {
sb.append(">") ;
sb.append(n.Name()) ;
}
return sb.toString() ;
}

srcnaks
February 11, 2015 What if there is a airport that has path to two airport? I think ,this solution does not work!!
for example,
let the array is {1,2,3,4,1,3,5,3,2,5,2,4}
so the paths are
1>2
3>4
1>3
5>3
2>5
2>4
So, the solution should be 1>2>5>3>4
But, your algorithm is return 1>3>4
My method is based on the mathematical formula that sum of numbers in between 1 and n which is "n*(n+1)/2"
Let say N is 20
the sum of numbers less than 20 and divisible by 3 are:
3 + 6 + 9 + 12 + 15 + 18 = (1+2+3+4+5+6)*3
In this case, I can calculate the sum of numbers in between 1 and 6 by using "n*(n+1)/2". So this is equals to (6*7/2) * 3
This is the same for the sum of numbers less than 20 and divisible by 5.
5 + 10 + 15 = (1+2+3)*5 => (3*4/2)*5
As seen, we add 15 in both of operations, so we have to eliminate duplicates.
In order to do that, I calculate the same for the sum of numbers less than 20 and divisible by 15.
At the end, I add the sum of divisible by 3 and the sum of divisible by 5 than subtract the sum of divisible by 15
That's it!
Firstly, I solved it by designing O(N) algorithm but than, by the help of interviewer, I came up with a solution that solves the problem in O(1)
My final solution is as follows:
public int SumOfNumber(int N){
N;
int divisibleBy3 = N/3;
divisibleBy3 = (divisibleBy3 * (divisibleBy3 + 1) /2)*3;
int divisibleBy5 = N/5;
divisibleBy5 = (divisibleBy5 * (divisibleBy5 + 1) /2)*5;
int divisibleBy15 = N/15;
divisibleBy15 = (divisibleBy15 * (divisibleBy15 + 1) /2)*15;
return divisibleBy3 + divisibleBy5  divisibleBy15
}

srcnaks
February 02, 2015 public int NumberOfPossibleStrings(String str){
if(str == null  str.length()==0) return 0;
if(str.length()==1)return 1;
if(str.length()==2)
if(str.charAt(0)<'3'&&str.charAt(0)>'0')return 2;
else return 1;
if(str.charAt(0)=='0'str.charAt(0)>'2')
return NumberOfPossibleStrings(str.substring(1));
return NumberOfPossibleStrings(str.substring(1))+
NumberOfPossibleStrings(str.substring(2));
}

srcnaks
January 20, 2015 public static char[] eliminate(char[] arr){
if(arr == null) return arr;
int p = 1;
for(int i = 0; i<arr.length;i++){
p++;
if(p!=i)
arr[p] = arr[i];
if( arr[p] =='b')
p;
if(arr[p] == 'c' && p>0 && arr[p1] =='a')
p=2;
}
p++;
if(p<=arr.length 1)
arr[p] = '\0';
return arr;
}

srcnaks
November 30, 2014 Java implementation
public static void fill(HashMap<String, Double> map,int L,int N,double capacity){
String key = "L"+L+"N"+N;
if(!map.containsKey(key)){
map.put(key, 0.0);
}
if(map.get(key)<0.25){
double c = 0.25map.get(key);
if(capacity>=c){
capacity = capacity  c;
map.put(key, 0.25);
}else{
map.put(key, map.get(key)+capacity);
capacity = 0.0;
}
}
if(capacity>0.0){
fill(map,L+1,N,capacity/3.0);
int p = (int)(Math.log(N)/Math.log(2)) + 1;
fill(map,L+1,N+p,capacity/3.0);
fill(map,L+1,N+p+1,capacity/3.0);
}
}
public static double capacity(int B,int L,int N){
HashMap<String, Double> tower = new HashMap<String, Double>();
fill(tower,1,1,B*0.75);
return tower.containsKey("L"+L+"N"+N) ? tower.get("L"+L+"N"+N) : 0.0;
}

srcnaks
November 29, 2014 Why no body uses HashMap ??
I think it can solve this O(n).
here is my Code
class Tuple3 {
String v1;
int v2,v3;
public Tuple3(String v1,int v2, int v3){
this.v1 = v1;
this.v2 = v2;
this.v3 = v3;
}
}
class Tuple2 {
String v1;
int v2;
public Tuple2(String v1,int v2){
this.v1 = v1;
this.v2 = v2;
}
}
public Tuple2[] convert(Tuple3[] arr){
HashMap<Integer, ArrayList<Tuple2>> map =
new HashMap<Integer, ArrayList<Tuple2>>();
for(Tuple3 t3 : arr){
if(!map.containsKey(t3.v2))
map.put(t3.v2, new ArrayList<Tuple2>());
map.get(t3.v2).add(new Tuple2(t3.v1, t3.v2));
if(!map.containsKey(t3.v3))
map.put(t3.v3, new ArrayList<Tuple2>());
map.get(t3.v3).add(new Tuple2(t3.v1, t3.v3));
}
Tuple2[] narr = new Tuple2[arr.length*2];
int pos = 0;
for(int k : map.keySet())
for(Tuple2 t:map.get(k))
narr[pos++] = t;
return narr;
}
public void testConvert(){
Tuple3[] arr = new Tuple3[]{new Tuple3("a", 1, 5),
new Tuple3("b", 2, 4),
new Tuple3("c", 7, 8)};
Tuple2[] narr = convert(arr);
}

srcnaks
November 29, 2014 Why no body uses HashMap ??
I think it can solve this O(n).
here is my Code
class Tuple3 {
String v1;
int v2,v3;
public Tuple3(String v1,int v2, int v3){
this.v1 = v1;
this.v2 = v2;
this.v3 = v3;
}
}
class Tuple2 {
String v1;
int v2;
public Tuple2(String v1,int v2){
this.v1 = v1;
this.v2 = v2;
}
}
public Tuple2[] convert(Tuple3[] arr){
HashMap<Integer, ArrayList<Tuple2>> map =
new HashMap<Integer, ArrayList<Tuple2>>();
for(Tuple3 t3 : arr){
if(!map.containsKey(t3.v2))
map.put(t3.v2, new ArrayList<Tuple2>());
map.get(t3.v2).add(new Tuple2(t3.v1, t3.v2));
if(!map.containsKey(t3.v3))
map.put(t3.v3, new ArrayList<Tuple2>());
map.get(t3.v3).add(new Tuple2(t3.v1, t3.v3));
}
Tuple2[] narr = new Tuple2[arr.length*2];
int pos = 0;
for(int k : map.keySet())
for(Tuple2 t:map.get(k))
narr[pos++] = t;
return narr;
}
public void testConvert(){
Tuple3[] arr = new Tuple3[]{new Tuple3("a", 1, 5),
new Tuple3("b", 2, 4),
new Tuple3("c", 7, 8)};
Tuple2[] narr = convert(arr);
}

srcnaks
November 29, 2014 public static Byte[] hexToByteBuf(String hex){
Byte[] buf = new Byte[hex.length()%2 == 0 ? hex.length()/2:(hex.length()/2)+1];
for(int i = 0; i<hex.length(); i++){
buf[i/2] = (i%2 == 0) ? 0 : (byte) (buf[i/2]<<4);
char c = hex.charAt(i);
if(c<=57)
buf[i/2] = (byte) (buf[i/2]  c48);// "0" : 48
else
buf[i/2] = (byte) (buf[i/2]  c55);// "A" : 65
}
return buf;
}

srcnaks
November 28, 2014 Open Chat in New Window
 srcnaks March 02, 2015