geeks for geeks links

16 Wednesday Apr 2014

Posted by Abhijit Gaikwad in Uncategorized

Implement Iterator class with peek() functionality in Java.

02 Sunday Feb 2014

Posted by Abhijit Gaikwad in Uncategorized

≈ Leave a comment

import java.util.Iterator;

import java.util.NoSuchElementException;

/**

* Implement a peeking iterator. This can be used to peek at values

* in the underlying iterator before iterating over them.

* Methods expected to be implemented:

* public class PeekIterator<T> implements Iterator<T> {

* public PeekIterator(Iterator<T> iterator) {…}

* public boolean hasNext() {…}

* public T next() {…}

* }

public class PeekIterator<T> implements Iterator<T> {

private final Iterator<T> iterator;

private T nextitem;

public PeekIterator(Iterator<T> iterator) {

this.iterator = iterator;

}

@Override

public boolean hasNext() {

if (nextitem != null) {

return true;

}

if (iterator.hasNext()) {

nextitem = iterator.next();

}

return nextitem != null;

}

@Override

public T next() {

if (!hasNext()) {

throw (new NoSuchElementException(“Iterator has no elements left.”));

}

T toReturn = nextitem;

nextitem = null;

return toReturn;

}

public T peek() {

if (!hasNext()) {

throw (new NoSuchElementException(“Iterator has no elements left.”));

}

return nextitem;

}

@Override

public void remove() {

throw new UnsupportedOperationException();

}

Word break

02 Sunday Feb 2014

Posted by Abhijit Gaikwad in Uncategorized

≈ Leave a comment

Map<String, String> memoized;

String SegmentString(String input, Set<String> dict) {
if (dict.contains(input)) return input;
if (memoized.containsKey(input) {
return memoized.get(input);
}
int len = input.length();
for (int i = 1; i < len; i++) {
String prefix = input.substring(0, i);
if (dict.contains(prefix)) {
String suffix = input.substring(i, len);
String segSuffix = SegmentString(suffix, dict);
if (segSuffix != null) {
memoized.put(input, prefix + " " + segSuffix);
return prefix + " " + segSuffix;

}
}
memoized.put(input, null);
return null;
}

Print all Possible Paths tree

09 Saturday Nov 2013

Posted by Abhijit Gaikwad in Uncategorized

≈ Leave a comment

void printPathsRecur(struct node* node, int path[], int pathLen)

{

if (node==NULL) return;

/* append this node to the path array */

path[pathLen] = node->data;

pathLen++;

/* it's a leaf, so print the path that led to here */

if (node->left==NULL && node->right==NULL)

{

printArray(path, pathLen);

}

else

{

/* otherwise try both subtrees */

printPathsRecur(node->left, path, pathLen);

printPathsRecur(node->right, path, pathLen);

}

Image

sorting algorithm time complexity

06 Wednesday Nov 2013

Posted by Abhijit Gaikwad | Filed under Uncategorized

≈ Leave a comment

Longest Compound Word

06 Wednesday Nov 2013

Posted by Abhijit Gaikwad in Uncategorized

≈ Leave a comment

Thanks to http://www.ardendertat.com/2012/06/15/programming-interview-questions-28-longest-compound-word/

Let’s illustrate the process with an example, the first word is cat and we add it to the trie. Since it doesn’t have a prefix, we continue. Second word is cats, we add it to the trie and check whether it has a prefix, and yes it does, the word cat. So we append the pair <’cats’, ‘s’> to the queue, which is the current word and the suffix. The third word is catsdogcats, we again insert it to the trie and see that it has 2 prefixes, cat and cats. So we add 2 pairs <’catsdogcats’, ‘sdogcats’> and <’catsdogcats’, ‘dogcats’> where the former suffix correspond to the prefix cat and the latter to cats. We continue like this by adding <’catxdogcatsrat’, ‘xdogcatsrat’> to the queue and so on. And here’s the trie formed by adding example the words in the problem definition:

After building the trie and the queue, then we start processing the queue by popping a pair from the beginning. As explained above, the pair contains the original word and the suffix we want to validate. We check whether the suffix is a valid or compound word. If it’s a valid word and the original word is the longest up to now, we store the result. Otherwise we discard the pair. The suffix may be a compound word itself, so we check if the it has any prefixes. If it does, then we apply the above procedure by adding the original word and the new suffix to the queue. If the suffix of the original popped pair is neither a valid word nor has a prefix, we simply discard that pair.

