Software Engineer Interview Questions

Start from the root, put all the nodes in a queue, keep track of number of nodes at current level and at next level by counting, dequeue a node from the queue, put its left and right children in the queue by updating your counts, using your counts, connect the nodes at the same level. O(N) in both time and space.

Queue size is never larger than half+1 of the node count, just noting. Rough code: Queue q = new Queue(); q.Enqueue(root); int count = 1; int nextCount = 0; T prev = null; while (!q.Empty()) { T cur = q.Dequeue(); if (prev != null) { // doubly-link level siblings prev.rightSibling = cur; cur.leftSibling = prev; } count--; if (count == 0) { // next level count = nextCount; nextCount = 0; prev = null; } else { // same level prev = cur; } if (cur.Left != null) { nextCount++; q.Enqueue(cur.Left); } if (cur.Right != null) { nextCount++; q.Enqueue(cur.Right); } }

You need to write a code for finding shortest path in maze. For a recursion use call stack.

A-star algorithm perhaps?

Keep an structure (array / binari Tree/ hash table) to "remember" if a "node" has been use to avoid loop. Building a graph and nodes to navigate trough the maze and track back on your node until you reach your first node that have no more "start node" or you have found the "exit node"

You'd enter the words into a binary search tree, which should be able to search down to a word in log(n) time, with n being the total number of words. If your db doesn't fit on one PC, then you'd place subtrees on different machines and have a master index, indicating which machine had which letter or prefix. For example, if you had 26 machines available, you could put a piece of the tree that corresponds to a letter on each machine. You'd structure the tree so the top node was as close to the middle of the set of possible values on each machine. While this would take some preparation, you'd get fast searches and relatively easy insertions of new nodes.

For dictionaries that fit in memory, a hash table will suffice. For larger dictionaries, you can use a bloom filter backed by an on-disk b-tree. To scale to multiple computers, you can hash the search word and use a token ring to consistently determine which node that word would exist on, then on each individual node use the bloom filter and b-tree.

Only implemented the naive solution O(M x N) time, should have implemented a line sweeping algorithm.

int line1[line size] int line2[line size] int overlap[line size] for each segment in set1 for i = segment start to segment end line1[i]++ for each segment in set2 for i = segment start to segment end line2[i]++ for i = 1 to line size if line1[i] and line2[i] overlap[i] = 1

Gave a naive O(1) time O(population) space solution, then created a python generator that implemented what is requested in O(n_cities) worst-case time.

int size = 0 int city_range[] initialization for each city i city_range[i] = size size += population[i] selection generate random integer r ranging from 0 to size for i = 0 to n_cities if city_range[i] <= r and r < city_range[i] + population[i] return city i

Beware that the characters are in UNICODE. You can have irrelevant stuff in the resource file of a language (not hotkeys)

The software was ASP.NET so this was key.