Cover image for Google
Logo
See All Photos
Best Places to Work 2020

Google

Engaged Employer

Google

Add an Interview

Interview Question

Software Engineer Test Interview

-

Google

Phone interview 1 : a) Simulate a Queue with stacks ? b)Find repeated occurrence of character in a string ? Phone interview 2 : a) Given a 2D matrix of numbers find the position of number . Constraints of matrix number always in increasing order left to right and top to bottom . b)When should version control be used . And a tricky discreet math problem ?

Interview Answers

13 Answers

2

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 .

Interviewee on

2

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?

ellemeno on

1

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

Anonymous on

1

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.

Interviewee on

1

@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.

ellemeno on

1

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 on

1

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 on

1

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

Anonymous on

1

Did they ask you any work culture questions? Why google, etc? I think they see a culture fit too. I guess they evaluate that over questions in lunch .

Interviewee on

1

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); } }

neakor on

1

Sorry, Log m + log n

Anonymous on

0

Answer to 1b in C++11: list findDupes(string s) { list ret; map m; for(char c : s) { m[c]++; if(m[c] == 2) { ret.push_back(c); } } return ret; }

Ryuho on

1

Wow, a lot of questions: 1. a) Something like this: public class StackBasedQueue { private final Stack store; public StackBasedQueue() { this.store = new Stack(); } public void addToTail(final Integer v) { this.store.push(v); } public Integer popHead() { final Stack temp = new Stack(); 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(); } }

neakor on

Add Answers or Comments

To comment on this, Sign In or Sign Up.

Google Careers

Cover image for Google

​​We strive to provide Googlers and their loved ones with a world-class benefits experience, focused on supporting their physical,...More

  • Where we work
  • Building belonging
  • Googler stories
  • Build your future
This is the employer's chance to tell you why you should work for them. The information provided is from their perspective.