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

Interview Answer

2 Answers

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

Add Answers or Comments

To comment on this, Sign In or Sign Up.