1

I am on an interview ride here. One more interview question I had difficulties with.

“A rose is a rose is a rose” Write an algorithm that prints the number of times a character/word occurs. E.g. A – 3 Rose – 3 Is – 2

Also ensure that when you are printing the results, they are in order of what was present in the original sentence. All this in order n.

I did get solution to count number of occurrences of each word in sentence in the order as present in the original sentence. I used Dictionary<string,int> to do it. However I did not understand what is meant by order of n. That is something I need an explanation from you guys.

nhahtdh
  • 55,989
  • 15
  • 126
  • 162
Sachin Shanbhag
  • 54,530
  • 11
  • 89
  • 103
  • 1
    Order N is a reference to Big O notation. Basically, it means the number of operations that the program executes should scale linearly as the data increases. If you run it on a string with 1000 words, it will be 100 times more operations than if run on a 10 word string. For example strlen() in C is linear. – caveman Mar 06 '11 at 06:15
  • 1
    `List` or `Dictionary`? – Oscar Mederos Mar 06 '11 at 06:27
  • @Oscar - Edited my question, Thanks. Dont know what I was thinking. List is just a single array. :) – Sachin Shanbhag Mar 10 '11 at 15:56

6 Answers6

2

There are 26 characters, So you can use counting sort to sort them, in your counting sort you can have an index which determines when specific character visited first time to save order of occurrence. [They can be sorted by their count and their occurrence with sort like radix sort].

Edit: by words first thing every one can think about it, is using Hash table and insert words in hash, and in this way count them, and They can be sorted in O(n), because all numbers are within 1..n steel you can sort them by counting sort in O(n), also for their occurrence you can traverse string and change position of same values.

Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83
  • Count of words is required. Not characters ;) – Sachin Shanbhag Mar 06 '11 at 06:19
  • @Sachin Shanbhag, Words count is smaller than length of string so you can use counting sort for words same as characters, and if you read question wroted ... character/word ... may be I'm wrong but this solution works for both. – Saeed Amiri Mar 06 '11 at 06:20
  • Aaah... the character mentioned in question means the sentence can have a character or words. In example given above, it refers to the character `A`. But in all, question is to count no. of word occurrences. – Sachin Shanbhag Mar 06 '11 at 06:22
1

Order of n means you traverse the string only once or some lesser multiple of n ,where n is number of characters in the string. So your solution to store the String and number of its occurences is O(n) , order of n, as you loop through the complete string only once. However it uses extra space in form of the list you created.

DhruvPathak
  • 42,059
  • 16
  • 116
  • 175
  • yes. That is nice, but when i go to next string, I need to first check if that string already exists in the list right? Would that be considered as a traversal too and account for order? – Sachin Shanbhag Mar 06 '11 at 06:20
  • 1
    Yes, in the simplest example that could be O(n^2). If you multiply the length of the list by 10, you would increase the number of operations (in the worst case) by 100 times. 10 times the number of words to traverse in the original list, and 10 times the number to search for each of those in the second list. – caveman Mar 06 '11 at 06:32
  • 1
    @sachin Yes, that is extra traversal too, to overcome that you should use some hash table where key based lookup is direct i.e. O(1). A language neutral pseudo code will be myStatistics['rose']++ , it will increase count of "rose" in myStatistics key-value based array – DhruvPathak Mar 06 '11 at 06:39
1

Order N refers to the Big O computational complexity analysis where you get a good upper bound on algorithms. It is a theory we cover early in a Data Structures class, so we can torment, I mean help the student gain facility with it as we traverse in a balanced way, heaps of different trees of knowledge, all different. In your case they want your algorithm to grow in compute time proportional to the size of the text as it grows.

Tom Murphy
  • 305
  • 3
  • 12
1

It's a reference to Big O notation. Basically the interviewer means that you have to complete the task with an O(N) algorithm.

Community
  • 1
  • 1
flight
  • 7,162
  • 4
  • 24
  • 31
1

"Order n" is referring to Big O notation. Big O is a way for mathematicians and computer scientists to describe the behavior of a function. When someone specifies searching a string "in order n", that means that the time it takes for the function to execute grows linearly as the length of that string increases. In other words, if you plotted time of execution vs length of input, you would see a straight line.

Saying that your function must be of Order n does not mean that your function must equal O(n), a function with a Big O less than O(n) would also be considered acceptable. In your problems case, this would not be possible (because in order to count a letter, you must "touch" that letter, thus there must be some operation dependent on the input size).

amccormack
  • 13,207
  • 10
  • 38
  • 61
1

One possible method is to traverse the string linearly. Then create a hash and list. The idea is to use the word as the hash key and increment the value for each occurance. If the value is non-existent in the hash, add the word to the end of the list. After traversing the string, go through the list in order using the hash values as the count.

The order of the algorithm is O(n). The hash lookup and list add operations are O(1) (or very close to it).

caveman
  • 1,755
  • 1
  • 14
  • 19