Google Interview Question
Software Engineer in TestsCountry: United States
Interview Type: Phone Interview
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)
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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++;
}
}
}
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;
}
}
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;
}
}
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;
}
}