Amazon Interview Question for Backend Developers


Country: United States




Comment hidden because of low score. Click to expand.
0
of 0 vote

Scan from end of the string and compare each character in the word. I assume that we are given a singly linked list and I also assume we are given helper functions such as reverseLinkedList(), insertAtBeginning, length(), etc. The idea is pretty straightforward, compare each character from end and if they are different break, else append the result. If there are no common characters which are suffixes, return the minimum length of the two linked lists. I present a solution in Python below. The time complexity is O(n) where n is the length of the longest suffix.

Solution:

def longestCommonSuffix(str1, str2):
  suffix = None
  str1rev, str2rev = reverseLL(str1), reverseLL(str2)
  str1Len, str2Len = getLengthofLL(str1), getLengthofLL(str2)

  while str1rev and str2rev:
    if str1rev.value != str2rev.value:
      break

    suffix = insertAtBeggining(suffix, str1rev.value)
    str1rev = str1rev.next
    str2rev = str2rev.next

  if not suffix:
    if str1Len < str2Len:
      return str1
    else:
      return str2
  else:
    return suffix

Test code:

# Test code
str1 = constructLinkedList('walking')
str2 = constructLinkedList('listening')
rev = longestCommonSuffix(str1, str2)
printLL(rev) # Outputs 'i->n->g->'

str3 = constructLinkedList('party')
str4 = constructLinkedList('partying')
rev = longestCommonSuffix(str3, str4) # Outputs 'p->a->r->t->y->'
printLL(rev)

- prudent_programmer March 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In case, some of you all want to test it, here are the helper functions I coded for my above solution:

class Node:
  def __init__(self, value):
    self.value = value
    self.next = None
    
def insertAtBeggining(head, value):
  if head is None:
    head = Node(value)
  else:
    tempNode = Node(value)
    tempNode.next = head
    head = tempNode
  return head

def reverseLL(head):
  # Creates a new LL and returns the head
  # instead of modifying it in place
  stack = []
  curr = head
  while curr != None:
    stack.append(curr.value)
    curr = curr.next

  newHead = curr = Node(None)
  while len(stack):
    elem = stack.pop()
    if curr is None:
      curr = Node(elem)
    else:
      curr.next = Node(elem)
      curr = curr.next
  return newHead.next

def getLengthofLL(head):
  counter = 0
  while head != None:
    counter += 1
    head = head.next
  return counter

def constructLinkedList(word):
  head = curr = Node(None)
  for char in word:
    if curr is None:
      curr = Node(char)
    else:
      curr.next = Node(char)
      curr = curr.next
  return head.next

def printLL(head):
  curr = head
  while curr != None:
    print(curr.value, end='->')
    curr = curr.next
  print()

- prudent_programmer March 19, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would say inverse and test for prefix is best to achieve. How ever reverse it in place, no auxiliary space to reverse and maybe mention to reverse it back after wards and note what this would mean for other concurrent accesses to that same structure.

- Chris March 20, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The problem can also be solved by pushing the values of LinkedList's into a stack
and in a loop check, if their top values are equal the count increase by one, top value is then poped else break and print count.

- Anonymous March 21, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The problem can be solved by pushing the values of linked lists into a stacks and checking each value by popping and printing the count whenever a mismatch occurs and exit

- Roy March 21, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class LongestListSuffix {

    static class ListNode {
        private ListNode next;
        private String value;

        public ListNode(String value) {
            this.value = value;
        }

        public void add(ListNode node) {
            if (next == null) {
                next = node;
            } else {
                ListNode current = next;
                while (current.next != null) {
                    current = current.next;
                }
                current.next = node;
            }
        }

        public String toString() {
            StringBuilder sb = new StringBuilder(value);
            ListNode current = next;
            while (current != null) {
                sb.append(current.value);
                current = current.next;
            }
            return sb.toString();
        }
    }

    public static void main(String[] args) {
        LongestListSuffix l = new LongestListSuffix();

        ListNode node = new ListNode("a");
        node.add(new ListNode("b"));
        node.add(new ListNode("c"));
        node.add(new ListNode("d"));
        node.add(new ListNode("e"));

        ListNode node2 = new ListNode("f");
        node2.add(new ListNode("c"));
        node2.add(new ListNode("d"));
        node2.add(new ListNode("e"));

        ListNode suffix = l.longestSuffix(node, node2);
        System.out.println(suffix.toString());
    }

    public ListNode longestSuffix(ListNode node1, ListNode node2) {

        node1 = reverse(node1, null);
        node2 = reverse(node2, null);

        if (!node1.value.equals(node2.value)) {
            return null;
        }

        ListNode suffixStart = node1;
        ListNode cur1 = node1.next;
        ListNode cur2 = node2.next;
        while (cur1 != null && cur2 != null && cur1.value.equals(cur2.value)) {
            suffixStart = cur1;
            cur1 = cur1.next;
            cur2 = cur2.next;
        }

        node1 = reverse(node1, null);
        node2 = reverse(node2, null);

        return suffixStart;
    }

    public ListNode reverse(ListNode node, ListNode prev) {
        if (node == null) {
            return null;
        }
        ListNode ret = reverse(node.next, node);
        ret = ret == null ? node : ret;
        node.next = prev;
        return ret;
    }

}

- Test March 21, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Swift,

func longetSuffix(str1: String, str2: String) -> String {
    let rev1: [Character] = str1.reversed()
    let rev2: [Character] = str2.reversed()

    var suffix = ""
    for i in 0..<min(rev1.count, rev2.count) {
        if rev1[i] == rev2[i] {
            suffix += String(rev1[i])
        }
    }
    
    return String(suffix.reversed())
}

longetSuffix(str1: "working", str2: "playing")

- takecian March 25, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More