CareerCup

Aren't you doing a bit of "hand waving" towards the end? You can't just "sort a hashmap". You'd have to move that into a sortable container. However, if you adjust your approach, you'll almost have it.

Have your hashmap store a pointer to a struct. The struct lives within a max-heap, and uses the count as its comparator. So you would do the same thing, but instead of count++, you'd do increase_key() to adjust the location in the heap.

At the end, you just need to suck everything out of the heap, and you're done.

If you use a fibonacci heap, inserts are O(1). Decrease Key is O(1). So that means that you are just O(N), where N is the sum of the number of elements that your friends have bought.

def print_char(ch, count):
	if None == ch:
		return
	sys.stdout.write("%s%i" % (ch, count))

def count_chars(string):
	if None == string or 0 == len(string):
		return
	count = 0
	curr = None
	for ch in  string.upper():
		if ch != curr:
			print_char(ch, count)
			count = 0
			curr = ch
		count += 1
	print_char(curr, count)

@Anonymous:

-1 % 5 = 4

Beauty of the modulus operator

Old array = O
New array = A
// Find the pivot offset
pivot_index = O.find(A[0])

// Find the element we are actually looking for, in the old code
index = O.find(item)

// Calculate the index in the new array
new_index = (index - pivot_index) % O.len()

/*
	O = [1 2 3 4 5]
	A = [3 4 5 1 2]

	pivot_index = O.find(A[0]) // returns index of 2

	// Look for 4
	index = O.find(4)  // returns 3
	
	new_index = (3-2) % 5
	new_index = 1
*/

The tricky part about these problems, is that the interviewer is looking for something, and that sometimes is lost when it comes to careercup. Hey may have been going towards a billion numbers, in a million files. Which leans towards a distributed application.

mem-mapping the file will be the fastest way to access it. You also will get a benefit from the multiple levels of cacheing from the OS. If you read a single number, the OS really reads at least a block of data (maybe more), because if you read one part of the data, you will most likely want the rest of it.

If K is small enough, you could just read K numbers from all 100 files into memory, as a front-end way to mitigate the burden.

Heck:

100million numbers = 400million bytes = 400Mb of memory. Based on the bounds of the application, you could read them in today, without a whole lot of pain. Once loaded, your disk latency is eliminated.

Which goes back to what I said earlier. Tricks like what I said, are easily eliminated if you go up to a billion numbers, or a trillion, or whatever. Interviews like this keep upping the ante to see what the candidate is capable of.

I just had a brilliant idea! I'm pretty sure it's O(K) in complexity.

Abstract each file out, and treat it like a stack. Call it a FileStack.

Create a min-heap, with good decrease-key performance ( O(1) ) and find-min performance ( O(1) ).

Put each FileStack on the heap. You have O(100) complexity.

# Get K numbers. find_min and decrease_key are both O(1)
for i in xrange(0, K):
	fs = heap.find_min()
	print fs
	heap.decrease_key(fs)

O(100) + O(1) + O(1) + O(K) = O(K)

Thoughts?


... and its effectively the same as OP, except that heapify() wouldn't need to be called every time.

Like kr.neerav said, a Stack would be a good fit I suppose, so long as you decide that you'll keep N items, and make sure that N doesn't grow beyond N. Specifically, when a product is accessed, you would add it to the stack, and then remove the last element to keep the size in check.

A database is really what seems appropriate. Have a last accessed time for each product, and then you can quickly query that information.

What would be bad with the stack approach, is that you'd blow it out really fast. In other words, if you are hitting this millions of times per second, you'll probably end up thrashing the mutex.

So, if you had a big enough min-heap, you could store everything in that, with a HashMap as a lookup data structure, and use the time-accessed as your heap comparison. Then just pull off the N min values when you need the information.

Lots of approaches you can talk about here, and the tradeoffs between them all. Database would utilize existing data structures and capabilities. The information would already be cached from the database or disk since they were presented to the user, so data locality is good.

@estif None of those is "fast" except union, which is O(1). The others take O(N) time.


