HCL America Interview Question for Software Engineer in Tests






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

how about using TRIE to get started. as we know trie's are the best option for implementing contact list in cellphones, right? i dont know how scalable it would be in case of a complete dictionary, though.

- googler August 12, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree, though TRIE takes up a lot of memory. I dont think hash tables are a good choice for preparing an Oxford like dictionary. Any other comments?

- Hank August 12, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution 1:
I would use an Array IndexA[26]. IndexA[0] corresonds to 'a'........IndexA[25] corresponds to 'z'. Each element of IndexA has a pointer to a tree(could be TRIE). This will reduce the memory used as in TRIE and provide fast search(as hash).
Solution 2:
To further reduce the memory and improve fast search, each element of IndexA contains a pointer to IndexB[26]. Each element of IndexB could be TRIE.
The above algorithm is more like double hash table(hence fast search) with TRIE(reduced node). The reason we used such complex data-structure is that we know dictonary contains words starting with 'aa', 'ab', 'ac'.....'ze'...'zz' with few exceptions such as 'zz'.

- Avinash September 10, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

One approach is using ternary tree.
1> create a ternary tree of all the words.
2> nodes of this ternary tree, instead of having " isEnd" field would have a pointer of Meaning type.Meaning is a structure having description, synonyms, antonyms, meaning and pronunciation kind of fields.
3>for all non end nodes "isEnd" pointer will be NULL.

- Aalok June 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

One approach is using ternary tree.
1> create a ternary tree of all the words.
2> nodes of this ternary tree, instead of having " isEnd" field would have a pointer of Meaning type.Meaning is a structure having description, synonyms, antonyms, meaning and pronunciation kind of fields.
3>for all non end nodes "isEnd" pointer will be NULL.

- Aalok June 28, 2012 | 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