Data structures Interview Questions | Glassdoor

# Data structures Interview Questions

117

interview questions shared by candidates

## Data structures Interview Questions

Sort: RelevancePopular Date

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

Jan 14, 2012
 Design an LRU cache1 AnswerThis was quite a difficult problem with answers ranging in runtime and data structures.

### Test Engineer at Qualcomm was asked...

Nov 19, 2010
 What are the differences between a linked list and an array? What are the pros and cons? What kind of situations would you use each in? Can a stack be a queue? Can a queue be a stack?1 AnswerLinked lists - objects with pointers to the next or previous object. Used mostly for sequential accesses. Array - a built in list accessed by an index. Better for random access. stack can be a FIFO queue, put two of the back to back. If the queue is a LIFO then it is a stack.

Jun 17, 2009

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

Apr 12, 2010
 How do you avoid collisions when multiple keys map to same hash value.1 AnswerChaining.

### Software Engineer at PayPal was asked...

Jan 20, 2012
 HashMap implementation1 AnswerIn C++, you can use a dynamic array with varying number of hash entries per row. The hash can be found by taking the modulo of the key. If a collision occurs, you can use linear probing by taking the modulo of (key + 1).

Nov 17, 2014
 Write a function that given a sequence and a number b between [-10,10] return a new sequence. Sequences are generated by this: http://en.wikipedia.org/wiki/Look-and-say_sequence a number b if equal to 0 the function will return the input sequence Valid sequences: 1 11 21 1211 111221 ... Example: input: 1211, +1 output: 111221 Example: input: 111221, -1 output: 12113 AnswersUsed recursion to generate sequences. Should be an iterative way to do the generation, but I was able to figure it out during the interview.See this problem on LeetCode: https://oj.leetcode.com/problems/count-and-say/static String look_and_Say_add_1(String num){ if(num==null) return null; StringBuilder sb = new StringBuilder(); char repeat = num.charAt(0); num = num.substring(1) + " "; int times = 1; for(char current: num.toCharArray()){ if(current==repeat){ times++; } else{ sb.append(times+""+repeat); times = 1; repeat = current; } } return sb.toString(); }

Nov 17, 2014
 main() { A() C() } A() { B() } B() {} C() {} input: t1 main enter t2 A enter t3 B enter t4 B exit t5 A exit t6 C enter t7 C exit t8 main exit output: main (t8-t1) A (t5-t2) B (t4-t3) C (t7-t6) Write a function that given the input will create the output1 AnswerI used a stack to solve the duration of functions, but wasnt able to solve how to do the indentation during the interview

### Software Engineer at Rent The Runway was asked...

Mar 28, 2013
 Create an application/program that lists all words in the English language that can be created using a set of random characters. Characters cannot be reused, words must use all characters in the set.1 AnswerCreate a hash function to map a words based on the character occurance to an array/HashMap. Solution should gives O(1) lookup.

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

Mar 6, 2014
 Implement a stack that supports push, pop and mode(the one from statistics) operation. Gave an O(log n ) push and pop and O(1) mode operation.Another good question was implement atoi function. I assumed it as base 10 but was asked to support from binary to any base numbers(even base 50).2 AnswersSolution to atoi function().It supports only base 10 operations. int atoi(char *str) { int is_negative = 0; int int_val = 0; /* Skip non digit characters excluding '-' */ while (!isdigit(*str) && (*str != '-')) { str++; } /* Number is negative */ if (*str == '-') { is_negative = 1; str++; } /* Compute the int_val for contiguous digits */ while (isdigit(*str)) { int_val = (int_val*10) + (*str - '0')%10; str++; } return ((is_negative) ? (int_val * -1): int_val); }how you get a O(log n) of push and pop in a stack?

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

Mar 9, 2011
 level by level print BST1 AnswerDetailed analysis and solution is available in the following blog: http://codercareer.blogspot.com/2011/10/no-11-print-binary-trees-from-top-to.html
5160 of 117 Interview Questions