If the numbers are coming in fast, then you can do some things to mitigate that, like put in a circular buffer, and pass it off to a separate thread. It's the typical producer-consumer pattern.

Secondly, what is interesting about this problem, is that you can do your typical tradeoff of space for speed. So, if you're getting numbers off the wire, then you have fixed set of numbers you can support, namely 2^32.

So, create two 2^32 bit arrays (only 536Mb each), labeled A & B. Number comes in, it's O(1) to flag the correct bit. Accessing the correct bit is simple arithmetic.
Union is A | B on all the bits.
Intersection is A & B.
A-B is A^ (A & B)
B-A is B^ (A & B)
All these operations will be fast-as-hell bit operations, and they're all O(1), since the array sizes are fixed.

You'd need to profile this for the actual performance gains, because the approach is a bit silly.



Otherwise, you could perform your various set constructions on the fly, as numbers are coming in.

The words "real time" are imprecise. What are the requirements? Is it 10ms? 20ms? 5ms?

Valgrind can help on smaller programs. Not always feasible on large programs. You can overload malloc() and new() to get when memory is created, and delete()/free() for when memory is deallocated.

Log the data, and correlate it to your application logs (you do have those, right?) to verify when stuff is happening. Match them up to make sure what's going on.

Is your program threaded? Try and disable threading. Did it just appear? Look at recent code additions. Isolate the "bad code" as much as you can, to reduce what you are looking at.

Also useful, is running it using strace, which will also give you system calls you can dive into to check out what is happening. It can be a very tedious thing to do, but these are the basic approaches to do so.

Pure data structure approach: Fibonacci heap

Find min is very cheap, and each subtree could be loaded separately as a file.

Otherwise, I don't know if a data structure is needed.

You have 100 sorted files, so you can open each one in time, as a speedup, you could read the first N/100 lines if it's small enough to minimize disk access. Then go through each file and do a merge.

Many approaches with different tradeoffs. What I think they are looking for at the 100 million level, is the tradeoffs of each tactic. Lots of wrong answers and no stand out right one.

Is a database forbidden? That's the "right" approach. If you couldn't use a database server, then SQLite (ha ha ha). Ok, pure data structures then:

You'd need a series of data structures.

1.) hash table/map of primary-key to data (name, phone number, address perhaps).
2.) Associative containers for each one of the attributes that youd want to search on.
2.1) Suffix array to support searching. Value would be lists of associated keys of data. (Joh would link to all Johns, Johnathan, Johnny, etc)
2.2) You could stick the phone numbers, and addresses, and all data in here as well, to support the searching functionality.

Right idea, but you'd do better with a heuristic than a simple BFS. See my comment below.

To add on to this:

Construct a graph of all the words, with edges between words that can be transformed from one to the other.

Locate the start node, and use a heuristic to determine the next best node. If all nodes have the same score, do a breadth-first traversal to examine the neighbors, use the heuristic, rinse, repeat.

The simplest heuristic would be to examine how many letters are in the correct location for the final word; for instance:

cat -> dog
rat has a score of "0", because no letters are shared with dog
cot has a score of "1", because the "o" is in the right location, when compared to dog

cog has a score of "2", because both the "o" and "g" are correctly placed

Finally, "dog" is the end word.

You can use this in an A* path traversal, to traverse the graph. Faster and "better" than a simple breadth-first search

make sure to check your inputs too. Thats a big part of what they are checking you for (null pointers, string lengths, etc...)

Otherwise, well done

Had to go back to my algorithms book. This isn't a popular problem, but it's the Clique problem (en.wikipedia.org/wiki/Clique_problem)

It's relatively well-studied, and graphs are the data structure to use. Specifically, I'm pretty sure that this is the maximum clique problem.

So, once you have your graph constructed, you would want to look at the set of nodes, that are all interconnected with each other, that have the highest degree.

I'm not going to describe a solution, since it's well studied. You'd be better off reading about it at the Wiki page (and other places), and understanding the problem, than looking at code here.


