Puzzles

Implement a trie

2011-08-02T04:46:00.001-07:00

1. without compaction - TRIE IMPLEMENTATION WITHOUT COMPACTION...here
2. with compaction
3. use it to implement a suffix TREE

Design an efficent structure to store an orginizational hirearchy

2011-04-02T12:10:00.000-07:00

You'll have someone starting from CEO, CTO, and multiple levels
Your data structure should be able to support the following operations efficiently

addInvididualContributor()
addManager()
deleteManager()
deleteIndividualContributor()
getEmployeeCountUnderAnEmployee()
getLeastCommonAncestorAcrossTwoEmployees()

Given a range find how many numbers occur within it

2011-03-15T00:12:00.001-07:00

You are receiving a continuous stream of numbers, at any point i'll provide a range eg: 5- 15 and the output should be the number of numbers between 5-15.

P.S. - Since the input is a stream the output can change for the same range if the function is called again.

Remove characters from String

2010-11-20T10:52:00.000-08:00

Input String = str, Character to be removed = removeArr[]

You have to do in O(n) time and if possible can you avoid any extra storage for the temporary storage

/*
    * Delete given characters from an input string
    * Approach
    * 1. Load charTodelete to delete in a hashmap
    * 2. keep two pointers -> charRead, positionToInsert
    * 3. Read input char by char and check if it's in the map above increment charToRead
    *    else increment charRead, positionToInsert and copy over the string from charRead to positionToInsert
    * 4. When charRead has reached end of string && positionToInsert < positionToInsert
    *    Remove characters
    *    string is "inder" delete i d e => nr
    */

    public String deleteCharactersFromString(String input, String[] charTodelete) {
        Map charTodeleteMap = new HashMap ();
        int charRead = 0, positionToInsert = 0;
        if (input == null || charTodelete == null)
            return null;
        char[] inputArr = input.toCharArray();
        // 1. Load charTodelete to delete in a hashmap
        for (String str: charTodelete) {
            if (str != null) {
                System.out.println("insert in map " + str.trim());
                charTodeleteMap.put(str.trim(), str.trim());
            }
        }
            //Read input char by char and check if it's in the map above increment charToRead
            //    else increment charRead, positionToInsert
            for(int j=0; j < inputArr.length; j++) {
                String ch = Character.toString(inputArr[j]);
                System.out.println("ch = " + ch);
                if (charTodeleteMap.get(ch) == null) {
                    System.out.println("Character not to be delted =" + ch + " positionToInsert = " + positionToInsert + " charRead " + charRead);
                    //delete this character from input

                    inputArr[positionToInsert] = inputArr[charRead];
                    charRead++;
                    positionToInsert++;
                }
                else {
                    charRead++;
                }

            }

        return new String(inputArr, 0, positionToInsert);

    }

Find first non repeating character in a String

2010-11-20T08:21:00.001-08:00

if input = "total" answer = "o"
if input = "tweetweer" answer = "r"
if input = " gnu " answer = ...

Approach - to do in O(n)

1. Parse the string character by character and populate a map with count of each character
2. parse the string again and lookup character in map and get the count, store the key returning 1 first as a potential answer
3. As a part of step2 also check if any character has a count > 1 in which case return the answer stored in step2 else return null

Java Code

--------------

package StringOps;

import java.util.HashMap;

import java.util.Map;

public class StringOps {

/* To find first non repeating character in a string
   * eg: if string is 'total' then 'o' is the answer
   * eg: if string is 'tweetwer' then 'r' is the answer
   * time complexity :
   * space complexity;
   */
   public String findFirstNonRepeatingChar(String s) {
       if (s == null)
           return null;

       // Parse the String and put it in a array of 256 bit characters if we
       // assume it's a ASCII string set, however for unicode the string
       // could have more characters, hence creating a large array would be waste
       // so we can use a Map which only consume space as the kind of characters
       // are present
       Map inputMap = new HashMap();
       for(int i=0; i < s.length(); i++) {
           String key = s.substring(i, i+1);
           if (inputMap.get(key) == null) {
               inputMap.put(key, new Integer(0));
           }
           else {
               Integer it = new Integer ((inputMap.get(key)).intValue() + new Integer(1).intValue());
               inputMap.put(key, it);
           }
       }
       //Now start from the start of the string and find the character which has count 1
       // first in order from left to right
       boolean found = false;
       boolean foundAnyRepeating = false;
       String nonRepeatingStr = null;
       for(int i=0; i < s.length(); i++) {
           String key = s.substring(i, i+1);
           if(inputMap.get(key).intValue() == 0 && !found) {
               nonRepeatingStr = key;
               found = true;
           }
           if(inputMap.get(key).intValue() > 0 ) {
               foundAnyRepeating = true;
           }
       }
       if (foundAnyRepeating) {
           return nonRepeatingStr;
       }
       else
           return null;
   }

   public boolean testFindFirstNonRepeatingChar(String str) {
       String repeatingCharacter = findFirstNonRepeatingChar(str);
       if ( repeatingCharacter == null) {
           System.out.println("No repeating character in [" + str + "]");
           return false;
       }
       else {
           System.out.println("First non repeating character in [" + str + "] = [" + repeatingCharacter + "]");
           return true;
       }
   }

       public static void main(String[] args) {
           StringOps sOps = new StringOps();
           String[] delArray = {"i", "d", "e"};
           String op = sOps.deleteCharactersFromString("inder", delArray);
           System.out.println("output = " + op);
           /*
           sOps.testFindFirstNonRepeatingChar("total");
           sOps.testFindFirstNonRepeatingChar("tweetwer");
           sOps.testFindFirstNonRepeatingChar("inder");
            */
       }

}

Find junction having GOLD

2010-11-15T22:51:00.000-08:00

You are at a road intersection wherein 1KM north, south, east, west there is another junction like this in all infinite directions. You need find the junction having GOLD.

Assume a graph like

a   <-> b <-> c <-> d
|          |      |           |
e <->f <-> g <-> h
|          |      |        |
i <-> j <-> k <->l

Solution1.
------------
use BFS to traverse the graph..DFS might not work as it works by going in depth and then backtrack but this graph is infinite...in this case BFS would be better as it can be intutively thought of as doing smaller coenctric circles in a infinite space and then increasing the radius of circle, idea is to visit north, south, east, west of starting node and then do the same recursively for all those 4 nodes..everytime you are going 2 POW i nodes...

GITHUB WORKING JAVA CODE ...here

Code

------

import java.util.ArrayList;

import java.util.List;

