Tech
BAN USERThe kth smallest number can easily be found if we can get a left sub-tree of a node which have k-1 elements. The smallest kth number will reside on that node only. Now using this idea you can navigate through tree to get the kth smallest node. Suppose you need to find the the 10th smallest node in tree and your root node tells you that this tree has 16 elements and right subtree (root->right->nodeCount) have 9 elements. It will means that left subtree have (16 - 9 -1) 6 elments, now you can be sure that left subtree will not 10th smallest node as total number of nodes itself that side will be 6, so you visit right sub tree. For code see Nikunj's Code.
- Tech October 07, 2011Decorates will be useful when u are trying to extend some property of object not modify, here we might need totally different implementation for these products. The answers to this question might be very specific depending on interviewers thinking, but to start with one suggest a generic class:
class Furniture<Material>{
}
Now extend this class to support product specific requirements.
- Tech October 07, 2011This should work, only issue is memory trace big. It uses a helper function pathSum which returns a list if a path exist with given sum, else null. Code is in Java.
//Get Path Sum if exist from given node
private ArrayList<Node> pathSum(Node r, int sum, ArrayList<Node> l){
ArrayList<Node> list;
if(r == null){
return null;
}
else if(r.data == sum){
list = new ArrayList<Node>(l);
list.add(r);
return l;
}else{
list =new ArrayList<Node>(l);
list.add(r);
if(pathSum(r.left, sum - r.data, list) !=null)
return list;
if(pathSum(r.left, sum -r.data, list)!=null)
return list;
else
return null;
}
}
//Check if given Path Sum exist any where in tree
private ArrayList<Node> pathSumExist(Node r, int sum, ArrayList<Node> l){
ArrayList<Node> list;
if(r == null)
return null;
else if ( (l= pathSum(r, sum, l)) != null)
return l;
else{
if ( (l= pathSum(r.left, sum, l)) != null)
return l;
if ( (l= pathSum(r.right, sum, l)) != null)
return l;
else
return null;
}
}
void Reverse(Node *header){
if(Header == null || Header ->Next == Null)
return;
Node* Last = Header;
Node* Curr = Header->Next;
//Reverse the Header Node
Header -> Next = null;
while(Curr != null){
Node* Temp = Curr -> Next;
Curr -> Next = Last;
Last = Curr;
Curr = Temp;
}
}
Using recursion this should work:
L1=LL1->value, L2=LL2->Value;
add(Header* LL1, Header* LL2, Value L1, Value L2){
if(LL1 ->Next != Null & LL2 -> Next !=Null){
L1 = L1*10+LL1->Next->Value;
L2 = L2*10+LL2->Next->Value;
add(LL1->Next, LL2->Next, L1, L2)
}
if(LL1 ->Next != Null & LL2 -> Next ==Null){
L1 = L1*10+LL1->Next->Value;
add(LL1->Next, LL2->Next, L1, L2)
}
if(LL1 ->Next == Null & LL2 -> Next !=Null){
L2 = L2*10+LL2->Next->Value;
add(*LL1, LL2->Next, L1, L2)
}
if(LL1 ->Next == Null & LL2 -> Next ==Null){
printf("Output is:",L1+L2);
exit();
}
}
I have written some code in java which works, but obviously not optimized, might interest you people:
package string;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
public class SubStringofKeywords {
/**First argument should be file name and rest of keywords
* @param args
*/
File file;
FileReader input;
String[] keywords;
boolean[] tracker;
int[] indexs;
boolean found;
int[][]kwMaps;
char[] data;
public SubStringofKeywords(String FileName, String[] keywords) throws FileNotFoundException {
this.input = new FileReader(FileName);
this.file = new File(FileName);
this.keywords = keywords;
this.tracker = new boolean[keywords.length];
this.indexs = new int[2];
this.found = false;
this.kwMaps = new int[keywords.length][2];
this.data = new char[(int) file.length()];
indexs[0]= 0;
indexs[1]=(int) file.length();
}
public boolean substringFinder() throws IOException{
BufferedReader reader = new BufferedReader(input);
char[] word = new char[20];
int keywordIndex;
int wordStartIndex=0;
reader.read(data);
for(int i=0;i<data.length;i++){
if(data[i] == ' ') {
if((keywordIndex = match(word))>=-1){
kwMaps[keywordIndex][0] = 1;
kwMaps[keywordIndex][1] = wordStartIndex;
}
if(checkCompletion());
calculatePositions();
reset(word);
wordStartIndex = i+1;
}
else add(word, data[i]);
}
if(!found)
return false;
else
return true;
}
private void calculatePositions() {
int max=0, min= (int) file.length();
for(int i=0;i<keywords.length;i++){
if(kwMaps[i][1]< min ) min = kwMaps[i][1];
if(kwMaps[i][1]> max ) max = kwMaps[i][1];
}
if((max-min)<(indexs[1]- indexs[0])){
indexs[1] = max;
indexs[0] = min;
}
}
private void reset(char[] word) {
for(int i=0;i<word.length;i++){
word[i]='\u0000';
}
}
private boolean checkCompletion() {
for(int i=0;i<keywords.length;i++){
if(kwMaps[i][0] == 0) return false;
}
return true;
}
private void add(char[] word, char c) {
int i=0;
while(word[i++]!='\u0000');
word[i]=c;
}
private int match(char[] word) {
for(int i=0;i<keywords.length;i++){
if(word.toString().equals(keywords[i]))
return i;
}
return -1;
}
private String retrieveSubstring(){
char[] subString = new char[data.length];
for(int i = indexs[0],j=0;i<=indexs[1];i++,j++)
subString[j] = data[i];
return subString.toString();
}
public static void main(String[] args) {
SubStringofKeywords test;
String[] keywords = new String[args.length -1];
for(int i=1;i<args.length;i++){
keywords[i-1] = args[i];
}
try {
test = new SubStringofKeywords(args[0], keywords);
test.substringFinder();
System.out.println(test.retrieveSubstring());
} catch (FileNotFoundException e) {
System.err.println("File Not Found");
} catch (IOException e) {
e.printStackTrace();
}
}
}
I think it is keyboard de-bouncing.
- Tech December 10, 2011