CareerCup

Limited network bandwidth and fixed browsers means we have to optimize the efficiency of how the browser and phone connect to the data center. If we cannot change any aspect of the browser, and we cannot expand the bandwidth, we probably should focus on handling the load better.

You can do any of the following:
1. Improve the algorithm handling bandwidth distribution from wireless cells to support a more dynamic structure permitting users to aquire more of the available bandwidth inversely proportional to the demand.

2. Improve the data center's ability to process incoming requests, possibly increasing its caching size, the number of parallel processors running, improving the connection hardware to raise transfer speed, or even refine the relay setup to optimize the transfers between the deployed wireless cells and the center.

3. On the phone, you can obviously upgrade all the hardware, affording more memory to browser, additionally a upgrade to the wireless component to allow for multithreading of connections or maybe synchronizing with local cells to improve quality.

4. Alter the phones thread scheduler to always prioritize the browser and the connection requests above anything else. (not the smartest move but it would certainly mean less delays on usage of the browser)

5. Prevent the installation of addons and plugins for the browser in the phones os or optimize for the specific browsers

6. add a ethernet port to the phone because no one said the connection has to be wireless all the time.

7. Have several thousand support techs or use a automation program to manage the networks allocation of bandwidth and priority.

This is, of course, all speculation. Rather nebulous question.

the first one is straight forward enough, though maybe im a spoil-sport and wouldnt bother writing out all the logic if i had a choice.

Two ways in python, one with a built-in, the other done manually:

def get_median_shortcut(a, b, c):
    return sorted([a,b,c])[1]

def get_median(a, b, c):
    if ((a<=b) and (a>=c)) or ((a<=c)and(a>=b)):
        return a
    elif ((b >= a) and ( b <= c)) or ((b <= a) and (b >= c)):
        return b
    else:
        return c

In any case, both will work given all 0's, duplicates, etc.

You maybe should give some more detail on that second one, I can give it a shot but I'm not 100% certain what you mean by it. If I interpret correctly, the min and max equal whichever values in a,b, and c that are min and max respectively. Use of bitwise operations are easy enough here, but I prefer to do the obvious arithmetic: a+b+c - min - max will just leave behind whichever value is the median.

in python:

def get_median_min_max(a,b,c,min,max):
    return a+b+c-min-max

If min and max are not included in a,b, and c, then the solution is to just call the other get_median function with a,b,c, i.e:

def get_median_min_max(a,b,c,min,max):
	return get_median(a,b,c)

Theres a few ways to do this, and a question like this is begging to be elaborated on. Do you want words that actually exist? Do you have a given set of words which are valid, or do you have the set of all possible combinations of letters?

Let's say, for start, that you do not have a dictionary of words to work with initially, so any values that match the given length are valid (i.e. a2e -> {aaae, aabe, abae, abbe....}) which creates an incredibly slow solution (O(26^n) where n is length of string minus first and last char)

I doubt that's what they meant initially, but the solution in this case is to use a recursive function to create to permutations, then apply the first and last char to each prior to returning.

In python:

def getStringFromNumeronym(numeronym):
    alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k',
                'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v',
                'w', 'x','y', 'z'  ]
    internal_length = int(numeronym[1:-1])
    permutations = permutate(alphabet, internal_length)
    for i in range(0,len(permutations)):
        permutations[i] = numeronym[0] + permutations[i] + numeronym[-1]
    return permutations

def permutate(chars, length):
    if length == 1 :
        return chars
    x = permutate(chars, length - 1)
    output = []
    for c in chars:
        for b in x:
            output.append(c + b)
    return output

As stated before, though, this a pure bruteforce answer.

If, however, you are given a dictionary of acceptable response terms, you can simply create an empty set and process through the dictionary, getting the numeronym for each word and comparing it to the input.

In python:

#assume we have a dictionary available
def get_string_with_dict(numeronym,dictionary):
    output = []
    for x in dictionary:
        if makeNumeronym(x) == numeronym:
            output.append(x)
    return output

This runs O(n) where n is size of the dictionary. This assumes your makeNumeronym function is O(1)

Some versions of the answer use a pre-processing into a hash table, but really this doesn't save any time or space as in both cases you still have to run through the ENTIRE dictionary input and process every word into a numeronym.

That's certainly a warm up. Python lets you answer this essentially in one line:

def makeNumeronym(word):
    return (word[0] + str(len(word[1:-1])) + word[-1]) if (isinstance(word, str) and len(word) >= 3) else word

This would be even shorter if it didn't do type checking and length checking.

The nlogn is a rather generous runtime allowance here, as it meanns we can run a heapsort or similar.

The idea here is to create a sorted version of the array, and compare to see if there are exactly m differences (in this case, m=2)

in python:

def only_m_switches(val_array, m):
    tmp_array = sorted(val_array)
    for i in range(0, len(val_array)):
        if tmp_array[i] != val_array[i]:
            m -= 1
    return m == 0

this fulfills the required space and time usage as well.

You can do this with a quick depth-first recursion.

In python:

def get_valid_nodes(root, curr_sum):
    if not root:
        return 0
    left_count = get_valid_nodes(root.left, curr_sum + root.val)
    right_count = get_valid_nodes(root.right, curr_sum + root.val)
    root_valid = 1 if root.val < curr_sum else 0
    return root_valid + left_count + right_count

What it does is keep track of the sum of values in the traversal to the current node in the tree. If it is the bottom of the tree, it returns 0. Otherwise, it recurses on its left and right child, then adds their values to 1 (if the curr node has a val less than the above sum) or 0 and returns that value.

runs in O(n log n)

While I normally stay away from recursion usage in interview questions, here's a case where it greatly simplifies life.

in python:

def swap_rec(node):
    if not node or not node.next:
        return node
    tmp = node.next
    node.next = swap_rec(tmp.next)
    tmp.next = node
    return tmp

To make it work, you hand it the head node of the linked list. It will do the reversals in pairs as specified, and handles cases such as an odd-length list.

The reason I say recursion saves us time here is because tracking the pointers in a loop can become a pain. In either case, the solution is O(n) runtime

these are simple expansion cases using some basic knowledge of ascii.

this is a classic, with some basic ascii conversion you can do this in one run.

in python:

def get_int_val(word):
	output = 0
	for i in range(0, len(word)):
		mult_val = 10**(len(word) -1 - i)
		x = ord(word[i])-48
		if x >= 0 and x <= 9:
			output += mult_val*x
	return output

this will fill any spots taken up by chars with 0's, it can easily be modified to not do that. The logic is to use the base-10 property of the integer to get properly placed values added to the sum and returned. O(n) time.

utilize a dynamic list-like structure, i.e. a set in python. Have two sets, values we know are repeated, and values weve only seen once so far.

As you traverse the characters in the string, check to see if char x (the current char) is already in the set of values we know repeat, if so, skip it. If x is in the set of values weve only seen once, add x to the set of repeating vals and remove it from the unseen set. Otherwise, just add it to set of unseen values.

in python:

def find_non_rep(word):
	seen_vals = set()
	unseen_vals = set()
	for x in word:
		if x in seen_vals:
			continue
		elif x in unseen_vals:
			seen_vals.add(x)
			unseen_vals.remove(x)
		else:
			unseen_vals.add(x)
	return unseen_vals[0] if unseen_vals else None

How this works is that any values we know (empirically) are repeated are made accesible to allow skipping and keep track of invalid values. If the value we look at has been seen before, it will be either in the repeated vals or the list of vals only seen once, in either case, it will be skipped. What is left after the whole process is finished is a set of values only seen once, just take the first one.

runs through the whole string once, so it runs in O(n) time, and the space usage is at most twice the size of the string, so, O(n) space.

Well, you gave a fixed upper limit, which means this can be done rather simply in O(1) because we have a O(1) preprocessing step (with no chance to go beyond a set limit, its considered constant)

To preprocess, take each value x from 0...n and add it to a lookup table in the format <x^2, x> unless x^2 is greater than 10000

in python:

def pre_process(upper_limit):
	sqr_table = {}
	for i in range(0, upper_limit):
		if i**2 <= upper_limit:
			sqr_table[i**2] = i
		else:
			break
	return sqr_table

def lookup_sqr_root(val, sqr_table):
	if sqr_table.get(val, None):
		return sqr_table.get(val, None)
	else:
		return False

A maze is, when simplified, little more than a set of permutations of choices, of which only one (unless it has multiple paths to end) is the correct. For a position p in the maze, there are at most c choices (usually 3, left, right, forward) so to traverse the maze accurately you need O(c^n) time, where n is the maximum number of turns possible in the maze before hitting a dead end or the end of the maze. This is essentially a tree.

Supposing the robot is able to backtrack and has no awareness of what lay around any of the presented options (left, right, forward) you can utilize a recursive algorithm

in python with some assumed functions:

class Position:
	#contains a list of pointers, choices, and position value.
	# also contains a function move_to which creates a position for that direction
	#and a function is_end which specifies if the position is the end of the maze

	#contains a static set called visited which indicates when a specific position has
	#been previously visited by the algorithm.


def solve_maze(position):
	if position in position.visited:
		return []
	position.visited.add(position)
	if position.is_end():
		return [position]
	for x in position.choices:
		y = solve_maze(position.move_to(x))
		if not y:
			continue
		else:
			return position + y
	return []

The solve_maze function returns a ordered list of positions. If the returned list is empty, it is ignored as it means that that sub-tree of movements resulted in a dead end. Otherwise, the current position of that recursion layer is added to it, and returned.

What this means is the recursion will always hit the bottom of the tree of possible paths first, then begin working in depth-first order. The only paths which will propagate back up to the root are those which result in reaching the end of the maze.

Additionally, the visited list will prevent parts of the maze which loop creating an infinite recursion. In no maze is there ever a reason to go to the same point twice.

The Position class will, when given the move_to command, continue until the next point in the maze where you encounter a choice.

This will run in the runtime stated above, not terribly efficient. Memoization is provided in the form of the visited list, as any one point will have a fixed set of valid paths, regardless of which direction it is approached from.

I'm assuming your question, which isn't a question by the way you said a word not sure what you expect of us please add more detail next time, is to find if a sentence is a pangram (contains at least 1 of every letter in the alphabet)

To do so, create a set containing all the letters, then remove each one if it is seen in the string.

In python:

def is_pangram(word):
    alphabet = set(["a", "b", "c", "d", "e", "f", "g", "h",
                        "i", "j", "k", "l", "m", "n", "o", "p",
                        "q", "r", "s", "t", "u", "v", "w", "x",
                        "y", "z"])
    for x in word.lower():
        if x in alphabet:
            alphabet.remove(x)
    return not alphabet

The logic is that, for each character, if you see it in the alphabet set, it wasn't seen before, so remove it, indicating it has been seen. If the character isn't in the set, it either hasn't been seen yet, or it's not a letter (so, a numeric value or symbol)

Some people have argued that this can be done by creating an empty set, then filling it as you go along, since sets in python will not duplicate entries, then checking that the size of the set is 26. When faced with the possibility of a number in the string, some suggest using ascii numeric conversion of characters to determine if they are letters, but the end result is that the exact same space is used, (the method I wrote starts with 26 and ends with none, the other method starts with none and ideally ends with 26) but containes extra logic that isn't necessary.

Runs in O(n) when using a lookup data structure with O(1) lookup time.

