# Virtual Array - Google Top Interview Questions

### Problem Statement :

Implement a virtual array which implements the following methods:

void set(int start, int end) which sets the values in the array from [start, end] inclusive to true.

boolean get(int idx) which returns true if it is set, otherwise false.

Bonus: solve using \mathcal{O}(k)O(k) space total where k is the number of disjoint intervals.

Constraints

0 ≤ start ≤ end < 2 ** 31

0 ≤ n ≤ 100,000 where n is the number of calls to set and get

Example 1

Input

methods = ["constructor", "set", "get", "set", "get", "get"]

arguments = [[], [2, 5], , [8, 9], , ]

Output

[None, None, True, None, False, True]

Explanation

va = VirtualArray()

va.set(2, 5)

va.get(4) == True

va.set(8, 9)

va.get(6) == False

va.get(8) == False

Example 2

Input

methods = ["constructor", "set", "set", "get"]

arguments = [[], [10, 100], [6, 100], ]

Output

[None, None, None, True]

Explanation

va = VirtualArray()
va.set(10, 100)

va.set(6, 100)

va.get(9) == True

### Solution :

                        Solution in C++ :

class VirtualArray {
const long long A = 1LL << 32;
unordered_map<long long, int> a;

public:
VirtualArray() {
}

void upd(long long x, int d) {
++x;
while (x < A) a[x] += d, x += x & -x;
}

int qry(long long x) {
++x;
int y = 0;
while (x > 0) y += a[x], x -= x & -x;
return y;
}

void set(int start, int end) {
upd(start, 1);
upd(end + 1, -1);
}

bool get(int idx) {
return qry(idx) > 0;
}
};


                        Solution in Java :

import java.util.*;

class VirtualArray {
private final TreeMap<Integer, Integer> truth = new TreeMap<>();

public void set(int start, int end) {
Map.Entry<Integer, Integer> entry = truth.floorEntry(start);
{
if (entry != null && entry.getValue().intValue() >= start) {
truth.remove(entry.getKey());
start = Math.min(start, entry.getKey());
end = Math.max(end, entry.getValue());
}
}
{
while (true) {
entry = truth.ceilingEntry(start);
if (entry == null || entry.getKey().intValue() > end)
break;
truth.remove(entry.getKey());
end = Math.max(end, entry.getValue());
}
}
truth.put(start, end);
}

public boolean get(int idx) {
Map.Entry<Integer, Integer> entry = truth.floorEntry(idx);
return (entry != null && entry.getValue() >= idx);
}
}


                        Solution in Python :

class VirtualArray:
__slots__ = "start", "end", "mid", "_left", "_right", "state"

def __init__(self, start=0, end=2 ** 31):
self.start = start
self.end = end
self.mid = start + end >> 1
self._left = self._right = None
self.state = 0

@property
def left(self):
if not self._left:
self._left = VirtualArray(self.start, self.mid)
return self._left

@property
def right(self):
if not self._right:
self._right = VirtualArray(self.mid + 1, self.end)
return self._right

def set(self, s, e):
if s <= self.start and self.end <= e:
self.state = 1
elif e <= self.mid:
self.left.set(s, e)
elif s > self.mid:
self.right.set(s, e)
else:
self.left.set(s, e)
self.right.set(s, e)

def get(self, index):
if self.state == 1:
return True
elif self._left is self._right is None:
return False
elif index <= self.mid:
return self.left.get(index)
else:
return self.right.get(index)


## Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

## Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing

Given the pointer to the head node of a linked list, change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty. Example: head references the list 1->2->3->Null. Manipulate the next pointers of each node in place and return head, now referencing the head of the list 3->2->1->Null. Function Descriptio