C9V5T3X8

1Problem
2Given a string, return the longest repeated substring.
3
4Examples
5"banana" -> "ana"
6"tomato" -> "to"
7"aaaaaa" -> "aaaaa"
8"Ask not what your country can do for you, ask what you can do for your country." -> " can do for you"
9Clarifications
10Is this word based? No, only think in terms of characters
11Does case matter? Yes, but what if it didn't?
12Can substrings overlap? Yes, refer to banana
13Solutions
14There are a wide range of approaches, commonly ranging from O(N^4) to O(N). The nice thing about this problem is one solution should lead to another. I've written the code in Java, since the approach may seem overly dependent on C style strings. However, some very nice aspects of Java can be utilized.
15
16=======
17
18Draw the following system: A website with multiple webservers connected to a single relational database on a third server. Like this:
19
20+------------+  +------------+
21| web server |  | web server |
22+------------+  +------------+
23
24 +----------+
25 | database |
26 +----------+
27Your manager comes to you one day and says "The site is slow." Your job is to investigate what is going wrong. This is very relevant to what SDEs at this company frequently do. It is also very open-ended and there are many acceptable responses.
28
29In general, you are looking for the candidate to attack the problem, compartmentalize the subsystems. This also allows you to see how much depth they have in a variety of problem domains, from networking to databases to distributed systems.
30
31Good answers:
32
33Connect to the site with a web browser and verify that it actually is slow.
34Connect to each web server individually to determine if it is a problem with only one web server.
35Look at the logs. People who expect logs are people who are used to writing maintainable software.
36Run a test suite to see where there's trouble. Similar to looking for logs, this suggests that they have good practices for writing robust, maintainable software.
37Look at web server logs to validate that each web server is receiving an appropriate share of the traffic. If not, something could be messed up with the upstream router/load-balancer.
38Look at both the web server and database server at a system level. Are the machines constrained on disk I/O, memory, processor? Make sure you get specifics from the candidate as to which tools they would use.
39See if the network pipe between the database server and the web server is flooded, and needed to be expanded.
40Is there some sort of database connection pooling going on? Is it sufficient?
41Take a look at the SQL statements to verify that they weren't doing anything that would thrash the server. If so, tune the statements.
42Look into the DB schema, to see if there were proper indices.
43Look at the application that accesses the database: is it locking up a whole table for each insert? Is it hitting the database only when it needs to, or is it hitting the database for every page load?
44Verify if any UI script or HTML that is causing a long render time.
45=======
46How do you think the "People who have shopped for this item also shopped for" feature works on our site?
47
48Another open-ended question with a lot of possibilities for follow-ups. Some aspects include:
49
50the scale at which this data operates. millions of customers and millions of orders.
51due to the scale, does the candidate really believe that this data is being queries out of a relational database in real-time? so how is the data stored? how is it generated? how frequently does it need to change?
52the source of the data. is it sessions, orders, both, neither?
53how come everything doesn't recommend Harry Potter?
54How will your system survive during a system crash? (Say perhaps the AZ serving your relational database is suffering from an power outage)
55Perhaps some of the Personalization gurus can chime in with other interesting aspects of this question.
56======
57Given an array of integers of length n, containing values between 1 and n-1, find the duplicate entry.
58
59Example Array:
60
61[2 1 2]
62
63First let them find a generic solution, then ask them for the fastest solution, and the solution which takes up no extra space but lets you destroy the array. (use it as storage basically).
64
65Note that this problem can be provably reduced to sorting. This means that if a linear time comparison based algorithm is found then we would have one for sorting as well (this is provably impossible). Ergo any linear time solution must make use of some space. Conversely the best algorithm using only comparisons will be to sort the entire list and look for the pair of numbers that are the same.
66
67===========
68This is a warm up question (for good candidates) and a weed out question (for bad candidates). A good candidate should be able to answer this question in a matter of minutes. See ShuffleArraySolutionsFromInterviewees for some "interesting" solutions.
69
70The question is: given an array of N elements, write a function to permute the elements in the array so that any permutation is equally likely. That means a given element should have a 1/N chance of being in any specific slot of the array. There are a lot of bad approaches to this algorithm, including:
71
72Randomly picking two numbers and permuting them (for some number of iterations).
73Generating a random index for each element of the array (i.e. for(i=1..N) { r = rand(1...N); a[r] = a[i]; }).
74Create another array of size N then, for each element in the original array, generate a random index and put it in the second array at that slot. If there is already an element in that slot in the second array, keep generating random indices until you find a slot that isn't taken.
75The right algorithm to solve this problem is to start with the first slot in the array and choose one of the N elements for that slot. So, for that slot, every element has a 1/N chance of being selected. Then, for the second slot, choose an element from the remaining N-1 elements. In that case, every element has a 1/N-1 chance of being selected, but they also had a N-1/N chance of not being selected as the first element and N-1/N * 1/N-1 = 1/N. The same logic applies for the rest of the elements in the array. This can be done in place by just swapping the current index with the randomly selected index. A good discussion of this, which is also known as the Fisher-Yates shuffle (1938), can be found at https://en.wikipedia.org/wiki/Fisher-Yates_shuffle
76
77A cheeky (but great!) answer would be the following:
78
79void shuffleArray(std::vector<int>& v)
80{
81    std::random_shuffle(v.begin(), v.end());
82}
83============
84This is a warm up question (for good candidates) and a weed out question (for bad candidates). A good candidate should be able to answer this question in a matter of minutes. See ShuffleArraySolutionsFromInterviewees for some "interesting" solutions.
85
86The question is: given an array of N elements, write a function to permute the elements in the array so that any permutation is equally likely. That means a given element should have a 1/N chance of being in any specific slot of the array. There are a lot of bad approaches to this algorithm, including:
87
88Randomly picking two numbers and permuting them (for some number of iterations).
89Generating a random index for each element of the array (i.e. for(i=1..N) { r = rand(1...N); a[r] = a[i]; }).
90Create another array of size N then, for each element in the original array, generate a random index and put it in the second array at that slot. If there is already an element in that slot in the second array, keep generating random indices until you find a slot that isn't taken.
91The right algorithm to solve this problem is to start with the first slot in the array and choose one of the N elements for that slot. So, for that slot, every element has a 1/N chance of being selected. Then, for the second slot, choose an element from the remaining N-1 elements. In that case, every element has a 1/N-1 chance of being selected, but they also had a N-1/N chance of not being selected as the first element and N-1/N * 1/N-1 = 1/N. The same logic applies for the rest of the elements in the array. This can be done in place by just swapping the current index with the randomly selected index. A good discussion of this, which is also known as the Fisher-Yates shuffle (1938), can be found at https://en.wikipedia.org/wiki/Fisher-Yates_shuffle
92
93A cheeky (but great!) answer would be the following:
94
95void shuffleArray(std::vector<int>& v)
96{
97    std::random_shuffle(v.begin(), v.end());
98}
99========
100Please walk me through what your object model would be if you had to design a text editor.
101
102GusLopez asks this question all the time.
103
104A good candidate could go on for the rest of the interview time with just this question. This question can be used to test many things:
105
106their sense of class design,
107how you separate function from display,
108what primitive data structures you might use to represent textual data. (Flyweight Pattern)
109Explore feature set -- for example, undo -- could be implemented with Command pattern.
110
111=======
112
113Please design an automated Air Traffic Control system where all the planes talk to a master ATC server which gives them commands that tell them where to fly and when to take off or land.
114
115This question is good because you can either expand it or constrict it based on the skill of the candidate. It has no wrong or right answer, its purpose is to see how creative the candidate is and how they approach a problem and determine the requirements for a solution.
116
117I often start out by asking them how the planes talk to the server on the ground and what kind of info would they be sending to the server so that it can make the best decisions.
118
119Useful info that the plane is going to want to send to the server:
120
121plane id (flight # / call sign)
122lat/long coordinates
123altitude
124heading (what direction the plane is flying in)
125speed
126fuel consumption per (second|minute|hour)
127amount of fuel left
128point of origin for the flight
129destination of the flight
130if an emergency is taking place, what kind of emergency is it
131if waiting to land, amount of time spent in holding pattern around airfield
132if waiting to take off, amount of time spent in line waiting to take off
133It's interesting to see what kinds of information that they think the planes should pass to the ground based computer. This part of the question is good for prodding them towards pieces of info that they didn't think about and to see how quickly they catch on to your hints.
134
135I let them spend 5-10 minutes designing the client and server classes and what kind of general data members they have. I don't really care about the data types, I just care about what pieces of information they want to track.
136
137Once they've come up with the design for the classes that are used by the plane and the master ATC computer, I ask them about implementation. How do you model the three dimensional position of a plane inside a data structure? What kind of data structure would make position comparisons between different planes efficient? What if you had to track hundreds or thousands of planes at once?
138
139How do you make sure that two planes won't collide? How do you figure out priority when multiple planes want to land? How do you make sure that a plane doesn't run out of fuel while waiting to land? What if one plane wants to take off and another wants to land at the same time?
140
141What kind of model do you use for the communication between the master server and the different planes? Do the planes subscribe to the server when they enter it's zone and then receive broadcasts that direct them (and all the other planes) what to do? Does the server talk to planes individually instead of over a broadcast? Is there any way to make the system be peer->peer only (i.e. no control computer on the ground)?
142
143This question is really open ended, but if you pay attention to their answers, you can drive them towards any part of the problem and see how they approach the design or implementation. It's a great way to check a candidate's skills in certain areas if you're not sure of their skills in that area. Sometimes I spend the whole time discussing the design of the system with the candidate and we don't even get into implementation, and sometimes the candidate ends up spending all their time explaining how they would represent the position of a plane in a data structure and how they would store and log all the data.
144
145Other things you could ask them about:
146
147message latency between planes and server, is it a problem?
148for certain mission-critical calculations, the space shuttle has multiple computers on board who all attack the same problem. when they find a solution, they compare answers. how might you expand the system so that there are multiple ATC computers in a particular zone? how do the different master computers pass information back and forth? how would they check to make sure that one of their peers wasn't giving out bogus information? what if they figure out that one of their peers is giving out bogus information?
149Finally, if they have a CS background, I ask them if they see any similarities between the master ATC computer's logic and other processes/methods/systems that are in the operating systems of most computers. Most smart candidates realize that it's a lot like a process scheduler. This problem makes a nice segue into questions about process priority, what queues are, what is a context switch, stuff like that. I only move on to those questions if they have a CS background and their resume lists that they did some OS work either in school or as part of their job.
150
151
152======
153What's the difference between hashing a string and encrypting a string? Give me some real-world examples of using hashing and encryption.
154
155When you hash a string, you get:
156
157fixed length output no matter what the length of the original string
158guaranteed one way operation, there is no way you can look at the checksum provided by a hash function and figure out what the original string was because the original string's length doesn't correspond to the hashed value
159no key is used, the only thing applied to the string is a mathematical transformation, so there's no way to get the original text back from the hash string
160collisions
161When you encrypt a string, you get:
162
163variable length output
164mostly guaranteed one-way operation, depends on algorithm and size of keyspace. encryption can be broken with enough cpu time or exploitation of weaknesses in the algorithm or poor key choices
165a way to recreate the original text if you have the proper key
166Real world examples of hashing:
167
168proxy servers hash the url and store the cached content in a directory structure based on the hashed url value:
169hash of 'www.amazon.com/exec/obidos/ASIN/15659...' => f092f0becc648514
170
171store fetched content to /cache/f092/f0be/cc64/f092f0becc648514
172
173When it gets another request for the same ASIN, it hashes the URL and sees if it already has content stored for that ASIN and returns the cached content if it exists.
174
175unix password files on some flavors of unix
176Some unices store the hashed password value in the password file. This is more secure than just using encryption since you can have a 40 character password if you want and it gets hashed to the same size string as a 4 character password. You don't have to hack in support for long passwords since when you try to login, the system just takes the hash of your supplied password and compares it with the hash stored in the password file for your username.
177
178(Why is this more secure than encryption? The consequence is that someone can break into the system using the 4 character password even if you prefer to use the 40 character version.)
179
180It is more secure than encryption because the 4 letter password and 40 letter password hash to *different* values. The fundamental measure of a hashing algorithm is the chance of collisions. The hash info above said that the passwords hash to the same *length* string, not the same string. This means that if you could look at the hash, there's no way to tell the input length from the output length. If someone wanted to type the first paragraph from their favorite book as a password, you wouldn't be able to tell. The encrypted passwords on unices typically are 8 characters or less, which make brute force attacks feasible. you only need to check 93^8 (93 printable characters between ! and ~ in the ascii table) combinations, versus 2^128 or 2^64 for MD5 (because you don't know how long the input string is from the hash output), depending on whether you use a brute force attack or a birthday attack (see google).
181
182checksums on downloads
183If you download software that has a signed checksum, you can make sure that the checksum was signed by the software's creator and then compute a checksum based on the file you download. Compare it to the checksum you get from the creator and if they match, you have the exact distribution. If they don't match, you might have a trojan or the wrong version of the distribution.
184
185Real world examples of encryption:
186
187using PGP to encrypt email
188unix password files (some unices still encrypt passwords instead of hashing them)
189encrypt sensitive business data on your machine
190ATM bank cards
191SSL
192I like asking this question because it gives the candidate a chance to fib and guess at an answer, and the creativity of the real world examples they give can show you how they think and how original they are. If they can't think of any real-world examples of encryption or hashing, then that might be a red flag.
193
194==========
195
196Roman Numeral Coding Question
197
198Description: Ask someone to write a program that converts a decimal number to a roman numeral.
199
200Focal categories: Coding Skills
201
202Phrasing: Everyone is familiar with Roman numerals[citation needed], but it seems like a lot of people seem to have little differences in the rules. So it's best to establish a baseline:
203
204"M" = 1000
205"D" = 500
206"C" = 100
207"L" = 50
208"X" = 10
209"V" = 5
210"I" = 1
211To find the value of a set of roman numerals you add up the value of the characters.
212A power of ten can only be repeated three times i.e., XXX = 30, XXXX is not valid.
213Those that are not powers of ten can only appear once, i.e. VV is not valid.
214The numbers must read highest-lowest from the left to the right. (with one exception, see the next rule)
215If a letter of a smaller value appears before a number of a higher value, then the smaller number is to be subtracted from the higher value. ex: IX = 9.
216You can subtract only powers of ten i.e., I, X, C
217Only one character can be used to subtract from a larger character. eg IIX = 8 is not allowed.
218You can't subtract a number from one that is more than 10 times greater. That is, you can only subtract I from V or X, X from L or C, etc. For e.g., IC can not be used for 99. It must be XCIX.
219I have no idea why they sometimes put IIII on watches. : )
220It's (traditionally) to avoid blasphemy -- IV used to stand for "Jove," and later "YHWH." Cite: http://en.wikipedia.org/wiki/Roman_numerals
221Another explanation that has made the rounds is that IIII provides better symmetry to the watch face than using IV. Though [[1]] provides evidence that in medieval times, IIII was often used instead of IV.
222
223=======
224
225The Date Problem
226Description:
227A purposely ill defined problem, that is much more complex than it looks on the surface. The problem is designed to see if the candidate asks for clarification of requirements, can come up with a reasonable approach to a reasonably complex problem s/he has never thought about before, can communicate that approach, can come up with the reasonable test cases and execute the logic s/he has designed.
228
229Focal Categories:
230Culture Fit I (smart, asks questions, changes directions easily), Computer Science Concepts (programming principles, can think and develop algorithms), Quality Focused Design Skills (can explore in a minor way) and Coding Skills (more of a can this person write pseudo code).
231
232Phrasing:
233Write an algorithm that will take two dates and tell you if they are more than a month apart, less than a month apart or exactly a month apart.
234
235Ranked Solutions:
236This is not a question where the answer is the important thing. These are however, several kinds of answers you typically see:
237
238Uses provided library functions (not too good - no library does it, tends to mean we have an assembler not an engineer). This kind of answer typically means that the candidate has not asked what a date is, or s/he doesn't really understand what library date routines do.
239Convert to Julian notation, subtract the days and compare to 30. A failed answer - a month is not 30 days.
240Build lots of 'if' statements comparing days, months and years. A clumsy but reasonable approach. When you see this you can probe for 'how would you test this' and work the test case through the provided pseudo code.
241Convert to Julian notation, get the number of days difference and then figure out how many days are in the current month. This is one of the better approaches you are likely to see. You can probe on how to compute the number of days in February if you see this one.
242orange-bang.png	Comparing the difference with the # of days in current month is not sufficient. For example: 01-29-17 vs 03-01-17 is exactly 31 days apart, but is more than a month apart. One should compare if the days part match too. - miroslar@
243A mathematical approach, (only one candidate has EVER gotten this answer). Create a 'Julian Month' notation (number of months since some starting date) multiply by 100, add the date portion, subtract the two dates and compare the difference to 100.
244Hints:
245You are letting the candidate proceed in their own path, unless they get flustered. Sometimes it helps to allow them to ignore the year for awhile.
246Reassure the candidate that s/he is writing pseudo code, not Java or C.
247Allow any convenient date format.
248Be in-exact in the definition of what a month is. Use examples such as 'January 15 to February 15 is exactly one month. February 15 to March 15 is exactly one month,' etc.
249orange-bang.png	Interesting - this invites the clever candidate to compare the day of the month, and if they're the same see if the months are adjacent. If they are, dates are a month apart. Similarly, adjacent months lets you do a simple numeric comparison on the day to determine less or greater than. However, without that how do we define what 'exactly 1 month apart' means? - paulbohm@
250Some design patterns are better than others. If s/he goes down a slow path, you may want to turn the problem by ignoring years.
251Indicators:
252You want to see if s/he refines the definition. An early question should be 'What is a month? How is a date represented,' etc.
253If the candidate uses the 'if' solution, you can let them plow into it, then start asking boundary conditions which they have missed. See how they react to errors being pointed out.
254Ask the candidate to define some test cases. Look for edge conditions, bad inputs, etc.
255Run the test cases through the paper algorithm. See if the candidate can act as a human computer executing the pseudo code s/he has produced.
256
257=======
258Prelude
259
260I'll first ask a candidate to define the term "garbage collection" to get us on the same page. If they have no idea what it is, no big deal, you can still have them work on the problem. This is roughly what the candidate should understand about garbage collection (from the GC FAQ [1]):
261
262A GarbageCollector is a part of a language's runtime system, or an add-on library, perhaps assisted by the compiler, the hardware, the OS, or any combination of the three, that automatically determines what memory a program is no longer using, and recycles it for other use. It is also known as ``automatic storage (or memory) reclamation.
263Problem statement
264
265I pose the main part of the problem as a set of requirements and constraints; the candidate must come up with a design that meets the criteria. "Let's say we have a Java virtual machine that does everything but collect garbage memory. Your goal is to design an accurate garbage collector for this JVM - that is, when the collector runs, it must reclaim any memory that can be reclaimed; a conservative solution that lets memory leak is not sufficient."
266
267If you'd rather pose this in the context of a C++ runtime environment, feel free. Assuming we're implementing a GC for a JVM tends to make some parts of the problem easier, though.
268
269My typical problem constraints:
270
271there can be any number of "mutator" threads in the system
272mutator threads modify the stack and heap
273there is one garbage collector thread
274when the garbage collector thread runs, all of the mutator threads are guaranteed to be at a "safe point"
275safe points are the call sites, dynamic link sites, thread yield sites, possible exception-throw sites, and allocation request sites [2]
276this sort of GC is known as a "stop-the-world" collector
277there is one shared heap
278you have access to every stack, the heap, and all object run-time type information (RTTI)
279The garbage collection entry point is some method (like System.gc() in Java) that is called by the runtime environment at a safe point. The candidate must determine what additional data structures they'll need, the GC algorithm, and the efficiency of their algorithm.
280
281=========
282Relatively easy coding question for an SDE candidate (good for college recruits).
283
284Problem statement: on the whiteboard, write a C function that will delete a node from a circularly-linked, singly-linked list.
285
286Issues: The candidate will need to define the node structure. They can assume that there is some global "list" pointer that points to the head of the list. Their solution must handle these special cases:
287
288list is empty
289list has only one element
290first element in list is the one to be deleted
291last element in a list is the one to be deleted (or is it?)
292the element isn't in the list
293the element is in the list more than once
294If they don't get all of these cases up front, you can give small hints. Candidates who need more help are probably not going to be good developers here.
295
296They also should be able to explain the complexity of the task in O(n) terms.
297
298=========
299Problem statement: on the whiteboard, write a C function that takes two strings, and returns the index of the first occurrence of one string in the other.
300
301Issues:
302
303if they ask for the return type, ask them what they think it should be. An int is fine.
304if they ask what to do if the string isn't found, again, ask them what they think it should do. Returning -1 is okay for this example.
305they can't use C string functions like strcmp, strncmp, and so forth. If you want to give them strlen, feel free.
306their solution should cover all of these cases:
307string not found
308either string is null
309either string is larger than the other
310search string "aaba" in "aaabacde" - this is the scenario most candidates miss, because their loop advances too far when there is a mismatch.
311KMP algorithm
312ask the candidate how they would test their solution. Given that they cannot try every possible set of test cases, what intelligent approach can they take? Make sure their test exercises each part of their code - if they don't get full code coverage on such a simple function, they'll likely have problems testing larger cases.
313their function signature should be something like this:
314 int find_string(const char *needle, const char *haystack) { ... }
315===========
316This is a conceptually simple problem that can be solved with a fairly straightforward recursive algorithm. It is a good test of a programmer's ability to recognize and solve problems that have recurrences. There is also an efficient iterative solution to the problem that requires a little bit of thinking outside the box. The problem is this:
317
318You are given an array of characters in some language. How would you go about printing all the subsets of characters from this array? For example, if the array you are given is [A,B,C], you would print:
319
320A B C AB AC BC ABC
321
322Note that order doesn't matter, so that the subsets [A,B] and [B,A] are the same (this makes the problem much easier).
323
324
325===========
326Code up a simple class in the language of your choice to represent a deck of cards with operations to shuffle the deck and to deal one card.
327
328Ordering Services requests this from candidates as a coding assignment after the first phone screen. The principle information garnered is "Can the candidate solve a simple problem in a simple, straight-forward way?" Its mostly a negative test, to weed out candidates that would otherwise make it through the phone screen process but are not actually decent coders. There are more of these people than one might at first think. The majority of people fail this test, and many submissions are quite bizarre.
329
330It is important to keep in mind that if a candidate makes a decent submission, it only weights to a minor degree in their favor, since the problem is so simple. A good submission only indicates that we should continue with the regular interview process.
331
332Wording
333
334The question is purposely left somewhat general and vague to see where a candidate goes with it.
335
336Submission Quality
337
338A good submission is one which is relatively short and simple, and follows common programming practices. What really stands out are submissions that are not short, or are not simple, or that contains code where one would say "why the heck did they do that?" Ordering services has 2-3 people critique each submission, listing observations of flaws and ranking them from 1 (astonishingly bad) to 5 (a little bad). If a submission is particularly nice for some reason, comments are made on that as well.
339
340Below are a number of typical flaws to serve as examples. But after reviewing submissions for a while, one quickly learns that there is no limit to the number of "interesting" variations there are for this problem.
341
342Deals Same Card Repeatedly
343
344Repeated calls to the deal() method always return the same card, i.e. a card is not removed from the deck when it is dealt.
345
346Init without using For-loop
347
348Does not use for-loop to initialize cards in the deck, i.e. something like
349
350void Deck::init()
351{
352  m_cards[SPADES][ACE]   = Card(SPADES, ACE  );
353  m_cards[SPADES][TWO]   = Card(SPADES, TWO  );
354  m_cards[SPADES][THREE] = Card(SPADES, THREE);
355  ...
356}
357Implements Own Linked List
358
359Implements own linked list class to store cards in the deck, as opposed to using STL vector or list, or simply using an array.
360
361Deck of Integers
362
363Doesn't create a card class. Just creates a deck of 52 integers with no reference to card suit or rank.
364
365class Deck
366{
367  ...
368  int deal();
369 private:
370  int m_cards[52];
371};
372Over Qualifies Names
373
374Redundantly encodes class name into member names.
375
376class Card
377{
378  Suit m_cardSuit;
379  Rank m_cardRank;
380};
381class Deck
382{
383  ...
384  void shuffleDeck();
385};
386Sort Key in Card
387
388Adds an integer member to card class to store random keys in and then use to shuffle deck.
389
390class Card
391{
392  Suit m_suit;
393  Rank m_rank;
394  int  m_key;
395};
396Strings for Suit and Rank
397
398Card class uses strings to store suit and rank. Works for this problem, but not a very general notion of what a card is. Would not allow card to be easily used in any card game where comparison of rank was required.
399
400class Card
401{
402  String suit;
403  String rank;
404};
405Extra Features
406
407Included a whole mess of methods and behavior not asked for.
408
409class Deck
410{
411 public:
412  Card dealTop   ();
413  Card dealBottom();
414
415  vector<Card> dealTop   (int n);
416  vector<Card> dealBottom(int n);
417
418  void addTop   (Card c);
419  void addBottom(Card c);
420
421  void cut();
422};
423Player & Game
424
425Creates player, game, or other similar classes. The problem statement doesn't request these.
426
427Unnecessary Copy Constructor or Assignment
428
429Hand writes a copy constructor or assignment operator in the card class even though they are not needed.
430
431class Card
432{
433  Card();
434  Card(Suit s, Rank r);
435  Card(const Card& c);
436
437  Card& operator=(const Card& c);
438
439  ...
440};
441Memory Leaks
442
443Memory leaks exist in the code. For example, deck uses dynamic memory to allocate cards, but fails to provide a destructor.
444
445class Deck
446{
447  ...
448
449  Card* m_cards[52];
450};
451Deck Copy Fails
452
453Uses dynamic memory for cards, but fails to provide a copy constructor and assignment operator for Deck.
454
455class Deck
456{
457  ...
458
459  Card* m_cards[52];
460};
461Private Copy Constructor & Assignment
462
463Make copy constructor and/or assignment private for Deck thus preventing clients from copying a deck if they want to. Worse if they do just one and not the other.
464
465class Deck
466{
467 private:
468  Deck(const Deck& d);
469  Deck& operator=(const Deck& d);
470}; 
471As a variation (maybe for SDE-I or entry-level candidates) it might be better to ask them to build a Card class (if in Java), then introduce a Deck class. I asked this question to a few candidates in phone screens and it went a lot smoother when I started bottom-up.
472
473============
474Design the controls for a modern four-way traffic intersection with all the works: weight vehicle sensors, pedestrian lights & buttons, etc.
475
476This is an interesting problem that tests the candidate's ability to think in terms of distributed systems, interrupt-driven (or event-driven) programming, state machines, and scheduling techniques.
477
478http://auto.howstuffworks.com/car-driving-safety/safety-regulatory-devices/question234.htm
479
480http://www.ccs.neu.edu/home/vkp/Papers/Traffic-sigcse98.pdf
481
482
483============
484You have a singly linked list. How do you find the 3rd element from the end?
485
486You or the candidate should clarify what is meant by "3rd from the end".
487============
488implement strstr() is a fairly well-rounded question. I like to ask it as a warmup at the beginning of onsite interviews, as it gets the candidate used to writing code on the board, and it can be a pretty good barometer of their coding ability.
489
490It's always a good idea to see actual code, even if you're just testing on design. Some people can talk through design pretty well, but fail miserably at basic code-writing. If you give this question during a phone screen, have them read the code to you verbatim.
491
492I usually phrase it as "please write me a function to find the first occurrence of one string in another string". I sometimes add the restriction of doing it without using the functions in string.h
493
494I give no more than 10 to 15 minutes for this question; if somebody is having a hard time with the problem in that timeframe, they're probably not a good candidate.
495
496Once the basic solution has been found, I ask the candidates how they would optimize the solution.
497
498Barometric pressure:
499
500If the candidate can't produce a working solution, they're a "no hire". Period. A first or second year college student should be able to produce reasonable code to do this. One of the strangest failure cases for this question that I'd encountered actually wanted to solve it recursively! Peanut gallery: I don't think a recursive solution is a failure for a first attempt, as long as they understand the practical issues with recursion and how to transform it into an iterative solution.
501
502Your SDE I candidate will
503
504give the baseline solution - nested for loops that compare each character of the needle string against the haystack string, and advancing one character in the haystack string if a match was not found.
505may ask about return types, and what to return if a match isn't found.
506may ask to use strlen()
507If you gave them strlen, they shouldn't call it excessively (ie, in the test section of the for loop).
508may walk through the entire haystack string, rather than just the first strlen(haystack) - strlen(needle) + 1 characters.
509Your SDE II candidate will:
510
511recognize this as strstr.
512set the pointers as const char * in the fn signature.
513check to make sure the inputs are not null pointers.
514(dawalker@) I disagree that an SDE II or stronger will check if the inputs are NULL. Libc's strstr() doesn't do this - it is implicit in the calling contract that needle and haystack are valid strings. It's one of subtle differences between C and C++.
515use pointer arithmetic rather than length + array indicies.
516may put constants on the LHS of comparisons.
517be able to walk through the strings by checking for the null byte rather than using strlen.
518be able to give a least some good optimizations, perhaps after coding the general solution.
519A decent baseline solution might be:
520
521int mystrstr( const char *needle, const char *haystack ) {
522  const char *cur_p = haystack;
523
524  if ( 0 == needle  || 0 == haystack ) {
525    return -1;
526  }
527
528  while ( *cur_p ) {
529
530    int i;
531    const char *p, *q;
532
533    for ( p = needle, q = cur_p;
534          0 != *p;
535          ++p, ++q ) {
536
537      if ( *p != *q )
538        break;
539
540    }
541
542    if ( 0 == *p ) {
543      return (int)(cur_p - haystack);
544    }
545
546    ++cur_p;
547  }
548
549  return -1;
550}
551There are several optimizations that are possible here:
552
553Recognize that you can eliminate the need to examine every substring by adding up the values of the characters in the needle string, and keeping a running total of the current strlen(needle) characters from the haystack string - if the values are different, the substring obviously doesn't match. The candidate should not create a separate character-to-value mapping, and they should understand that this technique can give false positives (aaab and baaa, or abbc and bbbb).
554Checking whether needle is longer than haystack is NOT really a good optimization; even the baseline solution will only need to walk through the needle string once before returning false on comparing against the NULL bye in the haystack string. Calling strlen will walk through both strings completely; you only save strlen(haystack) comparisons.
555Your SDE III candidate will:
556
557think through the optimizations before writing code.
558They may also come up with a Monte Carlo type solution for generating substring values in such a manner as to eliminate false positives, using prime numbers and a polynomial equation rather than a simple sum. (I have yet to actually see this produced in an interview, but I still have my hopes.)
559(tonyw) Suggest other ways to advance though the haystack more rapidly. I'm still waiting for someone to implement a Boyer-Moore solution in an interview.
560Most Efficient Algorithm
561Yoinoue 08:23, 9 December 2009 (UTC) This isn't easy to answer question for fast algorithm. :-)
562
563See collection of algorithm in ASIN: 0954300645 Handbook of Exact String Matching Algorithms (Paperback)
564
565As far as I know Search algorithm is the most efficient for large alphabets and small pattern [Lecroq95]. It is faster than Boyer-Moore, Turbo-BM, BM-Horspool.
566
567Features from [Charras04]:
568
569Simplification of the Boyer-Moore algorithm;
570Uses only the bad-character shift;
571Easy to implement;
572Pre-processing phase in O(m+s) time and O(s) space complexity;
573Searching phase in O(mn) time complexity;
574Very fast in practice for short patterns and large alphabets
575where m is length of pattern, n is length of test, s = size of alphabet.
576
577
578===========
579Intro
580This question could be used as a warmup question or a weed out. It assumes that the person being interviewed has some experience with the C standard library. This is derived from an actual bug in the Amazon.com codebase (authored by an intern).
581
582Original (Buggy) Code
583To start, put the following code on the board (or tell them over the phone).
584
585 1 std::string bytesToHex(char * bytes, size_t size)
586 2 {
587 3     std::string result;
588 4     for (int i=0; i<size; i++) {
589 5         char hexByte[2];
590 6         sprintf(hexByte, "%02x", bytes[i]);
591 7         result.append(hexByte);
592 8     }
593 9     return result;
59410 }
595Questions
596Then ask them the following questions.
597
598What is wrong with this code?
599If they're good they'll figure it out right here. The problem is that the 'hexByte' character array is one character too short. When sprintf writes the hex digit to 'hexByte', it will write two characters of hex followed by a null string terminator, for a total of three characters written to 'hexByte'. Since 'i' is the most recent variable, it will probably be the one that gets trampled by the buffer overflow, which means that 'i' keeps getting reset to 0 and thus the loop becomes infinite.
600
601Does this function ever return?
602The answer is no, or probably not (depends on the compiler). Ask this only if they don't immediately understand what's going on with the code. If you need to, you can tell them that you ran the code through a debugger and put a breakpoint at line 7. You printed out the variable 'i' each time and found that it was always zero.
603
604How would you fix this function?
605Once they understand what's wrong they should be able to fix the code by changing the size of hexByte to 3. If they're good, they may also decide to switch from sprintf to snprintf and do error checking on the return value (snprintf should always return 2 for this usage). You may need to lead them a little to realize the need to switch to snprintf.
606
607Why should you never use sprintf, and what can be used to replace it?
608If they've had any training in writing secure code they should know that sprintf is evil given the potential for buffer overflows. The bug would probably have been detected much easier if snprintf was used in the first place, and the return value was checked for correctness.
609
610Final (Fixed) Code
611Following is a fully bugfixed version of the bytesToHex function.
612
613 1 std::string bytesToHex(char * bytes, size_t size)
614 2 {
615 3     std::string result;
616 4     for (int i=0; i<size; i++) {
617 5         char hexByte[3];
618 6         if (2 != snprintf(hexByte, 3, "%02x", bytes[i])) {
619 +             fprintf(stderr, "failed to write hex byte '%02x' to string.", bytes[i]);
620 +             abort();
621 +         }
622 7         result.append(hexByte);
623 8     }
624 9     return result;
62510 }
626===========
627Problem
628There is a common type of word puzzle (called word ladders or doublets) where you are given two English words of the same length, say, "HEAD" and "TAIL". The puzzle is to come up with a sequence of valid English words, starting with "HEAD", and ending with "TAIL", such that each word is formed by changing a single letter of the previous word. Create an algorithm to automatically solve such puzzles.
629
630Example (altered letters capitalized):
631
632 HEAD
633 heaL
634 Teal
635 teLl
636 tAll
637 taIl
638Observations / Variations
639Not every word in a solution necessarily uses the corresponding letters from either the beginning or ending word (in the example above, 'L' in the 3rd position of "TELL" and "TALL" doesn't appear in HEAD or TAIL. Some solutions may require using letters that don't appear in either the starting or ending words
640You may choose to require that the algorithm return the shortest possible solution, or not.
641If you require it, then you may be putting the candidate at a disadvantage, because it requires them to be able to identify some very particular techniques that lend themselves to shortest path solutions.
642I usually don't require it, because I want to give people enough room to explore the solution space on their own.
643A candidate who happens to be familiar with basic graph theory will tend to be able to identify the breadth & depth-first approaches sooner than other candidates. You can go on to ask them to code the algorithm, to see if they understand it well enough to put it into code.
644Solutions
645All solutions will require some way to determine if a word is an english word, so allow them some sort of dictionary. If they do well enough at the basic algorithm, there is room for optimizing it with a specialized dictionary, so I don't usually ask about the details of the dictionary straight away.
646
647Basically, this is a graph problem, and it's nice if the candidate identifies it as such. A full solution involves generating the graph (explicitly or implicitly), plus a path searching algorithm.
648
649Depth First
650Virtually all candidates who aren't well versed in graph theory take this approach, probably because it most closely models how they themselves would solve this kind of problem. Elements of a correct solution include:
651
652How to generate the next set of candidate words
653Either generating them on the fly by correctly looping through positions & letters in the alphabet.
654They might pre-process the dictionary into a data structure that returns all 1-letter adjacent words from any given word. This is especially helpful if the algorithm is expected to be run many times in succession, as it eliminates the overhead of the generate & test.
655How to keep track of the sequence of words and return the solution to the caller
656They might keep an explicit stack/list somewhere, and modify it is they traverse the graph
657Or just keep the current search path on the call stack
658Or maintain a set of back-pointers from each word they visit, to the previous word that they visited. When the final word is reached, you
659Avoid infinite loops, which usually means keeping track of at least every word in the current search path, and skipping those that are encountered again.
660Knowing when to stop descending down a branch (i.e., they've found a solution, or there isn't one).
661Elements that make a solution better are:
662
663Not only avoiding re-use of words that are already in the current search path, but any word that has ever been visited during the search.
664If they're trying to find the shortest path, then they need to keep track of the "best answer so far", and stop going down a branch if it has become longer than that best answer.
665If they're also keeping track of already-visited words, then they'll need to augment that with information about how many steps it took to visit that word, and continue if the current solution has arrived at that word in fewer steps.
666Avoiding useless substitutions: Changing the same position back-to-back in successive words. Such substitutions make a solution unnecessarily long. E.g., HEAD -> BEAD -> LEAD could just be HEAD -> LEAD
667Breadth First
668This could also be called a degenerate form of Dijkstra's Algorithm, where the edge weights are the same value.
669
670A thorough answer should talk about:
671
672dequeueing the next candidate word
673generating all the next possibilities
674enqueueing those on the end of the queue.
675How to track the sequences of words leading to each possibility
676Avoiding re-use of words (same as in depth-first)
677A*
678https://en.wikipedia.org/wiki/A*_search_algorithm
679
680A* search would be suitable too for finding the shortest path. The heuristic function would be based on how many letters are incorrect, which is a lower bound on the number of remaining steps.
681
682Bidirectional Breadth First
683Same as BFS, but we start searching from both ends at the same time and stop as soon as we find common word in both search trees. Improvement comes from the fact that two circles with radius r have smaller total area than 1 big circle with radius 2r.
684
685Complexity of naive BFS for two words N connections apart in the network with M connections per word on average is O(M^N), while complexity of bidirectional search will be O(M^(N/2)).
686
687============
688Reversing a singly-linked list is a good phone screen question. You should write code to do this before asking the question!
689
690Regardless of whether the candidate starts with a recursive or iterative solution, you should ask them to produce both.
691
692The basic recursive solution will set the head list pointer to the value of a recursive call which defers evaluation of the return value until the last node in the list. The functions basically look like this:
693
694   Node *Node::reverse_rec( void *prev ) {
695       Node *retval = this;
696
697       if ( next != NULL ) {
698           retval = next->reverse_rec( this );
699       }
700
701       next = (Node *)prev;
702       return retval;
703   }
704
705   void List::reverse( void ) {
706      head = head->reverse_rec( NULL );
707   }
708Here is an alternative method that doesn't use a helper function:
709
710 Node * reverse( Node *n ) {
711     Node *m;
712
713     if ( n == NULL || n->next == NULL )
714         return n;
715     else {
716         m = reverse( n->next );
717         n->next->next = n;
718         n->next = NULL;
719     }
720
721     return m;
722 }
723The basic iterative solution will use 3 pointers (prev, cur, and next) and looks like this:
724
725   void List::reverse( void ) {
726       Node<C> *prevp = NULL;
727       Node<C> *curp = head;
728
729       while ( curp != NULL ) {
730           Node<C> *nextp = curp->next;
731           curp->next = prevp;
732           prevp = curp;
733           curp = nextp;
734       }
735
736       head = prevp;
737   }
738Note that there may be some differences in the function signature depending on how they've set up the list. I generally put a "dummy" node on the front of my hand-written lists so that all inserts can be handled in a uniform manner (i.e., there's no special handling for adding to the head of the list). Of course, this is a memory vs. code simplicity tradeoff.
739
740I will generally have candidates write their algorithm down and talk me through it, then read the whole thing to me after they're done so that I can analyze the loop.
741
742Unfortunately, this question can take a lot of time - plan for 10 to 15 minutes with sharp candidates and up to half an hour with the weaker ones. I generally don't allow candidates to continue beyond 30 minutes.
743
744This is a fairly standard question, but from my experience, people are rarely prepared to do it both recursively and iteratively.
745
746Bonus points:
747
748the candidate asks if the list is singly or doubly linked
749the candidate verifies that the list has no cycles
750the candidate calls out the fact that if ( ptr ) is equivalent to if ( 0 != ptr ) or if( NULL != ptr)
751================
752
753This is one of our interview questions, first brought to Amazon by Chris Brown (cb@), as far as I know.
754
755Write a function that takes an array and size as a parameter. The array contains non-negative numbers. Every number in the array appears an even number of times, except for one number that appears an odd number of times. The function should return the number that appears an odd number of times.
756
757A useful follow-up question you should ask is, how would you test this code. There are lots of edge cases that should be tested for, and it's very revealing to see if the candidate can come up with a reasonable set of them.
758
759Warning: this is Googleable, so if your candidate immediately gives the XOR answer, you may want to move on to another question instead.
760
761
762==========
763https://www.geeksforgeeks.org/huffman-coding-greedy-algo-3/
764==========
765Question: Given a pointer to the root of a binary tree write that tree to disk or to a database. Read the tree back in to memory, getting the exact same tree.
766
767Stop_hand.png	WARNING: This question can get a canned response like - https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
768
769While it's possible to get a canned solution, you can ask follow ups and variations to compensate. I haven't had a candidate give a canned response yet. Mluker
770You can give the following hints depending on the level:
771
772This is a Binary Tree not a Binary Search Tree. That means that it is not necessarily sorted; it only means that every node has a degree <= 2.
773Remember you want to get the exact same tree when you read it in.
774You should break this problem into three pieces. a) format in database or file b) write it out c) read it back in
775Things to consider:
776
777Whatever value you use (int, string, etc), there's nothing in the problem statement that requires the node value to be unique. This can complicate some formats/solutions.
778Serialization format is not specified. If you get a canned answer, ask them to do it in a different format--one that would not be dependent on order.
779You can also followup with questions that look for re-usability and design patterns (iterators, visitors, etc).
780Two trees can have the same pre-order traversal, making serialization/deserialization complex
781   A
782 B
783  C
784and
785
786   A
787B     C
788===========
789Premise
790The problem is to determine the dimensions (x,y) of a grid that is as square as possible and large enough to contain n elements with no more than 2 empty spaces. Orientation of the grid does not matter (tall vs. wide).
791
792Distilled problem statement: given n, minimize |x - y| such that n <= x * y <= n + 2 and n,y,x are positive integers.
793
794Highlights
795General problem solving
796Understanding the problem rules
797Multiple solutions: brute force or optimized
798Loop design and use
799Examples
800n = 4
801x = 2, y = 2
8020 empty spaces
803square
804n = 17
805x = 6, y = 3
8061 empty space
807more square than other options (x = 9, y = 2... etc)
808n = 23
809x = 5, y = 5
8102 empty spaces
811square, better than other options with fewer empty spaces (x = 6, y = 4)
812consider withholding this case since the optimal solution has 2 empty spaces
813n = 18
814x = 5, y = 4
8152 empty spaces
816more square than x = 6, y = 3which has no empty spaces)
817Observations
818The candidate may elect a brute force solution. In doing so it should quickly become apparent to him/her that the solution will consider far too many useless values. For example, when searching for the solution where n = 17, the candidate might loop over all possible solutions:
819
820x = 1, y = 17 | x = 2, y = 17 | x = 3, y = 17 | ...
821Immediately we see a lot of waste will be considered. So, they might trim y while incrementing x:
822
823x = 1, y = 17 | x = 2, y = 16 | x = 3, y = 15 | ...
824Still, far too many wasteful attempts, and they may not be careful to skip over a potential solution that might be the best one. If these wasteful attempts need to be explained to the candidate that that is a red-flag.
825
826There are many variations on how the candidate will iterate x and y. Will the candidate find it necessary to use a nested loop? How does the candidate know to exit the loop(s)?
827
828Also, what expression does the candidate propose for determining the "squareness" of the possible solution and whether it's more square than another possible solution?
829
830abs(x1 - y1) < abs(x2 - y2)
831If the candidate begins the search at sqrt(n) then that's good. But, of course, that won't always be the answer so what does the candidate do to find y when x = sqrt(n)? Discuss performance of the candidate's solution and allow suggestions for improvement.
832
833If you require the candidate implement a function, what does his/her prototype look like for something with 1 input and 2 result values?
834
835Is there an n for which the rules cannot be met? - (A1: no...there's always n x 1) n/2 x 2 provides a better solution for all values of n than n x 1 --Bartzs 20:37, 15 January 2016 (UTC) - (A2: no...there's always n/3 x 3) Given that we're always examining a range of 3 consecutive integers, one is bound to be divisible by 3 --dbronaug 17:30, 21 December 2017 (UTC)
836
837Solution
838C
839By kradek@
840
841 #include <stdio.h>
842 #include <stdlib.h>
843 #include <math.h>
844 
845 int main(int argc, char** argv) {
846     if (argc > 1) {
847         int n = atoi(argv[1]);
848         int x = (int) sqrt(n);
849         if (x * x == n) {
850             printf("%d x %d = %d\n", x, x, x*x);
851             return 0;
852         }
853         int y = ++x;
854         while (x * y - n > 2) {
855             y--;
856             x = (n + y - 1) / y;
857         }
858         printf("%d x %d = %d\n", x, y, x*y);
859     }
860     return 0;
861 }
862=============
863
864Premise - You are given two separate web access log files, say from Apache or some similar web server. The first log file is from day 1, the second one is from day 2. The web site is set up in such a way that every access logged will contain a unique identifier for that customer somewhere in the request line. The website is a fairly high traffic, so these log files are very large.
865
866Question - How can you find a unique list of customers who visited on day 1 and then came back for a visit on day 2?
867
868Follow-up Question - This question gets much more interesting once you impose memory constraints. What if the set of distinct customers won't fit in memory?
869
870Solutions
871
872Some candidates will start off trying to use grep/sed/awk etc. to pull out the customer ID's... which is good that they're aware of text processing tools and regular expressions, but that's not necessarily the real guts of the problem.
873Other candidates, ignoring the fact that the log files are very large and will still try to read the entire file into memory. In that case, specifically state that the file itself cannot be read into memory, but this is usually a red flag in my mind.
874In some cases, candidates will try to load the data into a database and find duplicates that way. This is not necessarily a bad solution, but if they choose this route, suggest that the number of unique customers is small enough that it can be held in memory, and that no database access should be necessary.
875The "optimal" solution would be to use a hashtable to store the list of unique customers from the first file, and then as you process the second file, check to see if the customer exists in your hashtable. If they do, put their ID into a second hashtable, if not, do nothing. At the end, the second hashtable should contain a list of unique customers that visited on both days. [I think a better solution doesn't use a second hashtable. Why not just use a List to store the *list* of repeat visitors? (This requires the candidate to also solve the duplicate problem which is pretty easy if you just modify the first hashtable.) -smithbr]
876The above "optimal" solution has a problem: it doesn't truly scale because it requires everything to fit into memory. Solutions for when you impose memory constraints include sorting each file and then a linear merge comparison. Of course, the candidate needs to describe a sort algorithm that can operate under memory constraints.
877Possible solution
878
879I actually like a variation of the "database" solution because it doesn't require you to write a script with a hashtable and is achievable just using unix commands. suppose the format of the customer ids, is parseable... then i'd do the following:
880
881sed 's/customer_id: //g' logFile1 | sort | uniq > day1CustomerIds
882sed 's/customer_id: //g' logFile2 | sort | uniq > day2CustomerIds
883join day1CustomerIds day2CustomerIds
884Just sort -u would do instead of two process' sort and uniq
885
886sed 's/customer_id: //g' logFile1 | sort -u > day1CustomerIds
887sed 's/customer_id: //g' logFile2 | sort -u > day2CustomerIds
888join day1CustomerIds day2CustomerIds
889This has the benefit of actually retaining the list of unique customerIds from day 1 and day 2.
890
891Scalable Solutions
892
893If one of the constraints is that the log files are extremely large and cannot fit into memory, one solution is to use a map/reduce approach where the customer IDs are extracted and combined with the date, which is the key then mapped to counts (of 1 initially) and then iteratively reduce the number of unique mappings to join the records and sum up the counts. You could throw this at Hadoop, Spark or come up with a single-host solution.
894
895Another approach might be to extract the ID and date and combine, writing out to a series of files each of which are small enough to be sorted in-memory before being written out, also eliminating uniques as they are found. Those sorted files can be merge-sorted into a single file or an ordered array of files (continue to eliminate uniques), then the final order can be iterated over to determine the number of unique customer IDs. When two customer IDs appear adjacent to each other but with different dates, those are your repeat visitors.
896
897=================
898Write a program that reads in a dictionary of words from a file and prompts the user for pairs of words. For each pair, display a shortest possible word chain using the input as the starting and ending words. Print all words in upper case, except the one letter that has changed between words. If either word is not in the dictionary or there is no chain or words, print an appropriate error message.
899
900Two words are connected if there is one letter that different and the rest are the same. For example, MALE connects to MILE (second letter, A to I), but not LIME (first and third letters are different). Here's a sample word ladder for MALL to BENT.
901
902MALL
903bALL
904BeLL
905BELt
906BEnT
907For determining connected words and finding an optimal word chain, describe the runtime for each operation in terms of number of words (N) and letters (L).
908
909(See also HeadToTailInterviewQuestion.)
910
911Note that, although a good question about CS fundamentals/graph search, this is a very old, well known problem with solutions readily available online in all languages; it even has it's own wikipedia article: http://en.wikipedia.org/wiki/Word_ladder
912===============
913
914Question
915So the Flatland Space Agency is attempting to send two rovers on a mission to Flatland-Mars. The mission requires the two rovers to meet up before they can be effective, but at the last moment the Agency runs out of funding and only has enough money to develop one piece of software that will have to run unchanged on both Rovers.
916
917Each lander lands like the 3d Earth Opportunity and Spirit rovers (lander crashes into the planet with big airbags, rovers emerge from lander, leaving the lander behind) an unknown distance apart.
918
919Problem: Develop a program in the following assembly language which allows the rovers to meet up. Efficiency counts, so try not to require a rover to drive all the way around the planet.
920
921Registers: r0, r1, r2 Instruction set:
922
923SET <reg> <dec value> (set the register to a decimal number value)
924J0 <reg> <label> (jump to label if the value of the register <reg> is 0)
925JN0 <reg> <label> (jump to label if the value of the register <reg> is not 0)
926BSE <reg> (Tests to see if the rover is in the same place (within 10 units) as a lander base station, if it is put 1 in the specified register, otherwise set it to 0)
927LFT <val> (Move left (counterclockwise) around the planet at specified value units per second for 1 second (assume the execution time for any opcode is 1 second))
928RHT <val> (same as LFT but clockwise)
929Answer
930The key to this question is understanding that in order to solve it you have to find a condition where the state of the rovers is not the same, so you can break out of the lockstep movement implied by running identical programs
931Best/simplest solution is to go in one direction until hitting a landing site, then increase speed to catch up with the other slower-moving rover. Solution should look something like:
932SET r1 0
933
934START: 
935LFT 10
936BSE r0
937JN0 r0 CATCHUP
938J0 r1 START
939
940CATCHUP:
941LFT 100
942J0 r1 CATCHUP
943Notes
944Since you need to get somewhere where the rover's states differ, there is no solution if the rovers land diametrically opposed on the planet. Bonus points if the candidate figures this out.
945The program can also fail if the ratio of the rover's normal and catchup speed is insufficient to catch up before the other lander goes all the way around the planet, finds the other landing site and goes into "catchup" mode as well. Some good math to be explored there, if you've got extra time to fill.
946
947
948=========== TYPE 2 ====================
949Technical Interview Questions
950Sub Trees
951Question: Write a algorithm to determine if a tree is a sub-tree of another tree.
952
953public static boolean containsTree(Node t1, Node t2) {
954    if(t2 == null)
955        return true;
956    if(t1 == null)
957        return false;
958    if(t1.data == t2.data)
959        if(matchTree(t1, t2))
960            return true;
961    return containsTree(t1.left, t2) || containsTree(t1.right, t2);
962}
963
964private static boolean matchTree(Node t1, Node t2) {
965    if (t1 == null && t2 == null)
966        return true;
967    if (t1 == null || t2 == null)
968        return false;
969    if (t1.data != t2.data)
970        return false;
971    return (matchTree(t1.left, t2.left) && matchTree(t1.right, t2.right));
972}
973ASCII
974Question: Write functions to convert from ASCII to integer & integer to ASCII
975
976public static int asciiToInt(String str) {
977    int result = 0;
978
979    for(int i = 0; i < str.length();i++) {
980        result*= 10;
981        result+= str.charAt(i)-'0';
982    }
983
984    return result;
985}
986
987public static String intToAscii(int i) {
988    StringBuilder sb = new StringBuilder();
989
990    while(i != 0) {
991        char c = (char) ('0'+(i%10));
992        sb.insert(0,c);
993        i/= 10;
994    }
995
996    return sb.toString();
997}
998Reverse Linked List
999Question: Write a function to reverse a singly-linked list.
1000
1001    public static ListNode reverseList(ListNode head) {
1002        ListNode newHead = null;
1003
1004        while(head != null) {
1005            ListNode temp = head.next;
1006            head.next = newHead;
1007            newHead = head;
1008            head = temp;
1009        }
1010
1011        return newHead;
1012    }
1013Reverse String
1014Write a function that takes a string as input and returns the string reversed.
1015
1016Example: Given s = "hello", return "olleh".
1017
1018Solution
1019
1020    public static String reverseString(String s) {
1021        char[] array = s.toCharArray();
1022
1023        for(int i = 0; i < array.length/2; i++) {
1024
1025            char beginning = array[i];
1026            char end = array[array.length - 1 - i];
1027
1028            array[i] = end;
1029            array[array.length - 1 - i] = beginning;
1030        }
1031        return new String(array);
1032    }
1033Hamming Distance
1034The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
1035
1036Given two integers x and y, calculate the Hamming distance.
1037
1038Note: 0 ≤ x, y < 2^31.
1039
1040Example:
1041
1042Input: x = 1, y = 4
1043
1044Output: 2
1045
1046Explanation:
10471   (0 0 0 1)
10484   (0 1 0 0)
1049       ↑   ↑
1050The above arrows point to positions where the corresponding bits are different.
1051
1052Solution
1053
1054public static int hammingDistance(int x, int y) {
1055        int xor = x ^ y;
1056        
1057        int count = 0;
1058        while (xor != 0) {
1059            if ((xor & 1) == 1) {
1060                count ++;
1061            }
1062            xor = xor >> 1;
1063        }
1064        return count;
1065    }
1066Solution 2
1067
1068public static int hammingDistance(int x, int y) {
1069    return (int) Integer.toBinaryString(x ^ y).chars().filter(e -> e == 49).count();
1070}
1071Add Digits
1072Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
1073
1074For example:
1075
1076Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.
1077
1078Solution
1079
1080public class Solution {
1081    public int addDigits(int num) {
1082        int x = 0;
1083        while(num != 0) {
1084            x+= (num % 10);
1085            num /= 10;
1086            if(num == 0 && x >= 10) {
1087                num = x;
1088                x = 0;
1089            }
1090        }
1091        return x;
1092    }
1093}
1094Max Consecutive Ones
1095Given a binary array, find the maximum number of consecutive 1s in this array.
1096
1097Example: Input: [1,1,0,1,1,1] Output: 3 Explanation: The first two digits or the last three digits are consecutive 1s. The maximum number of consecutive 1s is 3.
1098
1099Note: The input array will only contain 0 and 1. The length of input array is a positive integer and will not exceed 10,000
1100
1101Solution
1102
1103public class Solution {
1104    public int findMaxConsecutiveOnes(int[] nums) {
1105        int max = 0;
1106        int currentMax = 0;
1107        
1108        for (int i : nums) {
1109            if (i == 1) {
1110                currentMax++;
1111                if(currentMax > max) {
1112                    max = currentMax;
1113                }
1114            } else {
1115                currentMax = 0;
1116            }
1117        }
1118        
1119        return max;
1120    }
1121}
1122Two Sum
1123Given an array of integers, return indices of the two numbers such that they add up to a specific target.
1124
1125You may assume that each input would have exactly one solution, and you may not use the same element twice.
1126
1127Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
1128
1129Solution
1130
1131class Solution {
1132    public int[] twoSum(int[] nums, int target) {
1133        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
1134        
1135        for(int i = 0; i < nums.length; i++){
1136            Integer k = map.get(target - nums[i]);
1137            if(k != null) {
1138                return new int[] {k, i};
1139            }
1140            map.put(nums[i], new Integer(i));
1141        }
1142        return null;
1143    }
1144}
1145Converging Linked Lists
1146Question: Write a function to determine whether two singly-linked lists converge. Write a function to find the intersection between two singly-linked lists.
1147
1148public class Node {
1149    int value;
1150    Node next;
1151}
1152 
1153public static boolean listsConverge(Node head1, Node head2) {
1154    if(head1 == null || head2 == null)
1155        return false;
1156 
1157    while(head1.next != null)
1158        head1 = head1.next;
1159 
1160    while(head2.next != null)
1161        head2 = head2.next;
1162 
1163    return head1.equals(head2);
1164}
1165 
1166public static Node listsIntersection(Node head1, Node head2) {
1167    if(head1 == null || head2 == null)
1168        return null;
1169 
1170    int list1Length = 0;
1171    int list2Length = 0;
1172 
1173    Node n = head1;
1174 
1175    while(n != null) {
1176        list1Length++;
1177        n = n.next;
1178    }
1179 
1180    n = head2;
1181 
1182    while(n != null) {
1183        list2Length++;
1184        n = n.next;
1185    }
1186 
1187    while(list1Length > list2Length) {
1188        head1 = head1.next;
1189        list1Length--;
1190    }
1191 
1192    while(list2Length > list1Length) {
1193        head2 = head2.next;
1194        list2Length--;
1195    }
1196 
1197    while(head1 != null) {
1198        if(head1.equals(head2))
1199            return head1;
1200 
1201        head1 = head1.next;
1202        head2 = head2.next;
1203    }
1204 
1205    return null;
1206}
1207Longest Unique Substring
1208Given a string, find the length of the longest substring without repeating characters.
1209
1210Examples:
1211
1212Given "abcabcbb", the answer is "abc", which the length is 3.
1213
1214Given "bbbbb", the answer is "b", with the length of 1.
1215
1216Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
1217
1218class Solution {
1219        public int lengthOfLongestSubstring(String s) {
1220            
1221            int max = 0;
1222            
1223            Set<Character> set = new HashSet<Character>();
1224            
1225            int start = 0;
1226            int end   = 0;
1227            
1228            while(end < s.length()) {
1229                Character c = s.charAt(end);
1230
1231                if(set.contains(c)) {
1232                    while(set.contains(c)){
1233                        set.remove(s.charAt(start++));
1234                    }
1235                }
1236                
1237                set.add(new Character(c));
1238                int len = end - start + 1; // Or equivalently, len = set.size();
1239                if(max < len) {
1240                    max = len;
1241                }
1242                end++;
1243            }
1244            
1245            return max;
1246        }
1247    }
1248
1249    public static String findLongestUniqueSubstring(String str) {
1250        java.util.Set<Character> set = new java.util.HashSet<Character>();
1251
1252        int currentStart = 0;
1253
1254        int length = 0;
1255        int start  = 0;
1256
1257        for(int currentEnd = 0; currentEnd < str.length(); currentEnd++) {
1258            char c = str.charAt(currentEnd);
1259
1260            if(set.contains(c)) {
1261                while(set.contains(c)) {
1262                    set.remove(str.charAt(currentStart++));
1263                }
1264            }
1265
1266            set.add(c);
1267            if(currentEnd - currentStart + 1 > length) {
1268                length = currentEnd - currentStart + 1;
1269                start = currentStart;
1270            }
1271        }
1272
1273        return str.substring(start, start+length);
1274    }
1275
1276Power Function
1277Question: Write a function to compute a^b efficiently. (A and B are both positive)
1278
1279public static int power(int a, int b) {
1280    if(b == 0)
1281        return 1;
1282 
1283    if(b == 1)
1284        return a;
1285 
1286    int result = power(a, b/2);
1287 
1288    if(b % 2 == 0)
1289        return result * result;
1290 
1291    return result * result * a;     
1292}
1293Making Change
1294Question: For US currency, there are six coins that are in use today: 1¢, 5¢, 10¢, 25¢, 50¢, 1$. Write a function that returns the number of possible combinations of change that can be made from n ¢.
1295
1296Example:
1297
1298input: 7 output: 2 (7p, 1n 2p)
1299
1300input: 10 output: 4 (1d, 10p, 2n, 1n 5p)
1301
1302input: 15 output: 6 (1d 1n, 1d 5p, 3n, 2n 5p, 1n 10p, 15p)
1303
1304public static int combinations(int n) {
1305    return combinations(n,100);
1306}
1307 
1308public static int combinations(int n,int m) {
1309    if(n < 0)
1310        return 0;
1311 
1312    if(n == 0)
1313        return 1;
1314 
1315    int combinations = 0;
1316 
1317    if(m == 100)
1318        combinations+= combinations(n-100,100);
1319    if(m >= 50)
1320        combinations+= combinations(n-50,50);
1321    if(m >= 25)
1322        combinations+= combinations(n-25,25);
1323    if(m >= 10)
1324        combinations+= combinations(n-10,10);
1325    if(m >= 5)
1326        combinations+= combinations(n-5,5);
1327 
1328    combinations+= combinations(n-1,1);
1329 
1330    return combinations;
1331}
1332Container With Most Water
1333Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
1334
1335Note: You may not slant the container and n is at least 2.
1336
1337public int maxArea(int[] height) {
1338    int max = 0;
1339    int i = 0;
1340    int j = height.length - 1;
1341
1342    while (i < j) {
1343        int k = Math.min(height[i], height[j]) * (j - i);
1344        if(k > max) {
1345            max = k;
1346        }
1347
1348        if(height[i]>=height[j]){
1349            j--;
1350        } else {
1351            i++;
1352        }
1353    }
1354
1355    return max;
1356}
1357Maximum Sub Array
1358Question: Given an array with at least one positive integer, find the contiguous sub-array with the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous sub-array with the largest sum is 4, −1, 2, 1, with sum 6.
1359
1360public static int [] maxSubArray (int [] array) {
1361    int starting_index = 0;
1362    int length = 0;
1363    int sum = 0;
1364 
1365    int t_starting_index = 0;
1366    int t_length = 0;
1367    int t_sum = 0;
1368 
1369    for (int i = 0; i < array.length; i++) {
1370        if(t_sum + array[i] > 0) {
1371            t_sum += array[i];
1372            t_length++;
1373 
1374            if(t_sum > sum) {
1375                sum = t_sum;
1376                length = t_length;
1377                starting_index = t_starting_index;
1378            }
1379        } else {
1380            t_sum = 0;
1381            t_length = 0;
1382            t_starting_index = i + 1;
1383        }
1384    }
1385 
1386    int [] sub = new int[length];
1387 
1388    System.arraycopy(array, starting_index, sub, 0, length);
1389 
1390    return sub;
1391}
1392Solution to find the max sum:
1393
1394public static int maxSubArray(int [] array) {
1395    int max_ending_here = 0;
1396    int max_so_far = 0;
1397 
1398    for(int i: array) {
1399        max_ending_here = Math.max(0, max_ending_here + i);
1400        max_so_far = Math.max(max_so_far, max_ending_here);
1401    }
1402 
1403    return max_so_far;
1404}
1405Zig-Zag Tree Traversal
1406Question: Print out items of a Binary Tree in a zig-zag fashion.
1407
1408ZigZagTraversal.png
1409
1410public static void zigZag (Node root) {
1411    Stack<Node> s1 = new Stack<Node>();
1412    Stack<Node> s2 = new Stack<Node>();
1413 
1414    s1.push(root);
1415 
1416    while(!s1.isEmpty() || !s2.isEmpty()) {
1417        while(!s1.isEmpty()) {
1418            Node n = s1.pop();
1419 
1420            System.out.println(n.data);
1421 
1422            if(n.right != null)
1423                s2.push(n.right);
1424 
1425            if(n.left != null)
1426                s2.push(n.left);
1427        }
1428 
1429        while(!s2.isEmpty()) {
1430            Node n = s2.pop();
1431 
1432            System.out.println(n.data);
1433 
1434            if(n.left != null)
1435                s1.push(n.left);
1436 
1437            if(n.right != null)
1438                s1.push(n.right);
1439        }
1440    }
1441}
1442Symmetric Tree
1443Write a program to check if the given binary tree is symmetric tree or not. A symmetric tree is defined as a tree which is mirror image of itself about the root node. For example, following tree is a symmetric tree.
1444
1445mirrorTree_0.gif
1446
1447    public static boolean isMirror(Node n1, Node n2) {
1448        if(n1 == null && n2 == null)
1449            return true;
1450 
1451        if(n1 == null || n2 == null)
1452            return false;
1453 
1454        if(n1.data != n2.data)
1455            return false;
1456 
1457        return isMirror(n1.left,n2.right) && isMirror(n1.right, n2.left);
1458    }
1459Stairs
1460Question: A man is walking up a set of stairs. He can either take 1 or 2 steps at a time. Given n number of stairs, find out how many combinations of steps he can take to reach the top of the stairs.
1461
1462public static int combinations(int stairs) {
1463    if(stairs == 0)
1464        return 0;
1465 
1466    int i = 0;
1467    int j = 1;
1468 
1469    for(int k = 0; k <= stairs; k++) {
1470        int temp = j;
1471        j+= i;
1472        i = temp;
1473    }
1474    return i;
1475}
1476Curly braces
1477Question: Curly braces can be used in programming to provide scope-limit. Write a function to print all valid( properly opened and closed) combinations of n-pairs of curly braces.
1478
1479Example:
1480
1481input: 1 output: {}
1482
1483input: 2 output: {}{}, Legacy Wiki template overrides
1484
1485input: 3 output: {}{}{}, {}Legacy Wiki template overrides, Legacy Wiki template overrides{}, [[:Template:}{]], {{{}}}
1486
1487input: 4 output: {}{}{}{}, {}{}Legacy Wiki template overrides, {}Legacy Wiki template overrides{}, {}[[:Template:}{]], {}{{{}}}, Legacy Wiki template overrides{}{}, Legacy Wiki template overridesLegacy Wiki template overrides, [[:Template:}{]]{}, [[:Template:}{}]], [[:Template:}Legacy Wiki template overrides]] {{{}}}{}, {Legacy Wiki template overrides{}}, {[[:Template:}{}]], Template:Legacy Wiki template overrides
1488
1489    public static void printBraces(int n) {
1490        printBraces(new String(), n, n);
1491    }
1492 
1493    public static void printBraces(String str, int start, int end) {
1494        if (start == 0 && end == 0) {
1495            System.out.println(str);
1496            return;
1497        }
1498 
1499        if (start > 0) {
1500            printBraces(str+"{", start-1, end);
1501        }
1502 
1503        if (start < end) {
1504            printBraces(str+"}", start, end-1);
1505        }
1506    }
1507BST to Array and back
1508Question: Write a function to convert a sorted array to a BST of minimum height. Write a function to convert a BST to a sorted array.
1509
1510public static Node arrayToBST(int [] array, int start, int end) {
1511    if(end < start)
1512        return null;
1513 
1514    int mid = (start + end)/2;
1515 
1516    Node n = new Node(array[mid]);
1517 
1518    n.left = arrayToBST(array, start, mid-1);
1519    n.right= arrayToBST(array, mid+1, end);
1520 
1521    return n;
1522}
1523 
1524public static Integer [] BSTtoArray(Node root) {
1525    Stack<Node> stack = new Stack<Node>();
1526    Node node = root;
1527 
1528    ArrayList<Integer> list = new ArrayList<Integer>();
1529 
1530    while(!stack.isEmpty() || node != null) {
1531        if(node != null) {
1532            stack.push(node);
1533            node = node.left;
1534        } else {
1535            node = stack.pop();
1536            list.add(node.data);
1537            node = node.right;
1538        }
1539    }
1540 
1541    Integer [] array = new Integer [list.size()];
1542    list.toArray(array);
1543    return array;
1544}
1545Island Perimeter
1546You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn't have "lakes" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.
1547
1548Example
1549
15500,1,0,0], [1,1,1,0], [0,1,0,0], [1,1,0,0
1551
1552Answer: 16 Explanation: The perimeter is the 16 yellow stripes in the image below:
1553
1554island.png
1555
1556    public static int islandPerimeter(int[][] grid) {
1557        int islandPerimeter = 0;
1558        for (int i = 0; i < grid.length; i++) {
1559            for (int j = 0; j < grid[i].length; j++) {
1560                if(grid[i][j] == 1){
1561                    if (i - 1 < 0 || grid[i-1][j] != 1) {
1562                        islandPerimeter++;
1563                    }
1564                    if (j - 1 < 0 || grid[i][j-1] != 1) {
1565                        islandPerimeter++;
1566                    }
1567                    if (j + 1 >= grid[i].length || grid[i][j+1] != 1 ){
1568                        islandPerimeter++;
1569                    }
1570                    if (i + 1 >= grid.length || grid[i+1][j] != 1){
1571                        islandPerimeter++;
1572                    }
1573                }
1574            }
1575        }
1576        return islandPerimeter;
1577    }
1578Candy
1579There are N children standing in a line. Each child is assigned a rating value.
1580
1581You are giving candies to these children subjected to the following requirements:
1582
1583Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. What is the minimum candies you must give?
1584
1585Solution
1586
1587public static int candy(int[] ratings) {
1588    int[] left = new int[ratings.length];
1589    int[] right = new int[ratings.length];
1590    
1591    Arrays.fill(left, 1);
1592    Arrays.fill(right, 1);
1593    
1594    for (int i = 1; i < ratings.length; i++) {
1595        if (ratings[i] > ratings[i-1]) {
1596            left[i] = left[i-1] + 1;
1597        }
1598    }
1599    
1600    for (int i = ratings.length -2; i >= 0; i--) {
1601        if (ratings[i] > ratings[i+1]) {
1602            right[i] = right[i+1] + 1;
1603        }
1604    }
1605    
1606    int candies = 0;
1607    
1608    for (int i = 0; i < ratings.length; i++) {
1609        candies += Math.max(left[i], right[i]);
1610    }
1611    return candies;
1612}
1613Binary Search Tree
1614Question: Write a function to determine if a Binary Tree is a Binary Search Tree.
1615
1616Solution
1617
1618class Node {
1619  int data;
1620  Node left;
1621  Node right;
1622}
1623 
1624public static boolean isBST(Node root, Integer min, Integer max) {
1625    if (root == null)
1626        return true;
1627
1628    if(min != null && min > root.data)
1629        return false;
1630
1631    if(max != null && max <= root.data)
1632        return false;
1633
1634    return isBST(root.left, min, root.data) && isBST(root.right, root.data, max);
1635    }
1636Hash Table
1637Write a basic implementation of HashTable
1638
1639public class HashTable {
1640    private class Node {
1641        public Object key;
1642        public Object value;
1643        public Node next;
1644 
1645        public Node (Object key, Object value) {
1646            this.key = key;
1647            this.value = value;
1648        }
1649    }
1650 
1651    private Node[] buckets;
1652    private int tableSize;
1653    private int size;
1654 
1655    public HashTable(int tableSize) {
1656        this.tableSize = tableSize;
1657        buckets = new Node[tableSize];
1658        size = 0;
1659    }
1660 
1661    public void put(Object key, Object value) throws NullPointerException {
1662        if (key == null)
1663            throw new NullPointerException("Key cannot be null!");
1664 
1665        int location = key.hashCode() % tableSize;
1666 
1667        if (buckets[location] == null) {
1668            buckets[location] = new Node(key, value);
1669        } else {
1670            Node n = buckets[location];
1671            Node p = null;
1672 
1673            while (n != null) {
1674                if (n.key.equals(key)) {
1675                    n.value = value;
1676                    return;
1677                }
1678 
1679                p = n;
1680                n = n.next;
1681            }
1682 
1683            p.next = new Node(key, value);
1684        }
1685 
1686        size++;
1687    }
1688 
1689    public Object get(Object key) throws NullPointerException {
1690        if (key == null)
1691            throw new NullPointerException("Key cannot be null!");
1692 
1693        int location = key.hashCode() % tableSize;
1694 
1695        Node n = buckets[location];
1696 
1697        while (n != null && !n.key.equals(key))
1698            n = n.next;
1699 
1700        if (n == null)
1701            return null;
1702        else
1703            return n.value;
1704    }
1705 
1706    public Object remove(Object key) throws NullPointerException {
1707        if (key == null)
1708            throw new NullPointerException("Key cannot be null!");
1709 
1710        int location = key.hashCode() % tableSize;
1711 
1712        Node n = buckets[location];
1713        Node p = null;
1714 
1715        while (n != null && !n.key.equals(key)) {
1716            p = n;
1717            n = n.next;
1718        }
1719 
1720        if (n == null)
1721            return null;
1722 
1723        size--;
1724 
1725        if (p == null)
1726            buckets[location] = n.next;
1727        else
1728            p.next = n.next;
1729 
1730        return n.value;
1731    }
1732 
1733    public int size() {
1734        return size;
1735    }
1736 
1737    public boolean isEmpty() {
1738        return size == 0;
1739    }
1740Min Stack
1741Question: Write an implementation of a Stack that supports push(), pop(), and min() functions in constant time.
1742
1743public class Stack {
1744    public class Node {
1745        Integer value;
1746        Node next;
1747
1748        public Node(Integer value) {
1749            this.value = value;
1750        }
1751    }
1752
1753    private Node head;
1754    private Node minHead;
1755
1756    public Stack() {
1757        head = null;
1758        minHead = null;
1759    }
1760
1761    public void push(Integer value) {
1762        Node node = new Node(value);
1763
1764        if(head == null) {
1765            head = node;
1766            minHead = new Node(value);
1767        } else {
1768            node.next = head;
1769            head = node;
1770
1771            if (value <= minHead.value) {
1772                Node newMin = new Node(value);
1773                newMin.next = minHead;
1774                minHead = newMin;
1775            }
1776        }
1777    }
1778
1779    public Integer pop() {
1780        if (head == null)
1781            return null;
1782
1783        Node n = head;
1784        head = head.next;
1785
1786        if (n.value == minHead.value)
1787            minHead = minHead.next;
1788
1789        return n.value;
1790    }
1791
1792    public Integer min() {
1793        if (minHead == null)
1794            return null;
1795
1796        return minHead.value;           
1797    }
1798}
1799Unique Characters
1800Question: Implement an algorithm to determine if a string has all unique characters.
1801
1802    public static boolean isUnique(String str) {
1803        boolean [] character_set = new boolean[256];
1804 
1805        for(int i = 0; i < str.length(); i++) {
1806            int val = str.charAt(i);
1807 
1808            if(character_set[val])
1809                return false;
1810 
1811            character_set[val] = true;
1812        }
1813        return true;
1814    }
1815Anagrams
1816Question: Write an algorithm to determine whether two strings are anagrams or not.
1817
1818    public static boolean isAnagram(String str1, String str2) {
1819        if (str1.length() != str2.length())
1820            return false;
1821 
1822        int [] character_set = new int[256];
1823 
1824        for(int i = 0; i < str1.length(); i++) {
1825            character_set[str1.charAt(i)]++;
1826            character_set[str2.charAt(i)]--;
1827        }
1828 
1829        for(int i = 0; i < str1.length(); i++)
1830            if(character_set[str1.charAt(i)] != 0)
1831                return false;
1832 
1833        return true;
1834    }
1835Merge two sorted lists
1836Question: Write a function, that given two sorted lists of integers as input, returns a single sorted list with items from both lists with no duplicate elements.
1837
1838Example: input: a = {1,2,3}; b = {4,5,6}; output: c = {1,2,3,4,5,6}; input: a = {7,8,9}; b = {1,8,20,24}; output: c = {1,7,8,9,20,24}; input: a = {3,3,4}; b = {4}; output: c = {3,4}; input: a = {1,2,2,3,3,4,5,6,7}; b = {4,5,6,7,8,8,8}; output: c = {1,2,3,4,5,6,7,8};
1839
1840    public static List<Integer> merge(int [] a, int [] b) {
1841        List<Integer> list = new ArrayList<Integer>();
1842 
1843        int a_index = 0;
1844        int b_index = 0;
1845 
1846        Integer i = null;
1847 
1848        while(a_index < a.length && b_index < b.length) {
1849            if(a[a_index] < b[b_index]) {
1850                if(i == null || i < a[a_index]) {
1851                    i = a[a_index];
1852                    list.add(i);
1853                }
1854 
1855                a_index++;
1856            } else {
1857                if(i == null || i < b[b_index]) {
1858                    i = b[b_index];
1859                    list.add(i);
1860                }
1861 
1862                b_index++;
1863            }
1864        }
1865 
1866        while (a_index < a.length) {
1867            if (i == null || i < a[a_index]) {
1868                i = a[a_index];
1869                list.add(i);
1870            }
1871            a_index++;
1872        }
1873 
1874        while (b_index < b.length) {
1875            if (i == null || i < b[b_index]) {
1876                i = b[b_index];
1877                list.add(i);
1878            }
1879 
1880            b_index++;
1881        }
1882 
1883        return list;
1884    }
1885Subsets
1886Find all subsets of a set
1887
1888Example:
1889
1890input: {a,b}
1891
1892output: {}{a}{b}{a,b}
1893
1894input: {a,b,c}
1895
1896output: {}{a}{b}{c}{a,b}{a,c}{b,c}{a,b,c}
1897
1898input:{abcd}
1899
1900output:{} {d} {b} {c} {a} {bc} {da} {ca} {dc} {db} {ba} {dbca} {bca} {dba} {dca} {dbc}
1901
1902public static Set<Set<Object>> getSubsets(Set<Object> set) {
1903        Set<Set<Object>> subsets = new HashSet<Set<Object>>(); 
1904 
1905        subsets.add(new HashSet<Object>());
1906 
1907        for(Object o : set) {
1908            Set<Set<Object>> temp = new HashSet<Set<Object>>();
1909            for(Set<Object> s: subsets)
1910                temp.add(new HashSet<Object>(s));
1911 
1912            for (Set<Object> s : temp)
1913                s.add(o);
1914 
1915            subsets.addAll(temp);
1916        }       
1917        return subsets;
1918    }
1919    
1920    public static Set<Set<Object>> getSubsets(List<Object> list) {
1921        Set<Set<Object>> subsets = new HashSet<Set<Object>>();
1922 
1923        for(int i = 0; i < Math.pow(2, list.size()); i++) {
1924            Set<Object> subset = new HashSet<Object>();
1925 
1926            int j = 1;
1927            for(int k = 0; k < list.size(); k++) {
1928                if((j & i) != 0) {
1929                    subset.add(list.get(k));
1930                }
1931                j = j << 1;
1932            }
1933            subsets.add(subset);
1934        }
1935        return subsets;
1936    }
1937String Permutations
1938Question: Find all permutations of a String.
1939
1940Example:
1941
1942input: abcd
1943
1944output: dcba, cdba, cbda, cbad, dbca, bdca, bcda, bcad, dbac, bdac, badc, bacd, dcab, cdab, cadb, cabd, dacb, adcb, acdb, acbd, dabc, adbc, abdc, abcd
1945
1946public static ArrayList<String> findPermutations(String str) {
1947    ArrayList<String> permutations = new ArrayList<String>();
1948    permutations.add(new String());
1949
1950    char [] strArray = str.toCharArray();
1951
1952    for(char c : strArray) {
1953        ArrayList<String> tempList = new ArrayList<String>();
1954
1955        for(String s: permutations) {
1956            for(int i = 0; i < s.length(); i++)
1957                tempList.add(new String(s.substring(0, i) + c + s.substring(i, s.length())));
1958            tempList.add(new String(s+c));
1959        }
1960        permutations = tempList;
1961    }
1962    return permutations;
1963}
1964Array Intersection
1965Question: Find the intersection of two unsorted integer arrays.
1966
1967public static Set<Integer> arrayIntersection(int [] list1, int [] list2) {
1968    Set<Integer> output = new HashSet<Integer>();
1969
1970    Set<Integer> set = new HashSet<Integer>(); 
1971
1972    for(int i : list1)
1973        set.add(i);
1974
1975    for(int i: list2)
1976        if(set.contains(i))
1977            output.add(i);
1978
1979    return output;
1980}
1981Sorting
1982Question: Write an efficient sorting algorithm.
1983
1984public static int[] quickSort(int [] array, int low, int high) {
1985        if(array == null)
1986            return null;
1987 
1988        if(array.length==0)
1989            return array;
1990 
1991        int i = low, j = high;
1992 
1993        int pivot = array[low + (high-low)/2];
1994 
1995        while (i <= j) {
1996            while (array[i] < pivot)
1997                i++;
1998 
1999            while (array[j] > pivot)
2000                j--; 
2001 
2002            if (i <= j) {
2003                int temp = array[i];
2004                array[i] = array[j];
2005                array[j] = temp;
2006                i++;
2007                j--;
2008            }
2009        }
2010 
2011        if (low < j)
2012            quickSort(array, low, j);
2013 
2014        if (i < high)
2015            quickSort(array, i, high);
2016 
2017        return array;
2018    }
2019 
2020    public static int[] mergeSort(int [] array) {
2021        if(array == null)
2022            return null;
2023 
2024        if(array.length < 2)
2025            return array;
2026 
2027        int [] array1 = new int[array.length/2];
2028 
2029        System.arraycopy(array, 0, array1, 0, array1.length);
2030 
2031        int [] array2;
2032 
2033        if(array.length%2==0)
2034            array2 = new int[array.length/2];
2035        else 
2036            array2 = new int[array.length/2+1];
2037 
2038        System.arraycopy(array, array1.length, array2, 0, array2.length);
2039 
2040        array1 = mergeSort(array1);
2041        array2 = mergeSort(array2);
2042 
2043        int a = 0;
2044        int a1 = 0;
2045        int a2 = 0;
2046 
2047        while(a1 < array1.length && a2 < array2.length)
2048            if(array1[a1]<array2[a2])
2049                array[a++]=array1[a1++];
2050            else
2051                array[a++]=array2[a2++];
2052 
2053        while(a1 < array1.length)
2054            array[a++]=array1[a1++];
2055 
2056        while(a2 < array2.length)
2057            array[a++]=array2[a2++];
2058 
2059        return array;
2060    }
2061Missing Number
2062Question: Find the missing number in an array of consecutive integers.
2063
2064Example:
2065
2066input:2,3,4,5,6,7,8,9,10,11,12,13,14,15 output: null
2067
2068input:2,3,5,6,7,8,9,10,11,12,13,14,15 output: 4
2069
2070input:2,3,4,5,6,7,8,9,10,11,12,14,15 output: 13
2071
2072    public static Integer missingNumber(int [] array) {
2073        int low = 0;
2074        int high = array.length -1;
2075 
2076        int mid;
2077 
2078        while(low<high) {
2079            mid = (low+high)/2;
2080 
2081            if(mid-low == array[mid]- array[low]) {
2082                if( mid+1< array.length && array[mid]+1 != array[mid+1])
2083                    return array[mid]+1;
2084                else
2085                    low = mid+1;
2086            } else {
2087                if(mid -1 > -1 && array[mid]-1 != array[mid-1])
2088                    return array[mid]-1;
2089                else
2090                    high = mid-1;
2091            }
2092        }
2093 
2094        return null;
2095    }
2096Missing Spaces
2097Question: You are given a sentence with no spaces and dictionary containing thousands of words. Write an algorithm to reconstruct the sentence by inserting spaces in the appropriate positions.
2098
2099Example:
2100
2101input: "theskyisblue" output: "the sky is blue"
2102
2103input: "thegrassisgreen" output: "the grass is green"
2104
2105    public static String makeSentence(String str, Set<String> dictionary) {
2106        char [] array = str.toCharArray();
2107 
2108        StringBuilder prefix = new StringBuilder();
2109 
2110        for(int i = 0; i < array.length; i++) {
2111            prefix.append(array[i]);
2112 
2113            if(dictionary.contains(prefix.toString())) {
2114                if (prefix.length() == array.length)
2115                    return prefix.toString();
2116 
2117                String suffix = makeSentence(new String(array,prefix.length(),array.length-prefix.length()), dictionary);
2118 
2119                if (suffix != null) {
2120                    prefix.append(" ");
2121                    prefix.append(suffix);
2122                    return prefix.toString();
2123                }
2124            }
2125        }
2126 
2127        return null;
2128    }
2129Nth smallest element in a binary search tree
2130Question: Write a function to find the nth smallest element in a binary search tree
2131
2132class Node {
2133    int i;
2134    Node left;
2135    Node right;
2136}
2137
2138public static Node nthSmallestElement(Node root, int n) {
2139    Stack<Node> stack = new Stack<Node>();
2140    Node node = root;
2141    int i = 0;
2142 
2143    while (!stack.isEmpty() || node != null) {
2144        if (node != null) {
2145            stack.push(node);
2146            node = node.left;
2147        } else {
2148            node = stack.pop();
2149            if(++i == n) {
2150                return node;
2151            }
2152            node = node.right;
2153        }
2154    }
2155 
2156    return null;
2157}
2158Implement a Queue
2159public class Node {
2160    public Node next;
2161    public Object data;
2162}
2163
2164public class Queue {
2165    private Node start;
2166    private Node end;
2167    
2168    public Queue() {
2169        start = null;
2170        end = null;
2171    }
2172    
2173    public void add(Object o) {
2174        Node newNode = new Node();
2175        newNode.data = o;
2176        
2177        if (start == null) {
2178            start = newNode;
2179            end = newNode;
2180        } else {
2181            end.next = newNode;
2182            end = newNode;
2183        }
2184    }
2185    
2186    public Object remove() {
2187        if (start == null) {
2188            return null;
2189        }
2190        
2191        Object o = first.data;
2192        first = first.next;
2193        return o;
2194    }
2195}
2196LinkedList of Nodes in a Binary Tree
2197Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth.
2198
2199public static ArrayList<LinkedList<Node>> makeLinkedLists(Node root) {
2200    LinkedList<Node> current = new LinkedList<Node>();
2201    LinkedList<Node> nextLevel = new LinkedList<Node>();
2202    ArrayList<LinkedList<Node>> lists = new ArrayList<LinkedList<Node>>();
2203
2204    current.add(root);
2205
2206    while (!current.isEmpty()) {
2207        lists.add(current);
2208        
2209        for (Node n : current)) {
2210            if (n.left != null) nextLevel.add(n.left);
2211            if (n.right != null) nextLevel.add(n.right);
2212        }
2213
2214        current = nextLevel;
2215        nextLevel = new LinkedList<Node>();
2216    }
2217    return lists;
2218}
2219Inorder Successor in Binary Search Tree
2220Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
2221
2222public static Node inorderSuccessor(Node root, Node n) {
2223    if(n.right != null){
2224        n = n.right;
2225        while(n.left !=null){
2226            n = n.left;
2227        }
2228        return n;
2229    }
2230    Node successor = null;
2231    while(root != null) {
2232        if(n.data < root.data){
2233            successor = root;
2234            root = root.left;
2235        } else if(n.data > root.data){
2236            root = root.right;
2237        } else {
2238            break;
2239        }
2240    }
2241    return successor;
2242}
2243Find min element in rotated, sorted array
2244Find the minimum element in a rotated, sorted array.
2245
2246Example: 4,5,6,7,8,2,3 Answer: 2
2247
2248public static int (int[] array) {
2249    int start = 0;
2250    int end = array.length - 1;
2251
2252    while(start < end) {
2253        if (array[start] < array[end]) {
2254            return array[start];
2255        }
2256        
2257        int mid = array[(start + end)/2];
2258        if (array[mid] >= array[start]) {
2259            start = mid+1;
2260       } else {
2261           end = mid;
2262       }
2263    }
2264    return num[start];
2265}
2266Palindrome
2267Question: Write a function to find out whether a string is a palindrome.
2268
2269    public static boolean isPalindrome(String input) {
2270        int i = 0;
2271        int j = input.length() - 1;
2272 
2273        while (i < j) {
2274            if (input.charAt(i) != input.charAt(j)) {
2275                return false;
2276            }
2277            i++;
2278            j--;
2279        }
2280 
2281        return true;
2282    }
2283Heap
2284Implement a min heap
2285
2286public class BinaryHeap<T extends Comparable<T>>{
2287    private static final int DEFAULT_CAPACITY = 10;
2288    private int size;
2289    private T[] heap;
2290
2291    public BinaryHeap() {
2292        size = 0;
2293        heap = (T[]) new Comparable[DEFAULT_CAPACITY];
2294    }
2295
2296    public T peek() {
2297        if (this.isEmpty()) {
2298            return null;
2299        }
2300        return heap[0];
2301    }
2302
2303    public void add(T value) {
2304        if (size >= heap.length) {
2305            heap = this.resize();
2306        }
2307
2308        heap[size++] = value;
2309        bubbleUp();
2310    }
2311
2312    public T remove() {
2313        T result = peek();
2314
2315        heap[0] = heap[size - 1];
2316        heap[size - 1] = null;
2317        size--;
2318
2319        bubbleDown();
2320
2321        return result;
2322    }
2323
2324    public boolean isEmpty() {
2325        return size == 0;
2326    }
2327
2328    public int size() {
2329        return size;
2330    }
2331
2332    private T[] resize() {
2333        return java.util.Arrays.copyOf(heap, heap.length * 2);
2334    }
2335
2336    private boolean hasParent(int i) {
2337        return i > 0;
2338    }
2339
2340    private int leftIndex(int i) {
2341        return (i * 2) + 1;
2342    }
2343
2344    private int rightIndex(int i) {
2345        return (i * 2) + 2;
2346    }
2347
2348    private boolean hasLeftChild(int i) {
2349        return leftIndex(i) < size;
2350    }
2351
2352    private boolean hasRightChild(int i) {
2353        return rightIndex(i) < size;
2354    }
2355
2356    private T parent(int i) {
2357        return heap[parentIndex(i)];
2358    }
2359
2360    private int parentIndex(int i) {
2361        return (i-1) / 2;
2362    }
2363
2364    private void swap(int index1, int index2) {
2365        T tmp = heap[index1];
2366        heap[index1] = heap[index2];
2367        heap[index2] = tmp;
2368    }
2369
2370    private void bubbleUp() {
2371        int index = this.size - 1;
2372
2373        while (hasParent(index)
2374                && (parent(index).compareTo(heap[index]) > 0)) {
2375            swap(index, parentIndex(index));
2376            index = parentIndex(index);
2377        }
2378    }
2379
2380    private void bubbleDown() {
2381        int index = 0;
2382
2383        while (hasLeftChild(index)) {
2384            int smallerChild = leftIndex(index);
2385
2386            if (hasRightChild(index)
2387                    && heap[leftIndex(index)].compareTo(heap[rightIndex(index)]) > 0) {
2388                smallerChild = rightIndex(index);
2389            }
2390
2391            if (heap[index].compareTo(heap[smallerChild]) > 0) {
2392                swap(index, smallerChild);
2393            } else {
2394                break;
2395            }
2396
2397            index = smallerChild;
2398        }
2399    }
2400}
2401Median Value
2402Question: Write a function to find the median value from a stream of integers.
2403
2404
2405public static Double median (Iterator<Integer> stream){
2406    Queue<Integer> minHeap = new PriorityQueue<Integer>();
2407    Queue<Integer> maxHeap = new PriorityQueue<Integer>(20, Collections.reverseOrder());
2408
2409    while(stream.hasNext()){
2410        maxHeap.add(stream.next());
2411
2412        if (!minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()){
2413            Integer maxHeapRoot = maxHeap.poll();
2414            Integer minHeapRoot = minHeap.poll();
2415            maxHeap.add(minHeapRoot);
2416            minHeap.add(maxHeapRoot);
2417        }
2418
2419        if(maxHeap.size() - minHeap.size() > 1) {
2420            minHeap.add(maxHeap.poll());
2421        }
2422    }
2423
2424    if (maxHeap.size() > minHeap.size()){
2425        return maxHeap.peek().doubleValue();
2426    }
2427
2428    return (maxHeap.peek() + minHeap.peek()) / 2.0;
2429}
2430Calculate Angle
2431Given the time, calculate the smaller angle between the hour and minute hands on an analog clock.
2432
2433public static int (int hour, int min) {
2434    int minuteAngle = min * 6;
2435    int hourAngle = hour * 30 + (min / 2);
2436    
2437    int angle = Math.abs(minuteAngle - hourAngle);
2438    return Math.min(360 -  angle, angle);
2439}
2440Implement a LRU Cache
2441Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
2442
2443class Node{
2444    int key;
2445    int value;
2446    Node pre;
2447    Node next;
2448 
2449    public Node(int key, int value){
2450        this.key = key;
2451        this.value = value;
2452    }
2453}
2454
2455public class LRUCache {
2456    int capacity;
2457    HashMap<Integer, Node> map = new HashMap<Integer, Node>();
2458    Node head=null;
2459    Node end=null;
2460 
2461    public LRUCache(int capacity) {
2462        this.capacity = capacity;
2463    }
2464 
2465    public int get(int key) {
2466        if(map.containsKey(key)){
2467            Node n = map.get(key);
2468            remove(n);
2469            setHead(n);
2470            return n.value;
2471        }
2472 
2473        return -1;
2474    }
2475 
2476    public void remove(Node n){
2477        if(n.pre!=null){
2478            n.pre.next = n.next;
2479        }else{
2480            head = n.next;
2481        }
2482 
2483        if(n.next!=null){
2484            n.next.pre = n.pre;
2485        }else{
2486            end = n.pre;
2487        }
2488 
2489    }
2490 
2491    public void setHead(Node n){
2492        n.next = head;
2493        n.pre = null;
2494 
2495        if(head!=null)
2496            head.pre = n;
2497 
2498        head = n;
2499 
2500        if(end ==null)
2501            end = head;
2502    }
2503 
2504    public void set(int key, int value) {
2505        if(map.containsKey(key)){
2506            Node old = map.get(key);
2507            old.value = value;
2508            remove(old);
2509            setHead(old);
2510        }else{
2511            Node created = new Node(key, value);
2512            if(map.size()>=capacity){
2513                map.remove(end.key);
2514                remove(end);
2515                setHead(created);
2516 
2517            }else{
2518                setHead(created);
2519            }    
2520 
2521            map.put(key, created);
2522        }
2523    }
2524}
2525Rotate Array
2526Write a function to rotate an array to the left n-times.
2527
2528    static int[] rotLeft(int[] array, int n) {
2529        int[] rotatedArray = new int[array.length];
2530        for(int index = 0; index < array.length; index++) {
2531            int newPos = (index + (array.length - n)) % array.length;
2532            rotatedArray[newPos] = array[index];
2533        }
2534        return rotatedArray;
2535    }
2536Rotate 2D Array
2537Write a function to rotate an NxN array 90 degrees.
2538
2539public static void rotate(int[][] matrix, int n) {
2540    for (int layer = 0; layer < n / 2; ++layer) {
2541        int first = layer;
2542        int last = n - 1 - layer;
2543        for(int i = first; i < last; ++i) {
2544            int offset = i - first;
2545            int top = matrix[first][i]; // save top
2546
2547            // left -> top
2548            matrix[first][i] = matrix[last-offset][first];          
2549            // bottom -> left
2550            matrix[last-offset][first] = matrix[last][last - offset]; 
2551
2552            // right -> bottom
2553            matrix[last][last - offset] = matrix[i][last]; 
2554
2555            // top -> right
2556            matrix[i][last] = top; // right <- saved top
2557        }
2558    }
2559}
2560Implement a Queue using two stacks
2561public class TwoStacks {
2562    Stack<Object> pushStack;
2563    Stack<Object> popStack;
2564
2565    public TwoStacks (){
2566        pushStack = new Stack<>();
2567        popStack = new Stack<>();
2568    }
2569
2570    public void push(Object o) {
2571        pushStack.push(o);
2572    }
2573
2574    public Object pop() {
2575        if (!popStack.isEmpty()) {
2576            return popStack.pop();
2577        }
2578        while(!pushStack.isEmpty()){
2579            popStack.push(pushStack.pop());
2580        }
2581        if (!popStack.isEmpty()) {
2582            return popStack.pop();
2583        }
2584        return null;
2585    }
2586}
2587Balanced Binary Tree
2588Implement an algorithm to determine is a binary tree is balanced. A balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one.
2589
2590public static boolean isBalanced(Node root){
2591    return (getHeight(root) != -1);
2592}
2593public static int getHeight(Node root) {
2594    if (root == null) {
2595        return 0;
2596    }
2597    
2598    int leftHeight = getHeight(root.left);
2599    if (leftHeight == -1) {
2600        return -1;
2601    }
2602    
2603    int rightHeight = getHeight(root.right);
2604    if (rightHeight == -1) {
2605        return -1;
2606    }
2607    
2608    if (Math.abs(leftHeight - rightHeight) > 1) {
2609        return -1;
2610    }
2611    
2612    return Math.max(leftHeight, rightHeight) + 1;
2613}
2614Lowest Common Ancestor
2615Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
2616
2617public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
2618    if (root == null || root == p || root == q) return root;
2619    TreeNode left = lowestCommonAncestor(root.left, p, q);
2620    TreeNode right = lowestCommonAncestor(root.right, p, q);
2621    return left == null ? right : right == null ? left : root;
2622}
2623Fibonacci
2624Implement a function which returns the nth number in Fibonacci sequences with an input n.
2625
2626public static int fibonacci(int n) {
2627    if (n == 0 || n == 1) {
2628        return n;
2629    }
2630
2631    int fibMinus1 = 1;
2632    int fibMinus2 = 0;
2633
2634    int fibN = 0;
2635
2636    for (int i = 2; i <= n; i++) {
2637        fibN = fibMinus1 + fibMinus2;
2638        fibMinus2 = fibMinus1;
2639        fibMinus1 = fibN;
2640    }
2641
2642    return fibN;
2643}
2644First Unique Character
2645Find the first unique character in a string.
2646
2647public static Character firstUniqueCharacter(char[] string) {
2648    Map<Character, Integer> map = new HashMap<Character, Integer>();
2649    for (char c: string) {
2650        Integer i = map.get(c);
2651        map.put(c, (i==null) ? 1: 1+i);
2652    }
2653    for (char c: string) {
2654        Integer i = map.get(c);
2655        if (i == 1) {
2656            return c;
2657        }
2658    }
2659    return null;
2660}
2661Largest number in BST which is less than or equal to N
2662We have a binary search tree and a number N. Our task is to find the greatest number in the binary search tree that is less than or equal to N. Print the value of the element if it exists otherwise print -1.
2663
2664public static int (Node root, int n) {
2665    int val = -1;
2666    while(root != null) {
2667        if(root.data > n) {
2668            root = root.left;
2669        } else {
2670            val = root.data;
2671            root = root.right;
2672        }
2673    }
2674    return val;
2675}
2676
2677========
2678
2679Problem
2680Given a linked list where each node has a next pointer and a random pointer, make a deep copy of the list.
2681
2682Clarification
2683The random pointer can be null for some list nodes.
2684=========
2685Background
2686Multiplication of a p×q matrix and another q×r matrix pqr scalar multiplications and pqr scalar additions, and results in a p×r matrix.
2687
2688Matrix multiplications are also associative, e.g. (AB)C=A(BC).
2689
2690However, given different dimensions of these matrices, different ways of parenthesizing may end up requiring different numbers of scalar operations. Example: Given a 2×300 A, a 300×4 B, and a 4×5 C:
2691
2692(AB)C involves first using 2×300×4=2400 scalar operations to calculate AB, a 2×4 matrix, then using 2×4×5=40 more scalar operation for calculating (AB)C; total: 2440 operations;
2693A(BC) involves 300×4×5=6000 scalar operations for first calculating BC, which is a 300×5 matrix, then involves 2×300×5=3000 more scalar operations for calculating A(BC); total: 9000 operations.
2694Question
2695Given the dimensions of N matrices Ai, 1 ≤ i ≤ N, where the dimensions allow their multiplication, i.e. A1A2A3…AN-1AN is defined:
2696
2697Part 1
2698Find all possible ways of parenthesizing them.
2699
2700Part 2
2701Find the best way to parenthesize them, i.e. so as to minimize the required number of scalar operations for its calculation.
2702
2703Give breakdowns of ABCD as an example early on
2704ABCD can be parenthesized in these ways:
2705
2706(((AB)C)D)
2707((AB)(CD))
2708((A(BC))D)
2709(A((BC)D))
2710(A(B(CD)))
2711It helps the candidate in two ways:
2712
2713It demonstrates that not every multiplication involves a leaf matrix—((AB)(CD)) is the counterexample; see the unviable leaf-assimilation approach below.
2714The candidate may realize that he had better remember the interim result of parenthesized portions, e.g. each of “(AB)”, “(BC)”, and “(CD)” occurs 3 times above, and this is the first step for a non-brute-force approach.
2715
2716========
2717Problem
2718To rotate/shift the elements of a square array clockwise by one at a time. (Not by 90 degrees, but by one element. Think of concentric circles.)
2719
2720Example:
2721
2722 1 2
2723 3 4
2724becomes:
2725
2726 3 1
2727 4 2
27283x3:
2729
2730 1 2 3
2731 4 5 6
2732 7 8 9
2733becomes:
2734
2735 4 1 2
2736 7 5 3
2737 8 9 6
2738Approaches
2739One of the cleanest approach is to temp 0,0, and move the first column first, first row last. Most candidate do not get time to realize this.
2740For starters, candidate should be able to shift the first row successfully.
2741Setting element [0][n] to temp is sufficient. Shift will occur in reverse order; second-last element first, first element last
2742BAD: if they shift first element first, which will create messy overwrite issues, and will need a lot of temporary variables set. Candidate should be able to observe this, and go to the correct solution.
2743Once they successfully completed first row and nth column, should not need to complete the rest.
2744For inner rotation, either recursion or iteration works fine.
2745Recursion may be more intuitive to most candidates. Either pass in boundaries of smaller array in context of bigger one, OR create a smaller array and pass that to the function.
2746Approach should work for 1x1. No need to handle as special case, but fine if they do point out as test case.
2747Need to handle 0x0 exception case. Also, need to make sure array is square if creating a function.
2748Solid candidate should solve this in 15 minutes max.
2749
2750==========
2751
2752Purpose
2753After searching for just the right problem complexity for SDE interview questions, I personally developed this coding problem for usage during SDE Interviews. It purposely does not use higher-level data structures which might ordinarily be used, like HashSet to guarantee uniqueness of values. In fact, the code solution shown here leverages nothing but Java Arrays. The focus of the problem is purely logical, with the goal of determining how the interviewee thinks about problems.
2754
2755To date (Aug 2019),  I have used this as an interview question over 20 times with good results. The code has several optional layers which can be added in case the candidate solves the problem quickly. For instance, these methods are optional and are normally not required for a standard 25~30 minute coding session:
2756
2757        sudoku.printGrid(sudokuGrid);  // prints the input grid
2758        sudoku.validateChars(sudokuGrid);  // validates that the int grid contains only the allowed chars (digits 1 through 9)
2759
2760When running a phone screen, I normally cut/paste the top comments section that contains the game rules (i.e. constraints) into the livecode window. Alternately, for in-person interviews, you can write these rules on the board or just state them, according to candidate's familiarity with the game.
2761
2762As long as the code solves the primary challenge, to validate whether the rules of the Sudoku Game have been met by the input grid, then the interview should be counted a success.
2763
2764Several times, candidates have pushed back on the need to validate the grid using all of the stated constraints. They have claimed there are shortcuts to arriving at the answer. Therefore, I have found the following discussion on Google Groups that talks about some potential shortcuts for solving Sudoku puzzles:
2765
2766https://groups.google.com/forum/#!topic/rec.puzzles/6AFT8aPHZ1E
2767
2768There is a proof that shows you can sufficiently test the validity by evaluating only 21 of the 27 stated constraints. However, the solution is actually harder to implement in code than simply walking through all the stated rules. Another claim is that if you simply add all the numbers in each row and column and arrive at a sum of 45 (= 1+2+3+4+5+6+7+8+9), then it is sufficient proof. However, I have proven via coding test that this alone does not provide sufficiency.