public class BFS {

public Node getGoldNode(Node node) {

if(node.hasgold)

return node;

        List nodeList = new ArrayList();
        //Start a BFS kind of search which
        // goes all the way in 2 power i

        //1. Visit all nodes of this node
        Node north = node.getNorth();
        Node south = node.getSouth();
        Node east = node.getEast();
        Node west = node.getWest();
        //2. Put these nodes in a list
        if(north != null) {
            System.out.println("Adding node [" + north.getData() + "] to queue");
            nodeList.add(north);
            north.setPendingCheck(true);
        }
        if(south != null) {
            System.out.println("Adding node [" + south.getData() + "] to queue");
            nodeList.add(south);
            north.setPendingCheck(true);
        }
        if(east != null) {
            System.out.println("Adding node [" + east.getData() + "] to queue");
            north.setPendingCheck(true);
            nodeList.add(east);

        }
        if(west != null) {
            System.out.println("Adding node [" + west.getData() + "] to queue");
            nodeList.add(west);
            north.setPendingCheck(true);

        }
        node.setIsvisited(true);
        //Iterate through the list
        while(nodeList.size() > 0) {
            //get the top node from the list and check whether it has gold
            Node checkNode = nodeList.remove(0);
            System.out.println("Checking node [" + checkNode.getData() + "] for GOLD");
            if(checkNode.isHasgold()) {
                //node found return
                return checkNode;
            }
            else {
                //mark this node as visited
                if(!checkNode.isIsvisited()) {
                    System.out.println("Node [" + checkNode.getData() + "] isn't visited..check for all directions for this node ");
                    //add the north, south, east, west of this node to the BFS search list
                    if(checkNode.getNorth() != null && checkNode.getNorth().isIsvisited() == false &&
                       checkNode.getNorth().isPendingCheck() == false) {
                        System.out.println("Adding node [" + north.getData() + "] to queue");
                        nodeList.add(checkNode.getNorth());
                        checkNode.getNorth().setPendingCheck(true);

}

if(checkNode.getSouth() != null && checkNode.getSouth().isIsvisited() == false &&

checkNode.getSouth().isPendingCheck() == false) {

System.out.println("Adding node [" + south.getData() + "] to queue");

nodeList.add(checkNode.getSouth());

checkNode.getSouth().setPendingCheck(true);

}

if(checkNode.getEast() != null && checkNode.getEast().isIsvisited() == false &&

checkNode.getEast().isPendingCheck() == false) {

System.out.println("Adding node [" + east.getData() + "] to queue");

checkNode.getEast().setPendingCheck(true);

nodeList.add(checkNode.getEast());

}

if(checkNode.getWest() != null && checkNode.getWest().isIsvisited() == false &&

checkNode.getWest().isPendingCheck() == false) {

System.out.println("Adding node [" + west.getData() + "] to queue");

nodeList.add(checkNode.getWest());

checkNode.getWest().setPendingCheck(true);

}

// this node is already seen...mark it as visited

checkNode.setIsvisited(true);

}

//Reached here

return null;

}

public static void main(String[] args) {

Node a = new Node();

Node b = new Node();

Node c = new Node();

Node d = new Node();

Node e = new Node();

Node f = new Node();

Node g = new Node();

Node h = new Node();

Node i = new Node();

Node j = new Node();

Node k = new Node();

Node l = new Node();

a.setNorth(null); a.setSouth(e);a.setEast(b); a.setWest( null); a.setData("a");

b.setNorth(null); b.setSouth(f);b.setEast(c); b.setWest(a); b.setData("b");

c.setNorth(null); c.setSouth(g);c.setEast(d); c.setWest(b); c.setData("c");

d.setNorth(null); d.setSouth(h);d.setEast(null); d.setWest(c); d.setData("d");

e.setNorth(a); e.setSouth(i);e.setEast(f); e.setWest(null); e.setData("e");

f.setNorth(b); f.setSouth(j);f.setEast(g); f.setWest(e); f.setData("f");

g.setNorth(c); g.setSouth(k);g.setEast(h); g.setWest(f); g.setData("g");

h.setNorth(d); h.setSouth(l);h.setEast(null); h.setWest(g); h.setData("h");

i.setNorth(e); i.setSouth(null);i.setEast(j); i.setWest(null); i.setData("i");

j.setNorth(f); j.setSouth(null);j.setEast(k); j.setWest(i); j.setData("j");

k.setNorth(g); k.setSouth(null);k.setEast(l); k.setWest(j); k.setData("k");

l.setNorth(h); l.setSouthsetEast(null); l.setWest(k); l.setData("l") ; l.setHasgold(true);

BFS bfs = new BFS();

Node finalNode = bfs.getGoldNode(f);

if (finalNode == null) {

System.out.println("No GOLD in the network");

}

else {

System.out.println("Gold Found in network at Node [" + finalNode.getData() + "]");

}

Other classes required for above program are

public class Node {

Node north;

boolean hasgold;

boolean isPendingCheck;

String data;

public String getData() {

return this.data;

}

public void setData(String data) {

this.data = data;

}

public boolean isPendingCheck() {

return isPendingCheck;

}

public void setPendingCheck(boolean isPendingCheck) {

this.isPendingCheck = isPendingCheck;

}

public boolean isHasgold() {

return hasgold;

}

public void setHasgold(boolean hasgold) {

this.hasgold = hasgold;

}

public Node getNorth() {

return north;

}

public void setNorth(Node north) {

this.north = north;

}

public Node getSouth() {

return south;

}

public void setSouth(Node south) {

this.south = south;

}

public Node getEast() {

return east;

}

public void setEast(Node east) {

this.east = east;

}

public Node getWest() {

return west;

}

public void setWest(Node west) {

this.west = west;

}

public boolean isIsvisited() {

return isvisited;

}

public void setIsvisited(boolean isvisited) {

this.isvisited = isvisited;

}

Node south;

Node east;

Node west;

boolean isvisited;

}

Solution2 ->

-------------

This is a classic case for single source shortest path(Dijkstra algorithm)using dynamic programming and can be implemented using min heap in O(V+E) logV. Requires getting minium for each vertex which contributes V log V and for each edge (degree of vertex) we have to update the values in the minimum heap which start at infinity and then get decremented which contributes E log V Look at the code to understand the time complexity better

Code

-------

import java.util.ArrayList;

import java.util.Comparator;

import java.util.HashMap;

import java.util.Iterator;

import java.util.List;

import java.util.Map;

import java.util.PriorityQueue;

public class dijkstra {

public void getSingleSourceShortestPath(Vertex s, Map g) {

        PriorityQueue minHeap = new PriorityQueue();
        //Iterate through the graph vertex nodes and create a min heap based on distance from s
        Iterator it = g.keySet().iterator();
        while (it.hasNext()) {
            Vertex v = it.next();
            System.out.println("adding vertex [" + v.getName() + "] to minHeap");
            minHeap.add(v);
        }
        // As long as there are elements in the min heap do the following
        while (minHeap.size() > 0) {
            //get the node minimum distance from s
            //first iteration would be s itself
            //This operation will repeat V times and each time the complexity is (logV)
            //so this operation will overall add V (log V) to overall algo complexity
            Vertex v = minHeap.remove();
            //visit all neighbours of v to see if there is a path already and if this path is better
            System.out.println("---- Removing current minimum from S from heap to check =" + v.getName());
            List edgeList = (List) g.get(v);
            for (Edge edge:edgeList) {
                Vertex v1 = edge.getToVertex();
                if (v1 == null)
                    System.out.println(" null edge");
                System.out.println("Checking for vertex = " + v.getName() + " against edges for vertex " + v1.getName());
                //new distance to reach v1 from s
                int newDistance = edge.getWeight() + v.getDistance();
                if( newDistance < v1.getDistance()) {
                    v1.setDistance(newDistance);
                    System.out.println("Setting [" + v1.getName() + "] as predecessor for [" + v.getName() + "]");
                    v1.setPredecessor(v);
                    //since we have changed the distance of v1 we need to remove and reinsert it to min heap
                    // as minheap isn't self adjusting
                    //The following opearation will take 2(log V) and needs to done based on degree(V) = E
                    //in the worst case if the graph is fully connected so this opeation contributes overall
                    // E log(V) to the overall time of this algorithm
                    minHeap.remove(v1);
                    minHeap.add(v1);
                }
            }
        }

    }

public static void main(String[] args) {
        Map> graph = new HashMap>();

        Vertex a = new Vertex();
        Vertex b = new Vertex();
        Vertex c = new Vertex();
        Vertex d = new Vertex();
        Vertex e = new Vertex();
        Vertex f = new Vertex();
        Vertex g = new Vertex();
        Vertex h = new Vertex();
        Vertex i = new Vertex();
        Vertex j = new Vertex();
        Vertex k = new Vertex();
        Vertex l = new Vertex();


        Edge e1 = new Edge();
        a.setDistance(Integer.MAX_VALUE);
        a.setName("a");
        e1.setWeight(1);
        e1.setToVertex(b);
        Edge e2 = new Edge();
        e2.setToVertex(e);
        e2.setWeight(1);
        List l1 = new ArrayList();
        l1.add(e1); l1.add(e2);
        graph.put(a, l1);

        b.setDistance(Integer.MAX_VALUE);
        b.setName("b");
        Edge e3 = new Edge(); Edge e4 = new Edge(); Edge e5 = new Edge();
        e3.setToVertex(a); e3.setWeight(1);
        e4.setToVertex(c); e4.setWeight(1);
        e5.setToVertex(f); e5.setWeight(1);
        List l2 = new ArrayList();
        l2.add(e3); l2.add(e4); l2.add(e5);
        graph.put(b, l2);

        c.setDistance(Integer.MAX_VALUE);
        c.setName("c");
        Edge e6 = new Edge(); Edge e7 = new Edge(); Edge e8 = new Edge();
        e6.setToVertex(b); e6.setWeight(1);
        e7.setToVertex(g); e7.setWeight(1);
        e8.setToVertex(d); e8.setWeight(1);
        List l3 = new ArrayList();
        l3.add(e6); l3.add(e7); l3.add(e8);
        graph.put(c, l3);

        d.setDistance(Integer.MAX_VALUE);
        d.setName("d");
        Edge e9 = new Edge(); Edge e10 = new Edge();
        e9.setToVertex(c); e9.setWeight(1);
        e10.setToVertex(h); e10.setWeight(1);

List l4 = new ArrayList();
        l4.add(e9); l4.add(e10);
        graph.put(d, l4);

        e.setDistance(Integer.MAX_VALUE);
        e.setName("e");
        Edge e11 = new Edge(); Edge e12 = new Edge(); Edge e40 = new Edge();
        e11.setToVertex(a); e11.setWeight(1);
        e12.setToVertex(i); e12.setWeight(1);
        e40.setToVertex(f); e40.setWeight(1);
        List l5 = new ArrayList();
        l5.add(e12); l5.add(e11); l5.add(e40);
        graph.put(e, l5);

        f.setDistance(0);
        f.setName("f");
        Edge e16 = new Edge(); Edge e17 = new Edge(); Edge e18 = new Edge();Edge e19 = new Edge();
        e16.setToVertex(b); e16.setWeight(1);
        e17.setToVertex(e); e17.setWeight(1);
        e18.setToVertex(j); e18.setWeight(1);
        e19.setToVertex(g); e19.setWeight(1);
        List l6 = new ArrayList();
        l6.add(e16); l6.add(e17); l6.add(e18); l6.add(e19);
        graph.put(f, l6);

g.setDistance(Integer.MAX_VALUE);

g.setName("g");

Edge e20 = new Edge(); Edge e21 = new Edge(); Edge e22 = new Edge();Edge e23 = new Edge();

e20.setToVertex(c); e20.setWeight(1);

e21.setToVertex(f); e21.setWeight(1);

e22.setToVertex(h); e22.setWeight(1);

e23.setToVertex(k); e23.setWeight(1);

        List l7 = new ArrayList();
        l7.add(e20); l7.add(e21); l7.add(e22); l7.add(e23);
        graph.put(g, l7);

        h.setDistance(Integer.MAX_VALUE);
        h.setName("h");
        Edge e24 = new Edge(); Edge e25 = new Edge(); Edge e26 = new Edge();
        e24.setToVertex(d); e24.setWeight(1);
        e25.setToVertex(g); e25.setWeight(1);
        e26.setToVertex(l); e26.setWeight(1);
        List l8 = new ArrayList();
        l8.add(e24); l8.add(e25); l8.add(e26);
        graph.put(h, l8);

        i.setDistance(Integer.MAX_VALUE);
        i.setName("i");
        Edge e27 = new Edge(); Edge e28 = new Edge();
        e27.setToVertex(e); e27.setWeight(1);
        e28.setToVertex(j); e28.setWeight(1);
        List l9 = new ArrayList();
        l9.add(e27); l9.add(e28);
        graph.put(i, l9);

        j.setDistance(Integer.MAX_VALUE);
        j.setName("j");
        Edge e29 = new Edge(); Edge e30= new Edge(); Edge e31 = new Edge();
        e29.setToVertex(f); e29.setWeight(1);
        e30.setToVertex(i); e30.setWeight(1);
        e31.setToVertex(k); e31.setWeight(1);
        List l10 = new ArrayList();
        l10.add(e29); l10.add(e30); l10.add(e31);
        graph.put(j, l10);

        k.setDistance(Integer.MAX_VALUE);
        k.setName("k");
        Edge e32 = new Edge(); Edge e33= new Edge(); Edge e34 = new Edge();
        e32.setToVertex(g); e32.setWeight(1);
        e33.setToVertex(j); e33.setWeight(1);
        e34.setToVertex(l); e34.setWeight(1);
        List l11 = new ArrayList();
        l11.add(e32); l11.add(e33); l11.add(e34);
        graph.put(k, l11);

        l.setDistance(Integer.MAX_VALUE);
        l.setName("l");
        Edge e35 = new Edge(); Edge e36= new Edge();
        e35.setToVertex(h); e35.setWeight(1);
        e36.setToVertex(k); e36.setWeight(1);
        List l12 = new ArrayList();
        l12.add(e35); l12.add(e36);
        graph.put(l, l12);

dijkstra dij = new dijkstra();

dij.getSingleSourceShortestPath(f, graph);

// Get node h

Vertex v = l.getPredecessor();

System.out.print("Shortest path starts from l to f..in reverse order is..." + v.getName() + " ");

while (v.getPredecessor() != null) {

System.out.print(" , " + v.getPredecessor().getName());

v = v.getPredecessor();

}

System.out.println("\n");

}

Find if two lists are same

2010-11-09T23:17:00.001-08:00

You are given two lists/arrays find if they are same

Find duplicates in a array of elements

2010-11-09T23:15:00.000-08:00

You are given an array of elements. Some/all of them are duplicates. Find them in 0(n) time and 0(1) space. Property of inputs - Number are in the range of 1..n where n is the limit of the array.

GITHUB WORKING JAVA CODE..here

Algorithm -

* 1. Read input from startPos

* 2. If input is within the maxRange or it's not in correct place then it's a candidate to be replaced else incrementStartPos

* 3. finalPosition for input is input[i]

* 4. if finalPosition < maxRange then swap input with finalPosition and increment finalPosition with MaxRange

* 5. else no need to swap as previous instances of this element are recorded at finalPos so just increment finalPosition with MaxRange to record another instance

* 6. if input at startPos is in correct place or reached zero then increment startPos++ till you go through end of Array

* 7. Iterate through the array and divide each element with maxRange. The divisor indicates how many times a element was repeated and 0 indicates a missing element

Working JAVA Code -
http://datastructure-puzzles-codesolutions.blogspot.com/2011/02/find-duplicates-in-array-of-elements.html

Find if a tree is a mirror of itself

2010-11-07T10:10:00.001-08:00

Find if a tree is a mirror of itself. You can consider the tree to be a binary tree

Approach1 : Tree will be a palindrome at each level. Do a level order traversal and check for palindrome and break

Approach2 : Use a variant of recursive function for checking sameTree() instead of checking left and left, right and right. Check left with right and right with left.

Code using palindrome approach

------------------------------------------

import java.util.ArrayList;

import java.util.List;

public class BFS {

    List nodeList = new ArrayList();
    List nodeList1 = new ArrayList();
    List list, list1;

    public boolean isSymmetricTree(Node n) {
        // do a BFS traversal of this tree
        if (n == null) {
            //null is symmetric
            return true;
        }
        if ( n != null && n.left == null && n.right == null ) {
            // only 1 node;
            return true;
        }
        nodeList.add(n.left);
        nodeList.add(n.right);

        list = nodeList;
        list1 = nodeList1;
        while (list.size() > 0) {
            int count = 0;
            while (count < list.size()) {
                //System.out.println("Count = " + count + " list.size = " + list.size());
                Node tempNode = (Node)list.get(count);
                if (tempNode != null) {
                    //store it's left right
                    if (tempNode.getLeft() != null)
                        list1.add(tempNode.left);
                    if (tempNode.getRight() != null)
                        list1.add(tempNode.right);
                }
                count++;
            }
            if (isPalindrome(list) == false) {
                return false;
            }
            emptyList(list);
            List tmp = list;
            list = list1;
            list1 = tmp;
        }
        return true;
    }



    private static void emptyList(List nodeList) {
        if (nodeList != null)
            nodeList.clear();
    }

private static void printArray(Node[] nodes) {
        for (int i =0; i < nodes.length; i++) {
            System.out.println ( i + " th Node = [ " + nodes[i].getData() + "]");
        }
    }

    private boolean isPalindrome(List nodeList) {
        if (nodeList == null || nodeList.size() == 0 )
            return true;
        Node[] nodes = new Node[nodeList.size()];
        nodeList.toArray(nodes);
        //printArray(nodes);
        //for it to be symmetric nodes.length should be an even number
        if (nodes.length % 2 != 0)
            {
                System.out.println("List size is not symmetric ..returning false");
                return false;
            }
        int start = 0;
        int end = nodes.length - 1;
        while ( start < end) {
            //System.out.println("Comparing " + nodes[start].getData() + nodes[start].getData());
            if (nodes[start].getData() == nodes[end].getData()) {
                start++;
                end--;
            }
            else
                {
                    //System.out.println("Comparing " + nodes[start].getData() + " " + nodes[start].getData() + " and returning false");
                    return false;
                }
        }
        //System.out.println (" isPalindrome function returning true");
        return true;
    }

}

public class Node {

Long data;

Node left;

Node right;

public Node() {

}

public Node(Long data) {

this.data = data;

}

public Long getData() {

return data;

}

public void setData(Long data) {

this.data = data;

}

public Node getLeft() {

return left;

}

public void setLeft(Node left) {

this.left = left;

}

public Node getRight() {

return right;

}

public void setRight(Node right) {

this.right = right;

}

public class TreeTest {

public static void main(String[] args) {

/* Test case 1 what we discussed over the phone */

Node n = FileUtils.constructTree();

BFS bfs = new BFS();

if (bfs.isSymmetricTree(n))

{

System.out.println("------Tree is symmetric------");

}

else {

System.out.println("-----Tree is asymmertric-------");

}

System.out.println(" ");System.out.println(" ");System.out.println(" ");

System.out.println("=============Second positive test case===============");

n = new Node(1L);

Node n1 = new Node(2L);

Node n2 = new Node(2L);

Node n3 = new Node(4L);

Node n4 = new Node(4L);

n4.setLeft(null);

n4.setRight(null);

n3.setLeft(null);

n3.setRight(null);

n2.setLeft(null);

n2.setRight(n4);

n1.setLeft(n3);

n1.setRight(null);

n.setLeft(n1);

n.setRight(n2);

if (bfs.isSymmetricTree(n))

{

System.out.println("------Tree is symmetric-------");

}

else {

System.out.println("------Tree is asymmertric------");

}

System.out.println(" ");System.out.println(" ");System.out.println(" ");

System.out.println("=============Third negative test case===============");

n = new Node(1L);

n1 = new Node(2L);

n2 = new Node(2L);

n3 = new Node(4L);

n4 = new Node(5L);

n4.setLeft(null);

n4.setRight(null);

n3.setLeft(null);

n3.setRight(null);

n2.setLeft(null);

n2.setRight(n4);

n1.setLeft(n3);

n1.setRight(null);

n.setLeft(n1);

n.setRight(n2);

if (bfs.isSymmetricTree(n))

{

System.out.println("Tree is symmetric");

}

else {

System.out.println("------Tree is asymmertric------");

}

}

Code using recursive Approach mentioned in Comment1
---------------------------------------------------------------------

public class TreeOps {

    class Node {
    int data;
    Node left;
    public int getData() {
        return data;
    }
    public void setData(int data) {
        this.data = data;
    }
    public Node getLeft() {
        return left;
    }
    public void setLeft(Node left) {
        this.left = left;
    }
    public Node getRight() {
        return right;
    }
    public void setRight(Node right) {
        this.right = right;
    }
    Node right;

    }
    public boolean isSymmetricTree(Node root) {
        if (root == null)
            return true;
        if (root.getLeft() == null && root.getRight() == null)
            return true;
        return isSymmetricTree(root.left, root.right);
    }

    private boolean isSymmetricTree(Node left, Node right) {
        if (left == null && right == null) {
            return true;
        }
        if ((left == null && right != null) ||
                (left != null && right == null))
            return false;

        return left.getData() == right.getData() &&
        isSymmetricTree(left.getLeft(), right.getRight()) &&
        isSymmetricTree(left.getRight(), right.getLeft());

    }

    public void testIsSymmetricTreePositiveOne() {
    Node n = new Node();
    Node n1 = new Node();
    Node n2 = new Node();
    Node n3 = new Node();
    Node n4 = new Node();
    n.setData(1);
    n1.setData(2);
    n2.setData(2);
    n3.setData(3);
    n4.setData(3);
    n.setLeft(n1);
    n.setRight(n2);
    n1.setLeft(n3);
    n1.setRight(null);
    n2.setRight(n4);
    n2.setLeft(null);
    System.out.println("testIsSymmetricTreePositiveOne = [" +isSymmetricTree(n) + "]");


    }

    public void testIsSymmetricTreePositiveTwo() {
        Node n = new Node();
        Node n1 = new Node();
        Node n2 = new Node();
        Node n3 = new Node();
        Node n4 = new Node();
        Node n5 = new Node();
        Node n6 = new Node();
        n.setData(1);
        n1.setData(2);
        n2.setData(2);
        n3.setData(3);
        n4.setData(3);
        n5.setData(4);
        n6.setData(4);
        n.setLeft(n1);
        n.setRight(n2);
        n1.setLeft(n3);
        n1.setRight(n5);
        n2.setRight(n4);
        n2.setLeft(n6);
        System.out.println("testIsSymmetricTreePositiveTwo = [" +isSymmetricTree(n) + "]");

        }

    public void testIsSymmetricTreeNegativeOne() {
        Node n = new Node();
        Node n1 = new Node();
        Node n2 = new Node();
        Node n3 = new Node();
        Node n4 = new Node();
        Node n5 = new Node();
        n.setData(1);
        n1.setData(2);
        n2.setData(2);
        n3.setData(3);
        n4.setData(3);
        n5.setData(4);
        n.setLeft(n1);
        n.setRight(n2);
        n1.setLeft(n3);
        n1.setRight(n5);
        n2.setRight(n4);
        System.out.println("testIsSymmetricTreeNegativeOne = [" +isSymmetricTree(n) + "]");

        }
    public static void main(String[] args) {
        TreeOps t = new TreeOps();
        t.testIsSymmetricTreePositiveOne();
        t.testIsSymmetricTreePositiveTwo();
        t.testIsSymmetricTreeNegativeOne();
    }


}

an array contain +ve and -ve element, find subarray whose sum =0;

2010-11-02T07:55:00.000-07:00

an array contain +ve and -ve element, find subarray whose sum =0;

Lets take input array as a[]={-3,2,4,-6,-8,10,11}
https://github.com/inders/datastructure-repo/tree/master/subarraywithsumzero/src

Working JAVA Code is here
GITHUB Working Java Code
Algorithm/Approach is here

How to think Approach

Since it's easier to think pictorial imagine the cummulative sumarry of the original array in a X-Y corrdinate and you'll see if there are negative/postive numbers negating each others within a region your graph would go up/down and reach the same point after a while. So essentially you could have nested subarray as seen above in the smaller RED line. Non overlapping such subarrays seen with the right side RED line. You are interested in the longest RED line.

Approach

1. Store the sum of elements till that element in a separate array
2. w.r.t to example in question our interim subarray would like
-3, -1, 3, -3, -11, -1, 10

3. looking at the interim array you can observe a pattern that if an element summed upto -3 at any index and there is another -3 at a further index ( Since this being a cummulative summation array wherein the summation started at -3 and then again went up and down and back to -3) These two indexes have elements which are negating each other completely and is one of the resultant set. You need to skip the element at head index as that has contribution from previous summation also.

You can achieve the above by putting the indexes in a hash map and check for collision's and use the start index and the current index as a resultant set.

So in out interim array
-3, -1, 3, -3, -11, -1, 10

-1, 3, -3 is one set and input elements = { 2, 4, -6}
3, -3, -11, -1 is another and input elements = { 4, -6, -8, 10}

Minimum number of scales required

2010-11-02T07:12:00.001-07:00

A company produces play ball of weights 0-25kg, 25-50kg, 50-75kg, 75-100kg. You need to put the balls in four different buckets daily depending on the number of ball company produces.BucketA (0-25kg), BucketB (25-50kg), BucketC (50-75kg) and BucketD(75-100kg).
A scale is provided on which you can weigh only 1 ball at a time which has a bulb. If the weight of the ball matches the scale category, the bulb will light up otherwise it will be OFF. e.g. If scale is marked to measure 10-25 kg, then any ball between 10 to 25kg (inclusive 10 and 25) will switch on the bulb and say if you weigh 26 it wont switch on the bulb. The cost of scale is 1 million dollar.
Question: You need to find the minimum number you will use to do the job.Also what is weight category you will choose for the scales to do the job.

Tie ropes in min cost

2010-11-02T07:02:00.001-07:00

you are given n ropes,maybe of different length. the cost of tying two ropes is the sum of their lengths.Find a way to tie these ropes together so that the cost is minimum.

Data structure to support Push, Pop and GetMin in O(1)

2010-11-02T06:50:00.001-07:00

Implement a data structure similar to stack which supports Push, Pop and GetMin in O(1)

find maximum interval across two arrays

2010-11-02T06:25:00.000-07:00

We are given with two arrays A and B..each of size N...elements of array contains either 1 or 0...
we have to find such an interval (p,q)(inclusive) such that the sum of all the elements of A (between this interval) and sum of all elements of B (between this interval ) is equal...
i.e.
a[p]+a[p+1]....+a[q]= b[p]+b[p+1]....+b[q]

An Ant Antic

2010-07-24T02:43:00.000-07:00

A 5 feel pole is so place that its ends rest on 2 buckets , one filled with sugar and the other with cream. Some ants are dropped randomly(wrt the point of drop) on the pole and they start running towards the left or right directions. If 2 ants hit each other they reverse their direction instantaneously and start moving again. If an ant reaches the either end of the pole it jumps into the bucket at that end to bask in heavenly sweetness.

If they travel at 1 inch/second how long will it take for all ants to fall off ?

Arrange players in relative order

2010-04-19T00:29:00.001-07:00

You have 'n' players who have played against each other and for each player you have 2 sets
Win = { } Loose = { } which tells you what all players has a given player lost/won against.

You need to arrange them in such a way that player's to left of each in final result should be winner's and to the right losers for a player.

Longest increasing subsequence in chain of numbers

2010-04-19T00:26:00.001-07:00

Find out the the longest increasing subsequence in a sequence of 'n' numbers.
eg: 1, 5, 3, 2, 100

Ways to climb steps

2010-04-19T00:25:00.000-07:00

you have 'n' steps and a person who wants to reach step 'n' currently standing at step1. What are the possible ways he can do that provided he can either take 1/2 steps at a time.

Partition array in k ranges to minimize the maximum sum over all ranges

2010-04-01T23:19:00.000-07:00

A given arrangement S of non-negative numbers and an integer k.

Output: Partition S into k ranges, so as to minimize the maximum sum over all the ranges. This so-called linear partition problem arises often in parallel processing, since we seek to balance the work done across processors so as to minimize the total elapsed run time. Indeed, the war story of Section revolves around a botched solution to this problem.

Application - Suppose that three workers are given the task of scanning through a shelf of books in search of a given piece of information. To get the job done fairly and efficiently, the books are to be partitioned among the three workers. To avoid the need to rearrange the books or separate them into piles, it would be simplest to divide the shelf into three regions and assign each region to one worker.

But what is the fairest way to divide the shelf up? If each book is the same length, say 100 pages, the job is pretty easy. Just partition the books into equal-sized regions,

so that everyone has 300 pages to deal with.

But what if the books are not the same length?

Minimum number of coins to make change

2010-04-01T21:43:00.001-07:00

You are given n types of coin denominations of values v(1) < v(2) < ... < v(n) (all integers). Assume v(1) = 1, so you can always make change for any amount of money C. Give an algorithm which makes change for an amount of money C with as few coins as possible

Arrange numbers in decreasing order of their frequency

2010-03-26T00:27:00.001-07:00

Input : {5, 13, 6, 5, 13, 7, 8, 6, 5}

Output : {5, 5, 5, 13, 13, 6, 6, 7, 8}

The question is to arrange the numbers in the array in decreasing order of their frequency, preserving the order of their occurrence.

If there is a tie, like in this example between 13 and 6, then the number occurring first in the input array would come first in the output array.

Design an algorithm for an automated parking lot

2010-03-24T02:00:00.000-07:00

You have a set of parking slots along with the distance from entrance, you need to devise an algorithm to support the following operations

1. Figure out a nearest free parking slot in the quickest way
2. Figure out where the car is parked for a valet to take it out in the quickest way.

Design an algorithm for optical character reading

2010-03-23T06:46:00.000-07:00

Assuming you have been given some very old papers which are scanned as JPG images.
You have been asked to write a program which can read those images and identify lines in the same.
Trick lies in the fact that the lines could have negative/positive slopes as they are old documents.

Source - Algorithm design manual by Stevens

How would you design an elevator algorithm

2010-03-23T06:43:00.001-07:00

How would you design an elevator algorithm

find row with minumum 0's

2010-03-22T01:08:00.000-07:00

You have a matrix with 0 & 1 with rows being in sorted order. Find the row with minimum number of 1's

0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
0 0 1 1 1

Find overlapping pairs

2010-03-18T01:16:00.001-07:00

You are given the following pairs
[1,3] [2,4] [5,8]

Output should be the following
[1,4][5,8]

Map rectangles to plane

2010-03-09T02:48:00.001-08:00

In my graphics work I need to solve the following problem. Given an arbitrary set of rectangles in the plane, how can I distribute them into a minimum number of buckets such that the subset of rectangles in the same bucket do not intersect each other? In other words, there should not be any overlapping area between any two rectangles in the same bucket.'

Formulate a way to detect tax fraud

2010-03-09T02:43:00.000-08:00

In organized tax fraud, criminals submit groups of phony tax returns in the hopes of getting undeserved refunds. These phony returns are all similar, but not identical. How can we detect clusters of similar forms so the IRS can nail the cheaters

Assumptions -> You can assume that there is a mechanism of detecting identical forms given.

How will formulate this problem to solve it efficiently.

Porting code from DOS to UNIX

2010-03-09T02:26:00.000-08:00

In porting code from UNIX to DOS, I have to shorten the names of several hundred files down to at most 8 characters each. I can't just take the first eight characters from each name, because ``filename1'' and ``filename2'' will get assigned the exact same name. How can I shorten the names while ensuring that they do not collide?''

Find median of two sorted Lists

2010-02-17T21:55:00.000-08:00

l1 = [1, 4, 5, 7, 7, 8, 9, 9]
l2 = [0, 1, 3, 6, 6, 6, 7, 8]

You have the above two lists, find the median among them

Unimodal Search

2010-01-11T09:28:00.000-08:00

An array A[1...n] is unimodal if it consists of an increasing sequence followed by a decreasing sequence. More precisely, if there is an index m in {1, 2, ... n} such that
A[i] < A[i+1] for 1 <= i < m and
A[i] > A[i+1] for m <= i < n

In particular, A[m] is the maximum element, and it is the unique "locally maximum" element surrounded by smaller elements.

Give an algorithm to compute the maximum element of a unimodal input array A[1...n] in O(lg n) time.

Source: Problem 1-3.from MIT OpenCourseWare Course - 6.046J / 18.410J Introduction to Algorithms (SMA 5503)

Is Binary Search Tree

2009-12-01T10:32:00.001-08:00

Given a binary tree, verify if it is Binary Search Tree

Approach which can do this in O(n) will have to track min, max and at each node check whether it's in range of min, max.

1. Root left will be in range of min=0, root.data (as elements in root left subtree) should be within this range
2. now root.left.left should be range of min=0 to root.left.data ( as it's subtree should be all all elements less than this)
3. root.right will be in range min=root.data to MAX
4. at step2 if root.left has right subtree also then it will be in range of root.left.data to MAX=root.data as root.left.right subtree should have everything greater than root.left and should be less than root.data

Java Code

-------------

public boolean isBST(Node root, Long currMin, Long currMax) {
        if (root == null)
            return true;
        if(root.getData() < currMin ||
                root.getData() > currMax)
            return false;
        return (isBST(root.getLeft(), currMin, root.getNodeData()) &&
                isBST(root.getRight(), root.getNodeData(), currMax));

    }

Find the string in 2 dimensional matrix

2009-11-30T10:31:00.001-08:00

Given a 2-dim matrix of characters 'm' and a string 's' - find if the string 's' is present in the matrix. Only characters in the neighboring cells of a cell can contribute to the string.

For example, for the case below B,D,F,G are neighbors of X. From 'X' possible strings (or substrings) are XB, XD, XF, XH.
|-----|-----|-----|
| A | B | C |
|-----|-----|-----|
| H | X | D |
|-----|-----|-----|
| G | F | E |
|-----|-----|-----|

Finally, an example. Given the matrix

(0,0)
    |-----|-----|-----|-----|
    | y | a | a | o |
    |-----|-----|-----|-----|
    | a | o | a | o |
    |-----|-----|-----|-----|
    | y | a | o | o |
    |-----|-----|-----|-----|
    | h | a | a | o |
    |-----|-----|-----|-----|
    | y | a | h | o |
    |-----|-----|-----|-----|
                          (3,3)

and asked to check for the string 'yahoo' the solution is true :
y - (3,0)
a - (3,1)
h - (3,2)
o - (3,3)
o - (2,3)

Random number generator, with equal probability

2009-11-30T10:13:00.001-08:00

RANDOM(a.b) is a random number generator that generates integers between a and b (inclusive), all equally likely.

Assuming we have an implementation of RANDOM(0.1), how can we implement RANDOM(a.b) - i.e. given we have a function that returns 0 OR 1 both with a probability of 1/2, how can we implement a function that returns integers from a to b (b > a), all with a probability of 1/n, where n = (b-a+1)

Source : Cormen - Problem 5.1-2 (randomized algorithms)

Similar problem :
At a restaurant, how can Veronica choose one out of three desserts with equal probability with the help of a coin?

Its on Gurmeet's site here http://gurmeetsingh.wordpress.com/2008/09/12/puzzle-tossing-with-one-third-probability/

Web consistent Caching

2009-11-17T10:45:00.000-08:00

you have enormous data in format key=val which needs to be cached in multiple web servers for fast look up. You could later on add servers for scaling up throughput/decrease latency or adding new data in which case some data from older caches could move to new. What's the best way to achieve this?

Good Link - http://www8.org/w8-papers/2a-webserver/caching/paper2.html#ch

Number guessing game

2009-09-21T11:36:00.000-07:00

Shankar chooses a number between 1 and 10,000. Geeta has to guess the chosen number as quickly as possible. Shankar will let Geeta know whether her guess is smaller than, larger than or equal to the number. The caveat is that Geeta loses the game if her guess is larger than Shankar’s chosen number two or more times. (A) How many guesses are necessary? (B) What if Shankar is allowed to pick an arbitrarily large positive number?

Source - http://gurmeetsingh.wordpress.com/puzzles/

How long will it take for my gossip to get back to me

2009-09-14T11:07:00.000-07:00

I am on yahoo mail and start a forward thread to all my contacts. How long will it take for the same gossip to travel back to me.

Transitive set correlation

2009-09-13T10:09:00.000-07:00

You have a large file of the following format

s1 => s2
s3 => s7
s9 => s15
s1 => s3
s3 => s4
s15 => s16
......
......
......

You need to arrange them in a transitive correlated set. Let me take a step back so that you digest this.
In the above example the end result should be following

(s1, s2, s3, s4, s7)
(s9, s15, s16)

What's the best time & space complexity in which you can achieve this?

Find the celebrity

2009-09-13T09:44:00.000-07:00

You are in a party which has 'n' guests. One of them being a celebrity which meets the following criteria.

1. Celebrity doesn't know anyone
2. All others except the celebrity know atleast one person including the celebrity.

You are allowed to ask any person - DO YOU KNOW X person.
How many questions you need to identify the celebrity

Walk the bridge, in paris as fast a possible

2009-09-06T03:35:00.001-07:00

There are 4 women who want to cross a bridge. They all begin on the same side. There is one flashlight. A maximum of two people can cross at one time. It is night. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each woman walks at a different speed. A pair must walk together at the rate of the slower woman's pace.
Woman 1: 1 minute to cross
Woman 2: 2 minutes to cross
Woman 3: 5 minutes to cross
Woman 4: 10 minutes to cross

For example if Woman 1 and Woman 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Woman 4 then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission.

Find jar with the contaminated pills

2009-09-06T03:25:00.001-07:00

You have 4 jars of pills. Each pill is a certain weight, except for contaminated pills contained in one jar, where each pill is weight + 1. How could you tell which jar had the contaminated pills in just one measurement?

Source : http://www.sellsbrothers.com/fun/msiview/default.aspx?content=question.htm

Find repeating element in array

2009-09-05T11:20:00.001-07:00

In an array from 1 to n, one number is present twice. How to do you determine which one?

There are multiple answers - all correct. We would, obviously, aim for the optimized one - benchmark parameters being time & space complexity

Source : http://www.noop.nl/2009/01/100-interview-questions-for-software-developers.html

Find direction of rotation

2009-09-05T10:59:00.001-07:00

Imagine a disk spinning like a record player turn table. Half of the disk is black and the other is white. Assume you have an unlimited number of color sensors. How many sensors would you have to place around the disk to determine the direction the disk is spinning? Where would they be placed?

Source : http://www.sellsbrothers.com/fun/msiview/default.aspx?content=question.htm

Pay for 7 days using 1 7-segment gold bar and 2 cuts

2009-09-05T10:57:00.001-07:00

You've got someone working for you for seven days and a gold bar to pay them. The gold bar is segmented into seven connected pieces. You must give them a piece of gold at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker?

Source : http://www.sellsbrothers.com/fun/msiview/default.aspx?content=question.htm

Divide 100 marbles into two piles

2009-09-03T11:54:00.001-07:00

How would you divide 50 black and 50 white marbles into two piles so that the probability of picking a white marble as follows is maximized: we first pick one of the piles uniformly at random, then we pick a marble in that pile uniformly at random?

Source : http://gurmeetsingh.wordpress.com/puzzles/

Flip bits in a matrix

2009-09-03T10:25:00.001-07:00

An 8×8 matrix contains zeros and ones. You may repeatedly choose any 3×3 or 4×4 block and flip all bits in the block (that is, convert zeros to ones, and ones to zeros). Can you remove all the ones in the matrix

Source - http://gurmeetsingh.wordpress.com/puzzles/

Find number of digits in a number

2009-09-02T08:12:00.000-07:00

Can you do it in constant time & memory?

Solution -

Lets consider for base 10
(i) 1 - 9 numbers have a tight upper bound of (10 POW 1)
(ii) 10 - 99 numbers have a tight upper bound of (10 POW 2)
(iv) 100 - 999 numbers have a tight upper bound of (10 POW 3)
.........
-------
-------

The above holds true for any n with base 10 as the numbers round off to multiple digits once the MSB reaches (base-1) for a single digit number and for a multi digit when all digits reach (base-1)

Using the above statements we can derive the following
M (Maximum supported number in a base for given 'n' digits) = (base POW 'n') - 1 .............(i)

As a proof replace n = 2 and base = 10 we get (10 pow 2)-1 = 99

What we want to find is 'n' in (i) Taking log both sides to negate exponential as 'n' is in the exponent
log(m) = log (base pow n ) - 1
= n log (base) - 1 ..... ( log(base) has base here...= 1)
= n - 1
n = log(m) + 1.....................(ii)

From (ii) it's evident that for multiple of BASE i.e. 10 in this case 10, 100, 1000... log won't be fractional however it would be fractional i.e. for any number between 100 - 999 it would be tending between 2 & 3. So the final formula should be the following

n = floor (log Number + 1 )................(iii)

Eg: Let's try 59 log base 10 is in between (1...2 ) assume 1.6 as per (iii) we get the following
n = floor ( 1.6 + 1) = floor (2.6) = 2

Another eg:: 500 log base 10 is in between (2...3) assume 2.5 as per (iii) we get the following
n = floor ( 2.5 + 1) = floor (3.5 ) = 3

Eg:: Let's try 1000 log base 10 is 3; as per (iii) we get the following
n = floor ( 3 + 1) = floor (4) = 4

Minimum colors to paint adjacent areas

2009-08-25T05:02:00.000-07:00

How many minimum colors are required fulfill areas which are divided by intersecting lines
such that adjacent areas do not have same color. Assume you have a square.

Solution - If you have 'n' intersecting lines in the square you could have more than two adjacent polygon's to anyone polygon. This maps to a graph theory problem where each polygon is a graph node and is connected to more than one nodes. You need to find the chromatic number of this graph. Finding the chromatic number is a NP-COMPLETE problem

Chromatic number - minimum colors required to paint the nodes such that adjacent nodes aren't of the same color.

Rope Escape

2009-08-19T06:26:00.001-07:00

Rajeev is trapped atop a building 200m high. He has with him a rope 150m long. There is a hook at the top where he stands. Looking down, he notices that midway between him and the ground, at a height of 100m, there is a ledge with another hook. In his pocket lies a Swiss knife. Hmm… how might he be able to come down using the rope, the two hooks and the Swiss knife?

Source : http://gurmeetsingh.wordpress.com/puzzles/

Solution -
1. You need 100 m to go down from mid hook of the building to the ground.
2. Cut into 100 and 50 m with the knife.
3. We need a mechanism so that 100 m is available to us midway.
4. Following diagram shows how that's possible. C
   (i) Create a nose in the 50 m rope and tie it to the top hook of building.
   (ii) Slide the 100m through this nose as a U turn. While getting down midway after 50 m use both the ropes to go down another 50 m.
   (iii) You have reached 100 m, slide the 100m back from the nose by pulling one end.
   (iv) Tie the 100m rope and come down.

[ALGO] Six Colored Balls

2009-08-19T06:24:00.001-07:00

We have two red, two green and two yellow balls. For each color, one ball is heavy and the other is light. All heavy balls weigh the same. All light balls weigh the same. How many weighings on a beam balance are necessary to identify the three heavy balls?

Source : http://gurmeetsingh.wordpress.com/puzzles/

Solution -
You can have three sets with H-heavy, L - light represented as follows
(H,L) (H,L) (H, L)
RED - BLUE - YELLOW
Approaches i thought of -

1. If you compare H,L from RED and find the H and L. Now replace R(H) with one ball in B and replace R(L) with one ball in yellow. There is a combination wherein you will have HH in set1 and LL in set2 and HH in set1 and HL in set2. In both cases set1 is greater then set2 and you are done with two comparisons with still ambiguity left. This approach will never work for identifying heavy balls.
2. Compare 1R and 1B. If they are greater or less you are good and can find the third ball in two comparisons. If they are equal you are still reach wherein you have wasted one comparison and haven't found one ball. This approach will also not work.

From 1 & 2 we know that we need to consider balls from all three groups in the very first comparison.

1. We take 1R, 1B, 1Y and compare them against the other corresponding 1R, 1B, 1Y balls.
If they are equal then again we have wasted one comparison and haven't found any H or L. This approach will not work.

Approach for Solution -
Can we try and chain up the H,L balls consecutively. If we start to build the chain out of all possible combinations the following seem to cover all.

Correction - Case 4 in figure above is (H,H) (L,H) not (H,H)(L,L) as that's already covered in Case3

More combinations would include (L, L)(H,H) and (L, L) (H, L) which are same 3 &4 in the figure above. If we start with L in the first set then (L,H)(L,L) and (L,L ) (H, L) are also posible which are opposite to 3 & 4in figure above . So if we solve for 3 &4 the inverse of that solution will work here.

1. From & case2 in figure above (H,L )= (H, L )
2. From case3 in figure above (H, H) > (L, L )
3. From case4 in figure above (H, H) > (L, H)
4. Inverse of 2 & 3 would be (L, L ) < (H, L)
5. Inverse of 2 & 3 would be (L, L ) < (H, H)
6. If we reach case1 then compare the first set and find whether the ball from R is H or L. All others in the chain are opposite to this. i.e. if R in chain is H then other R is light, R is connected to Blue L which is connected to H yellow.
7. In case 2 & 3 since we have the same operator there is some ambiguity.
(i) Replace 1 ball each among the two sets.

Initial set after comparison 1 was (H, H) > (L, L)
if we replace any ball in the first set we get (H,L) = (H, L)

Initial set after comparison 1 (H, H) > (L, H)
if we replace H in set1 with L in set2 we get (L, H) < (H, H)
if we replace H in set1 with H in set2 we get (H, H) (L, H) - no change in weight
Since we have three different operators as a result we can come to know which balls were replaced.

Find the posionous bottle

2009-08-19T03:11:00.000-07:00

A king has 1000 wine bottles out of which 1 is poisonous. The poison takes effect only after 30 days and the king has to host a party after 31 days. The king would make the prisoners (call them lab-rats if you must) drink from the bottles to find the poisonous bottle before hosting. What is the minimum number of prisoners that would die to help find the bottle?

Catch the Fox

2009-08-16T10:46:00.001-07:00

Consider five holes in a line. One of them is occupied by a fox. Each night, the fox moves to a neighboring hole, either to the left or to the right. Each morning, you get to inspect a hole of your choice. What strategy would ensure that the fox is eventually caught?

Solution
Let's name the five holes as 1, 2, 3, 4, 5

Approach - Try and corner the wolf
Assumtion - Wolk starting point could be any 1 to 5

1. Checking 1 & 5 in the start is waste as if the wolf was at 1 or 5 initially he would have moved.
2. Cornering the wolf can be done better through 2,3,4
3. If we stop at 2, 3, 4 once we will miss out the wolf.
4. If we start at 3 first and be there for two jumps it's still possible we will miss out a single catch even if the wold starting point is 3
5. Solution which worked -
(i) Be at 2 for the first two days.
(ii) Go to 3; wait for a day.
(iii) Come to 4; wait for two days
(iv) If you haven't caught the wolf till now there is only one case wherein he reached 2 on the 5th Day.
Check 3 on 6th day if not found at 3 he is at 1.

Water jugs problem

2009-08-11T12:03:00.001-07:00

Suppose that you are given 'n' red and 'n' blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. For every red jug, there is a blue jug that holds the same amount of water & vice versa.

How can you find the grouping of the jugs into pairs of red & blue jugs that hold the same amount of water, in the minimum number of comparisons.

Operations allowed

always compare between a red and a blue jar (no two reds, no two blues)
fill water in red / blue jug
pour from red jug to blue (& vice versa). This will help compare the capacity of the jugs.

Source : Introduction to Algorithms (by Cormen..., Problem 8-4)

Find number of digits in a factorial of number

2009-08-09T07:59:00.000-07:00

Without calculating factorial of a number is there a way to number how many digits will be there in the result.

Solution - Based on a mathematical proof(
http://stackoverflow.com/questions/1113167/can-one-know-how-large-a-factorial-would-be-before-calculating-it)
The logarithm of the factorial can be used to calculate the number of digits that the factorial number will take:

log (n!) = log(n * (n-1) * (n -2 ) *......1)
= log(n) + log (n-1 ) + ...... log(1)
= SUM (log k) ( 1<= k <=n)

There is a proof posted at
http://inder-gnu.blogspot.com/2009/09/find-number-of-digits-in-number.html
for number of digits in a number 'n' this problem is a special case of the same where n is n!

Can some one provide a proof of the base theorem here.

Proof for number occuring n/2 times works always with three pointers

2009-08-09T07:42:00.001-07:00

With reference to http://inder-gnu.blogspot.com/2009/08/number-occuring-n2-times.html
Can you provide a mathematical proof that the three pointer approach will always work.

Problem - Find if a number is occuring exactly n/2 times in a sequence where other numbers are unique

Solution Brief in previous blog to above problem - Keep three pointers and if any of them match each other break else keep moving the pointers. The matched number is occuring n/2 times.

Arrangement Problem - The three pointers approach fails if there is a possible arrangement such both the following are true
1. Two 'a' are separated by a distance > 3 units
2. No two 'a' occur together.

If we have an arrangement adhering to Condition1
.... , b, c, d, ,.....
we are left with n/2 'a' an (n/2 )-3 other unique elements.

With n/2 'a' and (n/2) -3 other elements fulfilling Condition2. (No two 'a' occur together.) is only possible on alternative arrangement of 'a' like ....a, b, a, c, a, d..... which isn't possible since n/2 > n/2 - 3 and alternative arrangement is only possible when both sides elements are same in count.

With reference to above if we fulfill condition1 our arrangement will have two consecutive 'a' (breaking Condition2) which will be caught by the proposed solution

No sorting can be better than O( n logn)

2009-08-09T07:15:00.001-07:00

We all know that the sorting algorithms can't do better than O(n logn). Can you prove that a tighter lower bound is not possible.

Solution.

I found some cool solutions over the internet which i am posting.

1. The sort will compare the numbers and based on the outcomes of those comparison move the values around, with the net effect of all the moves being summarized by these arrows:

It cannot also run that same way on these inputs

2, 3, 4, 5, 1

because if it did the outcome would be

The execution must take a different path for every permutation of inputs. One can visualize all these executions as an execution tree. Each node is some action, either an assignment or a comparison; the tree branches after each comparison; each path from the root to a leaf is one execution of the program; and the height of the tree is the (worst-case) running time of the program

If the sorting program has to sort numbers it must reach the leaf doing comparisons finally.
Height of tree is log(n) where n- number of elements.
In this case the numbers of elements are all possible permutations of the input sequence which is n!

Height of tree having all permutations of input data out of which one is sorted is log(n!)

log (n * (n-1) * ... * 1) =
 log n + log (n-1) + ... + log 1

With reference to (http://en.wikipedia.org/wiki/Stirling%27s_approximation)

The above is O(n log n) as per http://www.crsr.net/Notes/BigO.html

k numbers in array of n numbers sum to T

2009-08-05T12:10:00.000-07:00

Given a set S of n integers and an integer T, give an O(n POW k-1 log n) algorithm to test whether k of the integers in S sum up to T.

Find max and min difference in unsorted numbers

2009-08-05T02:54:00.000-07:00

(a) Let S be an unsorted array of n integers. Give an algorithm that finds the pair that maximizes |x-y|. Your algorithm must run in O(n) worst-case time.

(b) Let S be a sorted array of n integers. Give an algorithm that finds the pair that maximizes |x-y|. Your algorithm must run in O(1) worst-case time.

(c) Let S be an unsorted array of n integers. Give an algorithm that finds the pair that minimizes |x-y|, for . Your algorithm must run in O(n log n) worst-case time.

(d) Let S be a sorted array of n integers. Give an algorithm that finds the pair that minimizes |x-y|, for . Your algorithm must run in O(n) worst-case time.

Posting Comment1 as solution for easier access

a. find max and min nos in the list. That is O(n). That itself is the pair that maximizes |x-y|

b. a[0] and a[n-1] is the pair if its a sorted list. so O(1)

c. sort the list[O(nlogn)] and see solution for d.

d. run through the list once and find the pair of consecutive nos with the least diff. O(n)

Find Number occuring exactly n/2 times

2009-08-03T02:59:00.000-07:00

You have an array of number/characters. Find if there is a number which occurs exactly n/2 times. All other characters in the set/array are distinct. Can you do it in log(n)

Using the distinct part as a hint here is a solution in O(n)

Assumption - All elements apart from the one occuring n/2 times is unique

Solution principle - If you find any two elements matching that's the solution.

Distribution of characters could be variant of following
1. b,c,d,a,a,a
2. a,b,a,c,d,a
3. a,b,c,a,a,d

Solution
--------
1. Compare consecutive elements if they match we have found the element occuring n/2 times.

2. Keep two ptr1 & ptr2 handy and store the two compared characters if they don't match.

3. Compare the third character (next one )with either two stored above.
If anyone matches then return
else
replace ptr1<-ptr2; ptr2<-current character 4. continue 2 &3

Number of comparisons

-------------------

We need to do atleast n/2 comparisons

Problem with above solution found by Madhur and mitigation.
--------------------------------------------------------------------------

The two pointer approach will not work for this data set :
a, b, c, a

We need 3 pointers :
ptr1 -> first element
ptr2 -> second element
ptr3 -> third element

while(end of array is reached) {
if(any one of ptr1/2/3's value is equal) {
then return the match
}
else
{
ptr1<-ptr2<-ptr3<-next element } }

Dividing array into groups

2009-08-02T10:56:00.001-07:00

Divide a list of numbers into groups of consecutive numbers but their original order should be preserved.

Example:
<8,2,4,7,1,0,3,6>

should be divided into two groups like this:
<2,4,1,0,3> <8,7,6>

Source : http://discuss.techinterview.org/default.asp?interview.11.770712.8

Sort on second key when, first key in a set is sorted

2009-08-01T05:41:00.001-07:00

Assume that we are given as input n pairs of items, where

the first item is a number
the second item is one of three colors (red, blue, or yellow).

Further, assume that the items are sorted by number. Give an O(n) algorithm to sort the items by color (all reds before all blues before all yellows) such that the numbers for identical colors stay sorted.

For example: (1,blue), (3,red), (4,blue), (6,yellow), (9,red) should become (3,red), (9,red), (1,blue), (4,blue), (6,yellow).

Find if summation of numbers from two lists is given number

2009-08-01T04:04:00.000-07:00

Problem: Given two lists A & B define an algo, which will identify two numbers 'a' and 'b', such that a + b = x, where 'x' is the input.

Find a number occuring > n/2 times in an array

2009-07-07T23:25:00.000-07:00

You are given an array of numbers/characters. A number/character occurs more than n/2 times. Find the number in 0(n) time O(1) space and one pass of array?

Array - a b a c a a a

Solution - Drawing parallels assume you have a room of 100 people who need to vote and the candidate wins iff 51 votes are under his name. Hypothetically if we ask people to bash the other person if he is not voting for the same candidate.

People voting for 'b' will bash people voting for 'a' and in return get bashed.
Since 'a' has 51% majority, 1 person voting for 'a' would be last man standing here.

a b a c a a a
|
a:0

a b a c a a a
|
a:1

a b a c a a a
|
a:0

a b a c a a a
|
a:1

a b a c a a a
|
a:0

a b a c a a a
|
a:1

a b a c a a a
|
a:2

a b a c a a a
|
a:3

Find change in sequence of digits

2009-05-02T04:43:00.000-07:00

For a sequence of digits like this

0000000000000000000001111111111111111........

given that

the sequence is a stream - so full length is not known
no '0's will appear after a '1'

What algorithm would efficiently find the change point - i.e. the point where '0's stop and '1's start?

Breaking mxn chocolate into 1x1 pieces

2009-05-02T04:08:00.000-07:00

We need to break a n/n bar of chocolate into 1 x 1 pieces? How many cuts will you have to make (horizontal or vertical) if

stacking of pieces is allowed
stacking is not allowed (neither side of a bar / piece)

Source : http://gurmeetsingh.wordpress.com/puzzles/

optimal implementation for LRU(least recently used) caching

2009-04-13T12:30:00.000-07:00

What be the most optimal way/data structure to implement LRU caching.

Requirements

--------------------------

Let's say i want to design a cache which adheres to the following requirements

1. Should grow upto infinity(bounded by runtime size, eg: in JAVA jvm size)
2. When the system runs out of memory all the entries except the top 'n' used should be flushed out.
3. get() and add() operations in cache should work in O(1)

Why not use WeakHashMap provided by Java?

---------------------------------------------------------------
1. Weak Hash map stores soft references to keys and not values. Then using Reference Queues the values are removed from the MAP.
2. Since our SOFT CACHE is infinite in nature and considering that most of the time memory used by VALUE part in cache is larger we want to store weak references to values and not keys. Eg: in a photo sharing site my key could be 'eventId' and value could be 'photos'

Code Details/File Explanation

--------------------------------------
1. Can be found at ->http://datastructure-puzzles-codesolutions.blogspot.com/2011/03/design-and-optimal-lru-cache.html
2. Direct Downloads available at ->https://github.com/inders/datastructure-repo/tree/master/LRUCache/src

Solution/Approach

--------------------------

1. Soft References in JAVA provide mechanism to create soft references to a heap area which (reference along with heap area) can be gc'd if it's reachable by soft references. We'll use this in designing our SOFTCACHE which will infinite entries.

2. To address requirement[2] above we'll create a hard Cache of top 'n' entries being used. Store strong references to heap areas in Hard Cache for top 'n' entries. This woul restrict gc from collecting them.

3. get and add shuffle around the data structures designed to give a O(1) time complexity. The following picture shows the details.

Notation in the figure below
1. SV1 - soft reference to value1
2. HV1 - hard reference to value1
3. HEAP - JVM heap

Merge k Sorted Arrays

2009-03-01T21:31:00.000-08:00

Posted By - madankumarrajan

Problem - Given K sorted arrays, there are 2 ways in which you can get one complete sorted array:

Solutions-

Let arrays be A1, A2,...Ak

Way 1:
Merge (A1, A2), (A3, A4),...
Then there are k/2 sorted arrays now.
Repeat the above procedure to get the full array sorted.
This way wont work as the memory we can use is limited.

Way 2:
Form a min heap from the first element of all the k arrays. Extract the min element. It is the min element among all the arrays. Now take the next element from the array from which the min element has come, and put it in the min heap. Repeat the procedure.

find optimum path between 2 words in a dictionary

2008-07-21T10:26:00.000-07:00

You have a dictionary of 1000 words each of 3 chars. Given 2 words you have to find the optimum path between the 2 words. The optimum path contains the words in the dictionary each word at a distance of 1 from the previous word.

for eg source = cat , target = sun

path is

cat -> bat -> but -> bun -> sun

given all these words are in the dictionary

Worm Travails

2008-06-11T04:52:00.000-07:00

A rubber string is 10 meters long. A worm crawls from one end to the other at 1 meter/hr. After each hour the string stretches to become 1 meter longer than it's last length.Will it reach the end ?

GCD question

2008-03-05T02:04:00.001-08:00

Prove the GCD of 2 numbers is equal to the GCD of the sum of the numbers and their LCM i.e. if numbers are A and B then GCD(A,B) = GCD(sum(A,B),LCM(A,B)).

A Lock with Grid of Switches

2008-02-13T08:45:00.000-08:00

There is a lock which is an N by N grid of switches. Each switch can be in one of two states (on/off). The lock is unlocked if all the switches are on. The lock is built in such a way that, if you toggle some switch, all the switches in its row and its column toggle too.

Give an algorithm which, given N and a configuration of the N^2 switches, will tell you whether the lock can be unlocked by a sequence of switch toggles.

Note 1: Can be done in O(N^2) time and O(1) space.
Note 2: You just need to tell if a sequence which unlocks the lock exists (and not the actual sequence)

Number is even or odd

2008-02-13T00:06:00.001-08:00

Figure out if a number/integer is even or odd without using the division operator.

sms suggest

2008-01-29T09:06:00.000-08:00

you have to implement sms suggest feature in mobile. The suggest feature is one which suggests valid words when we press the keys once for any of the letters the key represents. for eg 2 represents a/b/c and 6 represents m/n/o, pressing 2,6 will suggest an, am , bo (eg bolder is a valid word)..etc. So if you have a dictionary of words how will you store this on the mobile optimally so that storage is minumum and the running time to fetch the valid words is minimum?

position of string in a dictionary

2008-01-24T09:50:00.000-08:00

A dictionary consists of words having the restriction that c[i] > c[i-1]. i.e character at ith positionis lexicographicaly greater than than character at i-1th position. eg abcd

given a string how do we find it's position in the dictionary?

eg a = position 1 , ab = position 27

pill puzzle

2008-01-19T05:28:00.000-08:00

You are on a strict medical regimen that requires you to take two types of pills each day. You must take exactly one A pill and exactly one B pill at the same time. The pills are very expensive, and you don't want to waste any. So you open the bottle of A pills, and tap one out into your hand. Then you open the bottle of B pills and do the same thing -- but you make a mistake, and two B pills come out into your hand with the A pill. But the pills are all exactly identical. There is no way to tell A pills apart from B pills. How can you satisfy your regimen and take exactly one of each pill at the same time, without wasting any pills?

Find element in row and column sorted matrix

2008-01-09T01:36:00.000-08:00

You are provided a n*n square matrix which has elements as both row and column sorted.
Suggest an algorithm to find and element in the best possible time complexity.

Probability of point lying close to circumference than centre

2008-01-08T08:49:00.000-08:00

You have a circle with radius r. What is the probability that a point lies more towards the circumference than towards the centre.

Solution
Probability of point lying close to circumference would be mean point is in the circle with area from r/2 from center till outside in the figure below it would be in blue part of the circle.

Probability = Area covered by circle from point r/2 towards circumference/ Area of the circle

In the above given circle formula would be = Area of blue circle/ Area of circle
= pi r pow 2/ 4 / pi r 2 = 1/4

Number placement on dice for equal probability sum

2008-01-08T01:58:00.000-08:00

You have a dice which has numbers from 1..6.
Another dice is provided to you empty; you need to place numbers on this dice so that whenever both dices are used there is an equal probablity of getting a sum between 1.. 12

Solution::
Totally there are 6*6 possible combinations from two dices. Since we need the sum from 1..12 with equal probability there should be three combinations among these 36 which sum up to each number in 1 to 12 to achieve a equal probability for all sums.

Other Dice Numbers Presently _ _ _ _ _ _

Getting 1 we need 0 on the other dice
Getting 12 we need 6 on the other dice

State of Numbers on other dice now 0 6 _ _ _ _

We need to get SUM=1 in three different combinations and only possibility is 1 and 0 on both dices so put two more 0's on second dice and we have three ways to get 1.

State of numbers on other dice now 0 6 0 0 _ _

Now all the sum's from 7 to 12 can be achieved with one of the numbers be 6 and using the other numbers from first dice. Eg:: 7 can be 1 and 6 from dice 1 and dice2 and if we put two more sixes in dice2 then again 1 and other 6's on dice2 give us 3 ways for seven
Similarly for 8 we can 2 from dice1 and the three sixes one by one we will have 3 ways for 8 and so on for all numbers from 7 to 12. Again we can use the three 0's on dice2 in the similar way we have used three sixes above for getting three ways for sum 1 to 6.

State of numbers on other dice now 0 6 0 0 6 6

Find the median in a continous stream of numbers

2008-01-04T10:51:00.000-08:00

You are given a stream of numbers which can be positive or negative. You are required to provide an operation FIND MEDIAN..which when invoked should be able return the median of the numbers in stream (in sorted order) in O(1) time.

Eg: 0 1 2 3 4
Right FIND MEDIAN returns 2 as median

Now input is -2 -4
So Stream = 0 1 2 3 -2 -2 -4
Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1

Working JAVA CODE https://github.com/inders/datastructure-repo/tree/master/medianInContinousStream/src

SOLUTION

1. Store the data in BST.
2. Store additional information at each node i.e. number of nodes in left subtree and number of nodes in right subtree. These can be updated on insert and delete operations in O(h) where h is the height of tree.
3. To find rank of any node in the tree use the following algorithm.

Index of a node is it's position as in a inorder traversal of a binary search tree At each node you can calculate it's rank as sizeof(left subtree of current node) + 1

Challenge:: This calculation becomes a problem once you move deep in a right subtree as it's rank should include rank of previous ancestors and it's left subtrees

Easier approach is the following -
   -------------------------------------------
    Rank of Node = (Number of nodes in left subtree) + 1
       Check k against rank of root
    if k == rank(root)
       return
       if ( k < rank(root))
       go in left subtree of root
       Till you are going in left subtrees you can calculate rank using above formula
    if the rank you are looking for is > than rank of current node then you move to right subtree
    and look for new rank = (Rank you are looking - rank of currentNode( as these many nodes you have already considered and are less than the rank you are looking)
    The above helps in not carrying forward any information when you move to right subtree and you look for a node with a smaller index in the right subtree

Merge k sorted lists with total n elements

2008-01-01T09:35:00.000-08:00

You are given k sorted lists with total n inputs in all the lists devise a algorithm to merge them into one single sorted list in O(n logk)

Solution:

1. First take two lists at a time and merge them so total elements parsed for all lists =O(n)
This operation results in k/2 lists
2. Repeat steps till k/2 == 1.

Time complexity of above solution = O(n logk)
Step1 would loop through logk times and each operation would require parsing all n elements in all the lists for making k/2 lists

eg:: if i had 8 lists then first pass would make 4 lists by parsing all n elements; second pass would make 2 lists by parsing again n elements and third pass would give 1 list again by parsing n elements.

Constraint of the above Solution
For merging we would require O(n) extra space.

Solution2: Without Using O(n) extra space; uses O(k) extra space
j = 1;
1. (For all lists L[i])
{
Take the jth element from each list and create a min heap in O(k) with the node data and
index information. Take the minimum element from the heap in O(1) i.e. root node and put
it in List1 indexj.
if the element didn't belong to list1[j] then swap it with list1[j] with list to which the min
element belonged.
Now increment the pointer j for the list l1(or to the list where in the min nodes are getting added) and add the new node to min heap
}
2. Keep repeating steps 1 till all n elements are being looked up

Time Complexity = O(n logk ) SPACE = O(k)
At a time we have k elements min heap and for all n elements we have to readjust the heap in log(k) time so total time = O(n logk ) and space used = O(k)

Find max viewed pages

2008-01-01T08:47:00.000-08:00

Design an algorithm to find out efficiently the maximum number of used pages.

Solution:
Take all the input stream and build a max heap in (n log n) time.
Then the topmost element of the heap is the one with maximum viewed pages.
Each insertion in the heap happens in (log n) time since we need to check all non-leaf
nodes on each insertion that the heap property is satisfied. And in a binary tree with
n nodes there will (logn) non-leaf nodes.

However the tight upper bound of creating a MAX heap is O(n). So this can be done in O(n).

Proof of Tight asymptotic bound

1. A binary heap with n elements will have a height of log(n); being a complete binary tree.
2. A binary heap with n elements has atmost n/2 pow (h+1) nodes of height h
3. Time required to build a MAX heap is O(h) when called on a node of height h; since it needs to check all non-leaf nodes from height h to MAX (height of heap).
4. for (n = 0; n <= log(n); n++)
{
n/2 POWER (h+1) O(h)
// All nodes at height h wil require O(h) time
}// Total we have to go though all non leaf nodes i.e. LOG(n) SO LOOP is like this.

O ( n( h/ 2 POWER h))
for (n = 0; n < = infinity; n ++)
{
h / 2 pow h is a constant
}
so total time complexity = O(n)

Data Structure for snake and ladder game

2008-01-01T08:42:00.000-08:00

Data Structure to be used for playing snake and ladder game

Solution:

1. Use an array representation of 1..100
2. each a[i] contains value (i+1) if no snake or ladder is there
a[i] contains the value > i and the value pointed by the ladder; if a[i] has a ladder starting
a[i] contains value < i; if a[i] is a snake mouth

3. Create the above array depending on the board structure.
4. Generate two random numbers MOD 100 and use them to take a chance.

To insert.delete, find and return the order of input

2007-12-19T02:58:00.000-08:00

Design a data structure which can support the following operations optimally.

1. Insertion

2. Deletion

3. Finding an element.

4. Returning the elements in the order in which they came as input.

Note:: A singly linked already does these O(n) i am looking for something better than that.

Dictionary valid permutations of a Word

2007-12-16T23:00:00.000-08:00

A string say "bat" is provided then design and algorithm to give all valid dictionary words possible with characters 'a', 'b', 't'.

Assumption :: If you need a dictionary to get valid english words then you are free to design the dictionary in the best possible way which reduces the time complexity of your problem.

Solution
======

1. Design a dictionary in the form of hash table with the following algorithm as a one time activity.
for(all valid words in (English))
{
tmp = Sort(word);
key = hash(tmp);
store(key, word);
}

Let's run through the above algo with "bat"
after sorting "bat" becomes "abt"; store "bat" in the hash key returned for "abt".
Now say another valid permutation of "bat" is "tab", after sorting becomes "abt"..store "tab" in
the same hash key as a list.

Now our data structure looks like the following
key - > "bat" ---> "tab"

2. Assume know our function to give the valid combinations of a word recieves "bat" as input
tmp = sort("bat")
// tmp = "abt"
key = hash("abt")
//key contains the pointer to list "bat" ---> "tab", just printing the entire list gives us this combination in O(1)

3. How do you design a hash function so that all combination's of 'bat' go to one hash key and no other word like 'bay' go the same, else it would result in a bug in functionality.
Weight 'a' ...'z' with prime numbers, hash function would be a product of corresponding primes..using the property of primes that it always has unique factors, no 2 primes would have different numbers giving the same product.

Create two lists with minum difference of their sums

2007-12-10T23:13:00.000-08:00

You have a list of numbers say 1 to n in unsorted fashion. Create two lists such that the difference in sum of numbers in each sublist is minimum.

Case 1: Both the lists can have equal number of numbers in them.

Case 2: Both lists can have unequal no. of numbers in them. (Harder)

Assume our list is 5, 20, 6, 4, 200

Solution for case 1:
===============
1. Sort the list in O(n(log(n))
//Now list is 4, 5, 6, 20, 200

2. Take two pointers
ptr1= start of list
ptr2 = end of list

3. flag = false;
while(ptr1 != ptr2)
if(flag == false)
Take [ptr1] and [ptr2] and put it sublist1.
flag = true;
else
Take [ptr1] and [ptr2] and put it sublist2.
flag = false;
ptr1++;
ptr2--;

Output
======
Sublist1 = 4, 200
sublist2 = 5, 20, 6

Solution2: for Case 2:
===============
1. Sort the list we get 4, 5, 6, 20, 200
2. Take the maximum number i.e. last and put it in sublist1
//sublist1 = 200
3. Take numbers from start and keep putting in sublist 2 till
the sum of all matches to the sum of sublist1.
Once the sum in sublist2 > sum(sublist1) start adding a number
in sublist1 and so on.

Output =
Sublist1 = 200
sublist2 = 4, 5, 6, 20

Sort number's in a HUGE file.

2007-12-10T23:10:00.000-08:00

You have a file with 10 numbers in random order; and a computer with memory which can read only five numbers at a time in RAM. You have to sort the numbers in best possible time complexity.
You can assume your input file is
2 6 6 8 12 10 14 16 20 18

Let’s Do Lunch

2007-11-27T23:47:00.000-08:00

A nice puzzle to solve :

http://www.coudal.com/lunch.php

Implement String1-String2 operation

2007-10-25T02:54:00.000-07:00

Set Theory operation on two strings
str1= apple
str2=pie

str1-str2 = (All elements of str1 which are not in str2)

Answer in above case = al

Reverse Linked list with Single Pointer

2007-10-24T23:05:00.001-07:00

Can you reverse a singly linked list in O(n) time with a single pointer.

Find unique number; when all have dup's except one.

2007-10-24T22:53:00.000-07:00

2n+1 numbers in a list except for 1 num all had duplicates, how to
find out that num in O(n)

Find two no's in an array whose sum =X

2007-10-02T23:47:00.000-07:00

We are given an array of size N with random numbers between any range and give a number x.

Find in O(n) time and O(1) space a pair of numbers form the array whose sum is equal to x.

Source :: Amazon

Solution:: If the array is sorted there is a solution in O(n) time complexity.

Suppose are array is
2, 5, 20, 50, 85, 90

And our asnwer is 70, so output should be= 20, 50

1. Take two pointers with the following positions
ptr1= (start of array)
ptr2=(end of array)

2. Add both the elements at pt1 and ptr2
tmpsum= arr[ptr1] + arr[ptr2];

3. if (tmpsum > answer)
{
// decrement ptr2(larger pointer..since it points to a bigger number)
ptr2--;
}
else
{
//tmpsum is too small for the answer increment ptr1( which is presently pointing to a smaller number)
ptr1++;
}

4. Repeat step2 and step3 till ptr1 != ptr2 (if both pointers meet and sum is not found then it's not in the array)

Example
Arr= { 2, 5, 20, 50, 85, 90}
answer = 70
arr[ptr1]=2
arr[ptr2] = 90
tmpsum = 92
tmpsum > 70..so decrment ptr2;

arr[ptr1]= 2
arr[ptr2]=85
tmpsum = 87
tmpsum > 70...decrement ptr2;

arr[ptr1]= 2
arr[ptr2]=50
tmpsum =52
tmpsum <>arr[ptr1]= 5
arr[ptr2]=50
tmpsum =55
tmpsum <>arr[ptr1]= 20
arr[ptr2]=50
tmpsum =70
tmpsum == 70..so return ptr1 and ptr2.

Time Complexity of above solution = O(n)
Space Complexity = O(1)

Search for a friend in optimum time

2007-10-02T23:24:00.000-07:00

You are standing at a crossing from where there emerge four roads extending to infinity. Your friend is somewhere on one of the four roads. You do not know on which road he is and how far he is from you. You have to walk to your friend and the total distance traveled by you must be at most a constant times the actual distance of your friend from you. In terminology of algorithms, you should traverse O(d) distance, where d is the distance of your friend from you.

Find k-th largest in two sorted arrays

2007-09-13T03:46:00.001-07:00

Find kth largest element in two sorted arrays.

Can there be a solution better that O(k)

Solution 1
=========

Suppose input array's are in the following fashion
A[] = {2, 3, 7, 12, 27, 81, 91}
b[] = {1, 25, 32, 74, 89}

1. Take two pointers ptr1 and ptr2 at start in A[] and B[]
2. if(A[i] > B[j])
j++;
else
i++;
3. if ( (i +j ) == k)
compare A[i] and B[j] and return the larger of them
else
repeat step2.

Time Complexity = O(k)

Solution2
==========

Idea = We have to find the median of first k elements of A and B and k = 5

1. The kth largest among the union of A[] and B[] would be in the first k elements of of A[] and b[]
2. Consider k elements from A[] and B[] which results in the following array
a[] = {2. 3, 7, 12, 27}
b[] = {1, 25, 32, 74, 89}
3. Compare (A[mid], B[mid])
if (A[mid] is GT)
{
For ArrayA = We can skip a[mid]..a[k] elements since a[mid] is greater and all elements from a[0]..a[mid] are valid candidates for being the median; since A[mid] is the greater element no point considering bigger elements than that for the median
For Array B = We can skip b[0]...b[mid] elements since b[mid] is less; so all elements less than are not valid candidates for being median.
}
4. Repeat Step3 till you are left with either 2 or 3 elements then you do a comparision and find kth largest.

Time Complexity = O(log k)

Example showing Solution 2
=========================

A[] = { 2, 3, 7, 12, 27}
B[] = {1, 25, 32, 75, 89}

After step2 i.e. k elements from both arrays
A[mid] = 7 and B[mid] = 32

B[mid] is Greater.

Now array becomes after step3
a[] = {7, 12, 27}
b[] = { 1, 25, 32}

a[mid] = 12 and b[mid] = 25
After step3 the arrays become
a[] = { 12, 27} -- skpping the left portion of smaller element array
b[] = { 1, 25} -- skipping the right portion of larger element array

Now a[mid] = 12 and b[mid] = 1
after step3 the array becomes
a[] = {12}
b[] = {1,25}

Find the median of 12, 1, 25 in O(1) which is 12 which is the 5th largest

Easy One :: How many matches to decide winner

2007-09-12T02:27:00.001-07:00

Suppose there are 125 tennis player for a tournamet. How many matches would be required to decide a winner.

Serialize a binary tree

2007-09-04T14:12:00.000-07:00

How do you serialize a binary tree to send it across a channel ?

Repositing 0's and 1's in array

2007-08-26T13:18:00.000-07:00

you are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY.

input array:
{0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 }
output array:
{0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 }

Represent 0 to 31 on two dices

2007-08-09T00:13:00.000-07:00

You have two dices which are cubes..now i want you to represent all dates of a month starting from 01..31. What would the numbering on the dices look like.

Note:: The method used is more important in this case than the answer.

Find the nth number with m binary 1s

2007-08-03T01:29:00.000-07:00

There is a series of numbers in ascending order. All these numbers
have the same number of binary 1s in them. Given the number of 1 bits set in
the numbers, write an algorithm/C program to find the nth number in
the series.

Ternary Operator

2007-08-02T00:51:00.000-07:00

Represent x ? y : z as function :
int myternary(int x, int y, int z);
One can use ONLY ~ ! ^ & + | << >> . But no - or * or if-else.

PS: Have we had this puzzle on this blog before? If so , sorry for reposting it.

Managers and Engineers

2007-08-01T23:31:00.000-07:00

** This is a well known puzzle and does not reflect my prejudices :)
The FBI has surrounded the headquarters of the Debacle corporation. There are n people in the building. Each person is either an engineer or a manager. All computer files have been deleted, and all documents have been shredded by the managers. The problem confronting the FBI interrogation team is to separate the people into these two classes, so that all the managers can be locked up and all the engineers can be freed. Each of the n people knows the status of all the others. The interrogation consists entirely of asking person i if person j is an engineer or a manager. The engineers always tell the truth. What makes it hard is that the managers may not tell the truth. In fact, the managers are evil geniuses who are conspiring to confuse the interrogators.

Under the assumption that more than half of the people are engineers, can you find a strategy for the FBI to find one engineer with at most n-1 questions?

Is this possible in any number of questions if half the people are managers?

Once an engineer is found, he/she can classify everybody else. Is there a way to classify everybody in fewer questions?