I should add that use of recursion or substrings only technically meets the requirements of the question, but is unnecessary and as always, recursion should be avoided if a solution of equal or better efficiency is available.

This is done with a 2 pointer method, assuming you want the ENTIRE string to be a palindrome. That makes it quick and easy.

Just iterate forward from the start of the string, and backwards from the end of the string at the same rate, comparing the two pointers values at each iteration. This also automatically solves the odd-length edge case that can occur (which many people often write an extra conditional statement for)

In python:

def is_palindrome(word):
    for i in range(0, len(word)/2):
        if word[i] != word[len(word) - 1 - i]:
            return False
    return True

Runs O(n) time (actually n/2 but you get the idea) and uses no external data structures.

This also returns True for an empty string or 1 char string, as an empty or 1 char will always be symmetrical.

a map isn't necessary you can do this with a set and save space. its also not efficient to add all these values into the map then look through the whole map when you already know, based on each value, what is required to create a valid pairing. Instead of focusing on creating a matching and seeing if it fits, create a set of valid answer values for each value you encounter, if that value isn't already found in the answer set.

Quick-and-dirty solution involving a flag with O(n) runtime:

in python:

def find_longest_sub_array(vals):
    curr_start = 0
    curr_sub = []
    flag = False
    for i in range(0,len(vals)):
        if vals[i] >= 0:
            if not flag:
                curr_start = i
                flag = True
        else:
            if flag:
                if i - curr_start > len(curr_sub):
                    curr_sub = vals[curr_start:i]
            flag = False
    return curr_sub

adjustments to return things such as the length of the subarray or the start index are trivial.

This is just a data structures application problem. If you use a O(1) lookup structure like a set in python, you can solve this in O(n) time.

In python, the solution would be:

def find_if_sum(total, vals):
    val_set = set()
    for x in vals:
        if x in val_set:
            return True
        else:
            val_set.add(total-x)
    return False

The logic is simple: as you traverse the array, you will see, for each number, its required sibling value such that the two sum to the given total. By the time you reach the last value, if it isn't already in the set, none of the preceding values will have worked for it. If you reached the last value and that is the case, none of the preceding values had a valid sibling within the set.

Sorting and whatnot is unnecessary. If the question were asking us to return the actual pair which equals that total, that would be a solution. But all it wants us to do is confirm it has a valid pairing.

Somewhat clunky but here's one solution utilizing a counting system

in python:

def fancy_shuffle(word):
    output = ""
    chars = {}
    for i in range(0,len(word)):
        if chars.get(word[i],None):
           chars[word[i]] += 1
        else:
           chars[word[i]] = 1
    val_sum = 1
    while val_sum > 0:
        val_sum = 0
        for letter, count in chars.iteritems():
            if count == 0:
                continue
            if output and output[len(output)-1] == letter:
                return False
            output += letter
            chars[letter] -= 1
            val_sum += count
    return output

The runtime is O(n), it takes O(n) time to run through the initial word and organize all the letter occurrences with their counts in the lookup table. It then takes another O(n) time to look through the table doing consecutive iterations and decrementing the letter counts as each is placed into the shuffled string.

Space efficiency is O(n)

two parts will prevent any compiling:

void static f2(){y=35;}

should be

static void f2(){y=35;}

That's just testing if you know the syntactic restrictions of the language.

Also, y must be declared as a static variable, as it must be instantiated on compile to be accessible via operation from f2.

Additionally, just nit-picking on style, but the class should have its first letter of the name capitalized (A in this case)

We should start by remembering that slope between two points is:

slope = (y2 - y1)/(x2 - x1)
or
slope = (change in y)/(change in x)

Effectively this problem asks us to locate two pairs of values who have a maximum difference between their y coordinates and a minimum diff between their x coordinates.

The brute force method is to compare each pairing to every other pairing but that is clearly not what is being asked for as it would take O(n^2) time.

While I forget the name of the concept (or if it has a common name), you can assume that given a set of points on any 2d plane with x and y axis, when sorted by x axis, the highest slope will always be between two points adjacent on the x axis.

To see this better, try drawing 3 points on a plane, look at how steep the line between each of them is, notice the line between non-adjacent points is never the steepest. At best, all three slopes are the same if you have them all aligned. If you try all combinations with four points, you will see the same principle still holds. And with 5 pts, etc etc. It can be summarized, non-algebraically, as

Given points a,b,c on a 2D plane where b has the median x-axis value, creating a triangle with these three points requires that either b->a or b->c will always be steeper than a->c, based on whether b is located above or below the a->c line.

If b is below the line, b->c will always be greater than a->c, if it is above the line, a->b will always be greater. This is the positive direction of slope to reach a common point from a closer x-axis position, so it will always be steeper. If b is on the a->c line, its slope is the same as a->c.

If we use this postulate within our solution, we can say that once we have sorted the points by x-coordinate, the highest slope will be found at one of the adjacent pairs of points.

In python, the solution would look like:

def find_highest_slope(points):
    output = ((1,1),(1,1))
    max_slope = 0
    #use some method to sort points by x axis
    for x in range(1,len(points)):
        delta_y = points[x][1] - points[x-1][1]
        delta_x = points[x][0]-points[x-1][0]
        if delta_x == 0:
            continue
        slope = (delta_y)/(delta_x)
        if slope > max_slope:
            max_slope = slope
            output = ((points[x-1][0],points[x-1][1]),(points[x][0],points[x][1]))

    return output

The part shown here will take O(n) time, as it merely compares each coordinate to its previous neighbor. The sorting may take longer, but assuming you use a heapsort or similar, you can say that the solution takes O(n log n) which beats the O(n^2) done with the brute force solution.

