## AP

BAN USERThis is a greedy strategy and won't necessarily work.

Consider following array:

10 2 3 5 7 8

According to your logic array1: 2 + 5 + 8 = 15 array2: 10 +3 + 7 = 20.

So you will select 20

Optimal solution is 23 by selecting 10 + 5 + 8 = 23, positions 0, 3, 5 no one is neighbor.

You can think of designing contact list using trie. Since, while using contact list we tend to use range queries (start typing name and all relevant names start getting displayed).

Trie will make search time logarithmic. Even while displaying entire contact list in sorted order, DFS can be used for traversal on trie.

My approach would be just convert binary numbers to integers (simple multiplication by power of 2), then add two decimals. Let k be number length binary number. So binary to decimal conversion will take O(n) time. Convert decimal answer back to binary. (log (k) time.)

This will avoid most of heavy if - else loops

I think this approach is good, but if we consider the case {1, 2, 3, 3, 1}, the negation approach will give 3 as answer as first duplicate.

The naive n^2 approach will give 1 as the answer because, in first iteration of comparison in array, it will find 1 as repeated element and break there.

I would just explain another approach that came in my mind, I haven't yet thought about the details of implementation.

1. But there can be the matrix representation to solve this problem. Where there will be one row corresponding to one entity (1 column for every name or every student) and one column for every ticketId or course.

2. Then set the corresponding bit to 1 if student have taken course (or ticket logged by name.)

3. Accessing the matrix row wise will give all tickets logged by name (or all courses taken by student)

4. Accessing the matrix column wise will give all all names who have logged by a ticket (or all students who have taken a course).

Time Complexity would be O(mn) when there are m distinct (students/names) and n distinct. (courses/tickets)

---------------------------------------------------------------------------------------------------------------

We can read data only once, create structure/class to store all attributes. Then traverse that list once to get distinct (students/names) and distinct (courses/tickets).

The tricky part could be finding out all unique (students/names) and all different (courses/tickets). Because, if we declare hash set for storing unique students and unique courses, that will be O(m+n) extra memory.

Still memory assignment will have the upper bound O(m * n) (memory required to store matrix. We can use boolen matrix to reduce memory requirement.)

Yes, I also had similar question in interview and instead of course and student, I has name and TicketID combination. I also thought about 2 HashMaps and HashSet approach. But it was not appreciated as I have to load data entire data twice. I am just wondering what else could be another data structure that would be efficient for both type of queries.

- AP May 03, 2015**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

At this point I haven't really thought about actual exact solution, but I think this problem can be reduced to Network Flow Problem or its variant and solving that problem would give the solution.

- AP May 31, 2015