Software engineering intern interview questions shared by candidates
how would you find the shortest path between two nodes in a social network?
do breadth first search from both ends at the same time. Keep a set of all nodes that each has reached. When the sets have any element in common, there is a path.
Does the above method have any advantage over the method in which we do bfs from one node of the nodes and stop when the other node is reached?
BFS from both sides is massively faster than just doing BFS from one. Suppose each person has k friends and that the two nodes are d apart. BFS from one node is O(k^d). BFS from both nodes is O(k^(d/2)) -- the exponent is half as big. To put some example numbers on it, if each person has 100 friends and they are 10 apart, then BFS from one node takes 10^20 operations, whereas BFS from both nodes is 2*100^5= 200 billion operations. BFS from one node is intractable. BFS from both nodes is slow, but tractable.
Write a function in Java that will take a sorted array of ints, possibly with duplicates, and compact the array removing all the duplicate numbers. That is, if the contains the numbers - 1, 3, 7, 7, 8, 9, 9, 9, 10, then when the function returns, the contents should be - 1, 3, 7, 8, 9, 10. Be sure your answer is as efficient as possible. Describe the efficiency of your algorithm using big O notation.
Say you have a single-column table of entries of variable size. Implement this table to also contain methods to lengthen one cell, cut a cell shorter, and to return which cell we're pointing at if given a certain distance from the beginning of the table. All methods need to be fast (assume a single-column table with many many entries).
See Interview Questions for Similar Jobs
- Software Engineer
- Software Engineer Intern
- Software Developer
- Senior Software Engineer
- Software Development Engineer
- Software Engineering
- Data Scientist
- Software Engineer New Grad
- Engineering Intern
- Technology Analyst