inheritance
BAN USER- 0of 0 votes
AnswersWrite a method to validate that given Binary tree is a BST.
- inheritance in United States| Report Duplicate | Flag | PURGE
Twitter Software Engineer / Developer Algorithm
public TreeNode<Integer> kthBST(TreeNode<Integer> root, int k) {
if(root == null)
return null;
if(k < 0)
return null;
int left = size(root.left);
if(k == left + 1)
return root;
else if(k < left)
return kthBST(root.left, k);
else
return kthBST(root.right, k - left - 1);
}
private int size(TreeNode<Integer> root) {
if(root == null)
return 0;
return size(root.left) + size(root.right) + 1;
}
The solution to this question is present in Cracking The Coding Interviews fifth edition, in the last chapter. The solution does not require pre-processing step, so there is no need to create a graph of the dictionary words. Complexity is O(nm) where n = length of start word and m = length of end word.
- inheritance November 24, 2013public static int nthPrime(int n) {
if(n == 0)
return 2;
if(n == 1)
return 3;
if(n == 2)
return 5;
boolean[] a = new boolean[n*n];
a[2] = true;
int k = 0;
int i = 2;
while(i < a.length) {
if(!a[i]) {
k++;
}
if(k == n)
return i;
for(int j = 2; j <= i && j*i < a.length; j++)
a[i * j] = true;
i++;
}
return i - 1;
}
private static String findLatest(String v1, String v2) {
String[] s1 = v1.split("\\.");
String[] s2 = v2.split("\\.");
for(int i = 0; i < s1.length && i < s2.length; i++) {
if(Integer.parseInt(s1[i]) == Integer.parseInt(s2[i]))
continue;
else
return Integer.parseInt(s1[i]) > Integer.parseInt(s2[i]) ? v1 : v2;
}
if(s1.length > s2.length)
return v1;
else
return v2;
}
Class structure would look something like this:
User {
String name;
//other properties
list<Post> posts;
list<User> subscribers;
public void getAllMessageOfUser(User user) {
if(subscribers == null)
subscribers = new List<User>();
subscribers.add(user);
}
public List<User> getSubscriptionList(){
return subscribers;
}
}
Post {
String text;
User owner;
String comment;
public void postMessage(String text, User user) {
this.owner = user;
this.text = text;
for(User u : user.getSubscriptionList()) {
u.notify(user, text);
}
}
}
Here we can use Observer pattern.
- inheritance February 18, 2013private long n = 4;
private int i = 2;
public Long next() {
long j = n;
for (j = n; j < n * n; j++) {
for (int k = i; k < n; k++) {
int s = (int) (Math.log(j) / Math.log(k));
if ((Math.log(j) / Math.log(k)) == s) {
n = j + 1;
return j;
}
}
}
return n;
}
public static int[][] represent(int[] a, int cols) {
int size = a.length;
int elementsPerCol = size / cols;
int remain = size % cols;
int[][] output;
if (remain <= 0)
output = new int[elementsPerCol][cols];
else
output = new int[elementsPerCol + 1][cols];
int k = 0;
for (int i = 0; i < output[0].length; i++) {
for (int j = 0; j < output.length - 1; j++) {
if (k >= a.length)
return output;
output[j][i] = a[k];
k++;
}
if (remain > 0) {
output[output.length - 1][i] = a[k];
remain--;
k++;
}
}
return output;
}
why not 1? I'd really appreciate your help in helping me understand how this works!
- inheritance January 25, 2013public static HashSet<ArrayList<Integer>> getSequences(int n) {
@SuppressWarnings("unchecked")
HashSet<ArrayList<Integer>>[] list = (HashSet<ArrayList<Integer>>[]) new HashSet[n + 1];
for (int i = 0; i < list.length; i++) {
list[i] = new HashSet<ArrayList<Integer>>();
}
ArrayList<Integer> arr = new ArrayList<Integer>();
arr.add(0);
list[0].add(arr);
arr = new ArrayList<Integer>();
arr.add(1);
list[1].add(arr);
if (n > 1) {
arr = new ArrayList<Integer>();
arr.add(1);
arr.add(1);
list[2].add(arr);
}
if (n <= 2)
return list[n];
for (int i = 3; i <= n; i++) {
for (int j = 1; j < i; j++) {
int t = i - j;
for (ArrayList<Integer> s : list[j]) {
ArrayList<Integer> tmp = new ArrayList<Integer>(s);
tmp.add(t);
list[i].add(tmp);
}
ArrayList<Integer> tmp = new ArrayList<Integer>();
tmp.add(t);
tmp.add(j);
list[i].add(tmp);
}
}
return list[n];
}
@johny what do you mean by "add {3}"
- inheritance January 25, 2013or were you provided with f(0) by the interviewer? to create a basic matrix for the equation, f(0) is must.
- inheritance January 25, 2013@Varun
you code will not be able to check for below BT:
10
5 15
4 11 6
public class MyBlockingQueue<T> {
private Queue<T> queue;
private AtomicInteger limit = new AtomicInteger(10);
private Lock put_lock = new ReentrantLock();
private Lock take_lock = new ReentrantLock();
public MyBlockingQueue(AtomicInteger limit){
queue = new LinkedList<T>();
this.limit = limit;
}
public boolean put(T item) throws InterruptedException{
put_lock.lockInterruptibly();
try{
while(queue.size() == limit.get()){
put_lock.newCondition().await();
}
put_lock.newCondition().signal();
queue.add(item);
}finally{
put_lock.unlock();
}
return true;
}
public T take() throws InterruptedException{
take_lock.lockInterruptibly();
try{
while(queue.size() == 0){
take_lock.newCondition().await();
}
take_lock.newCondition().signal();
return queue.poll();
}finally {
take_lock.unlock();
}
}
}
What if we do below:
1. Get the number of elements in left subtree in O(log n) time
2. if n < noOfElementInLeftSubtree then recurse in left sub tree
3. if n == noOfElementsInLeftSubtree + 1 then return root
4. else it has to be in right subtree so recurse in right subtree
That's correct. I realized my mistake. Thanks for pointing it out :)
- inheritance January 19, 2013find number of elements in left and right subtree. If n lies in left subtree then recursively search for (n - noOfElementsInRightSubtree). Same for right side if n lies in right subtree. The base case would be:
if(n == noOfElementsInLeftSubtree + 1)
return root;
hi can you please share the reason behind above being a very bad code. What is wrong with that code? I too came up with a similar solution so I would like to know, where are we going wrong?
- inheritance January 19, 2013
- inheritance December 14, 2013