谷歌实习店面挂经

Job Hunting Interview
, , , , ,
1

第一轮
Given an starting String I had to determine if it was possible to change it to another String, changing only one character at the time. The only restriction was that every resulting word after any change had to be in a word dictionary. For example:

Start: abc
End: aaa
Dictionary: [abc,aac,aba,aaa]
Output: true

It is possible because it can follow this path abc->aac->aaa. I came up with a solution using BFS. It is very similar to https://leetcode.com/problems/word-ladder-ii/ .

At the end the interviewer asked me to ask her a few questions related to his experience. She was a great person.

第二轮

Started with a question asked the favorite project I have worked on. Then the question was hard to understand due too poor signal, but I was able to know what it was about.

Given an String I had to determine if it is possible to get to another String. The difficulty of this one was that when I changed a character to another, all the characters have to change. For example:

Start: bdcb
End: acea
Output: true
Steps:
b->a => bdcb->adca
c->p => adca->adpa
d->c => adpa->acpa
p->e => acpa->acea

Start: qqq
End: ade
Output: false

没做出来

2

报个我的

a variation of prefix evaluation:
Evaluate the below string:

( + 5 6 ( * 2 3 4( + 3 4…) 7 8) 123 456)

Operands can be of any digit length and oprators can be either + or -. Also, there can be any number of operands after an operator.

Approach: Stack based

I took a stack of strings and entered all operators and operands. Whenever a closing bracket is encountered, I pop till the top of stack is an operator and push in an array. I evaluate the array and push it on top of the stack after popping the operator.
On worst case, this will run in O(n^2) time. n for pushing in the stack and n to pop and evaluate the array.

3

Find the subsequences in the circular linkedlist.

Input: A->B->A->B

Answer - [1, 4, 2] Explanation ([A-B] has 2 subsequence, [A B A B] 4 , [A->B->A-B] 1 )

Input: A

Answer[1]

Input A->B->C->A

Answer [4, 1]