Interview question: Find the intersection of two linked lists(corrupt)

So the question assumes that there are two linked lists with two heads h1 and h2 but they end in the same location. It's like a Y shape.

So our quest is now to find out the intersected node (red node). The linked lists can be of any length and need not necessarily have same number of nodes. So the above list can have 50 nodes and below only 5.

I had this question for an in person tech screen and since I do not know the answer/idea before it was pretty difficult for me. So here's how my brainstorming went

1. So the lists can be either like 5,4 or 4,4 or 4,5 nodes. So a simple approach of
   
   1. while(cur1!=cur2){
      

      cur1=cur1.next;
      

      cur2=cur2.next;
      

      }
      

      Would not work.
      

2. The only distinguishing factor for the red node is that it has two links pointing to it.
   
3. So if we can have a mechanism to identify the parent links of each node then we can find the red node
   
   1. Hence create a hash table with node and parent links
      
   2. But this approach would waste a lot of space and I know from gut feeling that this would not be an elegant solution.
      
   3. As expected my interviewer doesn't want this approach
      
4. Have two pointers one fast and one slow and try to find if they merge
   
   1. For this my interviewer said this is not a cycle detection problem.
      
   2. I knew that and I was just trying to get a feeling if it could work
      
5. Now I am desperate I mumbled something with bit vector and mapping each node to a bit vector
   
   1. Now he laughed sarcastically
      
6. I felt that this is not going my way at all but there is nothing at this stage than to try all the approaches that I come up with.
   
   1. How about finding the lengths and may be this could help
      
   2. As soon as I said this he asked me to write code for this.
      
      1. I was skeptical but as soon as I started writing code I realized the trick for this problem
         
7. We have to make sure that both heads are at the same distance from the intersection point
   
   1. With this insight I got the solution – traverse both lists and find lengths- lenght1, lenght2.
      
   2. Whichever is larger move it length1-length2 times.
      
   3. Now use the first code snippet to find the intersection.
      
8. After I wrote the code I said it was not clean and wanted to refactor because it has duplication and I didn't handle case where length1 is lesser than lenght2.
   
   1. He allowed me to do that and I got code in less than 10 lines! And two helper functions.
      
9. After I written code we discussed test cases and where the code would fail, for example if there is no intersection or one list ends prematurely.
   

Urgh! Though I was able to solve this problem I felt very uncomfortable during the interview process, I mean I was being insulted or smirked at when I am trying to brainstorm a solution. Well whatever I got the answer. I only wished that I knew the solution before as many folks on career cup did if nothing but to save the embarrassment. So here goes the code.

public
ListNode findIntersection(ListNode h1,ListNode h2){

if(h1==h2)//this also handles both null case

return h1;

if(h1==null ||h2==null)

return
null;

ListNode cur1=h1;

ListNode cur2=h2;

int length1=findLength(cur1);

int length2=findLength(cur2);

if(length1>length2)

cur1=moveList(h1,length1-length2);

else
if(length2>length1)

cur2=moveList(h2,length2-length1);

while(cur1!=cur2){

cur1=cur1.next;

cur2=cur2.next;

}

return cur1;

}

private ListNode moveList(ListNode h1, int times) {

for(int i=0;i<times;i++){

h1=h1.next;

}

return h1;

}

private
int findLength(ListNode cur1) {

int count=0;

while(cur1!=null){

count++;

cur1=cur1.next;

}

return count;

}

Update: So even after my heroic solving of this problem, I got rejected. Well I don't know what to say.

Also there are 6 approaches to solve this - http://exclusiveminds.com/2010/03/05/write-a-function-to-get-the-intersection-point-of-two-linked-lists/

How do edit column wise in an editor

As a programmer I google a lot for code snippets. A very prevalent problem is to copy code and to remove the line numbers. Its not always possible to copy code without the line numbers, so how do you go about deleting them?

For example code like this - http://www.java-examples.com/simple-java-treemap-example

Many sites either offer an option to copy just the code but some don't.

I have several solutions, what's your approach?

Interview question: Convert a sorted doubly linked list to Binary Search Tree.

