Google Interview Question for Software Engineer in Tests


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
0
of 0 vote
Simply reverse the pointers {{{ public Node reverse(Node head){ Node current=head; Node prev=null, next=null; while(current!=null){ next=current.next; current.next=prev; prev=current; current=next; } return prev; } - Anwar July 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

As node structure is given so it is either a singly linked list or circular linked list. For simplicity let's assume it is singly linked list. So my idea here is to traverse through the linked list and maintain 2 pointers one indicating start of word (say i) and other indicating end of word (j), I will also use string s which contains character from node i to node j and whenever I encounter the space, I would replace reverse of string to the node i through j.
I think by looking at code, you will get more understanding

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
    
    static class Node {
        char val;
        Node next;
        
        Node(char ch){
            this.val = ch;
            next = null;
        }
    }
    
    static Node reverse (Node head) {
        Node i=head,j=head;
        Node temp = head;
        String s = "";
        while(temp!=null){
            if(temp.val==' '||temp.next==null) {
                
                if(temp.val!=' ')
                    s = s+temp.val;
                
                int z = s.length()-1;
                while(z!=-1){
                    i.val = s.charAt(z--);
                    i = i.next;
                }
                s= "";
                i = temp.next;
                j = temp.next;
            }
            else{
                s += temp.val;
                j = j.next;
            }
                
            temp = temp.next;
        }
        
        return head;    
    }
    
	public static void main (String[] args) {
	    
	    Node temp = null;
	    
	    Node head = new Node('H');
	    head.next = new Node('e');
	    head.next.next = new Node(' ');
	    head.next.next.next = new Node('W');
	    head.next.next.next.next = new Node('o');
	    
	    System.out.println("INPUT:");
	    temp = head;
            while(temp!=null) {
            	System.out.print(temp.val);
           	temp = temp.next;
            }
	    System.out.println();
	    
	    head = reverse(head);
	    
	    
	    System.out.println("OUTPUT:");
	    temp = head;
            while(temp!=null) {
                System.out.print(temp.val);
                temp = temp.next;
            }
	}
}

Space Complexity: At any point in time max length of string s would be size of longest word in given input, so space would be O(|No. of characters in longest word|)

Time Complexity: if there are M words and size of each word is N then time complexity is O(MN)

- sagartiwari230 July 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

First you need to create an empty linked list for output. Remove one by one character from start of input linked list till the input linked list is not empty and add character in the stack. While adding a character in the stack if character is space character, then remove one by one character from the stack and add the character in the output linked list. Once the input linked list is empty and then remove all characters from the stack and add in the output linked list.

public static LinkedList<Character> reverseLinkedList(LinkedList<Character> input) {
        LinkedList<Character> result = new LinkedList<>();
        Stack<Character> stack = new Stack<>();
        while(!input.isEmpty()) {
            Character c = input.removeFirst();
            if (c  != ' ') {
                stack.add(c);
            } else {
                while (!stack.isEmpty()) {
                    result.add(stack.pop());
                }
                result.add(' ');
            }
        }
        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }
        return result;
    }

- Ravi July 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Public node reverseWord(Node node){
	Stack<Character> stack = new Stack<>();
	Node fsn =node;
	Node result = node;

	while(node != null){
		Char c = node.val;

		if(c==’ ‘){
			while(!stack.isEmpty()){
                                        fsn.val = stack.pop();
     fsn = fsn.next;
}
			fsn = node.next;
		}else{
stack.push(c);
		}
		node = node.next;
	}
	return result;
}

- Anonymous July 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Public node reverseWord(Node node){
	Stack<Character> stack = new Stack<>();
	Node fsn =node;
	Node result = node;

	while(node != null){
		Char c = node.val;

		if(c==’ ‘){
			while(!stack.isEmpty()){
                                        fsn.val = stack.pop();
     fsn = fsn.next;
}
			fsn = node.next;
		}else{
stack.push(c);
		}
		node = node.next;
	}
	return result;
}

- DD July 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static Node reverseWords(Node root) {
		Node dummy = new Node('0');
		Node curr = root, temp = null, spaceCharDummy = null;
		dummy.next = curr;
		while (curr != null && curr.next != null) {
			while (curr.value == ' ') {
				//if there are multiple spaces, make the final space marks the sublist header of the new word
				spaceCharDummy = curr;
				temp = spaceCharDummy;
				curr = spaceCharDummy.next;
			}
			if (curr == null) {
				//No more words can be found.
				break;
			}
			temp = curr.next;
			if (temp.value != ' ') {
				curr.next = temp.next;
				temp.next = spaceCharDummy == null ? dummy.next : spaceCharDummy.next;
				if (spaceCharDummy != null) {
					spaceCharDummy.next = temp;
				} else {
					dummy.next = temp;
				}
			} else {
				spaceCharDummy = temp;
				curr = spaceCharDummy.next;
			}
		}
		return dummy.next;
	}

- Ahmed.Ebaid August 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static Node reverseWords(Node root) {
		Node dummy = new Node('0');
		Node curr = root, temp = null, spaceCharDummy = null;
		dummy.next = curr;
		while (curr != null && curr.next != null) {
			while (curr.value == ' ') {
				//if there are multiple spaces, make the final space marks the sublist header of the new word
				spaceCharDummy = curr;
				temp = spaceCharDummy;
				curr = spaceCharDummy.next;
			}
			if (curr == null) {
				//No more words can be found.
				break;
			}
			temp = curr.next;
			if (temp.value != ' ') {
				curr.next = temp.next;
				temp.next = spaceCharDummy == null ? dummy.next : spaceCharDummy.next;
				if (spaceCharDummy != null) {
					spaceCharDummy.next = temp;
				} else {
					dummy.next = temp;
				}
			} else {
				spaceCharDummy = temp;
				curr = spaceCharDummy.next;
			}
		}
		return dummy.next;

}

- Ahmed.Ebaid August 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static Node reverseWords(Node root) {
		Node dummy = new Node('0');
		Node curr = root, temp = null, spaceCharDummy = null;
		dummy.next = curr;
		while (curr != null && curr.next != null) {
			while (curr.value == ' ') {
				//if there are multiple spaces, make the final space marks the sublist header of the new word
				spaceCharDummy = curr;
				temp = spaceCharDummy;
				curr = spaceCharDummy.next;
			}
			if (curr == null) {
				//No more words can be found.
				break;
			}
			temp = curr.next;
			if (temp.value != ' ') {
				curr.next = temp.next;
				temp.next = spaceCharDummy == null ? dummy.next : spaceCharDummy.next;
				if (spaceCharDummy != null) {
					spaceCharDummy.next = temp;
				} else {
					dummy.next = temp;
				}
			} else {
				spaceCharDummy = temp;
				curr = spaceCharDummy.next;
			}
		}
		return dummy.next;

}

- Ahmed.Ebaid August 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) time and O(1) space.

