Questions d'entretiens - Software developer

google_interview = ( [(1, 5), (10, 15), (20, 25) ], (12,27) ) just_insert = ( [(1, 5), (10, 15), (20, 25), (80,89)], (17, 18) ) join_case = ( [(1, 5), (10, 15), (20, 25), (80,89)], (12, 22) ) empty_case = ( [], (1,10) ) def merge(orig,anew): """ If the input items are sorted, and interval is a 2-tuple, create a new list of intervals, such that we join together any overlapping intervals into a single tuple describing the combined range of the two or three tuples that could collide when we merge another interval into a list""" newlist = [] if len(orig)==0: return [anew] n = 0 # get items that are before the join while norig[n][0]: middleitem[0] = orig[n][0] if n=orig[n+1][0] and middleitem[1] middleitem[1]: # print "break",orig[n] break if orig[n][1] > middleitem[1]: # print "extend" middleitem[1] = orig[n][1] # print "skip",orig[n] n = n + 1 # now append remaining items newlist = newlist + [tuple(middleitem)] newlist += orig[n:] return newlist def test(tup): print 'merge( '+repr(tup[0])+', '+ repr(tup[1])+ ' )' print ' -> ', merge(tup[0], tup[1] ) print ' ' print "Test begin" test( google_interview ) test( just_insert ) test( join_case ) test( empty_case ) print "Test end"

n*lgn sorted by lower bound and gogogo scan once.

JAVA CODE: import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; /** * Created by admin on 3/2/16. */ class Interval { int start; int end; Interval() {start = 0;end =0;} Interval(int s, int e) { start = s; end = e; } } public class Solution { public List insert(List intervals, Interval newInterval) { ArrayList result = new ArrayList(); intervals.add(newInterval); return merge(intervals); } public List merge(List intervals) { ArrayList result = new ArrayList(); if (intervals == null || intervals.size() == 0) { return result; } Collections.sort(intervals, new Comparator() { public int compare(Interval a, Interval b) { return a.start - b.start; } }); for (int i=0;i= intervals.get(i+1).start) { current.end = Math.max(current.end, intervals.get(i+1).end); i++; } result.add(current); } return result; } } Time Complexity: nlgn + n = O(nlgn)

