coding puzzle one

[fake_Bezawada]

Strings can be efficiently stored as a data structure, to have efficient searching methods.
A new startup is going to use this method, but they don't have much space. So they want to check beforehand how much memory will be required for their data. 
Following method describes the way in which this startup's engineers save the data in the structure.

Suppose they have 5 strings/words: et,eq,bd,be,bdp
A empty node is kept NULL, and strings are inserted into the structure one by one. 
Initially the structure is this:

NULL

After inserting "et", the structure is this:

NULL
 |
 e
 |
 t

After inserting "eq", the structure is this:

   NULL
   /
  e
 / \
t   q

After inserting "bd", the structure is this:

   NULL
   /  \
  e    b
 / \    \
t   q    d

After inserting "be", the structure is this:

     NULL
   /     \
  e       b
 / \     / \
t   q   e   d

After inserting "bdp", the structure is this:

    NULL
   /     \
  e       b
 / \     / \
t   q   e   d
             \
              p

Therefore a total of 8 nodes are used here.

Input: 
First line contains N, the number of strings they have. 
Each of the next N lines contain one string. Each string consists only of lowercase letters.

Output: 
Print the required number of nodes.

**Constraints: 
1≤N≤105 
Length of each string ≤30

Note: No two strings are same, though one string could be prefix of another.

SAMPLE INPUT

 

 

5
et
eq
bd
be
bdp

SAMPLE OUTPUT

 

 

8

[fake_Bezawada]

@karthikn raa uncle ippude try chesa 2/10 inputs through ayayi 

nee code kooda veyyi chudam enni inputs through aythayo

[fake_Bezawada]

@BaabuBangaram come here you're the only one who can solve this 

[BaabuBangaram]

35 minutes ago, fake_Bezawada said:

@BaabuBangaram come here you're the only one who can solve this 

trees use cheyya nenu.....so no idea.....

[karthikn]

6 hours ago, fake_Bezawada said:

@karthikn raa uncle ippude try chesa 2/10 inputs through ayayi 

nee code kooda veyyi chudam enni inputs through aythayo

Constructing trie is the question. Chesta evening 

[JANASENA]

Baa naaku chinese bhasha raaadu

[Popkatapetapotapulti]

I dont think this is a difficult problem. Just create a trie data structure and in your insert method increment a global counter variable(only when you are creating a node).  Difficultly epudu vastundi ante if he/she insists to not create a trie ds...but I highly doubt if it can be solved using DP. Kasepu alochinchi malli post chesta

 

@Pichkaari neku ede adigaru anukunta kada..or some version of this

[Pichkaari]

1 hour ago, Popkatapetapotapulti said:

I dont think this is a difficult problem. Just create a trie data structure and in your insert method increment a global counter variable(only when you are creating a node).  Difficultly epudu vastundi ante if he/she insists to not create a trie ds...but I highly doubt if it can be solved using DP. Kasepu alochinchi malli post chesta

 

@Pichkaari neku ede adigaru anukunta kada..or some version of this

Yeah smiliar e .. but adhi NLP related question anukunta bhayya.

[Popkatapetapotapulti]

17 minutes ago, Pichkaari said:

Yeah smiliar e .. but adhi NLP related question anukunta bhayya.

ok 

[fake_Bezawada]

20 hours ago, karthikn said:

Constructing trie is the question. Chesta evening 

nenu already chesesa my code is running good but not for all test cases 3/10 through ayayi 

[fake_Bezawada]

13 hours ago, Pichkaari said:

Yeah smiliar e .. but adhi NLP related question anukunta bhayya.

NLP ante 

[fake_Bezawada]

1. import java.io.BufferedReader;
2. import java.io.IOException;
3. import java.io.InputStreamReader;
4.  
5. import java.util.HashMap;
6.  
7. public class TestClass {
8. static int count=0;
9. public static void main(String[] args) throws IOException {
10.  
11. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
12. int noOfInputs = Integer.parseInt(br.readLine());
13. String[] strInputs=new String[noOfInputs];
14. for(int i=0;i<noOfInputs;i++) {
15. String input=br.readLine();
16. strInputs[i]=input;
17.  
18. }
19. doProcess(strInputs);
20. }
21.  
22. private static void doProcess(String[] splInput) {
23.  
24. HashMap<String,String> result=new HashMap<String,String>();
25.  
26. for(String s:splInput) {
27.  
28. for(int i=0;i<s.length();i++) {
29. if(i!=0) {
30. String value=String.valueOf(s.charAt(i));
31. if(result.keySet().contains(String.valueOf(s.charAt(0)))) {
32. if(String.valueOf(result.get(String.valueOf(s.charAt(0))).charAt(0))!=value) {
33. value =value+result.get(String.valueOf(s.charAt(0)));
34. result.put(String.valueOf(s.charAt(0)),value);
35. }
36. }else {
37. result.put(String.valueOf(s.charAt(0)),value);
38. }
39.  
40. }
41. }
42. }
43.  
44. getFinalresult(result);
45. }
46.  
47. private static void getFinalresult(HashMap<String, String> result) {
48. int count=0;
49. for(String s:result.keySet()) {
50. count=count+result.get(s).length()+1;
51. }
52. System.out.println(count+1);
53. }
54.  
55.  

}

[Pitta]

gp

[Pichkaari]

6 hours ago, fake_Bezawada said:

NLP ante 

Natural Language Processing. AI related dude.

[fake_Bezawada]

12 hours ago, Pichkaari said:

Natural Language Processing. AI related dude.

eppudu vinaledu papachak uncle chustanu adhi kooda