## 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
rev = longestCommonSuffix(str1, str2)
printLL(rev) # Outputs 'i->n->g->'

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

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

if head is None:
else:
tempNode = Node(value)

# Creates a new LL and returns the head
# instead of modifying it in place
stack = []
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

counter = 0
while head != None:
counter += 1
return counter

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

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

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.

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.

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

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

ListNode node2 = new ListNode("f");

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;
}

}``````

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")``````

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.

### 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.