↳

first clarify if it is ASCII or UNICODE string For ASCII, create BOOL checkArray [128] = {false}; walk the string and update the index of checkArray based of the character. for (int index=0;index< strlen(str); index++) { if (checkArray[str[index]] == true) { printf (str[index]); return; } else { checkArray[str[index]] = true; } } Less

↳

for (int i=0;i

↳

public static in findDuplicateChar(String s) { if (s == null) return -1; char[] characters = s.toCharArray(); Map charsMap = HashMap(); for ( int index = 0; index < characters.length; index++ ) { // insert the character into the map. // returns null for a new entry // returns the index if it previously if it existed Integer initialOccurence = charsMap.put(characters[index], index); if ( initialOccurence != null) { return initialOccurance; } //there where no characters that where duplicates return -1; } } Less

↳

Iterate the array and add each number to a set, if number is already there, it won't be added again, thus removing any duplicates. Complexity is Big-O of N Less

↳

The array is already sorted, no need for a set. example: 2,2,5,7,7,8,9 Just keep tracking the current and previous and the index of the last none repeated element when found a difference copy the element to the last none repeated index + one and update current and previous, no extra space and it will run in O(n) Less

↳

public RemoveDuplicates() { int[] ip = { 1, 2, 2, 4, 5, 5, 8, 9, 10, 11, 11, 12 }; int[] op = new int[ip.Length - 1]; int j = 0, i = 0; ; for (i = 1; i <= ip.Length - 1; i++) { if (ip[i - 1] != ip[i]) { op[j] = ip[i - 1]; j++; } } if (ip[ip.Length - 1] != ip[ip.Length - 2]) op[j] = ip[ip.Length - 1]; int xxx = 0; } Less

Software Engineer In Test was asked...March 18, 2009

↳

Hi Xin Li, A binary tree is not the same as binary search tree.. A binary tree is a tree in which every node has atmost two children nodes. It is a k-ary tree in which k=2. A complete binary tree is a tree in which all nodes have the same depth. Less

↳

For the love of god I wish I got a problem this easy

↳

Binary Search tree is a storage data structure that allows log(n) insertion time, log(n) search, given a balanced binary search tree. The following implementation assumes an integer bst. There's a million implementations. Just look on wikipedia for search and insert algorithms. Less

Software Development Engineer In Test || was asked...March 14, 2012

↳

I'm sorry but Anon's answer is not correct, at least according to "Introduction to Algorithms, 3d Edition" by Cormen. The binary search tree property says that there CAN be duplicates: "Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y.key = x.key." In other words, the value of a child node may be equal to the value of a parent node, which would yield the result that "Interview Candidate" posted on Mar 14 2012. Performing an inorder tree walk would yield sorted nodes. Less

↳

public static isValidBST(TreeNode root, MIN_INTEGER, MAX_INTEGER) { if (root == null) // children of leaf nodes { return true; } return root.data >= INTERGER_MIN && root.data <= INTEGER_MAX && isValidBST(root.left, INTEGER_MIN, root.data) && isValidBST(root.right, root.data, INTEGER_MAX) } Less

↳

Further, know that the difference between the two is that a binary search tree cannot contain duplicate entries. recur down the tree - check if element is already in hashtable - - if it is, return false - - if it isnt, insert element into the hashtable - - - recur to children Less

↳

2 ways. At the low level: reverse the entire string. 'Hello World' becomes "dlroW olleH". Then reverse each word, becomes "World Hello". At a higher level: Tokenize the words and push them onto a stack, then pop them out. Less

↳

class Solution { public static void main(String[] args) { String input = "Hello World this is a string"; reversestring(input); } public static void reversestring(String input){ // Stack stack = new Stack(); String[] str = input.split(" "); for(int i = str.length-1;i>=0;i--) { System.out.print(" "+str[i]); } } } Less

Software Development Engineer In Test (SDET) was asked...October 22, 2010

↳

Found this good link. Time complexity is O(n). http://www.dreamincode.net/code/snippet1481.htm The algorithm can still be improved but gives some basic idea on how to implement. Less

↳

This was not really that hard to write it, however the interviewer asked me to reduce the complexity. My initial version had n*log(n) complexity and he asked me to reduce it to no more than n complexity. If you have had some upper level Computer Science classes this is not too difficult, however what they are looking for is a way to stump you. If you adjust your code or thinking rapidly to their request they will change it again until they find something that you have trouble with. Do not be discouraged by this, it is the interviewers job to determine how much you know! Less

Software Development Engineer In Test (SDET) was asked...September 4, 2009

↳

I would first answer with, "First, I would analyze the problem and determine if it didn't make better sense to come to the mountain rather than move the mountain. Assuming that's not feasible..." I think that's a key element they're looking for in an answer. That you can look at a major task and first identify if there isn't a better approach. The next element is to determine how you would go about completing a seemingly impossible or gargantuan task. The specifics of this part of the answer don't matter other than to show that you have an understanding that huge problems need to be broken down into smaller, more manageable tasks using the resources you have. Less

↳

When they ask a quesion like this at MS, they do want an answer. If you tell them that you want to consider alternatives up front, they will wave that off and tell you that, in this hypothetical situation, alternatives were already considered and that moving the mountain is the approach was chosen. They really want you to answer the question. The point of this question is - process. They want to see what process you use to solve problems. It is important to show that you solve the problem not by arranging and re-arranging a series of random thoughts but that you can approach it methodically and that this methodology can be applied to any problem. Do not to to some up with a clever answer that attempts to solve the problem - they will just keep insisting that you tackle the problem. If you don't, you won't pass the interview. So, brush up on your problem solving process before you interview at MS. Use these questions as an opportunity to impress them with how well you can solve difficult problems. Less

↳

This is a common dorky Computer Science joke. The answer I believe they are looking for is that you use the Tower of Hanoi algorithm to move the mountain (i.e. that the problem of moving Mt. Fuji is reducible to the already-solved Tower of Hanoi problem). This could be accomplished by having a large laser and a couple of really good cranes. Less

↳

Put all the numbers from the array into a hash. So, keys will be the number and values of the keys be (sum-key). This will take one pass. O(n). Now, foreach key 'k', with value 'v': if k == v: there is a match and that is your pair. this will take another O(n) pass totale O(2n) ~ O(n) Less

↳

Easiest way to do it. Written in python. If you consider the easiest case, when our summed value (k) is 0, the pairs will look like -50 + 50 -49 + 49 -48 + 48 etc.... etc... So what I do is generalize the situation to be able to shift this k value around. I also allow us to change our minimums and maximums. This solution assumes pairs are commutative, i.e. (2, 3) is the same as (3, 2). Once you have the boundaries that you need to work with, you just march in towards k / 2. This solution runs in O(n) time. def pairs(k, minimum, maximum): if k >= 0: x = maximum y = k - maximum else: x = k + maximum y = minimum while x >= k / 2 and y <= k / 2: print str(x) + " , " + str(y) + " = " + str(x + y) x = x - 1 y = y + 1 Less

↳

here is my solution using hash table that runs in O(2n) => O(n): public static String findNums(int[] array, int sum){ String nums = "test"; Hashtable lookup = new Hashtable(); for(int i = 0; i < array.length; i++){ try{ lookup.put(array[i], i); } catch (NullPointerException e) { System.out.println("Unable to input data in Hashtable: " + e.getMessage()); } } int num2; int num1; for (int i = 0; i < array.length; i++){ num2 = sum - array[i]; Integer index = (Integer)lookup.get(num2); if ((lookup.containsKey(num2)) && (index != i)){ num1 = array[i]; nums = array[i] + ", and " + num2; return nums; } } //System.out.println(lookup.get(-51)); return "No numbers exist"; } Less

Software Development Engineer In Test was asked...December 7, 2012

↳

function findLCA(Node node1, Node node2) { int counter1 = 0; int counter2 = 0; Node temp; //Find the level for each node, use a temp node to //traverse so that we don't lose the info for node 1 and node 2 temp = node1; while( temp.parent ! = null) { temp = temp.parent; counter1++; } temp = node2; while( node2.parent ! = null) { node2 = node2.parent; counter2++; } /* * We wanna make them at the same level first */ if(counter1 > counter2) { while(counter1 != counter2) { node1 = node1.parent; counter1--; } } else { while(counter2 != counter1) { node2 = node2.parent; counter2--; } } while (node1.parent != node2.parent) { node1 = node1.parent; node2 = node2.parent; } System.out.println("Found the LCA: " + node1.parent.info); } Less

↳

//correction temp = node2; while( temp.parent ! = null) { temp = temp.parent; counter2++; } Less

↳

Consider this is a BST, where max node is always on the right of min node, we can traverse max upward one node at a time while comparing min nodes as it traverse upward toward root. BinaryNode findBSTLCA( BinaryNode min, BinaryNode max ) { BinaryNode tempMax = max; BinaryNode tempMin = min; while( tempMax != null ) { while( tempMin != null ) { if( tempMin.element == tempMax.element ) return tempMin; tempMin = tempMin.parent; } tempMin = min; // reset tempMin tempMax = tempMax.parent; // traverse tempMax upward 1 node } return null; // no LCA found } Less

quality assurance engineersoftware quality engineertesting engineertest specialisttest analystqa engineersoftware developer in testqa analystsoftware engineersoftware testing freshersoftware test leadqa testerqa automation engineersoftware testing quality assurance analystmanual testersoftware tester