Problem Solving…

Memory related issues:

Multi-threading issues:

Debugging IO problems


 Google Interview Questions: Software Engineer

  • What is the difference between a mutex and a semaphore? Which one would you use to protect access to an increment operation?
  • Write a C program which measures the the speed of a context switch on a UNIX/Linux system.
  • Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.
  • Describe the algorithm for a depth-first graph traversal.
  • Design a class library for writing card games.
  • Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N.
  • You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?
  • Explain how congestion control works in the TCP protocol.
  • In Java, what is the difference between final, finally, and finalize?
  • What is multithreaded programming? What is a deadlock?
  • Write a function (with helper functions if needed) called to Excel that takes an excel column value (A,B,C,D…AA,AB,AC,… AAA..) and returns a corresponding integer value (A=1,B=2,… AA=26..).
  • You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it.
  • Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state.
  • You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36.
  • Describe the data structure that is used to manage memory. (stack)
  • What’s the difference between local and global variables?
  • If you have 1 million integers, how would you sort them efficiently? (modify a specific sorting algorithm to solve this)
  • Talk about your class projects or work projects (pick something easy)… then describe how you could make them more efficient (in terms of algorithms).
  • Write some code to reverse a string.
  • Write some code to find all permutations of the letters in a particular string.
  • What method would you use to look up a word in a dictionary?
  • There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).
  • There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random. Hint: 1. Use random function rand() (returns a number between 0 and 1) and irand() (return either 0 or 1) 2. It should be done in O(n).
  • Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M>> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm.
  • You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game. You need to tell the algorithm first and then need to write the code. Note: Some position may be blank in the game। So your data structure should consider this condition also.
  • You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*…*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed.
  • How do you put a Binary Search Tree in an array in a efficient manner. Hint :: If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise)Its not the most efficient way.
  • How do you find out the fifth maximum element in an Binary Search Tree in efficient manner. Note: You should not use use any extra space. i.e sorting Binary Search Tree and storing the results in an array and listing out the fifth element.
  • Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 … iN c1 c2 c3 … cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 … in cn
  • Given two sequences of items, find the items whose absolute number increases or decreases the most when comparing one sequence with the other by reading the sequence only once.
  • Given That One of the strings is very very long , and the other one could be of various sizes. Windowing will result in O(N+M) solution but could it be better? May be NlogM or even better?
  • Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one?
  • Given a binary tree, programmatically you need to prove it is a binary search tree.
  • You are given a small sorted list of numbers, and a very very long sorted list of numbers – so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?
  • Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?
  • Given a file of 4 billion 32-bit integers, how to find one that appears at least twice?
  • Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.
  • Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.
  • Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.
  • Given an array, i) find the longest continuous increasing subsequence. ii) find the longest increasing subsequence.
  • Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?
  • Write a function to find the middle node of a single link list.
  • Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.
  • Implement put/get methods of a fixed size cache with LRU replacement algorithm.
  • You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.
  • Distance is defined like this : If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))” Please give a solution in O(n) time complexity
  • Write a function that flips the bits inside a byte (either in C++ or Java). Write an algorithm that take a list of n words, and an integer m, and retrieves the mth most frequent word in that list.
  • Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one?
  • How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.
  • Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?
  • How long it would take to sort 1 trillion numbers? Come up with a good estimate.
  • Order the functions in order of their asymptotic performance: 1) 2^n 2) n^100 3) n! 4) n^n
  • There are some data represented by(x,y,z). Now we want to find the Kth least data. We say (x1, y1, z1) > (x2, y2, z2) when value(x1, y1, z1) > value(x2, y2, z2) where value(x,y,z) = (2^x)*(3^y)*(5^z). Now we can not get it by calculating value(x,y,z) or through other indirect calculations as lg(value(x,y,z)). How to solve it?
  • Given two linked lists, return the intersection of the two lists: i.e. return a list containing only the elements that occur in both of the input lists.
  • What’s the difference between a hashtable and a hashmap?
  • How would you reverse the image on an n by n matrix where each pixel is represented by a bit?
  • Create a fast cached storage mechanism that, given a limitation on the amount of cache memory, will ensure that only the least recently used items are discarded when the cache memory is reached when inserting a new item. It supports 2 functions: String get(T t) and void put(String k, T t).
  • What sort would you use if you had a large data set on disk and a small amount of ram to work with?
  • What sort would you use if you required tight max time bounds and wanted highly regular performance.
  • What is the size of the C structure below on a 32-bit system? On a 64-bit?

struct foo {

char a;

char* b;









Building Successful Products

All successful products:

  1. target well understood and defined customer and market segments
  2. solve need(s) that customers are willing to pay for
  3. have very clear and concise Customer Value Proposition (CVP)
  4. follow simple principles such as “vm centric”, “easy to use”, “scalable” which guides everyone involved with the product
  5. are built for the customers and validated by the customers during the entire development cycle
  6. often have “game changing” features on top of “table stakes” features. For example, “no data loss” is a table stakes for a storage solution and “linearly scalable” is a game changer
  7. follow “less is more” philosophy when adding features. Additional features are add-ons and not part of the core offering
    • Adding features adds complexity, adds customer support costs, adds maintenance costs and most importantly fewer people can figure out your product. In other words, adding non-necessary features adds distractions to everyone involved
  8. are built using a good balance of engineering-driven and customer-driven requirements
  9. Too much engineering-driven requirements may result in building products for wrong reasons. Few of these are:
    • let’s use the new technology as it will be fun using it,
    • let’s build the strongest encryption algorithm (AES-1024) as not one has developed it so far
    • I don’t understand what XYZ has implemented so let us build a new one
    • Too much customer-driven requirements may result in building product for few customers and for a wide range of customers
  10. meet the emotional needs of the customers.
    • These emotional needs of the customers become apparent only after investing time in talking to customers or observing them when they use it
  11. follow standards wherever customer don’t see any value in customization
    • Forcing customers to learn new way of doing something which is not solving any pain points is bad design