please define for us the meaning of "pair of prime number and even number", as that doesn't really specify anything beyond that pairs need to be a prime matched to an even? Is there some ordering rule, a requirement of how they be paired? My answer is going to be based on what I can interpret from your example

To take a preliminary stab at this with my limited understanding, I would say a answer which yields an array of paired prime-evens with the unpaired values on the end would be:

1. Use sieve of erastosthenes or another prime mapping method to create a lookup set of all prime vals from 1 to the highest value in the array

2. create three arrays, lets's call them Prime, Even, Odd

3. Scan through array, if a value is in the prime lookup set from step 1, add it to Prime, if that value modded by 2 is 0, add it to Even (two can be treated as a special case, the only even prime), otherwise, add it to Odd

4. Scan through Prime and Even at same rate, adding Prime[i],Even[i] to array until one or both of the arrays has ended. After that, add all values remaining in Even and any values in Odd to the array.

I'm not going to implement the sieve as it is irrelevant and can be replaced by any standard method of mapping primes.

The python solution:

import sieve 	#not an actual library but just assume

def pair_prime_even(vals):
	prime, even, odd = [], [], []
	max_val = 0
	for val in vals:
		if val > max_val:
			max_val = val
	prime_ref = sieve.get_all_primes_up_to(max)  #assume it returns a hashset or similar
	for val in vals:
		if prime_ref.get(val,None):
			prime.append(val)
		elif val%2 == 0:
			even.append(val)
		else:
			odd.append(val)
	output = merge_arrays(prime, even)
	for x in odd:
		output.append(x)
	return output
	
def merge_arrays(a,b):
	i = 0
	output = []
	while i < len(a) or i < len(b):
		if i <len(a) and i < len(b):
			output.append(a[i])
			output.append(b[i])
		elif i < len(a):
			output.append(a[i])
		else:
			output.append(b[i])
		i += 1
	return output

While the main logic here will run in O(n) time (O(1) lookups for primes, O(2n) for merging prime and even, O(n) for for merging in odd), the choice of function for getting the reference set of primes is what will most likely determine the overall runtime.

This problem can test either of two skills: Understanding the language you use/regular expressions and the usage of existing resources, or simply how to create a way to scan the string, pick out the numbers, and add them from scratch.

The first method is really quite simple, most languages have support for regex operations, such as python's re library. Use the regular expression "[0-9]+" with the findall function in the re library and then iterate through, adding as you go to a sum.

In python:

import re

def find_sum(s):
	parsed_list = re.findall(r'[0-9]+',s)
	sum = 0
	for val in parsed_list:
		sum += int(val)
	return sum

For interviews, this is a mixed bag, as the interviewer will either see this as smart and effectively using a helpful technology, or they will think you are being lazy and don't know how to implement the manual solution.

Admittedly, the manual solution is a pain in the rear, or at least it seems that way when you know you can use a regex (please, if you do the manual method, afterwards mention that it could be done in less lines with use of regex, just to get some points for knowing practical tech). For the manual solution, the process looks more like:

def find_sum(s):
    start_pt = 0
    tracking = False
    sum = 0
    for i in range(0,len(s)):
        converted_val = ord(s[i]) - 48
        if converted_val <= 9 and converted_val >= 0:
            if not tracking:
                start_pt = i
                tracking = True
        else:
            if tracking:
                sum += convert_to_int(s[start_pt:i])
                tracking = False
    sum += convert_to_int(s[start_pt:]) if tracking else 0
    return sum

def convert_to_int(val):
    sum = 0
    for i in range(0,len(val)):
	    sum += (10**(len(val) - 1 - i))*(ord(val[i])-48)
    return sum

the logic here is that initially you are not assessing a group of values, if you see one which when converted through ascii values is actually a decimal unit (0-9) you set the starting pointer to that index, and flag that you are tracking a group. When you run into a non-decimal, you run the substring from the start pointer to the last valid value you saw through basic conversion from separate digits to a whole int. Then add it to the sum, and set the tracking flag to false to indicate that the start pointer should be moved next time you see a valid digit.

a bit messy and not quite what i would say is truly from scratch (i did utilize the ord conversion, but as most languages can convert a char to its ascii value, its fair game) but it will get the job done in O(2n) => O(n) time, since it only runs through the array once, and the only other iterations are done in conversion, worst case, the entire string is one int value and it must be iterated through twice. It also has O(1) space usage, since you are only using ints and booleans to track the values.

My bad, the first answer using lookup tables doesn't work in unordered arrays. In any case, the second version works.

If the order in which the ranges are given in output doesn't matter, we can do this with a lookup table in a relatively short time (ideally, O(n) time). It works by having each entry seen check the table for its predecessor (i.e. for value x, check if table has value x-1) and then removes that key from the table, replacing it with the current one. The val assigned to that key is the val of the first entry in the range.

I'm bad at describing this so let's see how it looks implemented in python:

def find_in_unsorted(vals):
    output = ""
    val_counts = {}
    for x in vals:
        if not val_counts.get(x-1, None):
            val_counts[x] = x
        else:
            start = val_counts.pop(x-1)
            val_counts[x] = start
    for end, start in val_counts.iteritems():
        if output != "":
            output += ", "
        output += "{}".format(end) if end == start else "{}-{}".format(start,end)
    return output

However, this solution isn't always ideal, tables with lots of collisions are going to have worse lookup times. If you are willing to run it through a heapsort for O(n log n) time, you can accomplish this in, worst case, O(n log n). The python code for the post-sort processing looks like :

def find_ranges(vals):
    output = ""
    curr_start = 0
    curr_end = 0
    for i in range(1,len(vals)):
        curr_val = vals[i]
        if curr_val == (vals[i-1] + 1):
            curr_end = i
            continue
        else:
            output += append_vals(curr_start, curr_end, vals)
            curr_start = i
            curr_end = i
    output += append_vals(curr_start,curr_end,vals)
    return output

