CareerCup

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.

This 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.

Dynamic programming solution:

If I have 1,...i houses, Maximum sum that I can get is represented by recurrence relation:

OPT(i) = max(OPT(i-1), Pi + OPT(i - 2));
where Pi is amount you can get from house i.

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

For 2nd approach Quick sort has time complexity O(n log n) not O(log n). Plus iteration of array to find duplicates has worst case complexity O(n)

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.

But hashmap will take additional space requirements which can range up to n elements. Hence, space complexity will be O(n) with this approach.

There are different memory segments when program is loaded in memory. The includes data segment, code segment, etc. The code segment contains actual instructions that will be executed. So I think, in this question, Text portion is code segment.

Briefly, it means Solving the problem by splitting it in sub problems. Store results for partial solution. Use stored results for taking next decision.