Amazon Interview Question
Backend DevelopersCountry: United States
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()
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;
}
}
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")
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:
Test code:
- prudent_programmer March 19, 2018