Software Engineer New Grad Interview Questions

Pick two numbers: A and B, Add the third number to each of the first two : (A+C), (B+C). Compare these two numbers and take the lesser of the two. Now compare C with the other member of the less number. The greater of these two is the median.

I'm not following. Is this: say, B+C is less than A+C, then the larger of B and C is the median? If so, isn't this a counterexample: A = 2, B = 1, C = 3?

Actually the answer is the next one: we could have an answer using only two comparisons. The main idea is that we need to examine one of the numbers to get into the segment created by the other two numbers. And another important thing is that one comparison could be used to definitely determine for both two segments created by two numbers. For example we are trying to examine number A and we have two segments formed by B and C numbers: [B; C] and [C; B]. But considering that for determining if A is in the segment created by B an C we need to make the following comparison: (A - B) * (C - A) >= 0. It is easy to notice that if A is in segment [B; C] (B is less or equals to C) we have both multipliers are positive but in an opposite case when A is in segment [C; B] (C is less or equals to B) we have both that multipliers are negative. If former comparison is negative - then number A is not in any of segments [B; C] or [C; B]. And here is a code of function on C/C++: int medianOfThreeNums(int A, int B, int C){ if ((A - B) * (C - A) >= 0) { return A; } else if ((B - A) * (C - B) >= 0) { return B; } else { return C; } }

Possible Solution: not necessary the right one. Notes: Will recommend use non recursive version of quick sort since 5GB log file could be considered to generate URL data to 500 MB ball park and worst estimate. That would blow the below solution. Also keeping the file open all the time while reading rather than putting it in buffer, since 5GB is a large file size and that may not hold in the memory provided for the program. Will have to ensure that file remains untouched in those moments. # Program to find the URLS that have been most referenced and used from a log file. import sys # Function that will quicksort the list of tuples that have occurence number as first # element in tuple and the URL as the second element in the list. The list is sorted # from the least referenced to most referenced as done in classical quicksort. # From: www.algolist.net/Algorithms/Sorting/Quicksort def sortDict(impurllist, left, right): i, j = left, right - 1 pivot = impurllist[int((left + right) / 2)] while (i pivot[0]): j = j - 1 if (i len(urllist): for element in reversed(urllist): print(str(element[1]), '\t', str(element[0])) else: j = -1 for i in range(num): print(str(urllist[j][1]), '\t', str(urllist[j][0])) j = j - 1 # Definition of main. def main(): try: int(sys.argv[1]) except ValueError: print('Please input a integer for the number of URLs you want to view.') return # Terminate program execution if the arguments provided are not right. if len(sys.argv) != 3: print('Usage: python3.2 HighURLFinder.py #URLs_you_want Log_file') return else: logdict = readLogFile(sys.argv[2]) if logdict is None: return # Terminate execution since the file read program encountered error. else: impurllist = sortLogDict(logdict) showUrlLast(impurllist, int(sys.argv[1])) # The starting point of the program main()

Quick Sort is O ( n log n ) avg case, so we could do better O (n) Now, onto design : Do the lines have other information other than URL? If so, we need to filter them out using Regular Expressions. Possible O (n) solution: A hashmap with URL's as keys and number of hits as values would yield a O(n) run-time to populate it. Algo: while input from file getURL (or filter out URLs from line) if URL exists in hashmap, increment its count else add URL to hashmap Ofcourse, being a large data set, we might get a ton of random disk seeks due to paging of memory. After profiling, if we really find that to be a problem then we could do something like encode the urls into something smaller that takes less space and hence has a lesser probability of causing paging. I can think of few more solutions but I think this should be sufficient.

I would add a min-heap of size 100 to BetterSolution's answer (in order to get the top 100).

count = 0 while(num) { num &= num-1; count++; } return count;

I thought the question was asking how to convert the integer to binary code and output it.

function getOnes($int) { return substr_count(decbin($int), '1'); }

Use the power of 2's to get to the answer.

Log base 2 of 15 billion

You should know offhand that 2^10 is 1024, so 2^20 = 1024^2 is approx a million, 2^30 is approx a billion, then you need four more years to get to 16 billion. Remember that you started with 1, not 2, so the answer is 35 years, not 34.

Create a histogram and do a two time pass.

function findSingle($str) { $arr = str_split($str); foreach ($arr as $char) { if (1 == substr_count($str, $char)) { echo "first letter that doesnt have a pair: " . $char . "\n"; return; } } echo "no such letter\n"; } findSingle("lala"); findSingle("lalas");

#include char getFirstNonRepChar(std::string& input) { int str_Len = input.length(); // Build a Hash Map Table std::map char_map; for(int i=0; i(input[i],1)); } for(int i=0; i< str_Len; i++) { if(char_map[input[i]] == 1) return input[i]; } } int main() { std::string input = "teeter"; char result = getFirstNonRepChar(input); std::cout << result <

public static void slidingAvg(int[] vals, int everyN) { int total = 0; for (int i = 0; i = everyN) { System.out.printf("%f\n", (double)total/(double)everyN); total -= vals[i-everyN]; } if (i < vals.length) total += vals[i]; } }

public static void averageOf7InList(List list){ int last = 0; // just for range tracking int i = 0; do{ if(i+6 < list.size()) i += 6 ; else // i += list.size()-i; not requested :) break; double average = 0.0; int j = last; for(;j < i; j++){ average += list.get(j); } System.out.println("Result : i: "+ i +" Range: from "+last + " to : "+i+" Average: " +(double) (average/j)); last = i; }while(i < list.size()); }

static void printAveragesForWindow(list ints, int windowSize) { // need at least windowSize elements per specification if((int)ints.size() ::const_iterator iter = ints.begin(); iter != ints.end(); ++iter) { // reminder: static variables only initialized on first pass static int windowSum = 0; static int pos = 1; static list::const_iterator windowStart = ints.begin(); windowSum += *iter; if(pos >= windowSize) { cout << windowSum / windowSize << endl; windowSum -= *windowStart; ++windowStart; } ++pos; } }

(print a tree, level by level) public static void printTree(Tree t) { int treeDepth = findDepth(t); for (int i = 0; i 0) { printLevel(t.left, level-1); printLevel(t.right, level-1); } }

(a^3 + b^3 = c^3 + d^3) public static void a3b3c3d3() { Hashtable> h = new Hashtable>(); for (int a = 0; a prev = h.get(lhs); if (null == prev) prev = new ArrayList(); for (String s : prev) { System.out.println(a + " " + b + " = " + s); } prev.add(a + " " + b); h.put(lhs, prev); } } }

(profit maximization) partition prices into non-decreasing sequences; buy at start of sequence of each sequence and sell at end; can be done iteratively by peeking ahead to next day's closing price