arpit.gautam
BAN USER- -1of 1 vote
AnswersDave's Father wants to make chocolates for his birthday. The volume of every chocolate will be 2 cm3. Every chocolate will be cuboid in shape. He has a box of a*b*c dimensions (again a cuboid). Given an input a,b,c write a function to find out if x number of chocolates of 2cm3 volume can fill the box completely. If so, find the number of chocolates too (x).
- arpit.gautam in India| Report Duplicate | Flag | PURGE
Amazon SDE-2 Math & Computation
int sum = 0;
int count = 0;
int totaCount = 0;
private void sumNode(MyLinkList.Node n1, MyLinkList.Node n2) {
if(n1.next != null){
count++;
if(totaCount < count){
totaCount = count;
}
sumNode(n1.next, n2.next);
}
int ret = n1.val+n2.val;
sum += (ret*Math.pow(10,(totaCount-count)));
count--;
}
Basically adding from back to front node to node and multiplying every node with its decimal position before adding
so
919
935
woule be
Sum += 9+5 = 14*10^0 = 14
sum += 3+1 = 4*10^1 = 40
sum+= 18*10^2 = 1800
sum = 1854
I think moving one pointer twice at speed of other is self evident, its like two people jogging on a circular track. the faster one will eventually meet the slower one.
Finding the node where the loop begins is interesting.
Lets say fast and slow meet at point p
head-------loopbegin------------meetingPoint----------pointingtoLoopBegin
Lets say head->LoopBegin = x
loopBegin->meetingPoint = y
meetingPoint -> pointingToLoopbegin = z
distance travelled by slow node = x +y
distance travelled by faster one = x + y + z + y
so as t = d/s and t(slower) = t(faster)
(x+y)/s = (x+2y+z)/2s
solving it will give x = z;
As there are millions of entries, in memory search is out of question. SAX parsing is one way as Debasis mentioned.
Secondly in most XMLpayloads, tags are limited and they are repeated so we can safely assume #tags would be much less than # entries. We can index this file on basis of tag names. So another file is to prepared as a pre processing step in which every entry would be somewhat like this
<<tag name>> index1,index2,index3...........
These entries can further be sorted on basis of tag name so that binary search can be done for a given tag. once we reach on the record containing tag name, it is easy to search on all the mentioned indexes.
Search Time complexity would be O(log(n)*t * (string matching complexity))
n = number of tags
t = average number of indexes for a particular tag
PreProcessing complexity -
n = number of tags
O(nlog(n))
Serialize is easy just do a preorder traversal and remember to note N as null nodes. lets say a tree gives
12N4NN35NNN
on preorder traversal.
Here is code to construct tree back.
public int construct(Node parent, char[] arr,int i , boolean left){
int ret = -1;
if(i < arr.length){
if(root != null){
if(arr[i] != 'N'){
Node n = new Node(arr[i]);
if(left){
parent.left = n;
}else{
parent.right = n;
}
int j = construct(n, arr, i+1, true);
ret = construct(n, arr, j+1, false);
}else{
ret = i;
}
}else{
root = new Node(arr[i]);
int j = construct(root,arr,i+1,true);
ret = construct(root,arr,j+1,false);
}
}
return ret;
}
Sure, Count and bstNode are class members. they are initialized in constructor as
-1 and null.
Explanation -
for a node which do not have right or left child we are returning depth 1 which means that this is a binary tree of depth 1. This is the base case.
We build on this as follows
For every node which have not null children we are trying to see if binary search tree property holds for it if so, we are returning whatever count is bigger left one or the right one. (simply the depth of binary search trees rooted at left and right child)
If at any point a tree is not binary tree we are returning -1 for that node.
At any point if we encounter a bst which is greater than in depth than earlier encountered binary tree we set the class members.
Hope it helps
Lets start with reducing our problem space.
suppose there are only 5 alphabets in question here
a,b,c,d,e so it would be like
a=1
b=2
c=3
d=4
e=5
ab = 6
ac = 7
ad = 8
ae = 9.....
to find 'cde' we will do = c*5^2 + d*5^1+c - invalid combinations.(aa,ba,bb,...) etc
finding invalid combinations -
of length 2
starting with
a=1(aa)
b=2(ba,bb)
c= 3(ca,cb,cc)
d=4(da,db,dc,dd)
e =5(ea,eb,ec,ed)
-----------
length 3
a = (a-a+1)*5^(length-2)+#(b-e) invalid of length 2
b= (b-a +1)*5^(length-2)+(c-e) invalid of length 2
and so on
-----------------
length 4
a = (a-a+1)*5^(length-2)+#(b-e) in valid of length 2
---------------------------
We also need to find invalid combinations selectively like in case of cde. we need to subtract total #invalid combinations of length 2 but we need to be selective in case of length 3.
We will subtract only those invalids which start with a*, b*,ca*,cb*,cc*,cda, cdb,cdc,cdd
for question problem _map would have
{4,5,6,8,3,1,4,5,6,3,1}
4=[0,6]5=[1,7]6=[2,8]8=[3,]3=[4,9]1=[5,10]
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
public class MaxLongestOccuranceFinder {
public void find(Integer[] integers) {
populateMap(integers);
findMaxLongest(integers);
}
private void findMaxLongest(Integer[] integers) {
for(int arrIndex = 0; arrIndex < integers.length;arrIndex++){
int arrVal = integers[arrIndex];
for(int listEntry:_map.get(arrVal)){
if(listEntry > arrIndex){
int a = arrIndex, b = listEntry;
while(a < integers.length && b < integers.length){
if(integers[a] != integers[b]){
break;
}else{
a++;b++;
}
}
if(a-arrIndex > length){
length = a-arrIndex;
index = arrIndex;
}
}
}
}
}
private void populateMap(Integer[] integers) {
int index = 0;
for(Integer i:integers){
if(_map.containsKey(i)){
_map.get(i).add(index);
}else{
List<Integer> l = new LinkedList<>();
l.add(index);
_map.put(i, l);
}
index++;
}
}
Map<Integer,List<Integer>> _map = new HashMap<>();
public int index = -1;
public int length = -1;
}
We need to find continuous sub sequence. The above approach will not pass following test case
{8,3,1,4,6,4,1,2,4,7,4,5,7,4,7,8,3,1}
Answer should be {8,3,1}
X was not given. We need to find x too. Its like volume of.chocolates will.be 2 cm3 and one is free to change thier dimensions to fit in the given box.
- arpit.gautam July 08, 2015