## eugene.yarovoi

BAN USERMake a graph where each vertex is a position in the array (0 to N-1). Let an edge connect two vertices whenever swapping the elements at those two positions is allowed. You need to get all the connected components of this graph, and then for each connected component, sort the elements available within that connected component so that the smallest positions have the lowest possible elements (smallest index within the connected component gets smallest element, second smallest index gets second smallest element, etc.). When this is done for all connected components, you will have the lowest possible permutation. This algorithm is about as efficient asymptotically as the sorting algorithm you use. Since all steps except sorting are O(N), it's asymptotically optimal.

- eugene.yarovoi July 20, 2012Doubtful. Basically you want to find pairs satisfying K + bi = a where i is some integer. So bi = a - K. This amounts to asking to find all b that are factors of a - K.

Is there a way to build a data structure that retrieves all the elements it contains that are factors of a particular number in time proportional to the number of factors retrieved? I don't know for sure, though it seems difficult.

It seems reasonable to think that the chessboard has a fixed orientation and that configurations that are rotated versions of other configurations are nonetheless considered distinct, and orientation does matter in chess, so you're probably the only one that interpreted the problem this way. Still, that's a good case to think about & clarify with the interviewer.

- eugene.yarovoi July 20, 2012C(n, k) = n! / ( k! * (n-k)! )

- eugene.yarovoi July 19, 2012There's really no guarantee the answer fits into an int, even.

- eugene.yarovoi July 19, 2012True enough, but you could place m*n in a long if you wanted to be careful about that. Or use Python.

- eugene.yarovoi July 19, 2012Yep, that's the way I would go too.

- eugene.yarovoi July 19, 2012If you want no extra space and can't destroy the input, you'll have to use the naive quadratic time algorithm.

The two approaches discussed don't use extra space but do destroy the input.

I think the solution for specific ranges and the sorting solution pretty much cover it.

- eugene.yarovoi July 18, 2012"2. Traverse the array and for each a[i] change sign of a[[a[i]- min]]"

Again, same assumption.

"Each time a element is found sign of location corresponding to that (mapped to a[i]-min) changes sign"

Why is a[i]-min necessarily in bounds? It's not, unless all a[i] are in the range [min, min + arr.length - 1]

@words&lyrics: You didn't specify the assumptions correctly. Your approach assumes that all elements are between [min, min + arr.length - 1]. How is that justified?

- eugene.yarovoi July 18, 2012This assumes that all elements are between [min, min + arr.length]. This is blatantly false for most inputs.

- eugene.yarovoi July 18, 2012@words&lyrics: your approach makes some assumptions that are probably not acceptable

- eugene.yarovoi July 18, 2012It's of course not possible to do this in less than O(n). Consider the character the string starts with. If it is not found anywhere else, it's the answer. But there can be no way to know whether it is found anywhere else or not until you inspect every other character.

@Manan: why is this question necessarily fake? Interviewers ask stupid things every now and then.

No, we should maintain them in a heap for greater efficiency. Although an array will do for really small k (like k=5 or something)

- eugene.yarovoi July 18, 2012You can't use the extra space even if it's on disk? Well, basically, using Quickselect requires you to destroy the input. So if you can use extra space, you copy the input and destroy the copy. If you can't, you have to destroy the original to use Quickselect.

If you can do neither, it's sort of hard to solve this if k can be large. If k=10 or a small number, just keep a heap of the largest or smallest elements seen so far. By small number, I just mean that the heap should fit into memory.

If you want your code to work well for large values of k, Quickselect is a good choice. Well, that depends, actually. Is it OK to either destroy the original input or use 4gb of extra space, on disk?

- eugene.yarovoi July 18, 2012How large is k? If k could be something like the number of integers / 2, an array might not fit into memory.

You could try the Quickselect algorithm. Just search for it. To implement it on disk, you'll just bring the input into memory one piece at a time.

inserting into a stack uses extra space. The constraint here is to not use extra space.

- eugene.yarovoi July 18, 2012Seems like what you really want is a course on OO design patterns. Try MIT OpenCourseware.

I've always found the online C++ FAQ by Marshall Cline to have some really well-phrased explanations of Oo concepts. ,;

@Nishant Kumar: That's not a correct complexity analysis. It's still O(mlogN).

- eugene.yarovoi July 17, 2012It is about a well-known theorem in graph theory. The theorem is that graph coloring is NP-complete. That doesn't mean it's impossible. It just means, in very rough and oversimplified terms, that no exact algorithms for solving this problem are known that are substantially more efficient than brute-force search. That doesn't even mean such algorithms don't exist, only that none are known right now.

- eugene.yarovoi July 17, 2012This is correct. Unfortunately coloring is NP-complete. This problem is too, because every coloring problem can be reduced to an instance of this problem.

- eugene.yarovoi July 17, 2012It doesn't look like O(n) was required when I look at the constraints. Just something slightly better than O(n^2).

- eugene.yarovoi July 17, 2012I don't know if this would meet the requirements of this problem or not. An n^2 solution is likely to time out given the constraints. You have, however, really done some good preprocessing to make sure that the n^2 step has a really small constant factor. Maybe this solution would scrape by.

- eugene.yarovoi July 17, 2012This approach is completely invalid. Suppose I have 3 people, and 1 dislikes 3. The inversion of that graph is still 1 connected component. This problem is the same as graph coloring, which is NP-complete.

