geeks for geeks links>


Implement Iterator class with peek() functionality in Java.

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;
public boolean hasNext() {
if (nextitem != null) {
return true;
if (iterator.hasNext()) {
nextitem =;
return nextitem != null;
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;
public void remove() {
throw new UnsupportedOperationException();

Word break

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

void printPathsRecur(struct node* node, int path[], int pathLen)
  if (node==NULL) return;
  /* append this node to the path array */
  path[pathLen] = node->data;
  /* it's a leaf, so print the path that led to here */
  if (node->left==NULL && node->right==NULL)
    printArray(path, pathLen);
  /* otherwise try both subtrees */
    printPathsRecur(node->left, path, pathLen);
    printPathsRecur(node->right, path, pathLen);

Longest Compound Word

Thanks to

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:


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;

All possible subsets of a set or powerset

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>();
    return sets;

Length of LCS (longest common subsequence)

LCS length


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);
     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;
         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?

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

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 :