Twitter Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

Build a suffix tree of all the names in the dictionary, since this is preprocessing, we will not take any time during execution, as we run through the text check if each word exists in the suffix tree, if it does return true else return false, this will take O(n*k) time where k = average length of a word and n = no of words...which implies O(n) for large sentences.

- Praveen August 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Let's say one of the names is "Lady Gaga". Wouldn't this algorithm consider the tweet "I am Gaga for Cocoa Puffs" to match?

- Matt B December 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not if you add spaces as possible values in the trie and then add an entire name as a trie entry.

- bluemoon January 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

import java.util.ArrayList;
import java.util.List;
import java.util.regex.Pattern;


public class StringTweetUserFind {
	
	public static Pattern createPat(String name){
		Pattern HEYPATTERN = Pattern.compile(".*"+name+".*");
		return HEYPATTERN;	
	}
	
	static Boolean findName(String tweet)
	{
		//Populating the list with names
		List<String> names = new ArrayList<String>();
		names.add("XXX YYY");
		names.add("SASDVZZXACC QADFGBADSEBFHDT");
		names.add("IIIIIIIII TTTTTTTTT");
		Boolean foundFlag = false;
			
		for(String itr:names){
			Pattern pattern = createPat(itr);
			if (pattern.matcher(tweet).matches()) {
				return true;
			} 
		}	
		return foundFlag;
		
	}
	
	public static void main(String[] args){
		String tweet = "Ok folks! Non BJP, non Cong front to be "
				+ "SASDVZZXACC QADFGBADSEBFHDT officially 'formed' today. The fun has only just begun! "
				+ "A long summer lies ahead! Time to work! Bye";
		
		Boolean output = findName(tweet);
		System.out.println(output);
		
	}
}

- Vinoth February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a map, insert all names in map.
Traverse through the tweet (word by word, perhaps using a helper function giving you the next word)
See if the word from tweet is present in the map. Iff yes then return true.

- Arjan August 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

A name is not just 1 word. How do you decide if we check 1 word, 2 words, 3 words as the key of the map?

- Anonymous October 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This returns true if any of the names in the list occur in the tweet.

import sys

def isNameInTweet(names, tweet):
  # insert names into dictionary
  prev = None
  nametable = {}
  tweetwords = []
  for n in names:
    nametable[n] = True
  # tokenize tweet by word
  tweetwords = tweet.split()
  print tweetwords
  # combine words into pairs in order, lookup in dict
  for w in tweetwords:
    if not prev:
      prev = w
      continue
    print "looking for " + prev + " " + w
    if str(prev + " " + w) in nametable:
      return True
    prev = w
  return False 

def main():
  names = ['Katy Perry', 'Russell Brand', 'Russel Crowe']
  tweet = 'Katy Perry and Russel Brand make a nice couple!'
  print str(names) + " " + str(tweet) + " " +str( isNameInTweet(names, tweet))

if __name__ == "__main__":
  sys.exit(main())

- schroeder.carl.j August 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this assumes that a "name" is always two words separated by a space. What if the name contained two spaces, or none?

- Matt B December 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sample trie based solution

/**
 * Load list of names into trie
 * Then compare the suffixes of given tweet with trie if found then return true 
 */


public class TwitterTrie {
    public TwitterTrie() {
        super();
    }

    public static void main(String[] args) {
        TwitterTrie twitterTrie = new TwitterTrie();
        TwitterTrie.Trie trie = twitterTrie.new Trie();
        String[] strs = { "Prakash", "Swathi", "Rama" };
        for (String str : strs) {
            trie.insert(str);
        }
        trie.print();
        System.out.println(twitterTrie.found("This is ramakrishna again", trie));
        System.out.println(twitterTrie.found("This is gopi again", trie));

    }

    public boolean found(String tweet, TwitterTrie.Trie root) {
        boolean b = false;
        for (int i = 0; i < tweet.length(); i++) {
            b = root.search(tweet.substring(i));
            if (b)
                break;
        }
        return b;
    }

