@JustVirtually This is purely based my experiences in my professional life, interviews and interactions with all kinds of engineers and managers.
Let me clear one thing, These are my own opinion. I am not stereotyping anything, neither to downgrade nor promote anyone/company. Having said that, I am sharing few points which should help someone to uncover unforeseen factors or might help to decide next move.
Social & Industry respect v/s your own Career growth. Make sure you have full idea what you will be working on.
No doubt Google has top reputation in CS world but every company will always have 0-100th level of work and you may end up working on trivial things (Its is really too idealistic to say "I will work my way to get best project", don't underestimate management & bureaucracy)
Never ever feel down by any interviewer: Even people working at Google are 'people'. Why: I was interviewed by a guy who could not even speak a complete sentence (May be language problem or what so ever), now imagine about interaction with such a guy! :) I was surprised to see such a person working at google. So believe me, interview can not decide your skills for Google everytime and you will understand the meaning of word 'luck'.
It is very important to decide what you want to from your career and work . Never choose based on name/salary of the company (I can say this after cracking Google, Amazon, Microsoft, Goldman Sachs) You may end up having work pressure, unexpected expectations which might lead to stagnant career. Best way is to research and having more interaction with different teams before you choose team at Google.
### my own code, run time is O(N*N)
def fourSum(self, nums, target):
:type nums: List[int]
:type target: int
length = len(nums)
d = dict()
for i in xrange(length):
for j in xrange(i+1, length):
val = nums[i] + nums[j]
if val in d:
d[val] = [(i,j)]
res = set()
for k in d:
val = target - k
if val in d:
vlist = d[val]
klist = d[k]
for (i,j) in vlist:
for (l,m) in klist:
ilist = [i,j,l,m]
if len(set(ilist)) != len(ilist):
mylist = [nums[i], nums[j], nums[l], nums[m]]
res.add( tuple(mylist) )
Clever but the running time doesn't decrease obviously. And the method is not general, just for 4 sum questions.
DFS handles an explicit tree.While Backtracking handles an implicit tree
Depth First Search is a special type of backtracking algorithmic design paradigm where the process of backtracking takes place in the leaf nodes. In case of backtracking,the algorithm also rejects the useless branch of the state-space tree.This is why DFS maintains the entire tree structure while Backtracking maintaines a pruned tree