autoboli
BAN USER- 0of 0 votes
AnswersGiven unsigned integer 'x', write an algorithm thet returns unsigned integer 'y' such that it has the same number of bits set as 'x' and is not equal to 'x' and the distance |x-y| is minimized.
- autoboli in United States
Example:
x: 01
y: 10
Note that one bit is set and 'x' is not equal 'y'. You may assume that x is positive integer between zero and 2^32-2;| Report Duplicate | Flag | PURGE
Google - 10of 10 votes
AnswersYou are given four integers 'a', 'b', 'y' and 'x', where 'x' can only be either zero or one. Your task is as follows:
- autoboli in United States
If 'x' is zero assign value 'a' to the variable 'y', if 'x' is one assign value 'b' to the variable 'y'.
You are not allowed to use any conditional operator (including ternary operator).
Follow up: Solve the problem without utilizing arithmetic operators '+ - * /'.| Report Duplicate | Flag | PURGE
Google - 0of 2 votes
AnswersYou are given two streams 's_a' and 's_b' of digits. Each stream represents an integer 'a' and 'b' from its less significant digit to the most significant digit. For example, integer 2048 is represented in the stream as 8, 4, 0, 2.
- autoboli in United States
Write a function that subtract two integers 'a - b' and returns the result as a string. You are not allowed to buffer entire 'a' or 'b' into a single string, i.e. you may access only a single digit per stream at time (imagine that 'a' and 'b' are stored in huge files). You may assume that 'a>=b'.
Example:
s_a: 8 4 0 2
s_b: 4 2 0 1
result: '1024'| Report Duplicate | Flag | PURGE
Google - 3of 3 votes
AnswersGiven two binary numbers each represented as a string write a method that sums up the binary numbers and returns a result in the form of binary number represented as a string. You may assume that input fits in the memory and the input strings are, in general, of different length. Optimize your solution, do not use unnecessary 'if' branching.
example:sumBinary('0111101', '1101')
returns
- autoboli in United States
'1001010'| Report Duplicate | Flag | PURGE
Amazon - 4of 4 votes
AnswersYou are given an unsorted sequence of integers 'a'. Find the longest subsequence 'b' such that elements of this subsequence are strictly increasing numbers. Elements in the subsequence 'b' must appear in the same relative order as in the sequence 'a'. You may assume that 'a' can fit to the memory.
- autoboli in United States
Example:
input: a = [-1 2 100 100 101 3 4 5 -7]
output: b = [-1 2 3 4 5]| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
AnswersWarm-up question: Write a function that prints all ASCII characters. You are not allowed to use for/while loop.
- autoboli in United States| Report Duplicate | Flag | PURGE
Google - 13of 13 votes
AnswersA book contains with pages numbered from 1 - N. Imagine now that you concatenate all page numbers in the book such that you obtain a sequence of numbers which can be represented as a string. You can compute number of occurences 'k' of certain digit 'd' in this string.
- autoboli in United States
For example, let N=12, d=1, hence
s = '123456789101112' => k=5
since digit '1' occure five times in that string.
Problem: Write a method that, given a digit 'd' and number of its occurences 'k', returns a number of pages N. More precisely, return a lower and upper bound of this number N.
Example:
input: d=4, k=1;
output {4, 13} - the book has 4-14 pages
input d=4 k=0;
output {1, 3} - the book has 1-3 pages| Report Duplicate | Flag | PURGE
Google - 4of 4 votes
AnswersYou are given an array of integers 'a' that can fit in a memory. Write a method that retuns an array of the same lenght such that each element 'i' of this array is a sum of 'a' except the element a[i]. You are not allowed to use '-' operator.
- autoboli in United States| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
AnswersGiven a sorted doubly linked list, write an algorithm to convert this list into a binary search tree (BST). The BST will be used to represent a set. You may expect that client will use it to search for presence of a key in the set.
You may assume that you are given the following Node implementation that you can not exted or modify:public class Node { public Node prev, next; public int key; }
You algorithm is not allowed to create any other instance of the Node.
- autoboli in United States| Report Duplicate | Flag | PURGE
Google - 0of 0 votes
AnswersYou are given a string 's' and you are given a dictionary of english words. You goal is to write an algorithm that returns all words from the dictionary the can be formed by characters from that string 's'.
- autoboli in United States
Example:
s = "ogeg"
following words can be formed from 's': go egg ego . . .
Further it is given that string 's' always consists of four lower case characters. Lets say that the dictionary is contained in a file and can be fitted in the memory. It is up to you which data structure you use to represent the dictionary.
How would you design an efficient algorithm? Follow up: What if the dictionary file can not be fitted in the memory?| Report Duplicate | Flag | PURGE
Google - 3of 3 votes
AnswersGiven a binary search tree (BST), write a mehtod that will convert this BST into a doubly linked list that is sorted (ascending or descending order) and returns the first element in this list. You may assume you are given following Node class:
public class Node { public Node left, right; public String val; }
Example: The following BST
- autoboli in United States
G
/ \
A T
can be converted into a list
A = G = T
Do it in place! Hnce the memory complexity of your algorithm shoul be O(1).| Report Duplicate | Flag | PURGE
Google Algorithm
I would propose the following: (i) Find ranges that that overlap with the newRange (ii) merge them together one by one (iii) copy non overlapped ranges to the output and add the new merged interval.
public Range[] mergeRanges(Range[] ranges, Range newRange) {
int N = ranges.length;
/*** Detect overlaps ***/
boolean[] isover = isOverlap(ranges, newRange);
/*** Merge overlapped ranges and count the output array size ***/
int Nout = N+1;
Range newGuy = newRange;
for (int k=0; k<N; k++) {
if (isover[k] == false) continue;
Range curr = ranges[k];
newGuy = merge(newGuy, curr);
Nout--;
}
/*** Generate output ***/
Range[] out = new Range[Nout];
for (int k =0, j=0; k<N; k++)
if (isover[k] == false) out[j++] = ranges[k];
out[Nout-1] = newGuy; // don't forget the new guy
return out;
}
private Range merge(Range a, Range b) {
int x = new int[] {a.begin, b.begin};
int y = new Int[] {a.end, b.end};
int begin = Math.min(x);
int end = Math.max(y);
return new Range(begin, end);
}
private boolean[] isOverlap(Range[] a, Range x) {
int N = a.length;
boolean[] out = new boolean[N];
for (int k=0; k<N; k++) {
if (a[k].begin < x.begin && a[k].end < x.begin) out[k] = false;
else if (a[k].begin > x.end && a[k].end > x.end) out[k] = false;
else out[k] = true;
}
return out;
}
I would propose the following pseudo code:
Define number 'nIter' - number of border points you want to plot
Define your plotting accuracy 'eps'
Initialize shape list // it will contain shape border points to plot
3. Find point x0 labelled as '0' - inside, via random sampling
4. while (nIter not exceeded) {
Find point x1 labelled as '1' - outside via random sampling
Connect the points x0, x1 by a line
Compute the unit vector of this line
Perform a binary search in order to find a breakpoint x_br
such taht: isBounded(x_br) == 0 and isBounded(x_br+eps*unit vector) == 1
Add x_br to the list
x0 = x_br
}
5. Plot the shape list points on the screen.
Hope this make sense. I am looking forward for some more exciting solutions :)
- autoboli February 20, 2015The problem can be solved via brute-force O(N^2) or in optimal O(N). I am proposing the following solution:
(i) compute tow cumulative products 'cpl[]' and 'cpr[]', one form left to right, the latter one form right to left
(ii) for each position 'idx' in the array compute the product of the left and right positions in respective cumulative arrayd, hence a[idx] = cpl[idx-1]*cpr[idx+1]; If index is out of bounds ignore it;
Notice that the left cumulative product need not be computed as you can keep track of the cumulative product 'on fly' as you finally go through the array a[]. In the following code the cpl[] is used for brevity.
A sample code is shown below:
public void exclusiveProduct(int a[]) {
int N = a.length;
int[] cpl = new int[N]; % cumulative products
int[] cpr = new int[N];
// Initialize cumulative products
cpl[0] = a[0];
cpr[N-1] = a[N-1];
for (int k = 1; k<N ;k++) {
int j = N-1-k;
cpr[j] = cpl[j+1] * a[j];
cpl[k] = cpl[k-1] * a[k];
}
// Replace elements within the input array
for (int k = 0; k<N ;k++) {
int left = (k-1)>0?cpl[k-1]:1;
int right = (k+1)<N?cpr[k+1]:1;
a[k] = left*right;
}
}
I hope it works.
- autoboli February 20, 2015The porblem can be solved by implementing maxHeap for comparable objects. The sample code for heap of the fixed size is shown below:
public class MaxHeap<E extends Comparable>{
privete int N, size;
private E[] heap;
public MaxHeap(int maxSize) {
this.size = 0;
this.N = maxSize;
this.heap = (E[]) new Object[N+1];
Arrays.fill(this.heap, null);
}
public void add(E item) {
if (size == N) throw new IndexOutOfBoundsException("Heap is full");
heap[++size] = item;
swim(size);
}
public E remove() {
if (size == 0) throw new IndexOutOfBoundsException("Heap is empty");
E item = heap[1];
heap[1] = heap[size]; // replace 1st with last
heap[size--] = null; // decrement size, avoid loitering
sink(1); // sink replaced item
return item;
}
public int size() { return this.size}
public boolean isEmpty() {return this.size == 0}
private void sink(int i) {
while (2*i < size) {
int j = 2*i;
if (j <= size && less(j, j+1)) j++;
if ( less(i, j) ) swap(i, j);
else break;
i = j;
}
}
private void swim(int i) {
while (i > 1 && less(i/2, i)) {
swap(i, i/2);
i /= 2;
}
}
private boolean less (int i, int j) { return heap[i].compareTo(heap[j]) < 0; }
private void swap(int i, int j) {
E aux = heap[i];
heap[i] = heap[j];
heap[j] = aux;
}
}
Probability of getting 'k' successes of probability 'p' within 'n' events is given by binomial distribution:
(n choose k) p^k(1-p)^(n-k)
In other words, I want to observe 'k' successes and '(n-k)' not successes and I do not care about permutation in which the events come (n choose k). Now lets substitute real numbers into the formula and we get:
p_220 = 400!/(220!*180!) 0.5^220*0.5^180
Notice that there is one significant problem which is factorial. Typically everything that is bigger than 69! is overflow even for long, here we have 400!, hence unfeasible to compute unless we implement the method that does string multiplication.
What the interviewer wanted us to do? I guess the goal was to identify this problem and propose empirical approach, hence, repeat experiment many times and estimate the probability.
A sample code is shown below:
public int flipCoins(int k, int n) {
int final Ntrials = 100000;
int cnt;
for (int j=0; j<Ntrials; j++)
if (isSuccess(k, n)) cnt++;
return (int) Math.round(cnt*100.0/Ntrials);
}
private boolean isSuccess(int k, int n) {
int cnt = 0;
for (int j=0; j<n; j++)
if (Math.random()>0.5) cnt++;
return cnt == k;
}
This code gives the probability p_220/400 ~= 0.53%
- autoboli February 01, 2015Let me sketch some sample code for ASCII:
public class TrieNode {
public final TrieNode[] children = (TrieNode[]) new Object[128];
public boolean isWord = false;
}
For insertion, follow the trie by characters, if a child for some character is null, create a new node and link parent to it. If you reach the final character mark 'isWord = true' (or if you query a word return isWord at terminal node). I hope it will help.
- autoboli January 29, 2015I think it depends if you came up with valid solution without a bug. My friend who is a recruiter in Google says that what matters most is (i) how you approach the problem (chos or systematic thinking) (ii) if your code is valid solution to the problem (iii) are you able to debug on the paper and finally (iv) how elegant is your code. No one care about your CV. It is just a ticket to get into the metro :)
So as long as your solution is valid, you have a nice code without bugs and you approached the problem systematically it should be ok. Good luck!
I would answer like this: It seems that each string represents a path. If there are two paths A and B such that B is a subdirectory of A the goal is to return only A. Now, how to implement: (i) All strings (paths) can be represented as a tire. (ii) Create a set of strings 'set'. Then,for each input string, flow the trie. Now, if you find a valid string along the path in the trie stop and add this string into the 'set', proceed the next input string.
The set finally contains only desired paths.
Quite complex question, I would probably arise a conversation and answer like this: In which context you will use the decision tree? Is it a random tree in a random forest? It is also important what are your features (ordered/unordered). Lets assume that tree is already trained. At each node you have to store:
1) links to children
2) dimension of a feature to be thresholded
3) a feature threshold
4) a probability vector (how many training data get to this node for each class)
Your implementation should also support training. Given the training data, dimension of a feature and threshold you will need to compute the information gain (or entropy if you will). How many data we have (bootstraping, cross validation)....
@CT: For simple problem the 'k' is number of samples seen so far. One can compute the probability of each sample being replaced after 'k-th' sample appears. It can be proven that for each sample, the probability is equal. Now, the problem is essentially the same except that probability being sampled is driven by weight.
- autoboli January 27, 2015Build a trie from given input string array. At query time, given the input string, (i) follow the trie at the node where incomplete url string stops. Then, (ii) follow the left-most non null node and return the first complete url you find in the trie.
Note: This would work for old ASCII URLs but for new URLs that can contain unicode characters the overhead would be unfeasible. One can consider e.g. R-way trie.
If there was no weight the problem would be to sample from a stream with equal probability: Sample the first input from the stream. Given the k-th input from the stream, generate random number p=1..k, if p=1 replace the sample.
Now, the problem is that selection is no longer uniform but driven by 'weight'. One can use very similar approach: (i) cumulate the weights seen so far and (ii) decide wheather to replace based on current weight and cumulated value.
A sample code is shown below:
public int getRandom(InputStream str) {
Scanner sc = new Scanner(str);
int sum = 0, sample;
while (sc.hasNext()) {
int val = sc.nextInt();
int wgt = sc.nextInt();
if (wgt == 0 && val == 0) break;
sum += wgt;
int p = Math.random()*(double) sum;
if (p <= wgt) sample = val;
}
return sample;
}
EDIT:
As some people requested, here is a proof of the simpler problem:
The goal is to find a random sample from the stream. After receiving the k-th input, the sample will be replaced with probability 1/k with this new input. Let's compute a probability that the first input is still the selected ranodm sample after k iterations. Several consecutive events must happen: (i) The first input is selected as a sample and (ii) the sample is never replaced afterwards.
The first input is selected with probability p1 = 1/k = 1/1, the j-th input does not replace the sample with probability not_pj = (j-1)/j. Hence, the probability of the first input is a sample after k-th iteration can be written as:
p1_isSample = p1 * not_p2 * not_p3 ... * not_pk= 1/1 * 1/2 * 2/3 ... (k-1)/k = 1/k
Notice that this result holds for the second, third, and any other n-th element
pn_isSample = 1/n * n/(n+1) * (n+1)/(n+2) ... (k-1)/k = 1/k
hence, each element can be selected as the sample with equal probability of 1/k.
Q.E.D.
This proof can be now generalized to the non-uniform distribution case with weights.
I would propose the following: First stack (left stack) will start at the beginning of the array while the other one (right stack) will start at the end and will grow backwards. Throw an exception when the stacks meet each other.
A sample code is shown below:
public class DoubleStack<E>{
E[] a;
int i, j, N;
pubic DoubleStack(int N) {
this.a = (E[]) new Object[N];
this.i = 0;
this.j = N-1;
this.N = N;
}
// Left stack
public void pushLeft(E e) {
checkSpace();
a[i++] = e;
}
public E popLeft() {
if (i == 0)
throw new IndexOutOfBoundsException("Left stack is empty");
E e = a[i];
a[i--] = null; // avoid loitering
return e;
}
// Right stack
public void pushRight(E e) {
checkSpace();
a[j--] = e;
}
public E popRight() {
if (j == N-1)
throw new IndexOutOfBoundsException("Right stack is empty");
E e = a[j];
a[i++] = null; // avoid loitering
return e;
}
private void checkSpace() {
if(i == j) throw new IndexOutOfBoundsException("Stack is full")
}
}
There are two tasks to be solved: first, mark occurence of character in a substring and second, scan the whole string while tracking the maximum lenght.
(i) Assuming that the string was ASCII one can use a boolean array of the size 128 in order to mark characters present in a substring.
(ii) We can use two array indexes defining the substring, 'left' and 'right' both starting at position zero. Both indexes can only increment at the time. When 'right' index increments, the new character is added to the substring and marked as present in via boolean array. If the left index increments a character is removed from a substring and unmarked in boolean array.
(iii) The last question is how do we increment indexes. Check char at 'right' and if not present, mark it and increment 'right'. However, if char at 'right' is present, increment unmark char at 'left' and increment.
A sample code is shown below:
public int maxlenSubstring(String s) {
int N = s.length();
int maxlen = 0;
boolean[] h = new boolean[128]; // ASCII, java inits to false
for (int k = 0, i = 0, j = 0; i < N; k++) {
if (!h[s.charAt(i)]) h[s.charAt(i++)] = true;
else h[s.charAt(j++)] = false;
if(maxlen < i-j) maxlen = i-j;
}
return maxlen;
}
Assume that both arrays are integers in ascending order. A self documenting code example for array merge is given below:
public int[] merge(int[] a, int[] b) {
int N = a.length+b.length;
int [] c = new int[N];
for (int k=0, i=0, j=0; k < N; k++) {
if (i == a.length) c[k] = b[j++];
else if (j == b.length) c[k] = a[i++];
else if (a[i] > b[j]) c[k] = b[j++];
else c[k] = a[i++];
}
return c;
}
Can be used for any comparables.
- autoboli January 21, 2015Not sure about Dijkstra but I think A* should be more effective than BFS even in this simple case with equal edge weights. Well, A* is just informed version of BFS so what is happening in this case is that nodes closer to the goal node are enqueued first which avoids exploring the whole state tree. Hence, less iterations is needed even in this simple case with up/right steps. Nice thing about this problem is that admissible heuristics is straightforward, I wanted to rebrush the best first search :)
- autoboli January 19, 2015Suppose that priority function is given F(c,t), then I would answer like this: We will need four things - an array of elements 'a', a symbol table 'st' (e.g. hash map or tree map) and priority queue 'pq' and a custom mutable class Node.
Now, how to put everything together: (i) Node contains an array index 'i' and priority of an element stored at a[i]. Node is comparable, hence can be comapred with other Node via priority. (ii) The priority queue 'pq' contains these nodes, notice that node with the highest priority is alway at the head. (iii) The map 'st' contains 'key, value' pairs which are an element hash and reference to the node (or a pointer if you will).
Given new element, first check if the element is present in the chache, hence check if the key is present in the map 'st':
a) Existing element
Get corresponding Node reference from 'st' and update its priority.
b) Non-existing element
(i) Dequeue the Node with the highest priority, get index 'i', get element at a[i]
(ii) Remove key (element a[i]) from the 'st'
(iii) Replace a[i] with the new element
(iv) Add new Node with F(c,t) and 'i' into the priority queue
(v) Add element, Node pair into the symbol table 'st'
This is just a general idea but it might work. I am not going to put some code here since it would be too long and not that interesting.
I would probably propose three different solutions: (i) DFS implemented via stack, (ii) BFS adn finally (iii) A* (Best first search) implemented via priority queue. An addmissible heuristic for A* could be for instance Manhattan distance or Euclidean distance.
An eaxmple of A* is shown below:
public Iterable<Node> findPath(boolean[][] maze, int p, int q) {
int N = maze.length;
int M = maze.length[0];
minPQ<Node> q = minPQ<Node>();
p = N-1-p; // convert to top left origin
q.add(new Node(N-1, M-1, p, q, null));
// A* search
Node curr = null;
while (!q.isEmpty()) {
curr = q.remove();
if (curr.i == p && curr.j == q) // is goal
break;
for (Node n : curr.adj(maze))
q.add(n);
}
if (curr.i != p || curr.j != q) return null;
// Path reconstruction
Stack<Node> stk = new Stack<Node>();
while (curr.parent != null) {
stk.push(curr);
curr = curr.parent;
}
return stk;
}
private class Node implements Comparable<Node> {
public int i,j,m,n;
public double priority;
public Node parent;
public Node(int i, int j, int m, int n, Node p) {
this.i = i; // current position
this.j = j;
this.m = m; // goal position
this.n = n;
this.parent = p;
this.priority = Math.sqrt((i-m)*(i-m)+(j-n)*(j-n));
}
public int compaterTo(Node other) {
if (this.priority < other.priority) return -1;
if (this.priority > other.priority) return +1;
return 0;
}
public Iterable<Node> adj(boolean [][] maze) {
Stack<Node> stk = new Stack<Node>();
if (i-1 >= 0 && maze[i-1][j]) // move up
stk.push(new Node(i-1, j, m, n, this));
if (j+1 < maze[0].length && maze[i][j+1]) // move right
stk.push(new Node(i, j+1, m, n, this));
return stk;
}
}
Let assume that you are given class Graph and source vertex: (i) push the source to the stack and mark it as visited, (ii) unless stack is empty, pop the vertex, if not visited add its adjacent vertices to the stackan mark as visited.
public void dfs(Graph G, int source) {
boolean[] isVisited = boolean[G.V()];
Stack<Integer> stk = new Stack<Integer>();
stk.push(source);
isVisited[source] = true;
while (!stk.isEmpty()) {
int v = stk.pop();
for (int w : G.adjacent(v))
if (!isVisited[w]) {
isVisited[w] = true;
stk.push(w);
}
}
}
Now the question is what the interviewer wanted you to do with the dfs.
- autoboli January 19, 2015The question is if this is the only information about the string we have. Can we assume that the sequence of numbers in the string will always consist of the same number of digits? Are the numbers always positive? Is the sequence always increasing? Is the miising number always in between? If yes, then I propose the following:
(i) Given number of digits 'k' convert respective substrings of the length 'k' into integers. (ii) Check the differences in order to identify missing integer. There must be only one break point with difference equal to 2 in the string. If not, increase 'k' and go to (i).
A spample code is shown below:
public int missingNumber(String s) {
int N = s.length();
int out;
for (int k=1; k<=N/2; k++) { // we need at least 2 numbers
out = findMissing(s, k);
if (out != -1) return out;
}
return -1;
}
private int findMissing(Strings, int k) {
int N = s.length();
if (N%k != 0) return -1;
int[] a = new int[N/k];
for (int j=0; j<N; j += k)
a[j] = Integer.parseInt(s.substring(k, k+c));
int cnt = 0, out;
for (int k=0; k<a.length-1; k++)
if (a[k+1]-a[k] > 1) { // breakpoint
cnt++;
out = a[k]+1;
}
if (cnt == 1) return out;
return -1;
}
I propose the following solution: (i) in general, for a random generator 0 - N-1, you toss the coin n = ceil(log2(N)) times and concatenate the result. The result can be viewed as a random binary number. Hence you have a random generator between 0 and M= (2^n-1) (ii) Now the problem remains that it could be that N<M. In this case generate a random number x and if it is out of range, throw it away, and generate the new one until you get the right one.
A sample code is shown below:
public int randomDice() {
return random(6)+1;
}
// random generator 0 - N-1
public int random(int N) {
if (N <=1) return 0;
int n = Math.ceil(Math.log2(N));
int x;
while(true) {
x = 0;
for (int k=0; k<n; k++)
x += Math.pow(2, k)*(toss()?1:0);
if (x < N) break;
}
return x;
}
Perform DFS via reursion or stack. At each step on can either (i) use one digit or (ii) use two digits to map to char. Well not actually, be careful because two digits can be used if and only if the first digit is 1 or if the first digit is 2 and the following is 0-5.
A sample code is shown below:
public int howMany(String s) {
return howMany(s, 0);
}
private int howMany(String s, int k) {
int N = s.length();
if (k >= N) return 0;
int cnt = 1;
cnt += howMany(s, k+1);
if (k == N-1) return cnt;
char c = s.charAt(k);
char d = s.charAt(k+1);
if (c == '1' || (c == '2' && d <= '5'))
cnt += howMany(s, k+2);
return cnt;
}
* ad folats: you are right, it handles only positive integers, the code was to demonstrate the approach.
* ad C#: First, it is a java code, second, as you said, I am also comparing ASCII codes and take advantage of the fact that digit characers follows each other in a single sequence in ASCII representation. Do you agree?
Lets assume that string is represented as a sequence of ASCII chars. Hence there exist mapping char -> int. Next you know that in this preresentations characters 0-9 is a continuous sequence. Given a string, for each of its character check if it is a character between '0' and '9'.
A sample code in java is shown below:
public boolean isNumber(String s) {
for (char c : S)
if (c < '0' || c > '9') return false;
return true;
}
Not sure how it would work for Unicode but I think it should. I the number was negative, just check for char '-' at position 0.
- autoboli January 13, 2015I propose the following: (i) Perform a DFS to search the tree until we find a candidate node, such that candidate.data == roota.data. (ii) Recursivelly check if A superimpose a subtree with root candidate.
If recursion is unfeasible due to the tree depth (stack overflow) use a DFS via stack and while loop.
A sample code with recursion is shown below:
public boolean isSubset(Node a, Node b) {
if ( a== null || b == null) return false;
if (a.data == b.data) return superimpose(a, b); // candidate
return isSubset(a, b.left) || isSubset(a, b.right);
}
private boolen superimpose(Node a, Node b) {
if (a == null) return true; // whatever 'b' is return true
if (b == null) return false; // 'a' is node but 'b' is not
if (a.data != b.data) return false;
return superimpose(a.left, b.left) && superimpose(a.right, b.right);
}
This is just an idea, I hope it works.
- autoboli January 12, 2015Hey, are these your homeworks?!
Build a symbol table with KEY,VAL pairs. VAL can be a linked list of strings. When adding a new KEY,VAL pair into the symboil table, if the KEY is present, append VAL to already existing VAL.
At query time, given string s, return VAL for given KEY=s it the KEY exist, return null otherwise.
Are these your homeworks?
Build a symbol table, use lowercase string as a KEY, store a number of occurences of this string in VALUE. At query time, given a string s, convert it to a lower case, if KEY=s is in a table return corresponding VALUE, null otherwise.
The complexity of constructing a symbol table either O(N) or O(N log N) depending on implementation. Query time will be amortized O(1). A cample code is shown below:
public class Finder {
private Map<String, Integer> st;
public Finder (String[] words) {
st = new HashMap<String, Integer>();
for (String key : words) {
key = key.lowercase();
if (st.containsKey(key))
st.put(key, st.get(key)+1);
else
st.put(key, 1);
}
}
public int count(String s) {
String key = s.lowercase();
retun st.containsKey(key)?st.get(key):0;
}
}
Client will use the BST to represent a set. This probably means that the tree should be more or less ballanced in order to guarantee O(log N) for hasKey() operation. Hence, a root of the tree sould be center of the linked list.
(i) Find the center
(ii) Recursivelly convert lef and right half of the list
public Node dll2bst(Node parent) {
// Base case
if (parent == null) return null;
Node mid = findMid(parent);
Node headL = parent;
Node headR = mid.next;
mid.prev.next = null; // break the dll
// Recursion
parent.prev = dll2bst(headL);
parent.next = dll2bst(headR);
return mid;
}
public Node findMid(Node head) {
Node aux = head.next;
while (aux != null && aux.next != null) {
head = head.next;
aux = aux.next.next;
}
return head;
}
Indeed, that is true. But how would your solution be implemented? Lets say you are given a binary number 'deck' which is 157bit long. How would you decode it? I am afraid your solution may be incorrect as you need more information to be encoded.
- autoboli February 23, 2015