#include <iostream>

using namespace std;

class Node
{
    public:
        Node(char val) : val_(val), next_(NULL) {}
        char val_;
        Node* next_;
};

Node* GetWord(Node* head, Node* &h, Node* &t)
{
    h = t = head;
    Node* n = head ? head->next_ : NULL;
    if (h)
    {
        h->next_ = NULL;
    }
    while (n)
    {
        if (n->val_ == ' ')
        {
            t->next_ = n;
            t = n;
            return n->next_;
        }
        Node* next = n->next_;
        n->next_ = h;
        h = n;
        n = next;
    }
    return NULL;
}

Node* ReverseWords(Node* head)
{
    Node* h = NULL;
    Node* t = NULL;
    Node* new_head = NULL;
    Node* new_tail = NULL;
    while (true)
    {
        head = GetWord(head, h, t);
        if (!h)
        {
            break;
        }
        if (!new_head)
        {
            new_head = h;
        }
        if (new_tail)
        {
            new_tail->next_ = h;
        }
        new_tail = t;
    }
    return new_head;
}

void Print(Node* head)
{
    for (Node* n = head; n != NULL; n = n->next_)
    {
        cout << n->val_;
    }
    cout << "\n";
}

int main()
{
    Node n1('g'), n2('o'), n3(' '), n4('o'), n5('n');
    n1.next_ = &n2;
    n2.next_ = &n3;
    n3.next_ = &n4;
    n4.next_ = &n5;

    Print(&n1);
    Print(ReverseWords(&n1));

    return 0;
}

- Alex November 11, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