This question has special meaning for me because I was asked this question back in April 2009 by Windows Azure team and I was not able to create a working code then. As a result I didn't get an offer. Today I thought of cracking this code and worked in for a few hours and successfully got a working running solution! I tried to search for a curt answer to this question but could not find exact code but only the idea. Idea is simple

Get to the middle of linked list and make it the root of the tree, then do the same for the left and right half's of the linked list iteratively.

The code that I jotted down in the first 5 minutes is exactly all that needed for this to work. Though during my walk through I convinced myself that it wouldn't work and needed extra logic for checking if a node already exists in tree.

    BinarySearchTreeNode createBST(DoubleLinkedList dll, int start, int end) {

        BinarySearchTreeNode root=null;

        if(start<=end){

            int mid=(start+end)/2;

            DoubleLinkedListNode cur=dll.getNode(mid);

            root=new BinarySearchTreeNode(cur.item);

            root.leftChild=createBST(dll, start, mid-1);

            root.rightChild=createBST(dll,mid+1,end);

        }

        return root;

    }

The second version I had with extra logic.

BinarySearchTreeNode createBST(DoubleLinkedList dll, int start, int end) {

        BinarySearchTreeNode root=null;

        if(start<=end){

            int mid=(start+end)/2;

            DoubleLinkedListNode cur=dll.getNode(mid);

            if(cur.visited)

                return root;

            else

                root= new BinarySearchTreeNode(cur.item);

                cur.visited=true;

            root.leftChild=createBST(dll, start, mid-1);

            root.rightChild=createBST(dll,mid+1,end);

        }

        return root;

    }

Recursion works in mysterious ways. I am still not entirely clear why we don't the extra logic but we don't J . Recursion is really mysterious!

For this code actually work there is lot of boiler plate that's needed, which I give below. In it one I liked is overriding the toString() method so that eclipse debugger is able to show the string and System.out.println(node) works.

package com.code.prolificcoder;

//To covert a sorted doubly linked list to binary search tree

class DoubleLinkedListNode{

    int
item;

    DoubleLinkedListNode next;

    DoubleLinkedListNode prev;

    public DoubleLinkedListNode(int item) {

        this.item=item;

        next=null;

        prev=null;

    }

    @Override

    public String toString(){

        StringBuilder sb=new StringBuilder();

        if(this.prev==null)

            sb.append("X--");

        else

            sb.append(this.prev.item+"--");

        sb.append(this.item);

        if(this.next==null)

            sb.append("--X");

        else

            sb.append("--"+this.next.item);

        return sb.toString();

    }    

}

class DoubleLinkedList{

    int
size;

    DoubleLinkedListNode head;

    public DoubleLinkedListNode getNode(int num){

        if(num<0)

            return
null;

        DoubleLinkedListNode cur=head;

        int i=0;

        while(cur!=null){

            if(i==num)

                return cur;

            i++;

            cur=cur.next;            

        }

        return cur;

    }

}

class BinarySearchTreeNode{

    int
item;

    BinarySearchTreeNode leftChild;

    BinarySearchTreeNode rightChild;

    public BinarySearchTreeNode(int item) {

        this.item=item;

        leftChild=null;

        rightChild=null;

    }

    public BinarySearchTreeNode(){}

    @Override

    public String toString(){

        StringBuilder sb=new StringBuilder();

        if(this.leftChild==null)

            sb.append("X--");

        else

            sb.append(this.leftChild.item+"--");

        sb.append(this.item);

        if(this.rightChild==null)

            sb.append("--X");

        else

            sb.append("--"+this.rightChild.item);

        return sb.toString();

    }

}

 

public
class DLLtoBST {

