Compare keyboard events sequences


  • 1
    K

    You are given two lists, each list contains a sequence keyboard events typed by different users. For simplicity, lets assume the keyboard contains only alphanumeric letters and a backspace key.

    Example Input:
    L1: a, b, z, <BACKSPACE>, c
    L2 f, o, o, <BACKSPACE> (3x times), a, b, c

    You can see that running both sequences you end up with the string "abc" in your screen. The question is to write a method that will return true if an arbitrary pair keyboard sequences will produce the same output.

    I was able to very quickly come up with a O(N) space and time solution that creates a linked list from each sequence, every time we see a BACKSPACE char, we just remove from the head of the list. Then just compare the resulting linked lists node by node and return.

    As expected, my interviewer asked if we could do better than that, and besides the usual one-off optimizations like comparing the length of the output O1 and O2 before comparing all letters, saving memory by not creating new linked lists but writing in the input list itself, etc. I was not able to come up with something fundamentelly different from my original idea.

    SInce I also had to take time to write my code down on his laptop I cut off and went with the easy approach to gain time. Can someone tell whether there is a sublinear (time or space) solution for this problem?

    Thanks!


  • 1
    S

    For optimization for comparing lengths before even starting to compare the two lists, you need to calculate anyway no of backspaces which requires at least one pass through each list.
    So don't worry about that.
    I would use following approach which do not require a linked list.

    StringBuilder sb1 = new StringBuilder();
    Iterator it1 = L1.iterator();
    while ( it1.hasNext() ) {
        char nextChar = it1.next();
        if ( nextChar == BACKSPACE && sb1.length() > 0 ) {
             sb1.deleteCharAt( sb1.length() - 1 );
       } else {
            sb1.append( nextChar );
       }
    }
    Now go through L2 and construct a similar string.
    StringBuilder sb2 = new StringBuilder();
    int index = 0;
    while ( it2.hasNext() ) {
         char nextChar = it2.next();
         if ( nextChar == BACKSPACE && sb2.length() > 0 )
            sb2.deleteCharAt( sb2.length()-1 );
        } else  {
           sb2.append( nextChar );
        }
     } 
    
    return sb1 == sb2;
    

    Or a better appraoch as suggested by interviewer would be to modify the list as you go:

    ListIterator it1 = L1.listIterator();
    while ( it1.hasNext() ) {
        char nextChar = it1.next();
        if ( nextChar == BACKSPACE  ) {
             it.remove();
             if ( it.hasPrevious() ) {
                it.previous();
                it.remove();
            }
       } 
    }
    //Now go through L2 
    ListIterator it2 = L2.listIterator();
    while ( it2.hasNext() ) {
         char nextChar = it2.next();
         if ( nextChar == BACKSPACE  )
            it2.remove();
            if ( it2.hasPrevious() ) {
               it2.previous();
               it2.remove();
           }
        } 
     } 
    
    // At this point lists are pruned. Now compare the iterator-led-modified lists
    if ( L1.size() == L2.size() ) {
         it1 = L1.iterator();
         it2 = L2.iterator();
         while ( it1.hasNext() && it2.hasNext() ) {
             if ( it1.next() != it2.next() ) {
                return false;
             }
        }
    } else {
       return false;
    }
    
    return true;
    
    

    If you want to go for multithreading, you could actually run the pruning of two lists on two separate threads.

    t1.start();
    t2.start();
    t2.join();
    
    //then compare the lists.
    

  • 0
    K

    The multithread pruning would be something nice to mention in the interview indeed, nice catch.

    I was afraid I missed some kind of divide-and-conquer solution that would make this algo even faster, but as you mentioned there is no way to solve without searching for BACKSPACEs on both lists.

    It just occurred to me that another optimization could be to just skip all BACKSPACEs from the beginning of both lists since they wont have any effect on the final output.

    Thank you for looking into this!


  • 0
    C

    @svasa said in Compare keyboard events sequences:

    Iterator it1 = L1.iterator();
    while ( it1.hasNext() ) {
    char nextChar = it1.next();
    if ( nextChar == BACKSPACE ) {
    it.remove();
    if ( it.hasNext() ) {
    it.next();
    it.remove();
    }
    }
    }

    Can you explain this? For example, using this sequence of key presses:
    a, b, z, <BACKSPACE>, c

    Once the iterator reaches BACKSPACE, it would remove the BACKSPACE first. Then it does an next(), which means it's now on "c". It then does a remove(). Wouldn't your code be removing "c" from the iterator?


  • 0
    S

    @chuckywang You are absolutely right, it should look for the previous, I modified my code with a listIterator instead to look for previous and delete it. Thanks for the observation.


  • 2
    J

    I think you can go over the list backwards - whenever you see a BACKSPACE you skip a key until you see a valid input, then compare both sides. This will require O(n) time and O(1) space.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.