Software Development Engineer Interview Questions

Duh - sorting is O(nlog n) ...

Using hashing, this can be done in O(N). store the n/2 mod i in the corresponding hash bucket. Now check the each hash bucket and you are done.

sort the array (o(n(log(n)) and take two pointers at both the ends say p1 and p2 if p1+ p2 move the pointer p2 by 1 and add to check if (p1+p2) > n -> move the pointer p1 by 1 and add to check if (p1+p2) = n ->print the pair [traversal takes o(n)] finally thus can be done in o(n)

I will not waste o(nlogn) in sorting the array. Instead assuming that the sum we looking for is k, i will divide the array into 2 arrays. First array will contain all values which are less than k/2 Second array will contain all values > k/2 This is bcoz in a sum if one number is less than k/2, the other has to be larger. I will iterate over the smaller array of the 2 since they would rarely be equal. For each x in array 1, i will find the k-x in array 2. Complexity will be O(n).

"keep on adding the elements,wherever the sum becomes odd that number is the odd one." Fails on int array[] = {2, 2, 4, 3, 3}

xor is the correct answer

Can explain the XOR answer pl. thanks

if you xor an number with it self you get 0 , if you xor a number with 0 you get the number it self, eg 2,2,4,3,3 2^2 = 0 0^4 = 4 4^3= 7 7^3 = 4 and the answer is 4,

We can also use a Hashmap and the first time we get an element we put 1, the next time we get it we remove it from the map...In the end only the required answer will be in the map

operating all each element xor Time complexity On Space complexity O1

operating all each element xor Time complexity On Space complexity O1

SUM(array) - (N(N+1)/2) = missing number.

@Facebook Intern: That wont help .. In case there are 2 duplicates this can be broken. {1, 1, 4, 4}

I attach pseudo code here: FindDuplicate(A) i = A.length j = 1 count = 0 while j < i if A[--j] - j == 0 j++ else count++ return count count holds the number of duplicated items

This cannot be done in linear time unless the data-structure used to hold the integers has a property that immediately flags duplicates upon insertion. For e.g. like in a Dictionary/HashMap.

I'm pretty sure OP posted something wrong there, and they were probably asking to do it in linear time and not constant. If it's constant, the way I would do it would be using a HashSet to check if the key (value in array) is contained, and if not add it to the set. If at any time I find an element that's already inside, return false;

If an array has elements from 1 to n the size of the array will be n, thus if the size of the array is greater than n, there must exist a duplicate.

I think they are just asking to determine if there is any duplicate number ir not. Its not mentioned to find out which number it is. So that we can find out by using sum of n numbers

I think they are just asking to determine if there is any duplicate number ir not. Its not mentioned to find out which number it is. So that we can find out by using sum of n numbers

They asked for constant time. So checking sum will not work. For zero indexed arrays, Check if arr[len(arr)-1] == len(arr) - 1.

^^ person who replied above: Your solution fails if the numbers aren't sequential - for all you know, 'a list of n numbers' could be 'n' random numbers

Merge sort it and then it iterate through the list. This takes nlogn time. public in getDuplicate(List list) { List sortedList = Mergesort(list); for(int i = 0; i < sortedList.length-1; i++) if(sortedList[i] == sortedList[i+1]) return SortedList[i]; Throw exception; }

take XOR of all the numbers.You will get the sum with out the duplicated number. (sum of all n - above sum) will give you the number

put the numbers into hashmap while traversing the list. Before placing the key into hashmap check whether it is null or not. if it isnot you've found it. worst case O(n). extra hashmap in the memory.

i would sort them in n log and then traverse them. while traversing, chech two adjacent numbers are different. if not, that is the number.

Construct a binary search tree with the given number.when u find a duplicate number return from the method as in binary search tree one has to put element either left or right.

Construct a binary search tree with the given number.when u find a duplicate number return from the method as in binary search tree one has to put element either left or right.

praveen's answer is correct but not good enough, you would not want to modify the pointer you got it might be your only ptr to the head of the list. public *Node LastElement(Node *Head) { Node *iter = Head; while(iter->next != null) { iter = iter->next; } return iter; } would be more correct.

Because the parameters are always passed by value. Even if you modify the input parameters, the original variable remains unchanged.

I am talking about the case where you don't specifically pass the params as references in C++. In C, my statement holds.

All the answers are partially correct. Anonymous: The function accepts a pointer not a reference to the pointer (pass by value). Hence if the pointer 'Head' is modified in the function, it doesn't affect the actualy pointer that was passed into the function. However, what's missing in Praveen's solution is the boundary condition of whether the Head node is NULL. If it is, then the starting statement of the while loop is going to access a NULL pointer. The correct solution should be something like: Node* GetLastNode(Node* head) { // Loops through till the end of the node for(; head != NULL && head->next; head = head->next); // Return the last node (This could be NULL if head was NULL). return head; }

For 3 missing numbers: Calculate: x+y+z = a x^2+y^2+z^2 = b x^3+y^3+z^3 = c Now, try every possible number from 1 to n as z: assuming that x+y = a-z x^2+y^2 = b-z^2 calculate x and y using method from solution for 2 missing numbers. If x,y,z are unique integers from 1..n try if x^3+y^3+z^3 equals to c calculated before, then those are the missing numbers. In last step we do n iteration of loop, but each iteration takes O(1), so the total time is O(n)

Lucita, your answers are impressive but how you are using O(1) space?

you don't need to allocate memory to compute a sum...

Yea? Where do you store the running sum then

O(1) meaning constant, which implies does not change due to input size change

Generate values from 1 to n and loop through comparing the elements in the array with the value from generated values. If a number doesn't match up it means it's missing. Can yield the value and search for 2nd and 3rd with another call. Linear time and constant memory

They may not be sorted..comparing won't work in linear time

Best way is do a bitwise xor of 1..n and the given array Then let's say we have x ^ y^ z = a Now based on the bits in 'a' we can derive x y and z Operations include bitwise shift Bitwise and This is more scalable and is in linear time and O(1) space

Here is a concept that may works, starting from the beginning point, each step could lead to possibly three path, we can draw a tree which each node has three children (max), then find the longest path would do it, each dead end will determine if the current node has any child or not.

enter the maze into a graph data structure where adjacent 0's are connected to each other with an edge. Label the starting and ending points, and do a DFS from the starting location. This would be an internal solution, as there would be no visual representation of it, but you could easily enough attach coordinates to each node to allow for a visual solution

A* Algorithm Wikipedia has a nice animated image to describe it

import java.util.Scanner; public class MazeProblem { int x, y; int[][] problem; public void solve() { int[][] solution = new int[x][y]; if (solveMaze(solution, 0, 0)) { System.out.println("Yes "); for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { System.out.print(solution[i][j] + " "); } System.out.println(); } } else { System.out.println("No Solution"); for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { System.out.print(solution[i][j] + " "); } System.out.println(); } } } private boolean solveMaze(int[][] solution, int x, int y) { if (x == this.x - 1 && y == this.y - 1) { solution[x][y] = 1; return true; } if (isSafe(x, y)) { solution[x][y] = 1; if (solveMaze(solution, x, y + 1)) { return true; } if (solveMaze(solution, x + 1, y)) { return true; } solution[x][y] = 0; return false; } return false; } private boolean isSafe(int x, int y) { if (x < this.x && y < this.y && problem[x][y] == 1) { return true; } return false; } public static void main(String[] args) { Scanner input = new Scanner(System.in); MazeProblem mazeProblem = new MazeProblem(); mazeProblem.x = input.nextInt(); mazeProblem.y = input.nextInt(); mazeProblem.problem = new int[mazeProblem.x][mazeProblem.y]; for (int i = 0; i < mazeProblem.x; i++) { for (int j = 0; j < mazeProblem.y; j++) { mazeProblem.problem[i][j] = input.nextInt(); } } mazeProblem.solve(); } }

should not sort it. Create an array or length 11 (index of 0-10), call it H, fill it with null (you can use -1 as null) Call original array A. Code is very simple: i = 0 while(i++) complement = 10 - A[i] if(H[complement] == null) H[complement] = i else break at this point A[H[complement]] + A[i] == 10 I'm essentially using H as a hash table where hash(n) = n this solves the problem in O(n) I believe.

I think hashing is preferred in this case.

@maxzed2k I'm not entirely sure if your solution will cover all cases. What if the complement (i.e. 10-A[i]) is negative? H[ ] will give you a segmentation fault.