Interview Question for SDE-2s
- 0of 0 votes
AnswerThis is a word splitter program, I wanted to know the complexity of this program:
- pragramticProgrammer March 08, 2018 in United StatesString s = //"The quick fox jumped over a lazy dog"; "The Java language provides special support for the string " + "concatenation operator ( + ), and for conversion of other " + "objects to strings. String concatenation is implemented " + "through the StringBuilder(or StringBuffer) class and its " + "append method. String conversions are implemented through " + "the method toString, defined by Object and inherited by " + "all classes in Java."; int charLimit = 13; System.out.println("-------------"); char[] chars = s.toCharArray(); boolean endOfString = false; int start = 0; int end = start; while(start < chars.length-1) { int charCount = 0; int lastSpace = 0; while(charCount < charLimit) { if(chars[charCount+start] == ' ') { lastSpace = charCount; } charCount++; if(charCount+start == s.length()) { endOfString = true; break; } } end = endOfString ? s.length() : (lastSpace > 0) ? lastSpace+start : charCount+start; System.out.println(s.substring(start, end)); start = end+1; }
| Report Duplicate | Flag | PURGE
SDE-2 String Manipulation
The outer loop runs for O(N-1) where N is the length of your input string and the inner loop runs for O(13). So the total runtime is O(N-1 * 13) => O(13N-13) => O(N). Therefore, I think the time complexity would be Linear time.
- prudent_programmer March 08, 2018Since you are using a temporary buffer, charArray, to modify and keep track of the changes, I think that the space complexity would be O(N) also.