An example will clarify the procedure, let’s check the pair <’catsdogcats’, ‘dogcats’> popped from the queue. Dogcats is not a valid word, so we check whether it has a prefix. Dog is a prefix, and cats is the new suffix. So we add the pair <’catsdogcats’, ‘cats’> to the queue. Next time we pop this pair we’ll see that cats is a valid word and finish processing the word catsdogcats. As you can see, the suffix will get shorter and shorter at each iteration, and at some point the pair will either be discarded or stored as the longest word. And as the pairs are being discarded, the length of the queue will decrease and the algorithm will gradually come to an end. Here’s the complete algorithm:

– See more at: http://www.ardendertat.com/2012/06/15/programming-interview-questions-28-longest-compound-word/#sthash.Yr3tigRg.dpuf

private boolean isCompoundWord(String word) {

if (dictionary.contains(word)) return true;

for (int i = 1; i < word.length(); i++) {

String prefix = word.substring(0, i);

if (isCompoundWord(prefix)) {

String remainder = word.substring(i, word.length());

if (remainder.length() == 0) return true;

return isCompoundWord(remainder);

}

return false;

}

https://github.com/welshamy/longest-compound-word-finder/blob/master/CompoundWordFinder.java

All possible subsets of a set or powerset

06 Wednesday Nov 2013

Posted by Abhijit Gaikwad in Uncategorized

≈ Leave a comment

public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {
    Set<Set<T>> sets = new HashSet<Set<T>>();
    if (originalSet.isEmpty()) {
    	sets.add(new HashSet<T>());
    	return sets;
    }
    List<T> list = new ArrayList<T>(originalSet);
    T head = list.get(0);
    Set<T> rest = new HashSet<T>(list.subList(1, list.size())); 
    for (Set<T> set : powerSet(rest)) {
    	Set<T> newSet = new HashSet<T>();
    	newSet.add(head);
    	newSet.addAll(set);
    	sets.add(newSet);
    	sets.add(set);
    }		
    return sets;
}

Length of LCS (longest common subsequence)

06 Wednesday Nov 2013

Posted by Abhijit Gaikwad in Uncategorized

≈ Leave a comment

Recursive

int lcs( char *X, char *Y, int m, int n )

{

   if (m == 0 || n == 0)

     return 0;

   if (X[m-1] == Y[n-1])

     return 1 + lcs(X, Y, m-1, n-1);

   else

     return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));

}

Dynamic Programming

int lcs( char *X, char *Y, int m, int n )

{

   int L[m+1][n+1];

   int i, j;

   /* Following steps build L[m+1][n+1] in bottom up fashion. Note

      that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */

   for (i=0; i<=m; i++)

   {

     for (j=0; j<=n; j++)

     {

       if (i == 0 || j == 0)

         L[i][j] = 0;

       else if (X[i-1] == Y[j-1])

         L[i][j] = L[i-1][j-1] + 1;

       else

         L[i][j] = max(L[i-1][j], L[i][j-1]);

     }

   }



   /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */

   return L[m][n];

}

Given a binary tree with parent pointers, find the right sibling of a given node(pointer to the node will be given), if it doesn’t exist return null. Do it in O(1) space and O(n) time?

06 Wednesday Nov 2013

Posted by Abhijit Gaikwad in Uncategorized

≈ Leave a comment

if (node->parent && node->parent->right) {
return node->parent->right;
} else {
return NULL;
}

Given a binary tree with parent pointers, find the right sibling of a given node(pointer to the node will be given), if it doesn’t exist return null. Do it in O(1) space and O(n) time?

Right sibling

06 Wednesday Nov 2013

Posted by Abhijit Gaikwad in Uncategorized

≈ Leave a comment

void connect(Node* p) {

if (!p) return;

if (p->leftChild)

p->leftChild->nextRight = p->rightChild;

if (p->rightChild)

p->rightChild->nextRight = (p->nextRight) ?

p->nextRight->leftChild :

NULL;

connect(p->leftChild);

connect(p->rightChild);

}

TechInterviewPrep

~ Collection of Interview Questions

geeks for geeks links

Implement Iterator class with peek() functionality in Java.

Word break

Print all Possible Paths tree

sorting algorithm time complexity

Longest Compound Word

All possible subsets of a set or powerset

Length of LCS (longest common subsequence)

Given a binary tree with parent pointers, find the right sibling of a given node(pointer to the node will be given), if it doesn’t exist return null. Do it in O(1) space and O(n) time?

Right sibling