How to pass a technical interview for a fresh Software Engineering role?

Today two guys asked me about how to pass an interview for a Software Engineering position (as I was offered SE jobs from Palantir and Google, and failed at tons of others). My answer was simple: think hard of a good solution and speak out loud what you are thinking, try to code without bugs, know how to test it and know what you are talking about, especially different data structures.

What I mean by “know” is that you should be able to explain the concept in a simple way and to answer most of the questions related to the concept.

To give an example, in an interview question, you can be asked: “Given a stream of sales: (item_id, number_of_items), how would you recommend a top N best-selling items”. Then be prepared to expect the conversation to be like:

Possible Question: how do you solve the problem?
Possible Answer: I use a max heap to remain the order of items with most sales. For any query, I return the top N items out of the heap. It takes O(NlgK) where K is the number of items in the heap.
Possible Question: How do you update the heap when a new tuple is received?
Possible Answer: For each tuple received from the stream, I update the counter of item_id in the heap, it takes O(lgK).
Possible Question: How do you know which node in the heap to update?
Possible Answer: In order to know which node to update in the heap, I use a hashmap item_id->node_id to keep track of where the item is located in the heap.
Possible Question: How does a hashmap work?
Possbile Answer: It keeps a list of linked list of (key, value). For lookup/modification, it uses the hash function of the key to locate the linked link, then iterates through the linked list to search for the key or add the new item to the linked list.
Possible Question: Implement a hashmap?
Possible Answer:
class HashMap(object):
def put(k, v):
….
def get(k):
….
Possible Question: How to remain O(1) for get/put?
Possible Answer: Keep the hash function of the key to be uniformly distributed.
Possible Question: What happens when the number of items is larger than the size of the list.
Possible Answer: I double the size of the list. Then, redistribute the items to the new list based on the hash(key) % list.size
Possible Question: How do you design the hash function?
Possible Answer: Do s.t like this: f(x)=(((31+x.t1)31+x.t2)31+x.t3) as suggested in Effective Java by Joshua Bloch.
Possible Question: Why do you choose 31?
Possible Answer: Because 31 is prime
Possible Question: Why do you choose a prime number?
Possible Answer: Assuming k=abf(x)=(((ab+t1)ab+t2)ab+t3)f(x)=(((abab+t1ab+t2)ab+t3)=(((ababab+t1abab+t2ab+t3)).    Then, (t1=a,t3=abab)  collides with (t1=1,t3=aabab). Hence, the less factors k has, the less collisions can happen.
Finally, interviewer will possibly say “cool”. Other possible questions include “how does the heap work?”, “implement a heap”, “what if I want top N-items in only last week”, “how to get top N from the heap in O(NlgN)”, “how does arraylist work?”, “implement LRU”,…

Make sure you know when interviewing for a grad level role:
  • Data structures: array, vector, trees, queue, stack, heap, hashmap, treemap.
  • Algorithms: sorts, recursive programming, dynamic programming, string matching, basic Graph algorithms (BFS, DFS, Dijkstra).
  • Concurrency: forking, deadlock, mutex, semaphore, Map/Combiner/Reduce.
  • Memory allocation and garbage collection.
  • Sql, database transaction and different isolation levels.
  • Bit operations: |, &, ^, <<, >>.
  • How disk works (seek, read, write).
  • Maintainability: different design patterns, git/svn, service-oriented architecture.
  • Scalability: load balancers, cache, proxy, index, shards, queue, replication.
  • Availability: share-nothing architecture (so SPOF), eventual consistency, RAIDs.
  • Consistency: vector clock, CAP theorem, FLP theorem, different levels of consistency, 2 phase, 3 phase commit, names of some concensus algorithms, consistent hashing, gossip protocols.
  • Basic concrete maths and probability.
  • Zen of Python (my bonus ;)).
Places to practice: Leetcode, Careercup, Glassdoor. Topcoder and Codeforces for more advanced algorithms.

Apart from technical performance, make sure you are polite, humble, and clear. Despite all of these effort, you still may fail for some unknown reasons. Not all interviewers are looking for the same thing or there will be other people who can do better than you. Just try your best and move on.

12 comments :

Amirtha rao said...

Nice post! I always preferred blogger to get ideas, because its provides more information over the books & here I gathered more precious skill from the professional, thanks for taking your to discussing this topic.
Regards,
Best JAVA Training in Chennai|JAVA Training

Priya R said...

Excellent post!!!. The strategy you have posted on this technology helped me to get into the next level and had lot of information in it.
cloud computing training in chennai | cloud computing courses in chennai

vensika said...

Great blog with useful information. Thanks for sharing such a nice blog. Kindly keep updating like this article. Software Testing Training in Chennai | Selenium Training in Chennai

Deshma Teja said...

Good post. I had read your blog, it's very nice and informative content.. Web Designing Training Institute in Chennai | Web Designing Training Institute in Velachery.

Siva Seo said...

Good post..Keep Sharing.! I'm working in brave technologies private limited.

Mehgna Sharma said...

Nice post Thanks for the Sharing this information Big Data Hadoop Training | PHP Training in Noida

prabash said...

Awesome blog., Java Training in Chennai | Dot Net Training in Chennai

rupesh rupi said...

Wonderful blog. I will gained more information from your post..Selenium Training Institute in Chennai | Selenium Training Institute in Velachery.

praveen said...

Nice Blog..Thanks for sharing..


Linux Training in Chennai | No.1 Linux Training Institute in Chennai | Red Hat Linux Training in Chennai | Online Linux Training in Chennai

revathi said...

Excellent post. I have read your blog it's very interesting and informative.Java Training Institute in Chennai | Java Training Institute in Velachery.

Webtrackker Sohit said...

Sas Training Institute in Noida-Webtrackker is the best sas training institute in noida. SAS has taken the lead role for a long time, where most companies have standard software. While you have this certification under your belt, give big rewards to the IT industry, it can also serve as an important payer on the business side of the economy. SAS can read data files created by other statistical packages. Therefore, for experienced users of these statistical packages, SAS does not threaten to create data files created by these packages in a SAS file format.
Sap Training Institute in Noida
PHP Training Institute in Noida
Hadoop Training Institute in Noida
Oracle Training Institute in Noida
Linux Training Institute in Noida
Dot net Training Institute in Noida
Salesforce training institute in noida
Java training institute in noida

ASO Services said...

Good post and I like it very much. By the way, anybody try this increase app downloads? I do not how to use.