Amazon.com

www.amazon.com
Engaged Employer

## Interview Question

Software Development Engineer Interview Seattle, WA

# I only remember three of the technical questions I was

asked, in addition to the usual general questions about my experience, skills, and work: 1. write code to replace spaces in a string with a * character (don't just use .replace functions though, hehe) 2. given an array with values that increase, reach some max, then decrease, find the max in less than O(n) + test cases 3. given a linked list that represents two numbers (e.g., 1234 represented by 1->2->3->4 and 5678 rep by 5->6->7->8), add the numbers. singly-linked list
Tags:

0

1. Iterate over the character array and replace * with ' '
2. Use Binary Search:
public static int findMax(int array[]) {
int start = 0;
int end = array.length -1;
int val = -1;
if (array.length == 0) {
return Integer.MIN_VALUE;
}
while (true) {
int mid = (start + end) / 2;
if (start >= end) {

val = array[mid];
break;
}
else if (array[mid] > array[start]) {
start = mid;
}
else if (array[mid] > array[end]) {
end = mid;
}
}

return val;
}
3. Reverse both of the lists (in place reverse, O(n), no extra memory) and then add.

Amit on Dec 14, 2012
0

It seems that Amit's answer of problem2 has taken it as a rotated array, but actually not. the second half is a decreasing one, instead of an increasing from the min value.
So when we get the array[mid], we should compare it with its neighbors instead of two ends;
if array[mid] is in the increasing part, then max should be on the right;
and if in the decreasing part, then max should be on the left;

helloslz on Dec 28, 2013