    public
static
void main(String args[]){

        DoubleLinkedListNode d4=new DoubleLinkedListNode(13);

        DoubleLinkedListNode d3=new DoubleLinkedListNode(11);

        DoubleLinkedListNode d2=new DoubleLinkedListNode(9);

        DoubleLinkedListNode d1=new DoubleLinkedListNode(7);

        DoubleLinkedListNode d0=new DoubleLinkedListNode(3);

        d0.next=d1;d0.prev=null;

        d1.prev=d0;d1.next=d2;

        d2.prev=d1;d2.next=d3;

        d3.prev=d2;d3.next=d4;

        d4.prev=d3;d4.next=null;

        DoubleLinkedList dll=new DoubleLinkedList();

        dll.head=d0;

        

        DLLtoBST db=new DLLtoBST();

        

        BinarySearchTreeNode root =db.createBST(dll,0,4);

        System.out.println(root);

        System.out.println(root.leftChild);

        System.out.println(root.leftChild.rightChild);

        System.out.println(root.rightChild);

        System.out.println(root.rightChild.rightChild);

    }

 

    private BinarySearchTreeNode createBST(DoubleLinkedList dll, int start, int end) {

        BinarySearchTreeNode root=null;

        if(start<=end){

            int mid=(start+end)/2;

            DoubleLinkedListNode cur=dll.getNode(mid);

            

            root=new BinarySearchTreeNode(cur.item);

            root.leftChild=createBST(dll, start, mid-1);

            root.rightChild=createBST(dll,mid+1,end);

        }

        return root;

    }

    

}

 

Interview question: Find if word exists in a crossword

In my preparation for google interview, I thought I should go over some problem in career cup and I found this crossword problem pretty interesting. In my mock interview yesterday I later found a simpler solution using an intuitive recursion, so I thought I should try this problem.

The problem statement is:

Given a puzzle of letters/ characters e.g.

a e r o p s

b h a r l s

w r i s l o

a s n k t q

Write a function to which this puzzle and a word will be passed to test whether that word exists in the puzzle or not.

e.g. rain and slow will return true. rain is present in the second column and slow in the third row wrapped around.

 

This problem reminded me of maze exploration which can be done recursively and I started coding in that mode.

• First I would have a main recursive function which checks if the first word matches
  

  private boolean stringFinder(char[][] ar, String str) {
  

          int size=ar.length;
  

          if(str.length()>size+1) return false;
  

          int k=0;
  

          char[] charArray=str.toCharArray();
  

          for(int i=0;i<size;i++)
  

              for(int j=0;j<size;j++)
  

                  if(ar[i][j]==charArray[k])
  

• If matches recursively check all the four directions
  

  return isMatch(ar,charArray,i,((j+1)%size),k+1)||
  

                      isMatch(ar,charArray,((i+1)%size),j,k+1)||
  

                      isMatch(ar,charArray,((i-1)%size),j,k+1)||
  

                      isMatch(ar,charArray,i,((j-1)%size),k+1);
  

• In each of the directions again search for a match. (this is wrong)
  

  private boolean isMatch(char[][] ar, char[] charArray, int i, int j, int k, Direction dir) {
  

          int size=ar.length;
  

          if(k==charArray.length-1)
  

          {
  

              if(ar[i][j]==charArray[k]) return true;
  

              else return false;
  

          }
  

          if(ar[i][j]==charArray[k])
  

              return isMatch(ar,charArray,i,((j+1)%size),k+1)||
  

                      isMatch(ar,charArray,((i+1)%size),j,k+1)||
  

                      isMatch(ar,charArray,((i-1)%size),j,k+1)||
  

                      isMatch(ar,charArray,i,((j-1)%size),k+1);
  

          }
  

          return false;
  

      }
  

  I verified this approach and it was working with pen and paper. So I opened up eclipse with a jolly mood and though I am a genius.
  

But there were several mistakes

• When the inevitable happened- the program is not responding as expected, I found that I am searching in all direction after I found a direction. So I modified my approach to include a direction enum.
  
• And tried to change i and j values based only on the direction. This time I got the directions wrong and it took a while to overcome it.
  
• Then I got the problem of comparing next recursion when I wanted to be in the current one. So I changed the order.
  
• Finally I got the result when I send in "rain" and the output is true ! And then I again checked for "slow" and magic it returned true!!
  
