Google Interview Question
Software Engineer / DevelopersCountry: Israel
Interview Type: In-Person
Can you explain your code? how does it solve the problem? what is your return value? It doesn't clear to me exactly what are you trying to achieve here.
@pavelkushtia :
Here i'm copying elements from Array {9,1,3,7,8,5,2 } into an hashtable
then while iterating over linked list, i check whether that value is in hashtable , if exists then printing the value , else simply escaping the node in linked list.
hence the output is : 1 2 3 5 7 8 9
I'm only printing the above output on screen , one can easily count these chunks!!!
Also i've mentioned an approach in which i'm modifying the structure of linked list.
as array contains pointers to the nodes , so on one iteration over that array i'm making the pointed node's previous pointer as null
and afterwards, iterating over linked list with the help of next pointer we'll print all the nodes which are having previous pointer as null and escaping those whose previous pointer is not null.
do revert if anything is not clear!!!
Here is my solution:
1) Sort the array according to the values of pointers.
2) Scan the array and when the [next element] not equals to [previos + 1] increment the result.
Time complexity O(nlogn), memory complexity O(logn) - sorting recursion stack size.
public static class Node{
public Node left;
public Node right;
public Integer value;
public Node(int v){
value = v;
}
}
private void exch(Node [] arr, int p, int q){
Node t = arr[p];
arr[p] = arr[q];
arr[q] = t;
}
private int partition(Node [] arr, int left, int right){
if(left > right) return -1;
int pivot = left;
int thresh = pivot;
for(int i = left + 1; i <= right; i++){
if(arr[pivot].value > arr[i].value)
exch(arr, ++thresh, i);
}
exch(arr, thresh, pivot);
return thresh;
}
private void quickSort(Node [] arr, int left, int right){
int pivot = partition(arr, left, right);
if(pivot < 0) return;
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
public int getResult(Node [] arr){
quickSort(arr, 0, arr.length - 1);
int result = 1;
for(int i = 0; i < arr.length - 1; i++){
if(arr[i].value + 1 != arr[i + 1].value)
result += 1;
}
return result;
}
public static void main(String [] args){
Node [] arr = new Node[7];
problem_4 d = new problem_4();
arr[0] = new Node(9);
arr[1] = new Node(1);
arr[2] = new Node(3);
arr[3] = new Node(7);
arr[4] = new Node(8);
arr[5] = new Node(5);
arr[6] = new Node(2);
System.out.println(d.getResult(arr));
}
Keep a list that contains pairs of sets.
1. set of elements that are in a sequence.
2. set of elements that should be neighbours of the elements in the sequence (their left and right pointers).
For every pointer in the pointer array, iterate through this list of ours checking if this pointer is in the set of should-be neighbours. If it is, we merge both sets.
At the end, our defined list will have one structure element for each sequence.
I know my description wasn't very good. I hope you can understand it.
m: size of pointer array
d: number of sequences of elements
Complexity: O(m*d) time
#include <vector>
#include <unordered_set>
#include <list>
class Node {
public:
Node *left;
Node *right;
};
typedef std::vector<Node*> PointerArray;
typedef std::unordered_set<Node*> NodeSet;
typedef std::pair<NodeSet, NodeSet> NodeSetPair;
typedef std::list<NodeSetPair> NPList;
int sequences(const PointerArray &A)
{
int n = A.size();
int i;
NPList l;
for (i = 0; i < n; ++i) {
Node *p = A[i];
NodeSetPair newpair;
// create sets for this new element
newpair.first.insert(p);
newpair.second.insert(p->left);
newpair.second.insert(p->right);
NPList::iterator lit, lend;
for (lit = l.begin(), lend = l.end(); lit != lend; ) {
const NodeSet &key = lit->first;
const NodeSet &neighbours = lit->second;
// merge sets
if (neighbours.count(p)) {
newpair.first.insert(key.begin(), key.end());
newpair.second.insert(neighbours.begin(), neighbours.end());
lit = l.erase(lit);
}
else {
++lit;
}
}
l.push_back(move(newpair));
}
return l.size();
}
#define MAX_ELEM 10
typedef struct node_t {
int elem;
struct node_t *left;
struct node_t *right;
}node_type;
void find_groups (node_type* root_p, node_type** node_p_arr_test) {
int group_count = 0;
int series = 0;
int i;
node_type *current_node_p, *prev_node_p;
current_node_p = root_p;
prev_node_p = root_p;
// make the 1st node left ptr point to itself (temp)
root_p->left = root_p;
i = 0;
printf("nodes passed \n");
while(node_p_arr_test[i] != NULL) {
printf("%d \t", node_p_arr_test[i]->elem);
(node_p_arr_test[i])->left = NULL;
i = i+1;
}
printf("\n");
current_node_p = root_p;
prev_node_p = root_p;
while(current_node_p != NULL) {
if(current_node_p->left == NULL) {
current_node_p->left = prev_node_p;
printf("%d \t", current_node_p->elem);
if(!series) {
series = 1;
group_count = group_count + 1;
}
} else {
if(series){
series = 0;
printf("group %d\n", group_count);
}
}
prev_node_p = current_node_p;
current_node_p = current_node_p->right;
}
root_p->left = NULL;
printf("group %d\n", group_count);
}
int main() {
int i;
node_type *new_node_p;
node_type *root_p = NULL;
node_type *prev_node_p = NULL;
node_type* node_p_arr[10];
node_type* node_p_arr_test[20];
memset(node_p_arr_test, 0, sizeof(node_p_arr_test));
for(i=0; i<MAX_ELEM; i++){
new_node_p = (node_type*) malloc(sizeof(node_type));
if(new_node_p == NULL) {
printf("malloc failed\n");
exit(0);
}
node_p_arr[i] = new_node_p;
new_node_p->elem = (i+1)*100;
new_node_p->right = NULL;
new_node_p->left = prev_node_p;
if(root_p == NULL){
root_p = new_node_p;
} else {
prev_node_p->right = new_node_p;
}
prev_node_p = new_node_p;
}
node_p_arr_test[0] = node_p_arr[9];
node_p_arr_test[1] = node_p_arr[7];
node_p_arr_test[2] = node_p_arr[8];
node_p_arr_test[3] = node_p_arr[9];
node_p_arr_test[4] = node_p_arr[5];
node_p_arr_test[5] = node_p_arr[2];
node_p_arr_test[6] = node_p_arr[3];
node_p_arr_test[7] = node_p_arr[7];
node_p_arr_test[8] = node_p_arr[4];
node_p_arr_test[9] = node_p_arr[9];
node_p_arr_test[10] = node_p_arr[2];
node_p_arr_test[11] = node_p_arr[4];
node_p_arr_test[12] = node_p_arr[3];
node_p_arr_test[13] = node_p_arr[0];
find_groups(root_p, node_p_arr_test);
return 0;
}
It seems like this can be answered much more simply than it looks. We can simply keep track of all visited nodes in a hash table. Then traverse the linked list looking for visited nodes, keeping track of connected sequences.
int CountSequences(node *head, vector<node*> nArray)
{
unordered_set<int> visited;
for (unsigned int i = 0; i < nArray.size(); i++)
{
int key = (int)nArray[i];
if (visited.find(key) == visited.end())
{
visited.insert(key);
}
}
int sequences = 0;
while (head != NULL)
{
while (visited.find((int)head) == visited.end() && head)
{
head = head->next;
}
if (!head)
break;
sequences++;
while (visited.find((int)head) != visited.end() && head)
{
head = head->next;
}
}
return sequences;
}
I could only come up a Time O(m+N), space O(m) solution, wish there is a better solution.
Go through the pointer array, store all nodes pointed into a hashset.
Go through the double-linked list, at each node, check prev and next of it, if(prev not included in set but next included), this node is the beginning of a group, so sum++.
return sum.
Similar to couple other answers, traverse array keeping track of visited nodes. Also have an integer counter initially set to 0.
When visiting a node, it is either the only element, first, last, or middle element in the list (checked by looking at node.prev and node.next).
What to do in each case:
i) Only element: counter++
ii) First element: if node.next is not visited, counter++
iii) Last element: if node.prev is not visited, counter++
iv) Middle element: if node.prev is not visited and node.next is not visited, counter++
Basically we increment the counter whenever we are starting a new sequence. Otherwise, we are just adding to an existing sequence so we don't increment.
At the end, return counter.
1) For i=0 to Array.Length:
insert Element[i] into a hash set.
2) Set counter = 0
3) For i=0 to Array.Length:
if HashSet.Contains(Element[i])
{
Increment the counter,
Remove Element[i] from the HashSet
n = Element[i].Next; while(n != null) { Remove n from HashSet; n = n.Next }
p = Element[i].Prev; while(p != null) { Remove p from HashSet; p = p.Prev }
}
Both the methods are O(n)
Method 1. by using extra space ( HashMap )
Method 2. by modifying linked list structure ie by removing the prev pointers of nodes
- Source January 29, 2015