package google;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class ReverseWords {
	
	
   public static void main(String[] args){
	   String[] testcases = {"Hello World", "Hello flat World"};
	   
	   for(int i = 0; i < testcases.length; i++){
		   String s = testcases[i];
		  char[] res = reverseWords(s, " ");
		   System.out.println(s + "\t" + Arrays.toString(res));
	   }
   }

   static char[] reverseWords(String s, String separators){
	   if(s == null || separators == null){
		   return null;
	   }
	   
	   char[] sc = s.toCharArray();
	   if(separators.length() == 0 || s.length() <= 1){
		   return sc;
	   }
	   
	   Set<Character> sep = new HashSet<Character>();
	   for(char c : separators.toCharArray()){
		   sep.add(c);
	   }
	   reverseWords(sc, sep);
	   return sc;
   }
   
   private static void reverseWords(char[] sc, Set<Character> separators) {
	   // keep track of indices of prev and current separators
	   int prevSeparator = -1, nextSeparator = -1;
	   int n = sc.length;
	   
	   for(int i = 0; i < n; i++){
		   char c = sc[i];
		   if(separators.contains(c)){
			   int tmp = nextSeparator;
			   nextSeparator = i;
			   prevSeparator = tmp;
			   
			   // optional optimization
			   if(nextSeparator > prevSeparator+2){
				   // reverse portion between prev+1 and next-1
				   int wordSize = nextSeparator - (prevSeparator+1);
				   reverseSubArray(sc, prevSeparator+1, wordSize);
			   }
		   }
	   }
	   if(nextSeparator != n-1){
		   int wordSize = n-1 - (nextSeparator+1) + 1;
		   reverseSubArray(sc, nextSeparator+1, wordSize);
	   }
	}
   
   static void reverseSubArray(char[] sc, int wordStart, int wordSize){
	   int j = 0;
	   while(j < wordSize-1-j){
		   char tmpc = sc[wordStart+j];
		   sc[wordStart+j] = sc[wordStart+wordSize-1-j];
		   sc[wordStart+wordSize-1-j] = tmpc;
		   j++;
	   }
   }
}

- just_do_it July 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

You dont need any stack or any memory for this, its merely a linked list pointers play. This runs in O(1) memory and O(N) time which modifies the linked list in place
P.S I hate it that we cant edit our posts as there was a typo in my post earlier..

public class Solution {
  public Node reverseLinkedListWord(Node n) {
    Node curr = n, prev = null, next = null;

    while(curr != null) {
      if(curr.value == ' ') {
        prev = curr;
        curr = curr.next;
        continue;
      }
      next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }

    return curr;
  }
}

- nk July 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Simply reversing doesn't produce the right answer: "dlroW olleH" but that wasn't the question. The question was to reverse the words but keeping the order of the words.

How ever the question left open if it's a java linkedlist (which is a doubly linked) or a custom singly linked list.

One way to do it, if space doesn't matter, is to traverse the list, put the characters of a word on the stack and if a space is reached, fill a new list with the elements on the stack by popping the elements (which reverses the order of this word)

however, a proper reverse would be inplace without stack, which is as well possible.

As much space complexity as possible? I'm not sure I understood that requirement, maybe it meant to use space as you like.

A working, not so clean solution would be (issues: redundant code, use of stack, creation of new list)

class Node {
	Node next_ = null;
	char value_;
	
	public Node(char value) {
		value_ = value;
	}

	public Node getReverseWords(Node n) {
		result = null;
		Node last = null;
		stack<Character> s = new stack<Character>();
		while(n != null) {
			// read word onto stack
			while(n != null && n.value_ != ' ') {
				n = n.next_; 
				s.push(n.value_);
			}

			// put reveresed wod into different list
			while(!s.empty()) {
				if(last != null) { 					
					last->next_ = new Node(s.pop());
					last = last->next_;
				} else {
					result = new Node(s.pop());
					last = result;
				}
			}

			// copy spaces, whether they are trailing or leadind
			while(n != null && n->value_ == ' ') {
				if(last != null) { 					
					last->next_ = new Node(' ');
					last = last->next_;
				} else {
					result = new Node(' ');
					last = result;
				}
			}
		}
		return result;
	}
}

- Chris July 04, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

You dont need any stack or any memory for this, its merely a linked list pointers play. This runs in O(1) memory and O(N) time which modifies the linked list in place

public class Solution {
  public Node reverseLinkedListWord(Node n) {
    Node curr = n, prev = null, next = null;

    while(curr != null) {
      if(curr.value == ' ') {
        prev = curr;
        curr = curr.next;
        continue;
      }
      next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }

    return curr;
  }
}

- nk July 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More