# 1 k

Questions d'entretien pour Software Engineer In Test partagées par les candidats

## Principales questions d'entretien

Trier: Pertinence|Populaires|Date
On a demandé à un Software Engineer In Test...19 mars 2009

### How would you determine if someone has won a game of tic-tac-toe on a board of any size?

15 réponses

I think maybe this question is worded a bit wrong, because given a tic-tac-toe board you would need to read in at least some of the values on the board to figure out if someone has won, and this would be impossible to do in constant time (the larger the board, the more values you would have to read). I think they must mean how can you determine if someone has won during a game in real time, as in checking after every move. This can be solved with a strategy in constant time. My solution would be: Create an array of size 2n+2 at the beginning of the game and fill it with zeros. Each spot in the array will be a sum of X's or O's horizontally (the first n places in the array), vertically (the second n places in the array) and diagonally (the last 2 places). Then with every move, you add 1 to the 2 places (or 3 if on a diagnol) of the array if X, and subtract 1 if its an O. After adding you check and see if the value of the array is equal to n or -n, if it is, n mean X has won and -n means O has won. I would bet there is a more elegant solution than creating a large array, but since this isn't my job interview I can't be bothered trying to figure one out. :) Moins

Happier player doesn't always mean the winner. A father teaching his son how to play tic tac toe for instance could be happier if his son actually beat him at the game. Your "simplest answer" is wrong. Moins

Assume that you are handed a board with no prior knowledge of what has happened in the game. Assume that, to win on a board of size NxN, the player must have N 'X' characters or 'O' characters in the same row, column, or diagonal. Assume that, for our problem, we are only checking if the winner is 'X'. We have to make at least one pass through the game board, but we should be able to solve the problem in one pass without checking any cell twice. Target running time O(N^2) for a board of size NxN. boolean checkXWinner(int[][] a, int n){ int[] diagonalSums = new int; int[] columnSums = new int[n]; initialize diagonalSums and columnSums with zeroes; int rowSum = 0; for (int i = 0; i &lt; n; i++) for (int j = 0; j &lt; n; j++) if (a[i][j] = 'X') rowSum++; columnSums[j]++; if (i == n-1 &amp;&amp; columnSums[j] == n) return true else if (i == j) diagonalSums++; if (i == n-1 &amp;&amp; diagonalSums == n) return true else if (i = n-1-j) diagonalSums++; if (j == 0 &amp;&amp; diagonalSums[i] == n) return true if (rowSum == n) return true Moins

Afficher Plus de réponses

### Phone interview 1 : a) Simulate a Queue with stacks ? b)Find repeated occurrence of character in a string ? Phone interview 2 : a) Given a 2D matrix of numbers find the position of number . Constraints of matrix number always in increasing order left to right and top to bottom . b)When should version control be used . And a tricky discreet math problem ?

13 réponses

For a) further challenge was to simulate a double ended queue , but we ran out of time . you could maintain temp stack as permanent variable and get around doing that. b) Kind of sort of what I wrote I was asked to optimize even further , so I said XOR the array make a note of elements left , remove from original list and you have set of repeated elements . Moins

2a. My idea is to first identify the column that might contain our element, then use binary search to see if our element is in that column. The column that might contain our element is the rightmost column where the first row's element is less than or equal to our target element. int[] matrixSearch(int[][] m, int numRows, int numCols, int target){ int[] firstRow = m[]; // not sure this works, can just use for loop to populate int targetCol = findWhichCol(firstRow, 0, numCols-1, target); int targetRow = findWhichRow(m[][targetCol], 0, numRows-1, target); if (targetRow == -1) { return null; // Element not found } return new int[] { targetRow, targetCol}; } int findWhichColumn(int[] a, int low, int hi, int target) { int midIndex = (hi+low)/2; int mid = a[midIndex]; if (mid &gt; target) { return findColumn(a,low,midIndex-1,target); } while (mid &lt;= target &amp;&amp; midIndex &lt; a.length-1) { midIndex++; mid = a[midIndex]; } return midIndex--; } int findWhichRow(int[] a, int low, int hi, int target){ int midIndex = (low+hi)/2; if (midIndex == target) { return midIndex; } if (hi-low == 0) return -1; // Element is not in the matrix if (midIndex &lt; target) { return findWhichRow(a,midIndex+1,hi,target); } return findWhichRow(a,low,midIndex-1,target); } Average: O(log n) Worst: O(n/2) = ~ O(n) This isn't very elegant. How would you do it? Moins

