Software Engineer In Test was asked...19 March 2009

↳

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. :) Less

↳

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

↳

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[2]; int[] columnSums = new int[n]; initialize diagonalSums and columnSums with zeroes; int rowSum = 0; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (a[i][j] = 'X') rowSum++; columnSums[j]++; if (i == n-1 && columnSums[j] == n) return true else if (i == j) diagonalSums[0]++; if (i == n-1 && diagonalSums[0] == n) return true else if (i = n-1-j) diagonalSums[1]++; if (j == 0 && diagonalSums[i] == n) return true if (rowSum == n) return true Less

Software Engineer Test was asked...21 November 2009

↳

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

↳

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[0][]; // 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 > target) { return findColumn(a,low,midIndex-1,target); } while (mid <= target && midIndex < 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 < 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? Less

↳

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

Software Engineer In Test was asked...2 April 2010

↳

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[0][m-1]) and traverse toward lower left corner (mat[n-1][0]). 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). Less

↳

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); Less

Software Test Developer was asked...8 October 2022

Software Engineer In Test was asked...15 January 2010

↳

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) Less

↳

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

↳

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 Less

Senior Software Engineer In Test was asked...21 September 2015

↳

#!/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 >= 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 >= len1 or stopIdx < 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() Less

↳

//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] > k) return a[start]; else return a[end]; } else { int mid = (start + end) / 2; if (k == a[mid]) return a[mid + 1]; if (k > 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)); } } Less

↳

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

Software Engineer In Test was asked...7 July 2014

↳

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

↳

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

↳

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

Software Engineer In Test was asked...1 February 2015

↳

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[0]; int max = Integer.MIN_VALUE; for (int i = 1; i < len; i++){ max = Math.max(max, array[i] - min); min = Math.min(min, array[i]); } return max; Less

↳

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

↳

^O(nlogn)

Software Engineer Test was asked...21 November 2009

↳

boolean isPowerOfTwo (int a) { return (a&(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) Less

↳

@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) Less

Software Engineer In Test was asked...14 May 2013

↳

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

↳

In C++11 (mainly for the simplified for loop syntax), assuming that the question is about transforming map> to map> below is my solution: map> 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> newMap; for(pair> p : oldMap) { for(char c : p.second) { newMap[c].push_back(p.first); } } Less

↳

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