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;
}

inheritance
December 03, 2013 The solution to this question is present in Cracking The Coding Interviews fifth edition, in the last chapter. The solution does not require preprocessing 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;
}

inheritance
November 23, 2013 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;
}

inheritance
November 23, 2013 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;
}

inheritance
February 11, 2013 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;
}

inheritance
February 11, 2013 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];
}

inheritance
January 25, 2013 @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

inheritance
January 23, 2013 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();
}
}
}

inheritance
January 19, 2013 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;

inheritance
January 19, 2013 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, 2013Open Chat in New Window
 inheritance December 14, 2013