• But when I am sending in a string that does not exist I am getting an exception. Reason: I am sending in negative indexes.. Even though I am wrapping i and j values I forgot to take of –ve signs.
  

  So finally my code became like this
  

  
   

  package com.code.prolificcoder;
  

  
   

  public class StringFinder {
  

      enum Direction{up,down,left,right};
  

      public static void main(String args[]){
  

          char[][] ar=new char[][]{{'m','s','s','h'},
  

                                   {'a','t','c','i'},
  

                                   {'p','d','a','n'},
  

                                   {'s','a','t','h'},
  

                                  };
  

          String str="tcia";
  

          StringFinder sf=new StringFinder();
  

          System.out.print(sf.stringFinder(ar,str));
  

          }
  

  
   

      private boolean stringFinder(char[][] ar, String str) {
  

          int size=ar.length;
  

          if(str.length()>size+1) return false;
  

          int k=0;
  

          char[] charArray=str.toCharArray();
  

          for(int i=0;i<size;i++)
  

              for(int j=0;j<size;j++)
  

                  if(ar[i][j]==charArray[k])
  

                      return isMatch(ar,charArray,i,Math.abs((j+1)%size),k+1,Direction.right)||
  

                      isMatch(ar,charArray,Math.abs((i+1)%size),j,k+1,Direction.down)||
  

                      isMatch(ar,charArray,Math.abs((i-1)%size),j,k+1,Direction.up)||
  

                      isMatch(ar,charArray,i,Math.abs((j-1)%size),k+1,Direction.left);
  

          return false;
  

      }
  

  
   

      private boolean isMatch(char[][] ar, char[] charArray, int i, int j, int k, Direction dir) {
  

          int size=ar.length;
  

          if(k==charArray.length-1)
  

          {
  

              if(ar[i][j]==charArray[k]) return true;
  

              else return false;
  

          }
  

          if(ar[i][j]==charArray[k]){
  

              if(dir==Direction.down)
  

                  i=Math.abs((i+1)%size);    
  

              else if(dir==Direction.right)
  

                  j=Math.abs((j+1)%size);    
  

              else if(dir==Direction.left)
  

                  j=Math.abs((j-1)%size);
  

              else //dir==Direction.up
  

                  i=Math.abs((i-1)%size);
  

          
  

              return isMatch(ar,charArray,i,j,k+1,dir);
  

          }
  

          
   

          
  

          return false;
  

      }
  

  
   

      
   

      
  

  }
  

  
   

  It took me more than 2 hours to get this version, in an interview you are not given this many chances and a compiler and a debugger. I should be able to correct my bugs in walkthroughs, all in all scary.
  

  Update: My tester wife found another bug in this code. Whenever there is a search for a char that is present twice I am returning the result of the first one which could be false but the later could be true.
  

  For eg: "scat" in the above it will return false because the first match for s resulted in false and I returned it. To solve this I update the code as follows.
  

private
boolean stringFinder(char[][] ar, String str) {

        int size=ar.length;

        if(str.length()>size+1) return
false;

        int k=0;

        boolean found=false;

        char[] charArray=str.toCharArray();

        for(int i=0;i<size;i++)

            for(int j=0;j<size;j++)

                if(ar[i][j]==charArray[k])

                    found= isMatch(ar,charArray,i,Math.abs((j+1)%size),k+1,Direction.right)||

                    isMatch(ar,charArray,Math.abs((i+1)%size),j,k+1,Direction.down)||

                    isMatch(ar,charArray,Math.abs((i-1)%size),j,k+1,Direction.up)||

                    isMatch(ar,charArray,i,Math.abs((j-1)%size),k+1,Direction.left)||found;

        return found;

    }

How not to do a technical phone interview

Today I had a phone screen from a good startup from NY, even though at the time I felt I aced the interview on second thoughts I think I will not hear back from them. I actually took the call from skype and used a tool called call burner to record my performance.

After going through it I am not impressed at all, its not a tough interview but I managed to stumble or blunder couple of times.

Ok, listing my mistakes in order of worstness and why I made them.

1. Got the technical question completely wrong. The question is "How would you reverse a string without using a for loop". To be honest I was expecting a simpler question this question kind of got be off guard. So, I asked if I can use a while loop, he goes to say that I can't use a iterator. Then I got this idea of swapping start and end pointers until start <= end and he did not object to it. But on later thoughts I think he gave up on me, what he is actually looking for a recursion based solution. Its not simple or intuitive but a recursive solution can be made.
2. What is the difference between abstract class and interface, I have been asked this question probably 5 times in an interview now and I can't explain why I stumbled today. I was talking about implementing an abstract class etc.. while the main difference is in how many of them a class can use. A class can have multiple interfaces but can only have one parent class. Though I knew it I didn't say it.
3. I didn't get the company website before the interview, I actually didn't understand so I couldn't look at it.