int[] mergeDisjointIntervals(int[] intervals, int[] range){ ArrayList result = new ArrayList(); for(int i=0;irange[0]&&high is inside return 0; } else if(lowrange[0]&&high overlaps tail return -1; } else if(low>range[0]&&lowrange[1]){ // 1 -> overlaps head return 1; } else{ // 2 -> does not overlap return 2; } }

int[] mergeDisjointIntervals(int[] intervals, int[] range){ ArrayList result = new ArrayList(); for(int i=0;irange[0]&&high is inside return 0; } else if(lowrange[0]&&high overlaps tail return -1; } else if(low>range[0]&&lowrange[1]){ // 1 -> overlaps head return 1; } else{ // 2 -> does not overlap return 2; } }

why not just a * b^(-1) :-)

// Write a function that divides one number by another, without using the division operator, // Assume that x%y = 0 // O(log n) (function() { 'use strict'; var divide = function(x, y) { var xLength = (x + '').length; var i = 0; var result = 0; var xAry = ('' + x).split(); var xStart = ''; for (i = 1; i = y) { xStart -= y; result = parseInt(result, 10) + 1; } } } return result; }; console.log(divide(1000, 4)); })();

Use logarithms? O(1) log(x/y) = log(x) - log(y) = log(answer) answer = 10 ^ log(answer)

Convert the number to divide into the base of the number that you are dividing with and then shift the 'bits' to the right by 1 then convert back to decimal

$a = [5, 1, 2, 3, 4]; $b = [5, 6, 7, 3]; $c = []; $hash = []; //Hash the first array foreach($a as $v) { $hash[$v] = 1; } foreach($b as $v) { if ($hash[$v]) { $c[] = $v; } } print_r($c);

public static void main(String[] args) { int a[] = {1, 2, 1, 4, 6, 7}; int b[] = {7, 6, 3}; int c[] = {5, 3, 4, 0, 9}; int maxLength = Math.max(Math.max(a.length, b.length), c.length); LinkedHashMap freq = new LinkedHashMap(); HashSet aSet = new HashSet(); HashSet bSet = new HashSet(); HashSet cSet = new HashSet(); for (int i = 0; i iterator = set.iterator(); while (iterator.hasNext()) { int key = iterator.next(); if (freq.get(key) >= 2) { System.out.print(key + ","); } } }

I guess you were asked to find common elements within three arrays. I would give it a try to use NSCountedSet to count them then populate the result array with those common elements. NSArray *a = @[@1,@3,@8,@-9]; NSArray *b = @[@-1,@3,@0,@-9]; NSArray *c = @[@0,@31,@32,@8,@6]; -(NSArray*)find2ElementsAtleastPresentIn2Arrays:(NSArray*)aList:(NSArray*)bList:(NSArray*)cList{ NSMutableArray *resultArr = [[NSMutableArray alloc]init]; NSMutableArray *largeArray = [[NSMutableArray alloc]init]; [largeArray addObjectsFromArray:aList]; [largeArray addObjectsFromArray:bList]; [largeArray addObjectsFromArray:cList]; NSCountedSet *cs = [[NSCountedSet alloc]initWithArray:largeArray]; for(NSNumber *num in cs){ //NSLog(@"%d **** %@",[cs countForObject:num], num); if([cs countForObject:num]>1){ if(![resultArr containsObject:num]){ [resultArr addObject:num]; } } } NSLog(@"%@", resultArr); return resultArr; }

#3 - to find the PID Or simply use: pidof

Opps!! there is typo; it should be: pidof

1. ./sample.sh &> output.txt :- to capture output and error message suppose sample.sh have below script: #!/bin/bash cat file1 cp file2 file3 lets assume there's no file2 exists in the current directory, returns an error message 2. from any current directory run the below line by line. for i in `find -maxdepth 1 -type f` do cat $i >> output.txt done in for loop i stores all the files (type f means normal file type) in a current directory (maxdepth 1), suppose you want to consider all subdirectory files remove this part. then redirecting all the files to output.txt 3. ps -ef | grep -i "*process name* ps displays running processes, -e utility here displays all the processing shell processes without ignoring any process, f gives the full text/all info of processes. if you are not sure on the exact process name give * as above by giving part of the process name that you can remember

All above answers are wrong. You can solve problem via dynamic programming / recursion. Let DP[a][b] be smallest cost of guessing number in worst case if you know that result is in range [a; b]. DP[x][x] = 0 (if range has only 1 element then there is no need of asking a question). DP[a][b] = min( max(DP[a][x-1], DP[x+1][b]) + x ) for all x in range [a; b] Optimal query is the x which gives minimum value for DP[][]. For example: If range is 10 you should try 7 as first guess. If range is 100 you should try 85. If range is 1000 you should try 873. So it is not like there is any best percentage which gives optimal value for any range.

binary search for question 1, Huffman encoding for question 2.

@andrew shouldn't the answer for range [1,1000] be 897 ?

Malik

The solution mentioned above is O(n^2), because for every node, it is comparing value with all the nodes in Vals array. We can do better than this because we have BST, which is in sorted order. (For unsorted Binary tree, we should have sorted first in O(nlogn) and then searched O(nlogn). O(nlogn) solution - Traverse the BST with DFS (O(n)). For each node of value 'a' search for node of value "b = k - a". Searching in BST would be O(logn). Thus the solution becomes O(nlogn)

HashMap tracker = new HashMap(); public SumPair parseTree(Node node, int sum) { if (node == null) { return null; } SumPair pair = parseTree(node.left, sum); if (pair == null) { pair = parseTree(node.right, sum); } if (pair == null) { if (tracker.containsKey(node.data)) { pair = new SumPair(node, tracker.get(node.data)); } else { tracker.put(sum - node.data, node); } } return pair; }

With a node reference to left,right and parent, it can be done in O(n) Start at deep left with 2 node references at lowest node, value L. move one reference in DFS way until it find a node R >= K-L. if equal then we have a L and R then move the first reference to the next value in DFS, until node L > K-R repeat until last node is reached and L + R > K lot of micro-optimization possible (skip a whole node by going direct to parent when the parent is still lower than what we looking for)

No

Thanks for replying, it seems they requested to do a background check on me currently