Amazon Interview Question: I only remember three of the ... | Glassdoor

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
technical, algorithm, amazon

Interview Answer

2 Answers


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

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

Add Answers or Comments

To comment on this, Sign In or Sign Up.