Kind of a bogus question, IMHO, since the "answer" is considered to be a (nontrivial tenet of computer science. I think the interviewer was probably looking for your knowledge of the problem space, identification of the Computer Science problem, choosing the right data structure, and then starting to work out the problem.

This is a NP-Hard problem, so some big brains have worked on this.

If I'm understanding the problem correctly, we need to take all the values in the interval, put them in order, and maintain the duplicates. Then we get the Nth element.


Naive, destructive approach in a mix of pseudo Python and C++:

def get_nth_value(intervals, N):

    # Put all the elements into a multiset
    all_values = multiset()
    for interval in intervals:
        for element in interval:
            all_values.add(element)

    # Pop off the items from the front, in sorted order
    ret = None
    for i in xrange(0, N):
        ret = all_values.front()
        all_values.remove(0)

    return ret

Constructive criticism:

I think this is the wrong approach for an interview (and maybe even for "real" software development). Why? It fails the "cocktail napkin test". In other words, I should be able to explain, or sketch out a solution simply enough to fit on a cocktail napkin.

Unless it is a nontrivial problem (which this is a trivial problem), then you should be able to explain it simply, elegantly, and fit it into no more than ~20 lines of code.

Interviewers are not typically looking for the "best possible solution". Neither is production work. The mark of good code, is that it simple enough for the person to come behind you in 6 months, and understand within a few minutes, what the heck you did.

Frankly, I didn't even read that wall of text, because I went right to the code. Then I started reading your code, and gave up. It's just too much.

There is a sample of doing this with integers, and you xor all the values together, and it spits out the one unique value. If you could encode these to big integers, xor them all, and then reverse the encoding, the same concept would apply.

You could do this with a hashing function (say, CRC or MD5 for simplicity), but you'd need to maintain a table of hash->value. You'd have O(N) storage, and O(N) for processing (keeping elements in a hashtable)

Pseudocode:

sum = bigint()
map = hashmap()
for element in list:
	h = hash(element)
	map[h] = element
	sum ^= h

print map[sum]

My first instinct is that it has similarities with string matching algorithms, specifically Rabin-Karp, which uses hashes to compare strings. So, if you start with that as a base concept, you can then perform rounds of matching, throwing away your data structures as necessary. This keeps your memory bounded for very large strings as well.

I neglected the hash() below, by just storing the string itself. But you can save the total amount of memory that you're using at any given time by cleaning up your data structure after each round.

Worst case, you've got a decreasing amount of memory usage at any given time. I have a hard time characterizing it, but it's a recurrence [ O(2*(N-1)) + O(3*(N-2)) ... ] that ends with O(N). I think that's what it all boils down to.

Processing time is O(N^2) for the nested loops. Lines of code could be reduced, but I left it this way for clarity.

Python:

def findLongestRepeat(str):
    s = set()

    # Loop from N-1 chars to 0
    for i in xrange(len(str)-1, 0, -1):
        print(len(s))

        # Clear our data structure since it's no longer needed
        s.clear()

        # Initial conditions
        start = 0
        stop = start+i

        # Until the end index isn't beyond our string
        while stop != len(str)+1:

            # Get a substring
            substr = str[start:stop]
            if substr in s:
                print substr
                return
            else:
                s.add(substr)

            stop += 1
            start += 1

I misspoke. I mean, count1 and count2. Count1 == <most frequent item>; Count2 == <2nd most frequent>.

Not a fan of this concept, because it's not easily extensible. What if I want the 5th most frequent item. The 25th most frequent item. The 32124th most frequent item (assume Unicode). This is what I mean by saying it falls apart.

Although, I'm not a fan of keeping a count. It would be trivial to say, I want the Nth biggest item, and the count is where your solution falls apart.

This *feels* like a valid solution. Assuming that the inputs are characters, you only have 26 possible array indices. However, it's not terribly extensible. Imagine changing it from english -> unicode. You could do it, but you need to understand the performance/space payoff. Regardless, a Hash Table would be a better overall data structure for extensibility in all cases.

@Jay Fibonacci Heap is O(1) insert

From "The Algorithm Design Manual":

Stop and Think: Nuts and Bolts
Problem: The nuts and bolts problem is defined as follows. You are given a collection of n bolts of different widths, and n corresponding nuts. You can test whether a given nut and bolt fit together, from which you learn whether the nut is too large, too small, or an exact match for the bolt. The differences in size between pairs of nuts or bolts are too small to see by eye, so you cannot compare the sizes of two nuts or two bolts directly. You are to match each bolt to each nut.
Give an O(n2) algorithm to solve the nuts and bolts problem. Then give a randomized O(n log n) expected time algorithm for the same problem.

Solution: The brute force algorithm for matching nuts and bolts starts with the first bolt and compares it to each nut until we find a match. In the worst case, this will require n comparisons. Repeating this for each successive bolt on all remaining nuts yields a quadratic-comparison algorithm.

What if we pick a random bolt and try it? On average, we would expect to get about halfway through the set of nuts before we found the match, so this randomized algorithm would do half the work as the worst case. That counts as some kind of improvement, although not an asymptotic one.

Randomized quicksort achieves the desired expected-case running time, so a natural idea is to emulate it on the nuts and bolts problem. Indeed, sorting both the nuts and bolts by size would yield a matching, since the ith largest nut must match the ith largest bolt.

The fundamental step in quicksort is partitioning elements around a pivot. Can we partition nuts and bolts around a randomly selected bolt b? Certainly we can partition the nuts into those of size less than b and greater than b. But decomposing the problem into two halves requires partitioning the bolts as well, and we cannot compare bolt against bolt. But once we find the matching nut to b we can use it to partition the bolts accordingly. In 2n − 2 comparisons, we partition the nuts and bolts, and the remaining analysis follows directly from randomized quicksort.
What is interesting about this problem is that no simple deterministic algorithm for nut and bolt sorting is known. It illustrates how randomization makes the bad case go away, leaving behind a simple and beautiful algorithm.


First, naive cut.

1.) Iterate through the string.
2.) Look up each character in a hash table. This map stores a reference to an item in a max-heap
3.) Use that reference to increase the reference count in the max-heap
4.) That max-heap stores a count, and the letter that it counts
5.) When done processing, take the max of the heap twice.