def append_vals(start,end, vals):
    output = "{}".format(vals[start]) if start == end else "{}-{}".format(vals[start],vals[end])
    return output + (", " if end < len(vals) - 1 else "")

This also prints the ranges in proper order.

The first method, if my memory serves me right, has a worst-case runtime (with lots of collisions and slow lookups) of O(n^2), so while the first solution is faster in ideal cases (O(n)) the second is stable and is not affected by such issues.

how does this handle the case

[1,0,1,2,3,2,1,2,1,2]

from my calculations it comes out as

1 +/- (2 + 10 - 1)/2 => 1 +/- 5.5

it seems your solution can locate the theoretical maximum and minimums possible (you are calculating the max distance it can continue in a direction while still being able to hold to the rules of the array) but it isn't effective for locating the real local max or min.

Another contradiction case is

[1,2,1,2,3,2,3,4,3,2]

Use of long arrays which include staggering between two numbers for extended portions can screw this one up.

As far as I know, without being able to use at least O(n) preprocessing, it isn't possible to meet these requirements. If the O(1) refers to final data assessment (post processed, i.e. put into a heap) then yes it is easily done (with a heap). If there is a way to do it in O(1) without pre-processing, I'd love to know how

You can just use a pointer to the first char and last char in the string. increment the first and decrement the last until they meet, comparing at each iteration. If they are not equal at any time, return False (is not palindrome).

in python:

def is_palindrome(word):
	ptr_front = 0
	ptr_back = len(word) - 1
	while ptr_front < ptr_back:
		if word[ptr_front] != word[ptr_back]:
			return False
		ptr_front += 1
		ptr_back -= 1
	return True

This solution is O(n) runtime, and works in-place thus being preferable to methods which use a stack or a second string with the same runtime. This could be done in fewer lines if i used something like

for i in range(0, len(word)):
	if word[i] != word[len(word)-i]:
		return false

but pointers are easier to visualize

Avoid using language-specific structures like stringbuilder if possible, and for problems like this you shouldn't use pre-existing methods to skip major portions of the logic they are testing you on. Using the stringbuilder's reverse method leaves you at the mercy of not knowing the space or time complexity, as well as leaving your interviewer underwhelmed.

We know that the minimum number will be found at the point of highest overlap between schedules. Similar to my answer to the question for finding whether schedules overlap, you can keep track of how many times any one hour slot is used, and simply find the highest slot.

in python:

def find_min_req_rooms(sched_list):
	slots = [0 for x in range(0,24)]
	for sched in sched_list:
		for hour in range(sched[0],sched[1] + 1):
			slots[hour] += 1
	max = 0
	for x in slots:
		if x > max:
			max = x
	return max

The runtime here is O(nm) where n is the total number of schedule entries and m is the largest number of hours in any schedule entry.

Create a array representing 24 hours, each hour's cooresponding element set to 0 (or true, to represent open). Iterate the schedule list, and if the start or end time values are not 0 (open) in the array, return True. Otherwise, set all values between start and end to 1 (closed).

in python:

def detect_sched_conflict(sched_list):
	slots = [0 for x in range(0,24)]
	for sched in sched_list:
		if slots[sched[0]] != 0 or slots[sched[1]] != 0:
			return True
		for x in range(sched[0],sched[1]+1):
			slots[x] = 1
	return False

This has O(n) runtime, where n is the length of the slots list. This is because you only have 24 (in this case) available slots, and at least one is lost in each iteration. No matter how many schedule entries you have, if you fill the slots array, you will return.

Caveats:
- For sub-hour scheduling, such as half hour or quarter hour increments, you would have to reconfigure to some degree, but the overall concept stays the same.
- This version doesn't allow schedules to intercent end-to-start (i.e. a 2-5 and 5-7 will not work because they have 5 in common) so it uses atomic assumption that any hour involved is used entirely
- requires use of 24-hour notation rather than 12 hour notation

and again that got messed up a bit. oh well you get the idea.

oops my art got butchered.

x       x
x       x
x       x
x       x
x x x x

this can be imagined as if the graph is a cross-section of some hills/mountains with rain falling on it. Where would the water collect vs where would it drain off and flow away? You want to calculate how much water is stored. Draw out a graph on paper and you can get a general idea.

a simple example:
[5,1,1,5]

