Google Interview Question
Software EngineersCountry: United States
public class FindNextLexogWord {
public static void main(String[] args) {
String[] wordList = {"Cat", "dog", "cow", "donkey", "zebra", "monkey"};
String input = "duck";
int nextLex = Integer.MIN_VALUE;
int value = 0;
String word = null;
for( int i = 0 ; i < wordList.length ; i ++ ) {
if(( value = input.compareTo(wordList[i])) < 0 ) {
System.out.println(value);
if( nextLex < value){
nextLex = value;
word = wordList[i];
}
}
}
}
public static String findNextWord(String[] words, String input) {
// go through each word
int closest = 0;// assume closest itself
String res = input;
for(String word: words) {
// compare input with the word
// since we are looking for more closer word lets look for < 0
if(input.compareTo(word) < 0) {
// which means input comes first
// check if there is any existing one?
if(closest == 0) {
// first time we found a closet
res = word;
closest = input.compareTo(word);
} else {
// if there is exisrts
if(closest < input.compareTo(word)) {
res = word;
closest = input.compareTo(word);
}
}
}
}
return res;
}
Use TST( Ternary Search Tree):
Try using display method coz it generally uses inorder traversal. if your searched element is found, the next element in the inorder traversal would be your next lexigraphic value.
I have solved this question. Please mail me if you need explanation.
class TSTNode{
Character data;
TSTNode left;
TSTNode right;
TSTNode middle;
boolean isWord;
public TSTNode(Character data){
this.data=data;
}
}
Using tree.
#include <string>
#include <memory>
#include <iostream>
class Node {
public:
Node(const std::string &word) : word_(word) {}
const std::string &word() const { return word_; }
static void insertWord(std::unique_ptr<Node> &tree, const std::string &word)
{
if (tree.get() == nullptr)
tree.reset(new Node(word));
else if (word < tree->word())
insertWord(tree->childs_[0], word);
else
insertWord(tree->childs_[1], word);
}
std::string findNextWord(const std::string &word)
{
if (word < word_) {
std::string w;
if (childs_[0])
w = childs_[0]->findNextWord(word);
return w.empty() ? word_ : w; // if less than me not found then return me
} else {
if (!childs_[1])
return std::string(); // not found
return childs_[1]->findNextWord(word);
}
}
private:
std::string word_;
std::unique_ptr<Node> childs_[2];
};
int main() {
std::unique_ptr<Node> tree;
for (decltype(auto) w : {"cat", "dog", "cow", "donkey", "zebra", "monkey"})
Node::insertWord(tree, w);
std::string w;
while (true)
{
std::cout << "Input: ";
std::cin >> w;
if (std::cin.eof())
break;
std::cout << "Output: " << tree->findNextWord(w) << std::endl;
}
}
- Dhruva.Bharadwaj April 16, 2017