O(n) to go through the input array
O(log n) for the heap maintenance

struct heap_struct{
	int count;
	char c;	

	heap_struct(const int& COUNT, const char& C) : count(COUNT), c(C){}
	bool operator<(const set_struct& rhs){
		return count < rhs.count;
	}
};

typedef heap<set_struct> heap_t;
heap_t count_heap;

typedef hash_table<char, set_t::iterator> hash_t;
hash_t char_hash;

int count_letters(const std::string& input, const int& rank){
	// check our inputs
	if(0 == input.size()){
		return -1;
	}
	if(0 >= rank){
		return -1;
	}

	// Iterate throught the characters
	for(unsigned int i = 0; i < input.size(); ++i){
		char c = input[i];

		hash_t::iterator hash_iter = char_hash.find(c);

		// Insert the item
		if(char_hash.end() == hash_iter){
			heap_t::iterator heap_iter = 
				count_heap.insert(heap_struct(0, c));
			hash_iter = char_hash.insert(std::pair(c, heap_iter));
		}

		// Increment the count
		hash_iter.second->count++;
	}

	// Return the Nth item
	int ret = -1;
	for(int i = 0; i < rank; i++){
		ret = heap.max();
	}

	return ret;
}

details?

what about the sequence:

push(10);	// count = 1, maxCount = 1;
pop(10);	// maxCount = 0;
push(10); // count = 2, maxCount = 2;
pop(10); // maxCount = 0
push(10); // count = 3, maxCount = 3;
pushd(5); // count = 1, maxCount = 3;
pop(10); // maxCount = 2

The maxCount = maxCount-1 line will cause you to lose items... Once the top item is removed, you cannot guarantee to get any of the other items in the stack.