- eugene.yarovoi July 17, 2012As much as this answer looks silly, it may well be true in some cases. Writing x*7 may be the fastest way to multiply by 7 because the compiler will often optimize it to the fastest way for the particular machine.

- eugene.yarovoi July 17, 2012It should.

- eugene.yarovoi July 17, 2012I would argue that a developer should think both constructively and destructively; after all, that's how you build software while being good at avoiding bugs in the first place.

- eugene.yarovoi July 17, 2012You're not checking for whether you're going down a path you've already colored.

- eugene.yarovoi July 17, 2012There seems to be some confusion here. The 4-color theorem is about coloring of contiguous regions on a planar map and is not about coloring a vertex graph with arbitrary edges.

Graph coloring is not unsolvable, but NP-complete. However, it seems that this question is asking for a coloring *given* that the graph can be colored with only 2 colors. That is not NP-complete, and can be done with a simple BFS.

My favorite way to answer this question is to present an empty Python file.

- eugene.yarovoi July 17, 2012No. You should not double-count. The answer is (64 C 8)*(56 C 8), which is the same as (64 C 16)*(16 C 8) [select 16 spaces first, and then select which will be black and which will be white].

You should not multiply by 2 just because you can pick white first or you can pick black first. The order in which you pick doesn't affect what ends up being on the board.

Use a doubly-linked list in combination with a HashMap. The HashMap should provide value lookup by key for your cache, in O(1) time. The HashMap should also contain a pointer to the corresponding node in the doubly-linked list so that when a key is accessed, the corresponding node in the linked list can be deleted from its current position and moved to the tail, which is the position for the most recently seen node. If you see a new element you haven't seen before (that is not in your HashMap), you add it to both the HashMap and the tail of the linked list. The linked list allows you to see which element expires next in O(1) time, and if the list exceeds the number of elements you want to cache, you delete the next-expiring element from both the linked list and the HashMap.

All operations are in O(1) time (expected time, in the case of the HashMap).

If you need determinism, you can use a balanced tree sorted by key instead of the HashMap; this will be O(logN) for lookup, insert, and delete.

You're basically iterating over all nodes for each edge. That's quadratic complexity instead of the linear complexity achieved by another solution here.

- eugene.yarovoi July 17, 2012I don't understand the question.

- eugene.yarovoi July 16, 2012The best answer to this question depends on the likely use cases. Is it likely that delims will be a long string? Is efficiency important? If the answer to both questions is yes, we might want to go with a complicated approach like a rolling hash. If the answer to either is no, we can just take a very simple approach where we just search for the search string starting with each character.

We should also clarify what happens if the delimiter overlaps with itself. For example, what if the delimiter is "aba" and we pass in the string "cababac"? Is the answer (c, c) or (c, bac) or something else?

Even more concise:

```
for (int i=0, j = 0 ;j <= strlen(input); ++j){
if(input[j] != ' ')
input[i++] = input[j];
}
```

Since the null terminator is also not equal to space, no need to have a special case for it.

- eugene.yarovoi July 16, 2012No it's not fine according to the question. Extra space is extra space, whether it's declared implicitly or explicitly.

- eugene.yarovoi July 16, 2012This is the right approach. The list will be modified, but will be returned to its original state before the function returns. This is a good way to do it if you want to avoid using extra space and do it in O(N) deterministic (not expected, like with a hash) time.

- eugene.yarovoi July 16, 2012That's the way to do it.

I would add 4) Reverse the nodes before the middle node again to repair the original input.

You also need to be careful how you treat the middle node if there's an odd vs. if there's an even number of nodes.

@Vick: it's not possible to do this with only one pass. How would you do it? If you put entries into a stack and then use that, you are 1) using extra space; and 2) still making a second pass, through the stack instead of the linked list in this case.

Using recursion is considered using extra space. No, the proper approach to do this is to find the middle node, reverse the linked list in place from the middle to the end, and traverse from the beginning and the end simultaneously, comparing characters that occur. Then you repair the original input by again reversing from the middle node to the end.

- eugene.yarovoi July 16, 2012You would need to use *c on the left side of the assignment, then

- eugene.yarovoi July 16, 2012Structs are passed by value. There is no problem here.

- eugene.yarovoi July 16, 2012And make the destructor protected so that the object can't be allocated in stack...couldn't a subclass still allocate the base class object on the stack?

- eugene.yarovoi July 15, 2012Code above is working fine.

- eugene.yarovoi July 15, 2012That's not what I meant. I meant that, provided you manage to visit the same cells, the order in which you visit doesn't matter. But yes, the order may affect which cells you are ultimately able to visit.

I'm saying that the fact that we only have to track which combinations of cells can be visited and that we don't have to track all the ways in which identical combinations can be visited may reduce complexity.

Yeah, sounds like a simple backtracking solution is likely to time out. I'm guessing you need to exploit the fact that the order in which items are visited doesn't matter.

- eugene.yarovoi July 14, 2012

Rep**Gayle L McDowell**, CEO at CareerCupGayle Laakmann McDowell is the founder / CEO of CareerCup, which provides programming interview prep for candidates interviewing with Microsoft, Google ...

Rep**Loler**, Employee at Google

Rep

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

You could return a long. Nothing in the problem statement says you can't.

- eugene.yarovoi July 20, 2012