this would look something like (sorry it's time for ascii art):

x x
x x
x x
x x
x x x x

water would collect in this one, you would have 8 units collected after it is done

Assume 1 unit of water is one unit of height per bar on the table (i.e. the x's in the example)

This is a good answer, though it can be done without recursion in O(n) as well.

O(n) solution in python:

def format_words(statement):
    words = statement.split(" ")
    output = []
    for word in words:
        if len(word)%2 == 0:
            x = ""
            for i in range(len(word) - 1, -1, -1):
                x += word[i]
            output.append(x)
        else:
            output.append(word.upper())
    for word in output:
        print "{}".format(word),

Due to the constraint that all chars in the input string may need alteration,
we are stuck with having to assume that a string like

"abcd efgh ijkl mnop qrst uvwx yz" would have to reverse every word in the input and
take O(n) time where n is number of chars total in the string.

A constant space solution would simply reassign the statement to a array of words split by spaces,
then operate on each word, with reversals being done in-place.

Sorting is unnecessary. You are seeking a version of an array where odd-index elements (1,3,5...) are local maxima in the range of their adjacent even-index elements.

My solution has the use of the mod operator (for better design, i recommend use of a flipping boolean as mod isn't the best operator in terms of efficiency if I recall correctly).
Each iteration, you determine whether to switch with the next element by whether or not you are on a odd element.

In python, it looks like this:

def find_local_max(arr):
	for i in range(0, len(arr) - 1):
		if (arr[i] < arr[i+1] and i%2 != 0) or (arr[i] > arr[i+1] and i%2 == 0):
			tmp = arr[i]
			arr[i] = arr[i+1]
			arr[i+1] = tmp
	return arr

Depending on if the index is even or odd, the logic of when to trigger a swap is inversed. Because it iterates one index at a time, you can handle the edge case where some values would get lost in the skipping portion and you could have a returned array that isn't matching the requirements.

As this only loops through the array once, its runtime is O(n).
To sum up the central logic component of this solution in pseudocode:

for each value/index in array:
		if current val is less than next, and current index is odd, swap them
		else if current val is greater than next and current index is even, swap them

To get an O(n) time solution, use the following method (in pseudo-python):

find_unique_substring(big_string, unique_count):
	ptr_1 = 0
	ptr_2 = 1
	uniques = {big_string[ptr_1]: 1} 
	curr_count = 1
	max = ""
	while ptr_2 < length of big_string:
		add big_string[ptr_2] to uniques:
			if big_string[ptr_2] is already in uniques:
				increment val by 1 for it
			else:
				set val to 1 for it
				increment curr_count
		if curr_count <= unique_count:
			if length of big_string[ptr_1:ptr_2] > length of max:
				max = big_string[ptr_1:ptr_2]
			increment ptr_2
		else:
			decrement val for big_string[ptr_1] in uniques by 1
			if val for big_string[ptr_1] == 0, decrement curr_count by 1
			increment ptr_1 and ptr_2
	return max

a little messy, but the general idea is since the substrings are contiguous you should only
need to run through the entire string once. As long as you keep track of what values youve seen
and whether or not any are still in the substring, and how many uniques are in the current substring,
you can find the max.

As stated above, the solution is a Dynamic Programming algorithm.

The opt for this looks like:

OPT(value, root):
    if value - (root^2) == 0 return 1
    if value - (root^2) < 0 return INF
    else return 1 + min(OPT(value - (root^2), k) for all k <= root)

We return INF if less than 0 to prevent overshoots from being counted.
Use of memoization is also helpful, having a cache which maps combinations of (value, root) to their calculated values will greatly improve our runtime.

In python, a quick mock up of this looks like

INFIN = 999999

memo = {}

def count_sqr_vals(val):
    max_root = int(pow(val, 0.5))
    return min([rec_search(val, x) for x in range(max_root, 0, -1)])

def rec_search(val, curr):
    if memo.get((val,curr)):
        return memo.get((val,curr))
    if val - (curr**2) < 0:
        memo[(val,curr)] = INFIN
        return INFIN
    if val - (curr**2) == 0:
        memo[(val,curr)] = 1
        return 1
    min_val = min([rec_search(val - (curr**2), x) for x in range(curr, 0, -1)])
    memo[(val,curr)] = 1 + min_val
    return 1 + min_val

Greedy solution would find, for the first example, a count of four:
12 = (3^2 + 1^2 + 1^2 + 1^2)

Arrays advantages:
- O(1) lookup time on any element regardless of relative position within the array
- No element in the array has any other element as a dependency, all can be edited or manipulated independently
- (In some languages) fixed size in memory, usually contiguous
- if ordered for whatever type of values are contained, lookup time goes from O(n) down to O(log n), whereas linked lists are always O(n) search

Linked Lists:
- Flexible data structure size, can grow or shrink as needed, better use of memory space
- elements in list are aware of/affected by other elements because of the linking, making this ideal for situations where you need to keep track of order/relation of elements (think stacks, queues)
- deletion of elements does not create blank gaps in the list, you can traverse the entire length and only need to be concerned about encountering a null pointer at the end

Jave implementation of sieve

public void print_pr_n(int n){
		HashSet<Integer> composites = new HashSet<Integer>(n);
		if(n >= 1) System.out.print("1, ");
		for(int i = 2; i <= n; i++){
			if(composites.contains(i)) continue;
			System.out.print(i + ", ");
			if(i <= Math.sqrt(n)+1){
				for(int j = 2; i*j <= n; j++){
					composites.add(i*j);
				}
			}
		}
	}

Here's my version of the answer. It uses two arrays, storing, for each x-coordinate, the max left and max right. For each x-coordinate, it compares the left and right max, whichever is smaller must be the shorter side of the current container, it then adjusts the sum accordingly.

public static int water_logger(int[] graph){
		int[] rmax = new int[graph.length];
		int[] lmax = new int[graph.length];
		rmax[graph.length - 1] = graph[graph.length - 1];
		lmax[0] = graph[0];
		
		int sum = 0;
		
		for(int i = graph.length - 2; i >= 0; i--){
			rmax[i] = Math.max(rmax[i+1], graph[i]);
		}
		for(int i = 1; i < graph.length; i++){
			lmax[i] = Math.max(lmax[i-1], graph[i]);
		}

		for(int i = 0; i < graph.length; i++){
			sum += (lmax[i] <= rmax[i])? lmax[i] - graph[i] : rmax[i] - graph[i];
			
		}
		return sum;
	}

It should run in O(n) (three for-loops going O(n) each, but no nested loops, no complex operations, etc)

It is able to detect multiple "bucket" regions, i.e.
{0 1 2 1 0 1 5 3 2 3 5 3 1 3 0}
sum for each is, in array form
{0 0 0 1 2 1 0 2 3 2 0 0 2 0 0}
totaled:
13

I'm going to make three time-saving assumptions:

i. Children have a parent pointer
ii. Each node can have at most 2 children
iii. a cousin will be defined here as any node in the tree which has the same distance from the root as the input node.

All three of these can be easily remedied by adding onto the following design, but I'm lazy today.

TreeNode find_cousin(TreeNode a){
   int h = 0;
   TreeNode tmp = a;
   while(tmp.parent != null){
      tmp = tmp.parent;
      h++;
   }
   TreeNode x = find_rec(tmp, h, a);
   return x;
}

TreeNode find_rec(TreeNode a, int h, TreeNode avoid){
   if(a == null || a == avoid.parent) return null;
   if(h==0)return a;
   TreeNode x = find_rec(a.right, h - 1, avoid);
   if(x == null) x = find_rec(a.left, h - 1, avoid);
   return x;
}

Why does it work? It will seek out the rightmost cousin of the given node, even if that cousin is to the left of the given node. It will avoid the input node (given as avoid) and its sibling by rejecting at the parent level. If going right doesn't work, either because it hits the avoid's parent or because it reaches a leaf node before h = 0, it will attempt to go left. If necessary, it will traverse all nodes in the tree from the input's height and upwards, but will stop the moment it finds a node that is at the same height as the input, which we can assume is the rightmost since it will always look right as far as it can from any one parent node before moving on to try the left.

Well, here's a fun way of doing it, not really any more efficient than the other methods shown here, this one uses a stack.

int[] add_arrays(int[] a, int[] b){

   Stack s = new Stack();
   int pa = a.length;
   int pb = b.length;
   int carry = 0;

   while(pa >= 0 || pb >= 0){
      if(pa < 0){
         s.push(b[pb] + carry);
         carry = 0;
         pb--;
         continue;
       }else if (pb < 0){
         s.push(a[pa] + carry);
         carry = 0;
         pa--;
         continue;
       }else {
         int x = a[pa] + b[pb] + carry;
         if(x > 9){
           carry = 1;
           x %= 10;
         }else {
           carry = 0;
         }
         s.push(x);
         pa--;
         pb--;
      }
   }

   int[] result = new int[s.length()];

   for(int i = 0; !s.isEmpty(); i++){
      result[i] = s.pop();
   }

   return result;
}

It will always take O(max(a.length,b.length)) time (so, O(n) where n is longest array's length). In no event will it have a extraneous digit on the front.

It's not a pretty or short solution, unfortunately, but it works and it is time efficient. It only works if you are adding in the following manner ( there is another version where the last digit is the highest)

{1,2,3} = 123.
{4,5,6} = 456.
{1,2,3} + {4,5,6} = 579

This isn't too bad, we can use the time-saving feature of java that the String class has, the .contains(CharSequence s) method, lovely little bugger isn't it?

We create an array of ints to track each associated strings "score", the number of other strings it contains.

then it's just a few for loops and we are done.

Let's take a look:

public String find_best(String[] strings){
   int[] scores = new int[strings.length];
   for(int i = 0; i < strings.length; i++){
      for (int j = 0; j < strings.length; j++){
          if(j == i) continue; //skip the string from counting itself
          if(strings[i].contains(strings[j])) scores[i]++;
      }
   }
   int max = 0;
   for(int i = 0; i < scores.length; i++){
      if(scores[i] > scores[max]) max = i; //a basic find-max array run through in O(n)
   }
   return strings[max];
}

This isn't the most terribly efficient process, unfortunately. String.contains is O(n), if I recall correctly. That means we have n lookups of n-1 elements, O(n^2) total, and for each of those, O(m) is the time for the contains lookup. m may or may not be greater than n, that is arbitrary, our runtime in this case, i believe, is O(m*(n^2)), which could be O(n^3) depending on the value of m. We can mitigate time by telling the loops to ignore attempts to compare strings to those of larger size (since they can't contain a string larger than themselves), but it won't do much.

Brute force answer. Anyone know a more efficient method?

Hooray OOP questions

1. What is difference between override and overload

Override: When a class inherits from another class, any method or value in the superclass that shares a name with the subclass will be overriden, meaning it will be ignored in favor of the subclass's definitions. If superclass contains a method

public int add_val(int a, int b){return a+b;}

and subclass contains a method

public int add_val(int a, int b){return a*b;}

calling subclass.add_val(5,5) will give a value of 25, whilst calling superclass.add_val(5,5) will give a value of 10.

Overloading: When any method has more than one possible set of input parameters, this is a huge part of polymorphic designs. Say I have two methods, add_val:

public void add_val(int a, int b){
   System.out.printf("%d\n", a+b);
}

public void add_val(String a, String b){
   System.out.println(a + " " + b);
}

calling

object.add_val(1,2);

prints "3"
whilst calling

object.add_val("Hello,", "World!");

prints "Hello, World!"

2. abstract. when will u use abstract

An abstract class is any class, at leastin the java definition, which contains an abstract method, such as

abstract int add_val();

Abstract methods have no implementation, they are meant to be implemented by a subclass.

Abstract classes can contain implemented methods and declared/initialized variables as well. If it only contains abstract methods, it should just be called an interface. This is good for the polymorphic usage of having a type of class you wish to have multiple other classes inherit from, all of which must have some common traits but which can (or must) define certain characteristics separately. Any subclass which doesn't implement one of the abstract methods from the superclass must also be called abstract, since it implicitly carries an abstract method through inheritance.

Say that I wanted to create a series of printers. They all have common traits,

abstract class Printer{
   int power;
   int speed;
   abstract void boot_sequence();
   abstract void call_in_warranty();
   public String print_paper(String s){
       //some code printing s onto paper
   }
}

Now, we have the requirements for something to be a printer (from an IT standpoint, warranty and whatnot). I could specify a hundred different brands of printer, each inheriting from the superclass. Since architecture is not going to be the same between all of them, they all have slightly different boot sequences, so boot_sequence() is left abstract until a subclass defines it. Anyone who has tried to call in a warranty on a printer or any hardware knows each company is different with how they handle it, somewhat. So, again, it should be defined by the company, not the printer. However, all printers must print onto paper, and while you could do it slightly different from others, it's easier to give a default behavior, then let someone override that if they want to do a different behavior (that's their own risk, see how many customers they get if their printer just eats paper and prints pictures of bananas all day)

3. what is an interface

An interface is similar to an abstract class, but all methods in it are implicitly abstract. These are not so much functional as they are useful for programmers. When we want to create something to fit into a functioning system, a new class, and want it to work in a certain area of the system just as easily as currently implemented classes, we have it inherit the interface, then implement what the interface gives us. Think of it as instructions about what must be included. Since all methods in interfaces are abstract, if you wish to use your new class, you have no choice but to implement all the methods inherited.


4. what is difference between array and link list

An array is a fixed-sized allocation of memory addresses of a specific type defined by the programmer. You can modify the values inside the array, but you cannot grow or shrink it. Good for when you know exactly how many things you will be working with (think a college class where you have 70 students and no one can drop or enroll, now you use a 70-element array to store their test score averages)

A linked list is a data structure consistent of nodes, each node points to another node, usually referred to as "next". Each node also has some data it carries. You create a list by linked one node to another, and that node to another, and that one to another, and so on, think

node 1 ---> node 2 ---> node 3 ---> node 4 ---> null

the node with a null next is the end of the list. Unlike arrays, these lists can change in size, shrinking or growing as needed. Traversing them must be done one node at a time, which means lookups are O(n), even if you know exactly which node you want to lookup, whereas in arrays, lookup time is O(1) when you know which index you want to access.

Linked lists are used for stacks, so, let's say you are doing some work on a compiler, you want it to check to make sure all scopes are resolved correctly, (for each {, there is a }, for each [, there is a ], for each (, there is a ), etc). You would create a linked list, where each time you saw an open bracket (a {,[, or ( in this case) you add a new element to the front of the list containing a char of that bracket type. Whenever you see a closing bracket, if the bracket at the front of the list is the same type, you remove it from the list. If, by the end of the program, you have an empty list, each open bracket had a closing bracket and you are good to go.

5. what is a tree

A tree is a structure in which nodes have one OR MORE next nodes (referred to as children). Where linked lists only have one next per node, trees can have as many as they want (the standard is one or two). We use these for a variety of purposes, but the most commonly seen is the Binary Search Tree, in which each node is sorted upon input to the tree such that doing an in order (reading each node left to right as it appears if they all were collapsed into a line) reads ordered numbers. This is done by adding a new value, looking at the root, and doing something like

if (new.val < curr.val){ 
  if(curr.left == null) curr.left = new;
  else traverse to curr.left and repeat from top
}
else if (new.val > curr.val){
  if(curr.right == null) curr.right = new;
  else traverse to curr.right and repeat from top
}
else, same val as current node, just ignore and continue to next input

Insert time is O(log n), lookup time is O(log n), and deletion time is O(log n), in the average case, for BST's.

6. what is a map\dictionary

A map, often referred to as a hashtable in data structures, is a array of keys with values assigned to them. A key is the index identifier, i.e. in a dictionary this would be the word, like aardvark or quotation, and the value is a adjustable associated input, in the case of a dictionary, the definition of the word.

The entries are sorted based on a hashing function before being input, so they know where to be put such that anytime you look at the map/dictionary, in ideal circumstances, you will see everything in order.

7. Explain (orally) how would you implement a dictionary via a tree

In an ugly manner, but okay. Each node in the tree has 26 possible children (we will pretend we only use alphabetical characters and case doesn't matter).

Each child's name is the alphabetical entry its index cooresponds to. 1st child = "a", 2nd = "b", etc. Each node carries a string value. When you traverse to a child, you append the character from its name onto the current string, and that becomes the child's string value.

So, traversing from a node with string "App" to child "l" gives that child node a string value of "Appl", now if you traversed from there to "e", you would havea node with "apple", a traversal to "i" would give you "appli", etc.

When we start with a empty root, we add a word as input, it will look at first character, go to that child (well, first it will initialize the child), then look at the next letter, go to that hcild, and so on.

This is roughshod and not the best design, a Trie would have worked well here.

In typical ditzy fashion I forgot to add a catcher at the start of dequeue

node dequeue (Stack s){
   if (s.isEmpty()){return null;}
...

otherwise we will get a runtime error (or maybe compiler, i mix java and c compilers up more often than i should) in the event of an empty stack being popped.

mkay let's assume the primary stack is static, i will be doing this in java.

This works in that the only difference between queue and stack is the end off of which you pop() a value. For the functions enqueue() and isEmpty(), we can simply put

void enqueue(Stack s, node curr){
	s.push(curr);
}

boolean isEmpty(Stack s){
	return s.isEmpty();
}

Easy peasy, lemon squeezy. dequeue, however, is going to have to be O(n) time because we don't have a direct pointer to the front(bottom) of the stack. The answer? We simply migrate all values over to another temporary stack, using the nature of LIFO data structures to our advantage. Then we simply pop() the top value of the temp stack, and move everything that is left back onto our original static stack, returning the popped value.

node dequeue(Stack s){
   Stack temp = new Stack();
   while(!s.isEmpty()){      //Migrate the first stack to the temp
      temp.push(s.pop());
   }
   node r = temp.pop(); //the top val of the temp stack is the bottom val of the original
   while(!temp.isEmpty()){ //once the top of temp is popped, migrate the rest back
      s.push(temp.pop());
   }
   return r; 
}

the first migration takes O(n) time, the second takes O(n - 1) time, popping is an O(1) method so we don't care about it, so totalled up and using conventions

O(n + n - 1) = O(2n - 1) = O(n)