Engineer Interview Questions | Glassdoor.ie

# Engineer Interview Questions

1,711

Engineer interview questions shared by candidates

## Top Interview Questions

Sort: RelevancePopular Date

### Software Engineer at Amazon was asked...

28 Dec 2010
 you have array with n elements. How would you do circular shift of k positions? Time and space complexity?6 AnswersMake a circular linklist, and move headpointer K position to do K shifts. It's O(n) time complexity. Space is contant. (circular link list).Well, space isn't constant because you took an array and then copied it somehow to a linked list. Remember, you were given an array? If I understand the question correctly, they're asking to do a circular shift of some range of values, like the first k values in an array of length n? So if you wanted to shift right, temp = array[k] from index=k to 1 array[index] = array[index-1] array = temp this would be O(k)? I mean, it would take k steps, but maybe it's somehow still O(n)oh, sorry, I misunderstood. Not k values, move everything k positions. Praveen Chettypally's answer works but the space complexity would be O(n) since there is a fully copy of the list? The simplest would probably be to make another array and copy in, starting at the (n-k)th element, going to the end, then starting at the beginning. A second array would probably be a better option than a completely different data structure. What if it has to be done in place? is there an O(n) solution?Show more responsesalright - http://stackoverflow.com/questions/876293/fastest-algorithm-for-circle-shift-n-sized-array-for-m-position shiftArray( theArray, M ): size = len( theArray ) assert( size > M ) reverseArray( theArray, 0, size - 1 ) reverseArray( theArray, 0, M - 1 ) reverseArray( theArray, M, size - 1 ) O(n) with no extra storage. Wish I could have thought of that one myself...I beieve this does the trick too: public static String shiftArray(char[] inputArray, int shiftLen) { assert(inputArray != null); int length = inputArray.length; assert(length > shiftLen); int moves = 0, from= 0, to = 0; char next, last; to = (from + shiftLen) % length; next = inputArray[from]; while(moves < inputArray.length) { last = inputArray[to]; inputArray[to] = next; next = last; from = to; to = (from + shiftLen) % length; moves++; } return String.valueOf(inputArray); }I tried the above function - shiftArray and the looks is not working: shiftItemsFromList class: class shiftItemsFromList{ public static String shiftArray(char[] inputArray, int shiftLen) { assert(inputArray != null); int length = inputArray.length; assert(length > shiftLen); int moves = 0, from= 0, to = 0; char next, last; to = (from + shiftLen) % length; next = inputArray[from]; while(moves < inputArray.length) { last = inputArray[to]; inputArray[to] = next; next = last; from = to; to = (from + shiftLen) % length; moves++; } return String.valueOf(inputArray); } } Part of the main function: System.out.println("Circle Shift N size array for M possitions:"); char [] array = {'a', 'b', 'c', 'd', 'e', 'f'}; shiftItemsFromList sh = new shiftItemsFromList(); String s = sh.shiftArray(array, 2); System.out.println("Print the Circle Shift N size array: " + s); System.out.println("DONE"); OUTPUT: Circle Shift N size array for M possitions: Print the Circle Shift N size array: cbadaf DONE

### Software Development Engineer In Test (SDET) at Microsoft was asked...

13 Feb 2012
 Given the root of a binary search tree, link all the nodes at the same level, by using an additional Node* level.2 AnswersStart 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); } }

### Software Development Engineer II at Microsoft was asked...

24 Mar 2009
 Find exist in maze or prove its non existence.3 AnswersYou 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"

### Technical Support Engineer at Citrix was asked...

28 Sep 2011
 if number of flowers in a garden doubles every day. garden became 100% full in day 100 in what day was the garden 50% full?3 Answers99'th dayyep!99

### Software Development Engineer at Amazon was asked...

23 Feb 2011
 difference between "hashing a string" and "encrypting a string". Then: is it possible to find two elements for which the hash is the same?3 Answersyou can't "go back" from a hash. You can go back from encription if you know the secret (say password, private key, whatever). Second question: yes but then you have a problem.1. Encryption uses a secret key while hashing does not require any key. Moreover, hash is one-way but encryption can be reversed by a decryption operation. 2. Yes, that's called hash collision, which although a low probability occurrence, does exist.Decryption of encrypted string is possible. But we cannot say same thing for hashing. Because hash is one way operation. Q2:Low probability, it is possible using brute force

### Software Engineer at Amazon was asked...

28 Dec 2010
 You have dictionary. How would you design function/system that should return true/false for check if a word is in a database? How would you scale your solution if word db does not fit in memory/disk? How would you scale it to really big db of words that should be located on n computers?2 AnswersYou'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.

9 Feb 2011
 Compute all the intersections of two sets of segments in a line.2 AnswersOnly 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

9 Feb 2011
 Given a set of cities, each with a given population, select randomly a city with a probability that is proportional to the population.2 AnswersGave 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