    class Trie {
        private static final int ALPHA_SIZE = 26;
        private static final int BUF_SIZE = 1024;
        private Trie root;
        private Trie[] trieArray;
        private char data;
        private boolean word;

        public Trie() {
            super();
        }

        public void insert(String data) {
            Trie root = this.getRoot();
            if (root == null) {
                root = new Trie(' ');
                this.setRoot(root);
            }
            for (int i = 0; i < data.length(); i++) {
                if (root.getTrieArray()[atoi(data.charAt(i))] == null) {
                    root.getTrieArray()[atoi(data.charAt(i))] = new Trie(data.charAt(i));
                }
                root = root.getTrieArray()[atoi(data.charAt(i))];
            }
            root.setWord(true);
        }

        public void print() {
            Trie root = this.getRoot();
            if (root == null) {
                return;
            }
            char[] buffer = new char[BUF_SIZE];
            int index = 0;
            traverse(root, index, buffer);
        }

        public void traverse(Trie root, int index, char[] buffer) {
            if (root == null)
                return;
            if (root.isWord())
                System.out.println(new String(buffer, 0, index));
            for (int i = 0; i < ALPHA_SIZE; i++) {
                if (root.getTrieArray()[i] != null) {
                    buffer[index] = root.getTrieArray()[i].getData();
                    traverse(root.getTrieArray()[i], index + 1, buffer);
                }

            }
        }

        public boolean search(String pattern) {
            Trie root = this.getRoot();
            if (root == null)
                return false;
            int x = 0;
            for (int i = 0; i < pattern.length(); i++) {
                if (atoi(pattern.charAt(i)) > 26) {
                    continue;
                } else if (root.getTrieArray()[atoi(pattern.charAt(i))] != null) {
                    root = root.getTrieArray()[atoi(pattern.charAt(i))];
                } else {
                    break;
                }
            }
            if (root.isWord()) {
                return root.isWord();
            }
            return false;
        }

        public int atoi(char ch) {
            int i = 0;
            if (ch >= 65 && ch <= 90)
                i = ch - 65;
            else if (ch >= 97 && ch <= 122)
                i = ch - 97;
            else
                i = (int)ch;

            return i;

        }

        private Trie(char data) {
            this.setData(data);
            this.setTrieArray(new Trie[ALPHA_SIZE]);
        }

        public void setRoot(Trie root) {
            this.root = root;
        }

        public Trie getRoot() {
            return root;
        }

        public void setTrieArray(Trie[] trieArray) {
            this.trieArray = trieArray;
        }

        public Trie[] getTrieArray() {
            return trieArray;
        }

        public void setData(char data) {
            this.data = data;
        }

        public char getData() {
            return data;
        }

        public void setWord(boolean word) {
            this.word = word;
        }

        public boolean isWord() {
            return word;
        }
    }
}

- Prakash August 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.ArrayList;
import java.util.List;


public class C {

public static void main(String[] args) {

List<String> names = new ArrayList<String>();

String tweet ="Ankit Jain yesterday met Anuj Jha";

names.add("Ankit Jain");
names.add("Anuj Jha");

for(int i=0;i<names.size();i++){

if(tweet.contains(names.get(i))){

System.out.println(names.get(i));
}
}
}
}

- Learner August 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Build a balanced BST of the dictionary words.
For every word in the tweet search it in the BST. Since Balanced BST guarantees O(logn). The time complexity is O(nlogk).

- Sat September 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use regex maybe?

use strict;
use warnings;


my @names  = qw/ name1 name2 name3 /;
my $tweet  = "this is a test tweet with name1";
my $tweet2 = "this is a test tweet without";

sub contains_name{
    my $search_tweet = shift;
    foreach my $name(@names){
        return 1 if $search_tweet =~ m/$name/;
    }
    return 0;
}

printf("$tweet %s name\n", contains_name($tweet) ? "contains" : "does not contain");
printf("$tweet2 %s name\n", contains_name($tweet2) ? "contains" : "does not contain");

- YK January 11, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

if tweets will be stored with hashes for each word then such search always will be O(1)

- LBaralgeen February 25, 2014 | Flag Reply


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