This isn't a "real" stack, since there is no FIFO. More of a priority queue with a twist.

template <typename T>
class frequency_stack{
private:
	struct pq_struct{
		int key;
		T value;
		pq_struct(const int& k, const T& v) : key(k), value(v){}
		bool operator<(const pq_struct& rhs) const {return key < rhs.key;}
	}
public:
	// Push an item - log(n)
	void push(const T& val){
		unordered_map<T, int>::iterator iter = count_table.find(T);
		if(count_table.end() == iter){
			iter = count_table.insert(val, 0);
		}
		p_queue.push(pq_struct(*iter, val));
        ++(*iter);  // Increment our count
	}

	// remove the top item -  log(n)
	T pop(){
		return p_queue.pop().value;
	}

	// Wipe out the history
	void obliterate(const T& val){
		count_table.erase(val);
	}

private:
	unordered_map<T, int> count_table;
	priority_queue<pq_struct<T> > p_queue;
};

It works, but best case would be o(log n). It's arguable whether a node -> node traversal would be better, because the ceil is most likely collocated nearby the original value. Of course the supposes that we already have the node we are looking for, not just its value.

If it's a binary search tree, then by "ceil" and the example given, i assume that you are looking for the element which immediately succeeds the given value. i.e.: 13 => 15

You have to handle two cases:

1.) The successor is your right child
2.) The successor is your ancestor

This assumes that we already have a pointer to the target node we are trying to get the ceil of. It's just a way to do an inorder traversal given a start-node, and not a traversal of the entire tree.

int ceil(const node* n){
    // Handle our right child
    node* curr = n;
    if(curr->right){
        while(curr->right){
            curr = curr->right
        }
        return curr;
    }

    // Get our ancestor.  We go up until we are no longer a left child
    while(curr->parent && curr->parent->left != curr){
        curr = curr->parent;
    }
    return curr;	// Would return NULL if it's invalid
}

@Anonymous: I'm curious on the DP and hash method.

Hash table, you need to store them, which would be O(n) * O(1) for the inserts, but you need to traverse the results.

DP has more promise, but I'm trying to come up with a good example. Since the order of the inputs doesn't matter (like strictly increasing subsequence), then you're still going to have to deal with *some* data structure to store the linkage information.

However, my DP background is weak, so I'm eager to learn.

Questions you ought to ask for clarification:

1.) Is the array sorted?
2.) Does the array order need to be maintained?


A.) If it's sorted, you can do it in O(n) with no additional data structures.

B.) If the order does not need to be maintained, then I would argue to sort the array O(n log n), space O(n), and then perform the O(n) search. However both these techniques would require you to delete from an array, which is O(n).

C.) If order doesn't matter, then the "simplest" thing to do would be to add them to a tree that doesn't allow repeats (like a set), insertion O(log n), and then traverse the tree to write out the results into the existing array. Space complexity goes up to O(n), but you stay at O(log n) + O(n)

Right, but it's not bitmasking. It's using bit manipulations. Bitmasking would be like:

C1 = (A & 0x000000FF + B & 0x000000FF) >> 1

where the 0x000000FF is the mask to manipulate the individual bits. My technique doesn't do the "obvious" (traditional) method of it. It takes advantage of the fact that when you bitshift a value, it pads the values with 0's. This is performing the same task (allowing you to only work on the bits you care about)

My "bitwise" trick is inefficient, but if you bitshift left, then bitshift right+1 bit for each byte in A & B, then add them, then shift back to final location. Repeat for all bytes.

Pseudo-code:

int C = 
     (A << 24) >> 25 + (B << 24) >> 25 |
    ((A << 16) >> 25 + (B << 16) >> 25) << 8 |
    ((A << 8)  >> 25 + (B << 8) >> 25) << 16 |
    ((A >> 25) + (B >> 25)) << 24;

That's not a bad thing. there are multiple search strings that will return the result. Use a pointer/reference to keep storage space down. Making each item searchable makes it an O(n) lookup vs an O(log n) lookup.