@above: I think the run time is log(n)*log(m)

Afficher Plus de réponses

### Assume a matrix of integers they are sorted in boh row and column vice .. how do u find a given number from the matrix in a optimal way?

10 réponses

Let the matrix is n*m matrix. Then O(n log m) solution is trivial (binary search in each row). There is a easy O(n+m) solution too. The idea is to start from upper right corner (mat[m-1]) and traverse toward lower left corner (mat[n-1]). On the way check each entry and depending on whether larger go left or down. If there is a solution you will find it on the way. Or you will arrive to a point where you can no longer move without going out of the matrix. Either way you will check at most O(n+m) entries thus the solution in O(n+m). Moins

What if you did a binary search on the diagonal....

I think it could be done even better than in O(n+m). Instead of starting at the upper right corner do a binary search on last column and find the biggest element that is still smaller than the given number. Say it's gonna be A[i, m-1]. Now we could throw away all rows up to an including i (since A[i, m-1] is larger than all of these elements) and the last column. Repeat everything for a smaller matrix of size (n - i, m - 1); Moins

Afficher Plus de réponses

### 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 réponses

Here is a C# implementation, using generics and .NET 4.0 Tuple: IEnumerable&gt; RearrangeCars( TCar emptyCarMarker, IDictionary initial, IDictionary desired) { // reverse the lookup: car -&gt; spot Dictionary pending = initial.ToDictionary(p =&gt; p.Value, p =&gt; 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) Moins

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. Moins

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&gt; 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 Moins

Afficher Plus de réponses

### Search a sorted array for the first element larger than k

6 réponses

#!/usr/bin/env python """Search a sorted array for the first element larger than k. """ def srch(list1, srchItem): """Perform Binary search and find the first element that is larger than the arg srchItem @list1: The sorted list @srchItem: The element to be searched for finding next greater value than that """ len1 = len(list1) startIdx = 0 stopIdx = len1 - 1 stop = False # saveIdx the index of the lowest value in the sorted list saveIdx = -1 while not stop and startIdx &gt;= 0 and stopIdx srchItem: # found greater item, but the previous one also could be greater stopIdx = midIdx - 1 saveIdx = midIdx elif list1[midIdx] srchItem: saveIdx = startIdx break elif startIdx &gt;= len1 or stopIdx &lt; 0: break if saveIdx == -1: return -1 # not found return list1[saveIdx] def testAll(): testList = [3, 6, 9, 34, 67] print 'Test: %s SrchItem: %d' %(testList, 34) print 'Result: %d' %srch(testList, 34) testList = [3, 6, 9, 34, 67, 69] print 'Test: %s SrchItem: %d' %(testList, 34) print 'Result: %d' %srch(testList, 34) # test for result to be the 1ast item in the list testList = [3, 6, 9, 34, 67, 69] print 'Test: %s SrchItem: %d' %(testList, 68) print 'Result: %d' %srch(testList, 68) # test for result to be the ist item in the list testList = [3, 6, 9, 34, 67, 69] print 'Test: %s SrchItem: %d' %(testList, 1) print 'Result: %d' %srch(testList, 1) # item not in the iist testList = [3, 6, 9, 34, 67, 69] print 'Test: %s SrchItem: %d' %(testList, 70) print 'Result: %d' %srch(testList, 70) if __name__ == '__main__': testAll() Moins

