Interview Question for Software Engineer Test at Google:

Wow, a lot of questions:
1. a) Something like this:

public class StackBasedQueue {
    private final Stack<Integer> store;

    public StackBasedQueue() {
        this.store = new Stack<Integer>();
    }

    public void addToTail(final Integer v) {
        this.store.push(v);
    }

    public Integer popHead() {
        final Stack<Integer> temp = new Stack<Integer>();
        while(!this.store.isEmpty()) {
            final Integer v = this.store.pop();
            temp.push(v);
        }
        final Integer head = temp.pop();
        while(!temp.isEmpty()) {
            final Integer v = temp.pop();
            this.store.push(v);
        }
        return head;
    }

    public int size() {
        return this.store.size();
    }
}

1. b) Something like this: O(n) runtime.
    public void findRepeats(final String str) {
        this.map.clear();
        final char[] array = str.toCharArray();
        for(int i = 0; i < array.length; i++) {
            final Character c = array[i];
            Integer count = this.map.get(c);
            if(count == null) {
                this.map.put(c, 1);
                continue;
            }
            count++;
            this.map.put(c, count);
        }
    }

For a) further challenge was to simulate a double ended queue , but we ran out of time . you could maintain temp stack as permanent variable and get around doing that.

b) Kind of sort of what I wrote I was asked to optimize even further , so I said XOR the array make a note of elements left , remove from original list and you have set of repeated elements .

2a.

My idea is to first identify the column that might contain our element, then use binary search to see if our element is in that column. The column that might contain our element is the rightmost column where the first row's element is less than or equal to our target element.

int[] matrixSearch(int[][] m, int numRows, int numCols, int target){
           int[] firstRow = m[0][]; // not sure this works, can just use for loop to populate
           int targetCol = findWhichCol(firstRow, 0, numCols-1, target);
           int targetRow = findWhichRow(m[][targetCol], 0, numRows-1, target);
           if (targetRow == -1) {
                        return null; // Element not found
           }
           return new int[] { targetRow, targetCol};
}

int findWhichColumn(int[] a, int low, int hi, int target) {
    int midIndex = (hi+low)/2;
    int mid = a[midIndex];
    if (mid > target) {
           return findColumn(a,low,midIndex-1,target);
    }
    while (mid <= target && midIndex < a.length-1) {
            midIndex++;
            mid = a[midIndex];
     }
     return midIndex--;
}

int findWhichRow(int[] a, int low, int hi, int target){
     int midIndex = (low+hi)/2;
     if (midIndex == target) {
                return midIndex;
     }
     if (hi-low == 0) return -1; // Element is not in the matrix
     if (midIndex < target) {
               return findWhichRow(a,midIndex+1,hi,target);
     }
     return findWhichRow(a,low,midIndex-1,target);
}

Average: O(log n)
Worst: O(n/2) = ~ O(n)

This isn't very elegant. How would you do it?

@above:
I think the run time is log(n)*log(m)

Sorry, Log m + log n

for 2a you had to describe the properties of the matrix , the diagonal elements have some unique properties which you can recognize . So a good start is initialize the search from of the corners of the non leading diagonal . and yes iterative or divide and conquer from thereon after.

@Anonymous

That's correct, but this part:

    while (mid <= target && midIndex < a.length-1) {
            midIndex++;
            mid = a[midIndex];
     }

makes it O(n) in the worst case. Right?

@Interviewee

Thank you for the additional explanation. You seem quite qualified. Is there a particular reason you think you weren't given a offer? Did any one interview go poorly? It's a little worrying to look through these interview reports and see so many apparently intelligent people not receive offers. I recently passed my phone interview and am waiting to schedule my on-site. As much as I agree with hiring only the best, I'm finding it difficult to feel optimistic in light of the evidence on this site. Thank you for sharing your experience.

Why I didn't get it ? don't know I am still in school , I applied for an internship and
they said I am qualified enough for full time since I work along with school .

I think I answered everything well (they said so themselves ... ) but there is the economy , a bit of this
http://valleywag.gawker.com/5392947/googles-broken-hiring-process
and the fact that I am not a states resident and I guess they didn't see any quality in me which they couldn't find locally . Big school names also count for a bit more at a place like Google .

Do your best , and be calm and composed , being nervous won't help.

For the program 2a you want to manipulate both indices at the same time to get a (logN) running time.

Why I didn't get it ? don't know I am still in school , I applied for an internship and
they said I am qualified enough for full time since I work along with school .

I think I answered everything well (they said so themselves ... ) but there is the economy , a bit of this
http://valleywag.gawker.com/5392947/googles-broken-hiring-process
and the fact that I am not a states resident and I guess they didn't see any quality in me which they couldn't find locally . Big school names also count for a bit more at a place like Google .

Do your best , and be calm and composed , being nervous won't help.

For the program 2a you want to manipulate both indices at the same time to get a (logN) running time.

@Interviewee:

Did they ask you any work culture questions? Why google, etc? I think they see a culture fit too.