Amazon Interview Question
1. Implement a method that verifies if one string can be constructed by another. E.g: "aaabc" can be constructed by "aaabbbccd"
2. Given a linked list containing numbers (Node element), implement a method that returns two lists: one containing even numbers and one odd numbers - without allocating new list elements.
Interview Answers
public static boolean containsInAnyOrder(String container, String containee) {
HashMap map = new HashMap();
char currentKey;
Integer currVal;
int i;
for (i = 0; i < containee.length(); i++) {
currentKey = containee.charAt(i);
currVal = map.get(currentKey) == null ? 1 : map.get(currentKey) + 1;
map.put(currentKey, currVal);
}
for (i = 0; i < container.length() && !map.isEmpty(); i++) {
currentKey = container.charAt(i);
currVal = map.get(currentKey);
if (currVal == null)
continue;
if (currVal == 1) {
map.remove(currentKey);
continue;
}
map.put(currentKey, currVal - 1);
}
return map.isEmpty();
}
void segregateEvenOdd()
{
Node end = head;
Node prev = null;
Node curr = head;
/* Get pointer to last Node */
while (end.next != null)
end = end.next;
Node new_end = end;
// Consider all odd nodes before getting first eve node
while (curr.data %2 !=0 && curr != end)
{
new_end.next = curr;
curr = curr.next;
new_end.next.next = null;
new_end = new_end.next;
}
// do following steps only if there is an even node
if (curr.data %2 ==0)
{
head = curr;
// now curr points to first even node
while (curr != end)
{
if (curr.data % 2 == 0)
{
prev = curr;
curr = curr.next;
}
else
{
/* Break the link between prev and curr*/
prev.next = curr.next;
/* Make next of curr as null */
curr.next = null;
/*Move curr to end */
new_end.next = curr;
/*Make curr as new end of list */
new_end = curr;
/*Update curr pointer */
curr = prev.next;
}
}
}
/* We have to set prev before executing rest of this code */
else prev = curr;
if (new_end != end && end.data %2 != 0)
{
prev.next = end.next;
end.next = null;
new_end.next = end;
}
}
public static boolean canBeConstructed(String a, String b)
{
if( a == null || b == null)
return false;
int i = 0;
boolean visited = false;
for(int j =0; j < b.length(); )
{
if(i == a.length())
return true;
if(a.charAt(i) == b.charAt(j))
{
++i;
++j;
visited = false;
continue;
}
else
{
i = 0; //start all over again
if(visited)
{
++j;
}
visited = !visited;
}
}
if(i == a.length())
return true;
return false;
}