//Run time complexity is logn public class FirstGreatestNumberThanK { public int prepareFirstGrtst(int[] a, int k) { return firstGrtst(a, 0, a.length - 1, k); } public int firstGrtst(int[] a, int start, int end, int k) { if (end == start + 1) { if (a[start] &gt; k) return a[start]; else return a[end]; } else { int mid = (start + end) / 2; if (k == a[mid]) return a[mid + 1]; if (k &gt; a[mid]) { start = mid; return firstGrtst(a, start, end, k); } else { end = mid; return firstGrtst(a, start, end, k); } } } public static void main( String[] args){ FirstGreatestNumberThanK f = new FirstGreatestNumberThanK(); // int[] a = {2,4,6,8,9,12,14,16}; // even length int[] a = {2,4,6,8,9,12,14}; // odd length // System.out.println(f.prepareFirstGrtst(a, 11)); // System.out.println(f.prepareFirstGrtst(a, 3)); // System.out.println(f.prepareFirstGrtst(a, 7)); // System.out.println(f.prepareFirstGrtst(a, 15)); // execute for even length data // System.out.println(f.prepareFirstGrtst(a, 14)); // execute for even length data // System.out.println(f.prepareFirstGrtst(a, 4)); System.out.println(f.prepareFirstGrtst(a, 12)); System.out.println(f.prepareFirstGrtst(a, 2)); } } Moins

def find_greater(aList, item): high = len(aList) low = 0 while low &lt; high: mid = (high + low) // 2 if item &lt; aList[mid]: high = mid else: low = mid + 1 return aList[low] Moins

Afficher Plus de réponses

### Not difficult. It is like why can not compare two strings. And how to compare one object which initialed as a string with string. The coding quesition is to find the kth in two sorted arrays.

5 réponses

Maybe I'd use a binary search on the two arrays... it's tricky, but the solution MUST be fast Moins

The above solution is m+n. The solution that gets you hired is log(m+n), but it doesn't involve binary search. Moins

So the ideas is instead of just cut one number each time, you cut k / 2 numbers every time. Moins

Afficher Plus de réponses

### Difficult to answer in short and first time attempt.

5 réponses

Its a forward difference, so you track the smallest number before your current number then you can get the biggest difference with the current number as the subtractor. If it means subtractor must be in earlier position than subtractee, reverse the algorithm. int min = array; int max = Integer.MIN_VALUE; for (int i = 1; i &lt; len; i++){ max = Math.max(max, array[i] - min); min = Math.min(min, array[i]); } return max; Moins

by the way, the above solution is O(n) complexity, and O(1) auxiliary space

^O(nlogn)

Afficher Plus de réponses

### Onsite Interview 2 a): check whether a number is the power of 2 b) Skyline silhouette puzzle . c) Discussion on uses of hash-tables and trees ? d) Few general questions on Work and academic background .

5 réponses

boolean isPowerOfTwo (int a) { return (a&amp;(a-1)==0); }

@ellemeno: You are expected to give the solution as Anonymous which by the way can be done in java as well , ( it's generally called bit wise operations) Moins

@ellemeno: You are expected to give the solution as Anonymous which by the way can be done in java as well , ( it's generally called bit wise operations) Moins

Afficher Plus de réponses

### Invert a Map e.g 1: {a,b} 2: {c,d} becomes a:1 b:1 c:2 d2

4 réponses

This guy has put the question wrongly. Actual question is something in these lines - You have a list of {key, value} pairs, sorted by keys in increasing order. And now you have a Iterator class that has two methods hashNext(), getNext() which return if next entry exists, and returns the next entry and moves to next entry, respectively. Now design a new iterator which will have same methods but returns a pair {key, List of Values} by gathering all values of a common key. Moins

In C++11 (mainly for the simplified for loop syntax), assuming that the question is about transforming map&gt; to map&gt; below is my solution: map&gt; oldMap; list one; one.push_back('a'); one.push_back('b'); oldMap.insert(make_pair(1, one)); list two; two.push_back('c'); two.push_back('d'); oldMap.insert(make_pair(2, two)); map&gt; newMap; for(pair&gt; p : oldMap) { for(char c : p.second) { newMap[c].push_back(p.first); } } Moins

Map map1 = new HashMap(); Map map2 = new HashMap(); for(Integer key: map1.keySet()){ for (int i=0; i &lt; a.size(); i++){ map2.put(map1.get(key).get(i).toString(), key); } } for(String key: map2.keySet()) System.out.println(key + ": " + map2.get(key)); Moins

Afficher Plus de réponses

### Implement a binary tree and explain it's function

4 réponses

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. Moins

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. Moins

Afficher Plus de réponses
1 - 10 sur 1 374 Questions d'entretien