I did some things ok and explained somethings good but overall it was an uninspiring performance. All in all I think it will be miracle if I am invited to onsite.

So what went wrong

1. I didn't take time when I have to a)while solving the problem b)while constructing sentences. I really don't understand my rush during the phone interview.
2. I am not getting the attitude of its ok to pause before attempting to say something. It creates a bad impression to mumble something than to pause a while and say something more coherent.

I hope I learn from this experience and would do better in future interviews.

Get a landline at your computer with google voice + skypein + regular phone

I have an iPhone and on the AT&T network. Even though I live in a city that has huge population of highly paid professionals AT&T signal in my house sucks. I have to go out to make a phone call and sometimes words just cut off. At the same point during different times of the day I will have different signal ranging from 0-5. I even did badly in one phone interview due to my damned iPhone and AT&T. Hence started my quest to solve this problem.

Attempt #1

I tried calling AT&T and explaining my problem. They simply don't care and my bad singal reception is due to the building materials of house. Their recommendation - buy a signal booster. So in addition to the m

oney I spend for the monthly bill I have to buy an additional device just to make the phone work? This is stupid.

Attempt #2

The next option I tried is to get a landline phone and use it as a home phone. This is the traditional(and age old) approach of doing things. First I checked the prices and AT&T, comcast are just out of proportion. Though quest had a decent plan with $13/pm and no contract and other strings, I can make only local calls without additional bill. Local means only numbers in my area code, this does not include even my cellphone, so this is not an option either.

Attempt #3

Since I am paying $50 for the internet connection anyway I thought I should be able to use the newer technologies out there to solve my problem.

I have Skype installed but their calling features are not cheap and you don't get a dedicated number. Though Skype has excellent VOIP call quality it doesn't work alone for me. I can' ask people to call me on skype handle :)

Attempt #4

I already have a google voice account and I am using it to get a local number and to route to my cell phone. Google voice is one of most useful products by Google and has many advanced features that try to mimic the features of email to a phone number. Features like call forwarding, online voice mail, voice mail transcripts, number blocking etc makes you feel like you this is the next evolution of the phone. But for me this does not solve the problem because even though google voice routes the calls the signal is crappy on my cell phone. There used to be a service called Gizmo which offers a free number that integrates perfectly with google voice. So some one can call you on the google voice number, which routes to gizmo and you can pick calls from there. But unfortunately Gizmo is now out of service or rather in

development of newer features and has been acquired by Google. So there is some hope for this nice integration but that's not going to happen anytime soon.

Attempt #5

So my quest has now become to create a online number that I can use in conjunction with Google voice. I've searched several services for this - VOIP buster etc they are not free. One service that's free works with extension number is ring2skype.com it works as expected with extension but google voice can't press extension numbers so this too does not work.

Final breakthrough

My solution came in when I decided to some money for getting a number. So I used SkypeIN to get a number. The actual number is irrelevant as long as it is a US number. I use it only for rerouting through google voice. So I paid $18 for three months and got a number. I added this number in my google voice phones. And made this number receive calls first. So whenever I get a call on my google voice number, it gets routed to

skypeIn number, which then routes to skype, so I can enjoy speaking over skype at my computer.

The setup requires to spend some money but it is totally worth it! Once again the steps

1. Download Skype.
2. Buy an online number from Skype
3. Add a phone in google voice using this number
4. Install google voice plugin for chrome (optional)
5. Make calls from your desk by clicking on the phone number and selecting SkypeIN
6. Talk from your computer
7. Receive calls on your computer through skype.

Another reject from Microsoft SDET

Today I again got a reject in the tech screen for SDET in Microsoft. Of course I am angry and thinks that the rejection is unjustified but here I am striving make a honest journal of what actually had gone wrong.