Java Interview Questions | Glassdoor

# Java Interview Questions

6,004

interview questions shared by candidates

## Java Interview Questions

Sort: RelevancePopular Date

### Software Engineer at Google was asked...

Apr 30, 2011
 Interviewer ask me to solve some permutation related problems. 1) Algorithm to get Index of a permutation when all permutations arranged in lexicographical order and its complexity9 AnswersThis is equivalent to searching in sorted array (which means that the word 'permutation' is here just to mislead you), that is, binary search. Complexity is O(log n) By the way, linear scan in an array of all permutations of n-character string is O(n!)you're a little off here. Using your definition of n, there are n! strings in the sorted array. Finding a particular one using binary search takes O(log n!) time.The permutations in lexigraphic order look like this 012345 ... ( 5!-1 more permutations that start with 0 ) 102345 ... ( 5!-1 more permutations that start with 1 ) 201345 ... ( 5!-1 more permutations that start with 2 ) So if the permutation starts with a 2 its position is 2 * 5! + (offset within the list that starts with a 2) I think this is a start of an efficient recursive method for determining the position, but in the recursion you have to translate the remaining digits properly...Show More ResponsesHere's my solution in Java, which takes log(N) time to 'calculate' the position. N being the length of the permutation string. Using a binary search ignores the fact that the list is not sorted but also complete, so we can calculate the position without going through the list. public static int getPermIndex(String[] perms, String needle) { // perms is ordered letters, take it as reference int itemsBefore = 0; for (int i = 0; i 0) itemsBefore += diff * fact(needle.length() - (i + 1)); } return itemsBefore; } public static int fact(int n) { if (n == 0 || n == 1) return 1; return n * fact(n - 1); }Your code is not correct, for this String[] s = {"123","132","213","231","312","321"}; for 321 will return 4 instead of 5.public static int IndexOfPermutationInLexicographicOrder(string start, string prefix, int index) { if (prefix == start) return index; int i = Array.BinarySearch(start.ToCharArray(), prefix); index += i * Factorial(prefix.Length - 1); index = IndexOfPermutationInLexicographicOrder(start.Remove(i, 1), prefix.Remove(0, 1), index); return index; }Just to clarify, initial call to the function will be made as follows IndexOfPermutationInLexicographicOrder("abcd", "bcad", 0), if bcad is the string whose index you need to find. the "start" specifies the original sort order/lexical orderHow about this: We look for the first "out of position" character, c, in our permutation string. Suppose we find it at "i". We know there must have been at least ret=(c-i)*(N-i-1) permutations before it. But there could be more than that, since the final part (i to N) might also contain some out-of-order characters. The "index" of this final part permutation must then be added to ret. We can easily find this index recursively using the logic above, if we first map that final part to a corresponding permutation. This can be easily done as per the code below. The total runtime of this method is O(N), where N is the length of the permutation. public static long getPermIndex(String perm) { int ret=0; for(int i=0;iHere's a solution that is O(k) where k is the number of letters in the input string For example: Say you have 6 letters being permuted (abcdef) and you want to know the index of the particular permutation, say facbed sort the letters: abcdef take the first letter of the input 'f' find its index in the sorted letters (5) Now you know that its index will be in the range of 5 * (n-1)! - compute that value: 5 * 120 = 600 now remove that letter from the input and sort the remainder abcde take the second letter of the input 'a', note its position is 0, so compute 0 * (n-2)! = 0 remove that letter and sort the rest bcde next letter of input is 'c', which is at position 1, so compute 1 * (n-3)! = 6 remove the letter, sort the rest, you get 'bde' and so on def findLexiPerm( input, sorted ): letters = input.split() n = len(input) first = input[0,1] index = sorted.find(first) * (n-1)! return index + findLexiPerm(str(letters[1:n]),sorted[1:n]) input = 'facbed' sorted = input.split().sort() index = findLexiPerm(input,sorted) Untested pythonish pseudocode but I believe this is the right answer

### Software Engineer at Facebook was asked...

Sep 20, 2011
 print out all prime numbers in a given string. abc2134kd31 -> 2, 13, 3, 310 AnswerseasyCode in C# - verified working: static void PrintPrimes(string str) { int i; string lastNum = null; foreach (char c in str) { if (Int32.TryParse(c.ToString(), out i)) { lastNum = lastNum += i.ToString(); int concatNum = Int32.Parse(lastNum); // Iterate through all nums for (int ix = 0; ix < lastNum.Length; ix++) { string currNumStr = lastNum.Substring(ix, (lastNum.Length - ix)); int currNum = Int32.Parse(currNumStr); // Print out if prime if (isPrime(currNum)) { Console.WriteLine(currNum); } } } else { lastNum = null; } } } static bool isPrime(int x) { for (int i = 2; i <= Math.Sqrt(x); i++) { if (x % i == 0) return false; } return true; }btw, correct answer is not "2, 13, 3, 3" but "2, 13, 3, 3, 31"Show More ResponsesHere is the answer bool isPrime(int num) { for (int i=2;i '9' || currentChar < '0') { return false; } int currentDigit = currentChar - '0'; num = num*(current+1); num += currentDigit; } return true; } void PrintPrimes(char* text, int length) { if (length == 0) { return; } int currentIndex; int currentLength; while (currentIndex < length) { char* temp = new char[currentLength+1]; strcpy(temp, text+currentIndex, currentLength); int num; if (ConverToNum(temp, currentLength, &num)) { if (isPrime(num)) { Console.WriteLine(num); } currentLength++; } else { // couldn't convert to a number therefore we hit a non-integer currentIndex = currentIndex + currentLength + 1; currentLength = 0; } } }public class Prime { /** * @param args */ public static boolean isInteger(char c) { try { Integer.parseInt(String.valueOf(c)); return true; } catch (NumberFormatException nfe) {} return false; } public static void main(String[] args) { // TODO Auto-generated method stub String str="abc2134d31"; findprime(str); } static boolean isPrime(int x) { for (int i = 2; i <= Math.sqrt(x); i++) { if (x % i == 0) return false; } return true; } private static void findprime(String str) { // TODO Auto-generated method stub for(int i=0;i\$str = "35713m2m16mmm16mm97m47"; for(\$i=0;\$i<=strlen(\$str);\$i++) { if (!is_numeric(substr(\$str,\$i,1))) { continue; } for(\$j=\$i+1;\$j<=strlen(\$str);\$j++) { if (is_prime((int)substr(\$str,\$i,\$j-\$i))) { print substr(\$str,\$i,\$j-\$i).","; \$i=\$j-1;break; } if (!is_numeric(substr(\$str,\$i,\$j-\$i))) { \$i=\$j-1;break; } } } function is_prime(\$i) { if(\$i == 2) return true; if(\$i % 2 != 1 || \$i == 1) return false; \$d = 3; \$x = sqrt(\$i); while (\$i % \$d != 0 && \$d < \$x) \$d += 2; return ((\$i % \$d == 0 && \$i != \$d) * 1) == 0 ? true : false; }Vishal's code has a small bug, if you input test61test , it checks if 6 is prime, if it is it does the checknext function, it should implement checknext regardless that number being prime or not. public class Prime { //Take any string and print all the prime numbers in it /** * @param args */ public static boolean isInteger(char c) { try { Integer.parseInt(String.valueOf(c)); return true; } catch (NumberFormatException nfe) {} return false; } public static void main(String[] args) { // TODO Auto-generated method stub String str="ibby37primete61s43"; findprime(str); } static boolean isPrime(int x) { for (int i = 2; i <= Math.sqrt(x); i++) { if (x % i == 0) return false; } return true; } private static void findprime(String str) { // TODO Auto-generated method stub for(int i=0;ijavascript version: var isPrime = function (n) { if (n === 2) return true; if (n < 2 || n % 2 === 0) return false; for (var d = 3, t = n; d < t; t = ~~(n/d), d += 2) { if (n % d === 0) return false; } return true; }; var printPrimes = function (s) { var i, j, k, c, d, result = []; for (i = 0, j = s.length; i < j; i++) { c = s.charAt(i); if (!isNaN(c)) { if (isPrime(~~c)) result.push(c); for (k = i + 1; k < j; k++) { d = s.charAt(k); if (!isNaN(k)) { c += s.charAt(k); if (isPrime(~~c)) result.push(c); } else { break; } } } } return result; }java version public boolean isPrime(int n){ if(n = 0 && c - '0' findPrimes(String str){ char[] chars = str.toCharArray(); List nums = new LinkedList(); for(int i = 0; i < chars.length; i++){ String temp = ""; for(int k = i; k < chars.length; k++){ char x = chars[k]; if(isNum(x)){ temp += x + ""; if(isPrime(Integer.parseInt(temp))){ nums.add(temp); } } else break; } } return nums; } One or more comments have been removed. Please see our Community Guidelines or Terms of Service for more information.

### Software Engineering Intern at Facebook was asked...

Mar 8, 2012
 Given a sorted array, write a program to decide if two elements sum up to a third.9 AnswersDid you coded a solution < O(n^2 + logn) ?Assuming each number only appears once: //Java code public static void targetsum(int[] arr, int target) { if(arr == null) return; int start = 0; int end = arr.length -1; while(start target end--; } }typedef vector vint; bool check_element_sum(vint &array) { // n^2 algorithm sort(array.begin(),array.end()); //general case : nlogn copy(array.begin(),array.end(),ostream_iterator(cout," ")); cout=0;--i) //n^2 { start=0; end=i-1; target=array[i]; //note a<=b<=c for the tuples formed here hence check for c=a+b only while(startShow More Responsesthe algorithm for 3 elements sum up to a given number is also the same; the only change one needs to make is replace line target=array[i]; with target=total-array[i]; is there an algorithm with a lower order? says O( nlogn ); I am not able to think of anything!we can modify the 3sum algorithm for this.It is possible to do it in O(n) create a binary tree from the sorted array in O(n) subtract each value in array from target and find if its there in the tree, if found push to hash map, with the array item as key and the subtracted value as key next time before subtracting value in the array from target check if it is in the hash map@Pal the hash map gives a lower constan because /2 elements need to be checked but the lookup is still n*lognimport java.util.Arrays; import java.util.HashSet; import java.util.List; import java.util.Random; import java.util.Scanner; import java.util.Set; public class SumOfTwoElements { public static void main(String[] args) { final Scanner in = new Scanner(System.in); final Random random = new Random(); while (true) { System.out.println("Enter array size : "); int size = in.nextInt(); int[] array = new int[size]; for (int i = 0; i > findSummingTriplets2(int[] array) { final Set> summingTriplets = new HashSet>(); for (int k = 2; k array[k]) { j--; } else if (sum > findSummingTriplets(int[] array) { final Set> summingTriplets = new HashSet>(); for (int i = 0; i end) { return false; } int mid = start + (end - start) / 2; if (array[mid] > value) { return contains(array, start, mid - 1, value); } else if (array[mid] < value) { return contains(array, mid + 1, end, value); } else { return true; } } }bool sumExists(vector nums, int target) { auto front = nums.begin(); auto back = nums.end() - 1; while (front != back) { if (*front + *back == target) return true; else if (*front + *back < target) front++; else back--; } return false; }

### Software Engineer at Facebook was asked...

Mar 26, 2012
 Implement the "see and tell" algorithm with a given seed number x and a number of iterations y. Output the result on iteration y10 AnswersThe description of the problem was very fussy at first. Hi didn't mention the "see and tell" algorithm, just started to show some example inputs and outputs on collabedit and asked to code a function to generate those outputs.FYI : http://en.wikipedia.org/wiki/Look-and-say_sequenceHere is a quick solution in PHP:Show More Responsesjava solustion: public static String seeAndTellAlgo(String num, int i) { if (i == 0) { return num; } // get next number String next = getNext(num); System.out.println(next); return seeAndTellAlgo(next, i - 1); } public static String getNext(String num) { if (num == "") { return num; } if (num.length() == 1) { return "1" + num; } String result = ""; char[] numChar = num.toCharArray(); int[] records = new int; char pre = numChar; records[pre]++; for (int i = 1; i < numChar.length; i++) { char cur = numChar[i]; if (cur != pre) { int count = records[pre]; records[pre] = 0; result += String.valueOf(count) + Character.toString(pre); } if (i == numChar.length - 1) { if (cur != pre) { result += '1' + Character.toString(cur); } else { result += String.valueOf(records[cur] + 1) + Character.toString(cur); } } records[cur]++; pre = cur; } return result; }Solution in c++ #include #include #include #include #include #include std::vector countOcuurence(std::deque lnsQueue, int len) { int prev = -1; int count = 0; std::vector output; while(!lnsQueue.empty()) { if(prev == -1) { prev = lnsQueue.front(); count++; lnsQueue.pop_front(); } while((!lnsQueue.empty()) && (lnsQueue.front() == prev)) { count++; lnsQueue.pop_front(); } output.push_back(count); output.push_back(prev); prev = -1; count = 0; } return output; } void lookandsay(int seedX, int iterY) { std::ostringstream outstring; std::deque lookNsayQueue; std::vector lookNsayV; int len,k; outstring 0) { for(int i=0;iRecursive solution in php function seetell(\$seed,\$n){ if(\$n>0){ \$seed = str_split(\$seed); \$output = ""; \$last = \$seed; \$count = 1; for(\$i=0;\$iThe previous solutions seem a bit long; here's a recursive C++ solution: string my_itoa(int x) { char res; sprintf_s(res, "%d", x); return string(res); } void lookAndSay(string& str, string& temp, int n) { if (n + to the resulting string, remove identical chars from str, and recurse temp += my_itoa(count) + c; lookAndSay(str.substr(i), temp, n); }import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class LookAndSayGenerator { public static void main(String[] args) { final Scanner in = new Scanner(System.in); while (true) { System.out.println("Enter starting number : "); final String start = in.nextLine(); System.out.println("Enter sequence length : "); final int nextN = in.nextInt(); System.out.println("Sequence : " + lookAndSaySequence(start.toCharArray(), nextN)); } } private static List lookAndSaySequence(char[] start, int nextN) { List sequence = new ArrayList(); if (nextN == 0) { return sequence; } int rep = 0; char ch = '\0'; String next = ""; for (int i = 0; i 0) { next = next + String.valueOf(rep) + String.valueOf(ch); rep = 1; ch = start[i]; } } if (rep != 0) { next = next + String.valueOf(rep) + String.valueOf(ch); } sequence.add(next); sequence.addAll(lookAndSaySequence(next.toCharArray(), nextN - 1)); return sequence; } } One or more comments have been removed. Please see our Community Guidelines or Terms of Service for more information.

### Intern at Google was asked...

Dec 30, 2011
 Find occurrences of a number in sorted array (allow duplicates).8 AnswersO(logN) requiredUse binary search to find the number (O(logN)). Once that is done you can search around that index. Though that could become O(N). Better answer: run binary search again twice once you have found the number the first time. For the upper half and the lower half - so total run time is O(logN)I think it is not possible in O(logN) because anyway traversing the complete array is needed to access all the numbers. Worst Case scenario would be the last number repeating itself 5 times. For example : {1,2,2,3,3,3,4,4,4,4,5,5,5,5,5} and if you are asked to find out the occurrences of number '5' then you have to traverse the complete array once which means the complexity should be O(N).Show More ResponsesJAVA Code : // For Sorted and UnSorted Array in O(N) time Complexity. import java.util.HashMap; public class FindOccurrences { /** * @param args */ public static void main(String[] args) { int unsortedArray[] = {4,6,7,8,4,5,6,8,3,2,4,5,7,8,9,3,4,6,7,8}; System.out.println(findOccurrencesUnsorted(unsortedArray,8)); int sortedArray[] = {1,2,2,3,3,3,4,4,4,4,5,5,5,5,5}; System.out.println(findOccurrencesSorted(sortedArray,5)); } private static int findOccurrencesUnsorted(int[] array, int number) { HashMap map = new HashMap(); for(int i=0;iO(logN) is possible for sorted arrays, the key here is to firstly check beginning and end to determine next binary-search steps, I attached my code below, and I think this is O(logN) in worst case. //inputs are the sorted array, k is the number looking for //start and end are two index values, main method calls with (start=0) and (end=length-1) int GetOccurance(int[] inputs, int k, int start, int end) { if(startk) return 0; if(inputs[start]==k&&inputs[end]==k) return end-start+1; int mid = (start+end)/2; if(input[mid]k) return GetOccurance(inputs, k, start, mid-1); else return GetOccurance(inputs, k, start, mid-1)+1+GetOccurance(inputs, k, mid+1, end); }With the last algorithm, how does it ever return anything but 0? If main calls with start := 0 and end := length - 1? The only case where you get past the base case is if the array is length 1... since (start < end) = (0 < length -1) from the input... and returns 0...Also, I think there is a good shot at a stack overflow with this method. I would add an extra variable and solve the problem tail recursively.Try this. int findLeftEdge( int A[], int num, int val ){ int mid = num/2; if( num == 1 ){ return 0; }else{ if( A[mid] == val && A[mid-1] != val ){ return mid; }else if( A[mid] == val || A[mid] > val ){ return findLeftEdge( A, mid, val ); }else if( A[mid] val ){ return findRightEdge( A, mid, val ); } } } int countOccurrenceSortedArray( int A[], int num, int val ){ int left = findLeftEdge( A, num, val ); int right = findRightEdge( A, num, val ); return right-left+1; } int main() { // your code goes here int A[] = { 1, 5, 10, 10, 12, 19, 19, 19, 20, 20}; int ans = countOccurrenceSortedArray( A, sizeof(A)/sizeof(int), 20 ); cout << ans << endl; return 0; }

### Software Engineer at Google was asked...

Feb 9, 2011
 Was asked how I would implement division without using division or mod operators. The answer should return in the form quotient r remainder.8 AnswersAnswer 1: Use subtraction and keep a count of how many times subtracted. When the remainder is smaller than the divisor, count is your answer, and whatever is left is the remainder. Was then asked the complexity in terms of binary. After that, was asked to come up with a solution with better complexity. Answer 2: Multiply the divisor by two until it is larger than the dividend. Go back one, subtract that out, multiply again. This solution will have a much better complexity.I could not get second solution. Though its really interesting .... e.g. 39/3 1. multiply 3 with 2 until it gets bigger 3->6->12->24->48 (using 8 3. Sub that out 39-24 = 14 4. Go to 11. multiply 3 with 2 until it gets bigger than 29: 6,12,24,48 2. Go back one: 24 =>8 3. Sub that out: 39-24 = 15 1. multiply 3 with 2 until it gets bigger than 15: 6,12,24 2. Go back one: 12 =>4 3. Sub that out: 15-12 = 3 1. multiply 3 with 2 until it gets bigger than 3: 6 2. Go back one: 3=>1 3. Sub that out: 3-3 = 0 Answer: 8+4+1 = 13Show More ResponsesI think you're very close, but perhaps the interviewer was suggesting to think of the quotient in terms of being a binary number. // QuickDivide, implemented in Java public static String QuickDivide(int num, int denom) { int quotBits = 1; // start with a single bit quotient int quot = 0; // get number of quotient bits while (Math.pow(2,quotBits) * denom = 0; bitExp--) { if (num >= Math.pow(2, bitExp)* denom) { // add to quotient and subtract from numerator quot += Math.pow(2,bitExp); num -= Math.pow(2, bitExp) * denom; } } // numerator is holding remainder return String.format("%1\$d R %2\$d", quot, num); }// gets leftmost bit position public native static int __builtin_clz(int n); /** * Divide x by y. * @return {result, reminder} */ public static int[] div(int x, int y) { int py = __builtin_clz(y); int res = 0; while(x > 0) { int px = __builtin_clz(x) - py; x -= y << px; if (x < 0) { x += y; px--; } res += 1 << px; } return new int[] {res, x}; }Besides the returning format, and according the algorithm above, I would write in C the following function: void div(int N, int D) { int Q = 0; int x = N; int it = 1; while (x >= D) { if ( x < (D << it) ) { x -= (D << (it-1)); Q += (1 << (it-1)); it = 0; } it++; } cout << "Quotient: " << Q << " Remainder: " << x << endl; }public class Division { public static void main(String[] args) { int num = 23, denom = 7; System.out.println(Divide(num, denom)); } public static String Divide(int num, int denom) { int quotBits = 1; // start with a single bit quotient int quot = 0; // get number of quotient bits while ((denom = 0; bitExp--) { if (num >= (denom<despite these comments, I would do a binary search on the quotient. the upper bound is the dividend

### Java Developer at Systems Logic was asked...

Feb 8, 2013
 They asked me about the Java Object - Oriented, Inheritance and Out-put the single value of the 2 dimension array7 AnswersAll the answers can be easily found from internet/ java book if you repair them beforeCould you be more specific about the questions? And could you explain how you answered their questions, please! I'm gonna have the C# interview from Systems Logic, and they're gonna ask me questions about C++. So, if you can specify the questions they asked you, it could be more helpful to me. Please!!!I have got the phone all and email from them but that's it. Did they contact you again? How did you set up the appointment with them?Show More ResponsesHi all. I've just passed the 2nd round technical interview for the JAVA Developer position. They sent me an email about attending a training session at their head office before job placement. Did any of you guys have such experience?What kind of question did they ask you in the technical interview?I have passed the technical interview and I received an offer letter and two agreements (training agreement and employment agreement) from them. But a lot of things in the agreements are not very clear, it didn't say anything about paid holidays, employee insurances, etc. I am not sure if I should sign it or not. Does anyone have idea about this whole thing?can you please tell me if this good company?

### Software Engineer at Facebook was asked...

Apr 24, 2011
 Convert a binary search tree to a sorted, circular, doubly-linked list, in place (using the tree nodes as the new list nodes).8 AnswersRecursively: - convert the left subtree (returns a dbl-linked list (DLL) with a head ptr & tail ptr) - convert the right subtree (same) - connect the left DLL tail to the right DLL head bi-directionally - return the combined list (head = left-head, tail = right-tail)struct StackEntry { Node *pNode; bool fVisit; }; inline void linkNodes(Node *pLeft, Node *pRight) { pLeft->pNext = pRight; pRight->pPrev = pLeft; } inline void visitNode(Node **ppFirst, Node **ppPrev, Node *pNode) { if(ppPrev == NULL) { *ppFirst = pNode; *ppPrev = pNode; } else { linkNodes(*ppPrev, pNode); *ppPrev = pNode; } } void doubleLink(Node *pRoot) { stack stack; Node *pFirst = NULL; Node *pPrev = NULL; StackEntry rootEntry = {pRoot, false}; stack.push(rootEntry); while(stack.size() != 0) { StackEntry &top = stack.top(); stack.pop(); if(top.fVisit) { visitNode(&pFirst, &pPrev, top.pNode); } else { StackEntry entry; if(pNode->pLeft != NULL) { entry.pNode = pNode->pLeft; entry.fVisit = false; stack.push(entry); } entry.pNode = pNode; entry.fVisit = true; stack.push(entry); if(pNode->pRight != NULL) { entry.pNode = pNode->pRight; entry.fVisit = false; stack.push(entry); } } } if(pPrev != NULL) { linkNodes(pPrev, pFirst); } }class TreeNode { TreeNode* left; TreeNode* right; int value; } TreeNode* MakeCircularDoublyLinked(TreeNode* head) { DoublyLink(head, head); return MakeCircular(head); } TreeNode* MakeCircular(TreeNode* node) { TreeNode* leftEnd = node; while (leftEnd->prev != NULL) { leftEnd = leftEnd->prev; } listNode* rightEnd = node; while (rightEnd->prev != NULL) { rightEnd = rightEnd->prev; } rightEnd->next = leftEnd; leftEnd->prev = rightEnd; return leftEnd; } listNode* DoublyLink(TreeNode* current, TreeNode* prevTreeNode) { if (current == NULL) { return NULL; } current->left = DoublyLink(current->left, current); if (current->left != NULL) { current->left->right = current; } current->right = DoublyLink(current->right, current); if (current->right != NULL) { current->right->left = current; } if (prevTreeNode->left == current) { // we are processing the left subtree, return the rightmost // element to the parent while (current->next != NULL) { current = current->next; } } else if (prevTreeNode->right == current) { // we are processing the right subtree, return the leftmost // element to the parent while (current->prev != NULL) { current = current->prev; } } return current; }Show More ResponsesDetailed analysis and solution is available in the following blog: http://codercareer.blogspot.com/2011/09/interview-question-no-1-binary-search.htmlJava, non-recursive. O(n) time, O(1) space: import java.util.Stack; public class TreeToCircList { public static class Node { public Node left = null; public Node right = null; public int data; } public void convert(Node node) { boolean leftChecked = false; Node prev = null; Node start = null; Stack s = new Stack(); while(node != null) { if(leftChecked == false && node.left != null) { s.push(node); node = node.left; } else { // Perform the linking node.left = prev; if(prev != null) prev.right = node; else start = node; // Mark start of the list prev = node; if(node.right != null) { node = node.right; leftChecked = false; } else if(s.empty() == false) { node = s.pop(); leftChecked = true; } else { node = null; } } } // Find the first node to link with the last node if(prev != null) { start.left = prev; prev.right = start; } } }Thanks to recursion .. this is a sorted linked list .. to make it circular just make a pointer from the last to the head. :) bst_node* getList(bst_node* nd) { if(nd == NULL) return NULL; bst_node* head; bst_node* l = getList(nd->lft); bst_node* r = getList(nd->rt); if(l != NULL) { head = l; head->lft = nd; nd->lft = r; } else { head = nd; head->lft = r; } return head; } void print_list(bst_node* bst) { bst_node* head = bst; while(head != NULL) { cout val lft; } }void BinTree::convert() { Node * head, * tail; convert_to_dlist(root, head, tail); Node * current = head; while(current != tail) { cout val right; } cout val val left; } cout val left, lhead, ltail); convert_to_dlist(node -> right, rhead, rtail); if(lhead == NULL && rhead == NULL) { head = node; tail = node; head -> left = head; head -> right = head; } else if(lhead == NULL && rhead != NULL) { head = node; head -> right = rhead; rhead -> left = head; tail = rtail; head -> left = tail; tail -> right = head; } else if(lhead != NULL && rhead == NULL) { head = lhead; head -> left = node; node -> right = head; tail = node; tail -> left = ltail; ltail -> right = tail; } else { head = lhead; tail = rtail; ltail -> right = node; node -> left = ltail; node -> right = rhead; rhead -> left = node; head -> left = tail; tail -> right = head; } return; }Solution by recursive in-order traversal. To make code simply I did not make linked list circular. It can be done by simply modification to return both head and tail and connect them outside recursion. Node Convert(Node root) { if (root == null) return null; Node last = null; return InOrder(root, ref last); } Node InOrder(Node node, ref Node last) { Node left = null; if (node.Left != null) left = InOrder(node.Left, ref last); node.Left = last; if (last != null) last.Right = node; last = node; if (node.Right != null) InOrder(node.Right, ref last); return left ?? node; // return the smallest node which will be the head }

### Software Engineer In Test at Google was asked...

Jan 15, 2010
 You are a parking lot attendant in a lot that has one open spot, and you want to move the cars from their original positions into a new arrangement. Create a program that will print out instructions on how to move the cars most efficiently. 7 AnswersThe problem is not too difficult, what you have to do is find the empty spot, then look in the desired arrangement for what car should be in that spot, and move that car there. Repeat until complete.Does this really work? If I the empty spot is expected to be the same, but the positions of two (or more) cars are switched, how to rearrange it without a complete search?It's the Tower of Hanoi Problem.Show More ResponsesSo there are actually 2 empty spots then or is there a way to 'stack' cars I don't know of?The parking lot problem has nothing to do with Tower of Hanoi, which requires O(2^n -1). This problem, however, can be solved in O(n) - that's because all you need to do is to perform (0 or more) rotations using the empty parking spot.Here is a C# implementation, using generics and .NET 4.0 Tuple: IEnumerable> RearrangeCars( TCar emptyCarMarker, IDictionary initial, IDictionary desired) { // reverse the lookup: car -> spot Dictionary pending = initial.ToDictionary(p => p.Value, p => p.Key); // remove emptySpot from lookup TSpot emptySpot = pending[emptyCarMarker]; pending.Remove(emptyCarMarker); while (pending.Any()) { // check if the empty spot is where is should be if (desired[emptySpot].Equals(emptyCarMarker)) { while (true) { // pick a car (any car would do) var carToMove = pending.First(); // check if this car is already in its desired position if (desired[carToMove.Value].Equals(carToMove.Key)) { // remove from pending, no moving is necessary pending.Remove(carToMove.Key); if (pending.Any() == false) yield break; } else { yield return new Tuple(carToMove.Key, carToMove.Value, emptySpot); // move the car TSpot newSpot = emptySpot; emptySpot = carToMove.Value; pending[carToMove.Key] = newSpot; break; } } } // move the car into its desired spot var car = desired[emptySpot]; var newEmptySpot = pending[car]; yield return new Tuple(car, newEmptySpot, emptySpot); emptySpot = newEmptySpot; pending.Remove(car); } } Note that there is a while-loop inside another while-loop. However, the complexity is still O(n) since at every iteration of internal or external loop, the "pending" map is reduced by one element. Below are some examples (emptyCarMarker == ""). EXAMPLE 1: Input: initial == { "", "B", "A"} desired == { "", "A", "B"} Output: (B, 1, 0) // move car B from spot #1 to #0 (A, 2, 1) // move car A from spot #2 to #1 (B, 0, 2) // move car B from spot #0 to #2 EXAMPLE 2: Input: initial == { "", "B", "A", "D", "C" } desired == { "A", "B", "", "C", "D" } Output: (A, 2, 0) (D, 3, 2) (C, 4, 3) (D, 2, 4)Here is a Java Implementation, using Google's guava library for the BiMap. It takes O(n) to first create the BiMap and O(n) to move the cars, total O(2n), i.e. O(n) time complexity. import com.google.common.collect.BiMap; import com.google.common.collect.HashBiMap; import java.util.Map; import java.util.Set; class ParkingAttendant { static class ParkingConfiguration { static final Integer EMPTY = -1; Integer moves = 0; BiMap conf, i_conf; static ParkingConfiguration getInstance(int[] conf){ return new ParkingConfiguration(conf); } private ParkingConfiguration(int[] conf){ this.conf = arrayToMap(conf); this.i_conf = this.conf.inverse(); } BiMap arrayToMap(int[] arr){ BiMap m = HashBiMap.create(arr.length); for(int i=0;i> entrySet(){ return conf.entrySet(); } } static void moveCars(ParkingConfiguration from, int[] to){ for(int pos=0; pos e : p.entrySet()){ int pos = e.getKey(); int car = e.getValue(); System.out.format("%1\$s, ", ParkingConfiguration.EMPTY.equals(car)?"_":car); } System.out.println("]"); } static void printCars(int[] p){ System.out.print("["); for(int pos=0; pos

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

Oct 31, 2016
 Coding Challenge 1) Find the longest palindromic substring from the given string. No need of DP solution. 8 AnswersI wrote a code in O(n^3) since I can spend only thirty minutes for each question and the IDE provided was no use. There will not be any auto complete. But you can use Java docs for coding.private static bool isPalindrom(string word) { bool res = false; int lastIndex = word.Length -1 ; for(int i = 0; i longestPalindrom.Length) ? word : longestPalindrom; } Console.WriteLine(longestPalindrom); }//Code in PHP = 0 && \$j - 1 >= 0) { \$answer[\$i][\$j] = \$answer[\$i - 1][\$j - 1] + 1; } else { \$answer[\$i][\$j] = 1; } } else { \$answer[\$i][\$j] = 0; } if (\$answer[\$i][\$j] > \$maxPalindromicLength) { \$maxPalindromicLength = \$answer[\$i][\$j]; \$endIndex = \$i; } } } if (\$maxPalindromicLength > 0) { \$start = \$endIndex - (\$maxPalindromicLength - 1); echo "Lenght: \$maxPalindromicLength"; echo "|"; echo "String:"; for (\$i = \$start; \$i <= \$endIndex; \$i++) { echo \$str[\$i]; } }Show More Responses\$str = "QDWASDDSA43"; \$i = 0; \$j = 0; \$length = strlen(\$str); \$maxPalindromicLength = 0; \$endIndex = 0; for (\$i = 0; \$i = 0 && \$j - 1 >= 0) { \$answer[\$i][\$j] = \$answer[\$i - 1][\$j - 1] + 1; } else { \$answer[\$i][\$j] = 1; } } else { \$answer[\$i][\$j] = 0; } if (\$answer[\$i][\$j] > \$maxPalindromicLength) { \$maxPalindromicLength = \$answer[\$i][\$j]; \$endIndex = \$i; } } } if (\$maxPalindromicLength > 0) { \$start = \$endIndex - (\$maxPalindromicLength - 1); echo "Lenght: \$maxPalindromicLength"; echo "|"; echo "String:"; for (\$i = \$start; \$i <= \$endIndex; \$i++) { echo \$str[\$i]; } }Was that string a string of words like "This is the Main string." Or a continuous string like "thisisthemainstring"?Java solution public static String getLP(String s){ int length = s.length(); for(int i = length; i>1; i--){ String pofL = getPofL(s,i); if(pofL!=null){ return pofL; } } return null; } public static String getPofL(String s, int length){ for(int i = 0; (i+length)int palindrome(){ char* str="asdfdsaasdfdsa"; char* lp = (char*)malloc(sizeof(char) * strlen(str)); int maxc=1; for(int i=0; i-1 && (e=e+1)maxc) { maxc=c; strncpy(lp, str+(s==-1?0:s), (e>strlen(str)?strlen(str):e)-s); } } printf("%s - %d", lp, maxc); free(lp); } One or more comments have been removed. Please see our Community Guidelines or Terms of Service for more information.
3140 of 6,004 Interview Questions